D. J. Bernstein
Hash functions and ciphers
Notes on the ECRYPT Stream Cipher project (eSTREAM)
Broken ciphers and tweaks of those ciphers
(new home for table of submissions)
(new home for aecycles, authspeed, timings)
Abbreviating the stream-cipher discussions
Why switch from AES to a new stream cipher?
a consortium of European research organizations,
issued a Call for Stream Cipher Primitives in November 2004.
This is an exciting opportunity for the cryptographic community
to settle on a new encryption standard
that simultaneously provides higher confidence and higher speed than AES.
Over the next several months,
a huge number of stream ciphers were submitted to ECRYPT.
ECRYPT has several web pages describing the ciphers:
There's also a Wikipedia page on the topic:
eSTREAM has also become an increasingly popular conference topic:
What happens when a cipher is broken?
Often the designers propose a tweaked cipher that resists the attack.
How should the community handle the new cipher?
- 2006.02.02-2006.02.03, SASC 2006, focused on eSTREAM.
- 2006.03.15-2006.03.17, FSE 2006:
"Cryptanalysis of Achterbahn" by T. Johansson, W. Meier, and F. Muller.
"Cryptanalysis of Grain" by C. Berbain, H. Gilbert, and A. Maximov.
"Cryptanalysis of Stream Cipher DECIM" by H. Wu and B. Preneel.
"Chosen Ciphertext Attacks Against MOSQUITO" by A. Joux and F. Muller.
"Distinguishing Attack on the Stream Cipher Py" by G. Sekar, S. Paul, and B. Preneel.
"Resynchronization Attack on WG and LEX" by H. Wu and B. Preneel.
- 2006.04.03-2006.04.04, SHARCS'06:
Iain Devlin and Alan Purvis,
"A fundamental evaluation of 80 bit keys employed by hardware oriented stream ciphers"
(Grain and Trivium).
- 2006.06.26-2006.06.30, ICE-EM RNSA 2006, "Recent advances in stream ciphers and hash functions."
- 2006.08.17-2006.08.18, SAC 2006:
Martin Hell, Thomas Johansson, "Cryptanalysis of Achterbahn-Version 2."
Hongjun Wu, Bart Preneel, "Cryptanalysis of the Stream Cipher ABC v2."
Alex Biryukov, "The Design of a Stream Cipher Lex."
Martin Hell, Thomas Johansson, "On the Problem of Finding Linear Approximations and Cryptanalysis of Pomaranch Version 2."
Bin Zhang, Dengguo Feng, "Multi-Pass Fast Correlation Attack on Stream Ciphers."
Joo Yeon Cho, Josef Pieprzyk, "Crossword Puzzle Attack on NLS."
- 2006.12.03-2006.12.07, Asiacrypt 2006:
Souradyuti Paul and Bart Preneel, "On the (In)security of Stream Ciphers Based on Arrays and
Modular Addition" (attacking Py6 et al.).
- 2006.12.08-2006.12.10, CANS 2006:
Xiaoyun Wang, "Cryptanalysis on Streamcipher ABC v3."
- 2006.12.11-2006.12.13, Indocrypt 2006:
Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw,
"Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4"
(Salsa20 reduced to 6 rounds; IV setup of TSC-4).
Kenneth Koon-Ho Wong, Bernard Colbert, Lynn Batten, Sultan Al-Hinai,
"Algebraic Attacks on Clock-Controlled Cascade Ciphers"
- 2007.01.31-2007.02.01, SASC 2007, focused on eSTREAM.
- 2007.03.26-2007.03.28, FSE 2007:
Antoine Joux, Jean-Rene Reinhard, "Overtaking VEST."
Hongjun Wu, Bart Preneel, "Differential-linear attacks against the stream cipher Phelix."
Maria Naya Plasencia, "Cryptanalysis of Achterbahn-128/80."
Hakan Englund, Martin Hell, Thomas Johansson, "Two general attacks on Pomaranch-like keystream generators."
- 2007.05.20-2007.05.24, Eurocrypt 2007:
Hongjun Wu, Bart Preneel, "Differential cryptanalysis of the stream ciphers Py, Py6 and Pypy."
- 2007.07.02-2007.07.04, ACISP 2007:
Steve Babbage, Carlos Cid, Norbert Pramstaller, Havard Raddum: "An Analysis of the Hermes8 Stream Ciphers."
Debojyoti Bhattacharya, Debdeep Mukhopadhyay, Dipanwita RoyChowdhury: "Strengthening NLS against Crossword Puzzle Attack."
- 2007.07.04-2007.07.06, WEWoRC 2007:
Gordon Meiser, Thomas Eisenbarth, Kerstin Lemke-Rust, Christof Paar, "Efficient Assembly Implementation of Dragon, LEX, Salsa20 and Sosemanuk on 8-bit AVR Microcontrollers."
Timo Gendrullis, Timo Kasper, and Christof Paar, "A Lightweight Hardware Implementation of the Stream Cipher VEST-4."
Gautham Sekar, Souradyuti Paul and Bart Preneel, "Attacks on the Stream Ciphers TPy6 and Py6 and Design of New Ciphers TPy6-A and TPy6-B."
Mara Naya-Plasencia, "Cryptanalysis of Achterbahn-128/80 with a new Keystream Limitation."
- 2007.08.16-2007.08.17, SAC 2007:
Alexander Maximov, Alex Biryukov, "Two trivial attacks on Trivium."
Yukiyasu Tsunoo, Teruo Saito, Takeshi Kawabata, Hiroki Nakashima, "Distinguishing attack against TPypy."
- 2007.11.29-2007.11.30, ICISC 2007:
Chuan-Wen Loe, Khoongming Khoo, "Side Channel Attacks on Irregularly Decimated Generators."
Haina Zhang, Xiaoyun Wang, "Differential Cryptanalysis of T-Function Based Stream Cipher TSC-4."
- 2007.12.02-2007.12.06, Asiacrypt 2007:
Martin Hell, Thomas Johansson, "A Key Recovery Attack on Edon80."
- 2007.12.09-2007.12.13, Indocrypt 2007:
Gautham Sekar, Souradyuti Paul, Bart Preneel, "Related-key Attacks on the Py-family of Ciphers and an Approach to Repair the Weaknesses."
- 2008.02.10-2008.02.13, FSE 2008:
Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, Christian Rechberger, "New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba."
Michal Hojsik, Bohuslav Rudolf, "Differential Fault Analysis of Trivium."
Andrea Röck, "Entropy of the internal state of an FCSR in Galois representation."
- 2008.02.13-2008.02.14, SASC 2008,
focused on eSTREAM.
ABC version 1 was broken.
The designers proposed ABC version 2.
ABC version 2 was broken.
The designers proposed ABC version 3.
Now ABC version 3 has been broken.
Why should valuable cryptanalytic effort
have been taken away from other ciphers that didn't need any tweaks?
After Grain version 0 was broken,
the designers proposed Grain version 1.
Grain version 1 has attracted widespread interest
(and is one of very few eSTREAM "hardware focus" ciphers)
because it is a very fast cipher in hardware.
It has not been broken.
Why should a silly mistake in Grain version 0
have kept Grain version 1 out of the spotlight?
``At the end of the first phase,
it is likely that a subset of the first phase ciphers
will be advanced to the second phase,''
said the original eSTREAM call.
``This will provide further
focus to ongoing analysis within the cryptographic community.
Since the goal of the project is to derive good stream ciphers,
it is likely that potentially significant "tweaks"
will be permitted in moving to the second phase.''
``Since June 13th 2005 ...
ECRYPT has refused any changes to the primitives available for download,''
said the ECRYPT web site.
``It is possible that the submitter of [a broken] algorithm
might be invited to try and repair their submission,''
said the eSTREAM Update 1 document.
Implementations of tweaked algorithms
(such as DICING v1, which replaced DICING v0 in May 2005,
and ABC v2, which replaced ABC v1 in July 2005)
have generally been allowed into the eSTREAM benchmark suite.
The consensus of the SASC 2007 audience
was that tweaks should continue to be allowed for "promising" ciphers.
At the end of phase 2,
the eSTREAM committee eliminated each of the cipher families that had a history of being broken:
It is reasonably clear that further tweaks will not be considered in eSTREAM.
Jin Hong writes:
``As for patent issues,
I personaly would not vote for a cipher that intends to use patent rights
for money unless it is truely an extrodinary work.''
- ABC: "the design approach appears to be flawed."
- Py: "there is sufficient analysis ... to suggest that the submitted versions of the cipher
demonstrate a weakness in the design."
- TSC: "the reliability of the underlying construction might be open to some question."
Matthew Dempsky writes:
``Why would anyone choose to license a cipher
they can't efficiently implement instead of use one like AES?''
``If we determined to ignore the value and potential
in patented ECRYPT submissions then we would be certainly
placing ourselves at odds
with practically every other area of scientific endeavour.''
``Ruptor'' (later identified as VEST's Sean O'Neil) writes:
``I also see no reason to discard such ciphers as VEST or Frogbit or any other
patented cipher until and unless they are broken ...
Why don't people use free stuff?
Probably because you always get what you pay for?''
``Matt Crypto'' writes:
``I think a pay-to-use patented stream cipher would have to be
significantly better than the opposition to justify being chosen over
Most ciphers have been clearly labelled as being free for any use:
But there are some exceptions:
- Dragon: "The Dragon algorithm is made freely available to all users, at their own risk."
- Edon80: "We hereby explicitly release any intellectual property rights to Edon80 into the
- F-FCSR (first version broken):
"The inventors wish that the F-FCSR ciphers and the provided reference implementations
are and remains freely available, and may be used by anyone for any purpose, including commercial
exploitation, without restriction."
- Grain (first version broken): GPL-like restrictions on derived ciphers.
- HC-128: "HC-128 is not covered by any patent and it is freely available."
- HC-256: "HC-256 is not covered by any patent and it is freely available."
- MICKEY: "The designers of the algorithm do not claim any IPR over it,
and make it freely available for any purpose.
To the best of our knowledge no one else has any relevant IPR either."
- MOUSTIQUE: "I do hereby declare that I am aware of no patent applications which may cover
the practice of my submitted algorithm."
- NLS (version 1 broken): "QUALCOMM Incorporated allows free and unrestricted use
of any of its intellectual property required to exercise the primitive."
"We hereby explicitly release any intellectual property rights to Phelix into the public domain."
- Py (broken): "No royalty will be necessary for use of Py."
- Salsa20: "My policy is that Salsa20 is free for everyone to use."
- SOSEMANUK: "Permission is granted to anyone to use this software
for any purpose, including commercial applications."
- CryptMT: Patent pending,
but noncommercial use is free,
and commercial use is free if CryptMT appears in the final eSTREAM portfolio.
- DECIM (version 1 broken): Patent pending. No free use.
- Frogbit (broken): Patent pending. No free use.
- ProVEST (only 100-bit security): Patent pending. No free use.
- Rabbit: Patent pending, but noncommercial use is free.
- ZK-Crypt (version 1 broken): Patent pending. No free use.
I think that the "get what you pay for" theory
is solidly disproven by the examples of DECIM v1, Frogbit, ProVEST, and ZK-Crypt v1.
I don't think a patented submission will attract serious interest
unless it offers truly outstanding performance.
At the end of phase 1,
the eSTREAM committee did not eliminate patented ciphers,
but it also did not allow them as "focus" ciphers.
At the end of phase 2,
the eSTREAM committee said that its newest decisions
were "completely independent of the IP status of any cipher."
The remaining software ciphers include
five free-to-use ciphers;
LEX (which has never had a clear statement on the topic);
CryptMT (patented although sometimes free);
and Rabbit (patented although sometimes free).
The remaining hardware ciphers include
five free-to-use ciphers;
POMARANCH (no clear statement);
Trivium (no clear statement);
and DECIM (patented).