Paper 2015/444

Revisiting Security Claims of XLS and COPA

Mridul Nandi


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).

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
XLSCOPAPseudorandom functionAuthenticated Encryptionforgerydistinguisher.
Contact author(s)
mridul nandi @ gmail com
2015-05-09: received
Short URL
Creative Commons Attribution


      author = {Mridul Nandi},
      title = {Revisiting Security Claims of XLS and COPA},
      howpublished = {Cryptology ePrint Archive, Paper 2015/444},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.