### Higher Order Correlation Attacks, XL algorithm and Cryptanalysis of Toyocrypt

Nicolas T. Courtois

##### Abstract

There is abundant literature on how to use linear approximations to break various stream ciphers. In this paper we show that it is possible to design an efficient attack based on higher degree approximations. We reduce the attack to solving an overdefined system of multivariate equations and use the XL algorithm from Eurocrypt 2000. The complexity of the XL algorithm is sometimes controversial, however in practice and for the cases relevant here (much more equations than variables), we show that the behaviour of XL is predictable with the utmost precision and 100% accuracy. Our new attack allows to break efficiently stream ciphers that are known to be immune to all the previously known attacks. It has also surprisingly small and loose requirements on the keystream needed, giving powerful attack scenarios, leading even to (almost) ciphertext-only attacks. For example, the new attack breaks the stream cipher Toyocrypt submitted to the Japanese government Cryptrec call for cryptographic primitives, and one of only two candidates accepted to the second phase of Cryptrec evaluation process. Toyocrypt is a 128-bit stream cipher and at the time of submission it was claimed to resist to all known attacks. Later, Mihaljevic and Imai showed that the effective key length in Toyocrypt is only 96 bits. Still Toyocrypt may be easily modified to avoid this attack and have full 128 bit key. Our best attack breaks both Toyocrypt and the modified versions taking exactly 2^92 CPU clocks for a 128-bit cipher. Moreover it works in much less restrictive conditions that the previous attack, for example knowing ONLY that the ciphertext is in English.

Note: Much faster algebraic attacks on Toyocrypt exist and will be described in a separate paper.

Available format(s)
Publication info
Published elsewhere. Presented at 5th International Conference on Information Security and Cryptology (ICISC 2002), November 28-29, 2002, Seoul, Korea. This as a full and updated version.
Keywords
Algebraic cryptanalysismultivariate equationsoverdefined equationsReed-Muller codescorrelation immunityXL algorithmGröbner basesstream cipherspseudo-random generatorsnonlinear filteringciphertext-only attacksToyocryptCryptrec.
Contact author(s)
courtois @ minrank org
History
2003-02-13: last of 8 revisions
See all versions
Short URL
https://ia.cr/2002/087

CC BY

BibTeX

@misc{cryptoeprint:2002/087,
author = {Nicolas T.  Courtois},
title = {Higher Order Correlation Attacks, XL algorithm and Cryptanalysis of Toyocrypt},
howpublished = {Cryptology ePrint Archive, Paper 2002/087},
year = {2002},
note = {\url{https://eprint.iacr.org/2002/087}},
url = {https://eprint.iacr.org/2002/087}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.