COCONUT98

Infobox block cipher
name = COCONUT98


caption =
designers = Serge Vaudenay
publish date = 1998
derived from =
derived to =
related to = DFC
key size = 256 bits
block size = 64 bits
structure = Decorrelated Feistel cipher
rounds = 8
cryptanalysis = Wagner's boomerang attack uses about 2¹⁶ adaptively-chosen plaintexts and ciphertexts, about 2³⁸ work, and succeeds with probability 99.96%.
The differential-linear attack by Biham, et al. uses 2^27.7 chosen plaintexts and about 2^33.7 work, and has a 75.5% success rate.

In cryptography, COCONUT98 (Cipher Organized with Cute Operations and N-Universal Transformation) is a block cipher designed by Serge Vaudenay in 1998. It was one of the first concrete applications of Vaudenay's decorrelation theory, designed to be provably secure against differential cryptanalysis, linear cryptanalysis, and even certain types of undiscovered cryptanalytic attacks.

The cipher uses a block size of 64 bits and a key size of 256 bits. Its basic structure is an 8-round Feistel network, but with an additional operation after the first 4 rounds, called a "decorrelation module". This consists of a key-dependent affine transformation in the finite field GF(2⁶⁴). The round function makes use of modular multiplication and addition, bit rotation, XORs, and a single 8×24-bit S-box. The entries of the S-box are derived using the binary expansion of e as a source of "nothing up my sleeve numbers". [cite conference | author = Serge Vaudenay | title = Provable Security for Block Ciphers by Decorrelation | booktitle = 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS '98) | pages = pp.249–275 | publisher = Springer-Verlag | date = February 1998 | location = Paris | url = http://lasecwww.epfl.ch/pub/lasec/doc/Vau98a.ps | format = PostScript | accessdate = 2007-02-26 ]

Despite Vaudenay's proof of COCONUT98's security, in 1999 David Wagner developed the boomerang attack against it. [cite conference | author = David Wagner | title = The Boomerang Attack | booktitle = 6th International Workshop on Fast Software Encryption (FSE '99) | pages = pp.156–170 | publisher = Springer-Verlag | date = March 1999 | location = Rome | url = http://citeseer.ist.psu.edu/wagner99boomerang.html | format = PDF/PostScript | accessdate = 2007-02-05 ] This attack, however, requires both chosen plaintexts and adaptive chosen ciphertexts, so is largely theoretical. [cite journal | author = Serge Vaudenay | title = Decorrelation: A Theory for Block Cipher Security | journal = Journal of Cryptology | volume = 16 | issue = 4 | issn = 0933-2790 | pages = pp.249–286 | date = September 2003 | url = http://lasecwww.epfl.ch/pub/lasec/doc/Vau03b.pdf | format = PDF | accessdate = 2007-02-26 | doi = 10.1007/s00145-003-0220-6 ] Then in 2002, Biham, et al. applied differential-linear cryptanalysis, a purely chosen-plaintext attack, to break the cipher. [cite conference | author = Eli Biham, Orr Dunkelman, Nathan Keller | title = Enhancing Differential-Linear Cryptanalysis | booktitle = Advances in Cryptology — Proceedings of ASIACRYPT 2002 | pages = pp.254–266 | publisher = Springer-Verlag | date = December 2002 | location = Queenstown, New Zealand | url = http://citeseer.ist.psu.edu/biham02enhancing.html | format = PDF/PostScript | accessdate = 2007-02-05 ] The same team has also developed what they call a "related-key boomerang attack", which distinguishes COCONUT98 from random using one related-key adaptive chosen plaintext and ciphertext quartet under two keys. [cite conference | author = Biham, Dunkelman, Keller | title = Related-Key Boomerang and Rectangle Attacks | booktitle = Advances in Cryptology — Proceedings of EUROCRYPT 2005 | pages = pp.507–525 | publisher = Springer-Verlag | date = May 2005 | location = Aarhus | url = http://vipe.technion.ac.il/~orrd/crypt/relatedkey-rectangle.ps | format = PostScript | accessdate = 2007-02-16 ]

References