Security amplification by composition: The case of doubly-iterated, ideal ciphers

William Aiello; Mihir Bellare; Giovanni Di Crescenzo; Ramarathnam Venkatesan

Paper 1998/023

Security amplification by composition: The case of doubly-iterated, ideal ciphers

William Aiello, Mihir Bellare, Giovanni Di Crescenzo, and Ramarathnam Venkatesan

Abstract

We investigate, in the Shannon model, the security of constructions corresponding to double and (two-key) triple DES. That is, we consider Fk1(Fk2(.)) and Fk1(Fk2-1(Fk1(.))) with the component functions being ideal ciphers. This models the resistance of these constructions to ``generic'' attacks like meet in the middle attacks. We obtain the first proof that composition actually increases the security in some meaningful sense. We compute a bound on the probability of breaking the double cipher as a function of the number of computations of the base cipher made, and the number of examples of the composed cipher seen, and show that the success probability is the square of that for a single key cipher. The same bound holds for the two-key triple cipher. The first bound is tight and shows that meet in the middle is the best possible generic attack against the double cipher.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: DES Double DES cipher block cipher cascade composition Shannon.
Contact author(s): mihir @ cs ucsd edu
History: 1998-08-31: received
Short URL: https://ia.cr/1998/023
License: CC BY

BibTeX

@misc{cryptoeprint:1998/023,
      author = {William Aiello and Mihir Bellare and Giovanni Di Crescenzo and Ramarathnam Venkatesan},
      title = {Security amplification by composition: The case of doubly-iterated, ideal ciphers},
      howpublished = {Cryptology {ePrint} Archive, Paper 1998/023},
      year = {1998},
      url = {https://eprint.iacr.org/1998/023}
}