Cryptology ePrint Archive: Report 2006/250

Linear Cryptanalysis of CTC

Orr Dunkelman and Nathan Keller

Abstract: CTC is a toy cipher designed by Courtois in order to prove the strength of algebraic attacks. In this paper we study the differential and the linear behavior of the 85 S-boxes version, which is attacked using algebraic techniques faster than exhaustive key search. We show that an $n$-round variant of the cipher can be attacked by a linear attack using only $2^{2n+2}$ known plaintexts, with a negligible time complexity. We conclude that CTC is insecure, even for quite a large number of rounds. We note that our observations can be probably used to devise other attacks that exploit the relatively slow diffusion of CTC.

Category / Keywords: secret-key cryptography / cryptanalysis, CTC, linear cryptanalysis

Date: received 22 Jul 2006

Contact author: orrd at cs technion ac il

Available format(s): PDF | BibTeX Citation

Version: 20060724:095712 (All versions of this report)

Short URL: ia.cr/2006/250

Discussion forum: Show discussion | Start new discussion