International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 01 May 2015

Peter Gazi, Jooyoung Lee, Yannick Seurin, John Steinberger, Stefano Tessaro
ePrint Report ePrint Report
We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number $q_e$ of queries to the underlying ideal block cipher, representing adversary\'s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number $q_c$ of plaintext/ciphertext pairs that is less than the entire codebook. For any such $q_c$, we aim to determine the highest number of block-cipher queries $q_e$ the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.

More concretely, we show the following results for key-length extension schemes using a block cipher with $n$-bit blocks and $\\kappa$-bit keys:

- Plain cascades of length $\\ell = 2r+1$ are secure whenever $q_c q_e^r \\ll 2^{r(\\kappa+n)}$, $q_c \\ll 2^\\ka$ and $q_e \\ll 2^{2\\ka}$. The bound for $r = 1$ also applies to two-key triple encryption (as used within Triple DES).

- The $r$-round XOR-cascade is secure as long as $q_c q_e^r \\ll 2^{r(\\kappa+n)}$, matching an attack by Gazi (CRYPTO 2013).

- We fully characterize the security of Gazi and Tessaro\'s two-call 2XOR construction (EUROCRYPT 2012) for all values of $q_c$, and note that the addition of a third whitening step strictly increases security for $2^{n/4} \\le q_c \\le 2^{3/4n}$. We also propose a variant of this construction without re-keying and achieving comparable security levels.

Expand

Additional news items may be found on the IACR news page.