Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / XLS, SPRP, Distinguishing Advantage, length-preserving encryption.

Original Publication (with minor differences): Asiacrypt 2014

Date: received 9 May 2015

Contact author: mridul nandi at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150509:152321 (All versions of this report)

Short URL: ia.cr/2015/445

Discussion forum: Show discussion | Start new discussion