Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes

Peter Gazi; Jooyoung Lee; Yannick Seurin; John Steinberger; Stefano Tessaro

Paper 2015/397

Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes

Peter Gazi, Jooyoung Lee, Yannick Seurin, John Steinberger, and Stefano Tessaro

Abstract

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 -bit blocks and -bit keys: - Plain cascades of length are secure whenever , and . The bound for also applies to two-key triple encryption (as used within Triple DES). - The -round XOR-cascade is secure as long as , 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 , and note that the addition of a third whitening step strictly increases security for . We also propose a variant of this construction without re-keying and achieving comparable security levels.

Note: An abridged version appears in the proceedings of FSE 2015. This is the full version.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A major revision of an IACR publication in FSE 2015
Keywords: block ciphers key-length extension provable security ideal-cipher model
Contact author(s): yannick seurin @ m4x org
History: 2015-05-01: received
Short URL: https://ia.cr/2015/397
License: CC BY

BibTeX

@misc{cryptoeprint:2015/397,
      author = {Peter Gazi and Jooyoung Lee and Yannick Seurin and John Steinberger and Stefano Tessaro},
      title = {Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/397},
      year = {2015},
      url = {https://eprint.iacr.org/2015/397}
}