Paper 2015/444

Revisiting Security Claims of XLS and COPA

Mridul Nandi

Abstract

Ristenpart and Rogaway proposed XLS in 2007 which is a generic method to encrypt messages with incomplete last blocks. Later Andreeva et al., in 2013 proposed an authenticated encryption COPA which uses XLS while processing incomplete message blocks. Following the design of COPA, several other CAESAR candidates used the similar approach. Surprisingly in 2014, Nandi showed a three-query distinguisher against XLS which violates the security claim of XLS and puts a question mark on all schemes using XLS. However, due to the interleaved nature of encryption and decryption queries of the distinguisher, it was not clear whether the security claims of COPA remains true or not. This paper revisits XLS and COPA both in the direction of cryptanalysis and provable security. Our contribution of the paper can be summarized into following two parts: 1. Cryptanalysis: We describe two attacks - (i) a new distinguisher against XLS and extending this attack to obtain (ii) a forging algo- rithm with query complexity about 2^n/3 against COPA where n is the block size of the underlying blockcipher. 2. Security Proof: Due to the above attacks the main claims of XLS (already known before) and COPA are wrong. So we revise the security analysis of both and show that (i) both XLS and COPA are pseudorandom function or PRF up to 2^n/2 queries and (ii) COPA is integrity-secure up to 2^n/3 queries (matching the query complexity of our forging algorithm).