Paper 2015/445

XLS is not a Strong Pseudorandom Permutation

Mridul Nandi

Abstract

In FSE 2007, Ristenpart and Rogaway had described a generic method XLS to construct a length-preserving strong pseudorandom per- mutation (SPRP) over bit-strings of size at least n. It requires a length-preserving permutation E over all bits of size multiple of n and a blockcipher E with block size n. The SPRP security of XLS was proved from the SPRP assumptions of both E and E. In this paper we disprove the claim by demonstrating a SPRP distinguisher of XLS which makes only three queries and has distinguishing advantage about 1/2. XLS uses a multi-permutation linear function, called mix2. In this paper, we also show that if we replace mix2 by any invertible linear functions, the construction XLS still remains insecure. Thus the mode has inherit weakness.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Asiacrypt 2014
Keywords
XLSSPRPDistinguishing Advantagelength-preserving encryption.
Contact author(s)
mridul nandi @ gmail com
History
2015-05-09: received
Short URL
https://ia.cr/2015/445
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/445,
      author = {Mridul Nandi},
      title = {{XLS} is not a Strong Pseudorandom Permutation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/445},
      year = {2015},
      url = {https://eprint.iacr.org/2015/445}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.