D. J. Bernstein
Hash functions and ciphers

Notes on the ECRYPT Stream Cipher project (eSTREAM)

Introduction
Broken ciphers and tweaks of those ciphers
Patented ciphers
Attacks (new home for table of submissions)
Leaks
Software timings (new home for aecycles, authspeed, timings)
Abbreviating the stream-cipher discussions
Why switch from AES to a new stream cipher?

Introduction

ECRYPT (www.ecrypt.eu.org), 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: http://en.wikipedia.org/wiki/ESTREAM.

eSTREAM has also become an increasingly popular conference topic:

Broken ciphers and tweaks of those ciphers

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?

Pessimist's example: 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?

Optimist's example: 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.

Patented ciphers

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.''

Matthew Dempsky writes: ``Why would anyone choose to license a cipher they can't efficiently implement instead of use one like AES?''

``Cryptowatch'' writes: ``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 unpatented/freely-useable alternatives.''

Most ciphers have been clearly labelled as being free for any use:

But there are some exceptions:

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).