Algebraic Attacks on Stream Ciphers
References - Algebraic attacks on stream ciphers:
- Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Kunzli, Willi Meier and Olivier Ruatta: Efficient Computation of Algebraic Immunity for Algebraic and Fast Algebraic Attacks, In Eurocrypt 2006, May 28-June 1, Saint Petersburg, Russia.
- F.Didier and J.Tillich: Computing the Algebraic Immunity Efficiently, In Fast Software Encryption 2006, 15-17 March 2006 Graz, Austria, to appear in Springer.
- Y.Nawaz, G.Gong, and K.Gupta: Upper Bounds on Algebraic Immunity of Power Functions, In Fast Software Encryption 2006, 15-17 March 2006 Graz, Austria, to appear in Springer.
- Nicolas Courtois: Cryptanalysis of Sfinks, eprint/2005/243/. In ICISC 2005, LNCS 3935, Springer.
- Frederik Armknecht, Gwenolé Ars: Introducing a New Variant of Fast Algebraic Attacks and Mimimizing their Successive Data Complexity, Inria report, Mars 2005.
- Nicolas Courtois: Algebraic Attacks on Combiners with Memory and Several Outputs, to appear in ICISC 2004, just before Asiacrypt, in Korea, LNCS, Springer.
The extended version of this paper is availble at eprint.iacr.org/2003/125/.
- Jovan Dj. Golic: Vectorial Boolean functions and induced algebraic equations. On eprint.iacr.org/2004/225/.
- Philip Hawkes and Gregory G. Rose: Rewriting Variables: the Complexity of Fast Algebraic Attacks on Stream Ciphers.
In Crypto 2004, LNCS 3152, pp. 390-406, Springer. Also on eprint.iacr.org/2004/081/.
- Frederik Armknecht: On the Existence of low-degree Equations for Algebraic Attacks, available at eprint.iacr.org/2004/185/. Also presented at SASC Ecrypt workshop (State of the Art in Stream Ciphers).
- A Finish course on algebraic attacks on stream ciphers.
- Frederik Armknecht: Algebraic Attacks on Stream Ciphers, Tutorial presented at ECCOMAS, Fourth European Congress on Computational Methods in Applied Sciences and Engineering, Jyväskylä, Finland, 24-28 July 2004. Available from Frederik's web page.
- Presentations by Frederik Armknecht: one that overwievs algebraic attacks on block and stream ciphers. Another one from summer school. And here about fast algebraic attacks, for Estonian Winter School.
- Frederik Armknecht:
Extending the resynchronization attack, SAC 2004, Waterloo Canda, to appear in LNCS, Springer.
- Will Meier, Enes Pasalic and Claude Carlet: Algebraic Attacks and Decomposition of Boolean Functions. Eurocrypt 2004, pp. 474-491, LNCS 3027, Springer, 2004. Slides can be found here.
- Frederik Armknecht: Improving Fast Algebraic Attacks, FSE 2004, LNCS, Springer.
- Algebraic Attacks on SOBER-t32 and SOBER-128, by Joo Yeon Cho and Josef Pieprzyk. FSE 2004, LNCS, Springer.
- Algebraic Analysis of Rabbit, (no interesting attacks found). Cryptico report, available here.
- Breaking the Stream Cipher Whitenoise, by Hongjun Wu, eprint.iacr.org/2003/250/. This paper claims to be able to break the whitenoise cipher by solving a system of 80,000 linear equations and given about 80,000 bytes of keystream.
- Dong Hoon Lee and Jaeheon Kim and Jin Hong and Jae Woo Han and Dukjae Moon: Algebraic Attacks on Summation Generators, eprint.iacr.org/2003/229/. Publshed in FSE 2004, LNCS, Springer.
- Elad Barkan, Eli Biham, and Nathan Keller: Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication. In Crypto 2003, LNCS 2729, pp: 600-616, Springer. In this paper we learn how to listen to tap encrypted conversations of cellular phones in real time. One of the attacks involves solving an overdefined system of multivariate quadratic equations.
- Nicolas Courtois: Fast Algebraic Attacks on Stream Ciphers with Liner Feedback. In Crypto 2003, LNCS 2729, pp: 177-194, Springer.
- Matthias Krause and Frederik Armknecht: Algrebraic Attacks on Combiners with Memory, Crypto 2003, August 17-21, Santa Barbara, CA, USA. To appear in LNCS 2729, pp: 162-176, Springer.
- Open problems in the field of algebraic attacks on various ciphers: STORK report "Open problems in multivariate cryptanalysis".
- Jean-Charles Faugère, Gwénolé Ars: An Algebraic Cryptanalysis of Nonlinear Filter Generators using Gröbner bases, INRIA report RR-4739. (This paper duplicates some of the results from Courtois and Meier below without quoting them).
- Nicolas Courtois, Willi Meier: Algebraic Attacks on Stream Ciphers with Liner Feedback. Eurocrypt 2003, LNCS 2656, pp. 345-359, Springer.
This attack has been implemented by Nicolas Courtois,
see the extended version of the paper.
and here are
EXTENDED SLIDES frome 2005 or so with a lot of added material.
- Frederik Armknecht: A Linearization Attack on the Bluetooth Key Stream Generator, posted on eprint in December 2002. This attack can be seen as a special case of the general attack proposed in the paper below.
- Miodrag Mihaljevic: Cryptanalysis of Fast Encryption Algorithm for Multimedia FEA-M, IEEE Communications Letters, vol. 6, no. 9, pp. 392-384, Sept. 2002.
- Nicolas Courtois: Higher Order Correlation Attacks, XL algorithm, and Cryptanalysis of Toyocrypt. In ICISC 2002, LNCS 2587, pp. 182-199, Springer. The extended version of the paper can be found on eprint.
References - How to avoid algebraic attacks on stream ciphers:
- Claude Carlet: Improving the algebraic immunity of resilient and nonlinear functions and constructing bent functions. This paper shows how to contruct Boolean functions with some inbuild minimal resistance against algebraic attacks. See http://eprint.iacr.org/2004/276/.
- Guang Gong: On Existence and Invariant of Algebraic Attacks, CORR 2004-17 report.
- Deepak Kumar Dalai and Kishan Chand Gupta and Subhamoy Maitra: Cryptographically Significant Boolean functions: Construction and Analysis in terms of Algebraic Immunity. To appear at FSE 2005.
- Lynn Margaret Batten: Algebraic Attacks over GF(q), In Indocrypt 2004.
- Deepak Kumar Dalai, Kishan Chand Gupta, Subhamoy Maitra: Results on Algebraic Immunity for Cryptographically Significant Boolean Functions, In Indocrypt 2004.
- Nicolas Courtois, General Principles of Algebraic Attacks and New Design Criteria for Components of Symmetric Ciphers. Invited talk, AES 4 Conference, Bonn May 10-12 2004, LNCS 3373, pp. 67-83, Springer. Available for Springer subscribers.
- An alternative to LFSR-based stream ciphers that allows to avoid algebraic attacks have been recently proposed by Adi Shamir and Alexander Klimov: Invited talk at FSE 2004, LNCS, Springer, also announced at the Rump session of Crypto 2003 and also presented at ENS, Paris in December 2003. New papers about this to appear at Asiacrypt and in SASC workshop.
Crypto Debates: The difficult question of strong cryptography
The AES 1 million dollar challenge (or why there should be such a thing)
Security of important ciphers used in practice: Security of DES
AES: is the new encryption standard already broken ?
New algebraic attacks on encrytion algorithms:
Algebraic attacks on block ciphers and AES
Algebraic attacks applied to stream ciphers
Positive applications of multivariate equations:
promoting/about multivariate cryptography:
The McEliece_based short signature scheme CFS
The HFE cryptosystem home page
The Minrank Zero-knowledge identification scheme
Quartz /Flash /Sflash signature schemes
Nicolas Courtois research page
TTM cryptosystem, GPT cryptosystem,
Open Problems in Multivariate Cryptography (Stork Document)