Stream-cipher attacks (original) (raw)

Introduction

This page summarizes various attacks on stream ciphers, particularly the eSTREAM submissions. The official eSTREAM status of the submissions (SW focus for phase-2 "software focus" ciphers, SW for other phase-2 software ciphers, HW focus for phase-2 "hardware focus" ciphers, HW for other phase-2 hardware ciphers) is listed parenthetically, along with the location of the cipher software in the official eSTREAM benchmark suite.

I have a new paper summarizing attacks on the eSTREAM submissions and discussing the standard definition of cipher security:

[broken]35pp.(PDF)D. J. Bernstein. Which eSTREAM ciphers have been broken? Document ID: 83331cc746de71bc71540a0f372acbf6. URL: https://cr.yp.to/papers.html#broken. Date: 2008.03.30. Supersedes:(PDF)2008.02.21. The paper does not include stream ciphers that were not submitted to eSTREAM.

I also have a separate page on side-channel leaks.

ABC v1 (submissions/abc/v1): withdrawn

Proposed by Vladimir Anashin, Andrey Bogdanov, Ilya Kizhvatov, Sandeep Kumar. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Berbain and Gilbert [paper] wrote: "We present an attack against ABC ... The attack requires 2^95 operations and 2^32 32-bit keystream words." Authors wrote: "We sent the ECRYPT stream cipher project committee an update. ... We would like the cryptographical community to regard the updated version of ABC as the basic one."
Khazaei [paper] stated another attack.

ABC v2 (submissions/abc/v2): withdrawn

Proposed 2005.07 by Vladimir Anashin, Andrey Bogdanov, Ilya Kizhvatov, Sandeep Kumar. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Khazaei and Kiaei wrote [paper]: "we ... mount a distinguishing attack on both versions of ABC with data, time and memory complexities of O(2^32)." The authors disputed the attack. Khazaei and Kiaei withdrew their claim and apologized.
Wu and Preneel [2006 paper] stated an experimentally confirmed attack that finds a key with probability 2^-32, given about 2^32 bytes of output. Authors wrote: "We would like to thank the authors for the nice attack."

ABC v3 (SW, submissions/abc/v3): broken

Proposed by Vladimir Anashin, Andrey Bogdanov, Ilya Kizhvatov, Sandeep Kumar. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Zhang, Li, and Wang stated an attack: "We show that, there are at least 2^{103.71} weak keys among 2^{128} random primary keys, and for each weak key, the expanded key can be recovered with about 2^{33.6} keystream words and 2^{50.56} operations."
Wu and Preneel (SASC 2007 rump session) stated a speedup of the Zhang-Li-Wang attack. The Wu-Preneel attack has only about 2^96 weak keys but detects a weak key from about 2^20 bytes of output and recovers the key from about 2^32 bytes of output.

Achterbahn v1 (submissions/achterbahn/v1): withdrawn

Proposed by Berndt Gammel, Rainer Goettfert, Oliver Kniffler. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Johansson, Meier, and Muller wrote [paper]: "We present several attacks which break the cipher faster than a brute force attack." I disagree: the attack uses 2^73 steps on a machine with 2^40 bits of memory, so it is much slower than a brute-force machine of the same size. Authors have nevertheless withdrawn Achterbahn version 1 in favor of Achterbahn-80 and Achterbahn-128.

Achterbahn-80 (HW, submissions/achterbahn/128-80) limited to 2^52 bits: unresolved

Proposed by Berndt Gammel, Rainer Goettfert, Oliver Kniffler. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Hell and Johansson stated an attack using 2^60 bits of keystream and a relatively small amount of processing. Authors responded (at SASC 2007): "A good-for-nothing paper."
Naya-Plasencia (SASC 2007) stated a comparable attack. Authors (SASC 2007) proposed stopping the attack by limiting Achterbahn-80 to 2^52 bits of keystream.
Naya-Plasencia (SASC 2007 rump session) stated an attack using 2^52 bits of keystream and "complexity 2^67." My current impression is that, as in the case of Achterbahn v1, overwhelming communication costs are being ignored in these "attacks."

Achterbahn-128 (HW, submissions/achterbahn/128-80) limited to 2^56 bits: unresolved

Proposed by Berndt Gammel, Rainer Goettfert, Oliver Kniffler. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Hell and Johansson stated an attack using 2^60 bits of keystream and a relatively small amount of processing. Authors responded (at SASC 2007): "A good-for-nothing paper."
Naya-Plasencia (SASC 2007) stated a comparable attack. Authors (SASC 2007) proposed stopping the attack by limiting Achterbahn-128 to 2^56 bits of keystream.
Naya-Plasencia (SASC 2007 rump session) stated an attack using 2^56 bits of keystream and "2^104 operations." See above regarding communication costs.

AES with 10 rounds (benchmarks/aes-ctr/aes-128): 128-bit security?

Cryptanalysis:

Obvious: Brute force to find 128-bit key.

AES with 14 rounds (benchmarks/aes-ctr/aes-256): 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

ChaCha6: 139-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Aumasson, Fischer, Khazaei, Meier, and Rechberger (2008.03.14) reported a 2^139-operation attack on ChaCha6. (The FSE version of the paper reported an attack on a slightly different "ChaCha" cipher.) For 128-bit keys, the Aumasson-et-al. attack uses 2^107 operations.

ChaCha7: 248-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Aumasson, Fischer, Khazaei, Meier, and Rechberger (2008.03.14) reported a 2^248-operation attack on ChaCha7. (The FSE version of the paper reported an attack on a slightly different "ChaCha" cipher.) For 128-bit keys, the Aumasson-et-al. attack doesn't work at all: it needs to guess all key bits.

ChaCha8: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

ChaCha9: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

ChaCha10: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

ChaCha11: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

ChaCha12: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

ChaCha20: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

CryptMT v1 (SW, submissions/cryptmt/v1): 256-bit security?

[paper] Proposed by Makoto Matsumoto, Hagita Mariko, Takuji Nishimura, Matsuo Saito. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Khazaei and Shakour wrote [paper]: "The LSB's ... of every two conseuctive output bytes are equal with probability (1/2)(1+2^(-24))." Authors respond: "This seems mathematically wrong." Khazaei and Shakour write: "We confess that we made a terrible blunder."

CryptMT v2 (SW, submissions/cryptmt/v2): 256-bit security?

Proposed by Makoto Matsumoto, Hagita Mariko, Takuji Nishimura, Matsuo Saito. Cryptanalysis:

Obvious: Brute force to find 256-bit key.

CryptMT v3 (SW, Phase 3 SW focus, submissions/cryptmt/v3): 256-bit security?

Proposed by Makoto Matsumoto, Hagita Mariko, Takuji Nishimura, Matsuo Saito. Cryptanalysis:

Obvious: Brute force to find 256-bit key.

DECIM v1 (submissions/decim/v1): withdrawn

[paper] Proposed by Come Berbain, Olivier Billet, Anne Canteaut, Nicolas Courtois, Blandine Debraize, Henri Gilbert, Louis Goubin, Aline Gouget, Louis Granboulan, Cedric Lauradoux, Marine Minier, Thomas Pornin, Herve Sibert. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Wu and Preneel wrote [paper]: "We point out two serious flaws in DECIM. ... DECIM is insecure." Gouget wrote: "H. Wu and B. Preneel showed two serious flaws in the stream cipher DECIM. The main serious flaw is in the keystream generation mechanism of DECIM."

DECIM v2 (HW, Phase 3 HW focus, submissions/decim/v2): 80-bit security?

Cryptanalysis:

Obvious: Brute force to find 80-bit key.

DECIM-128: 128-bit security?

Cryptanalysis:

Obvious: Brute force to find 128-bit key.

DICING v0: withdrawn

[paper] Proposed by Li An-Ping. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Piret wrote [paper]: "We describe practical distinguishing and key recovery attacks ... a keystream of about 128 words ... 2^22 hash table lookups."

DICING v1 (submissions/dicing/v1): withdrawn

[paper] Proposed by Li An-Ping. Replaced DICING v0 in May 2005. Cryptanalysis:

Obvious: Brute force to find 256-bit key.

DICING v2 (SW, submissions/dicing/v2): 256-bit security?

Proposed by Li An-Ping. Cryptanalysis:

Obvious: Brute force to find 256-bit key.

Dragon (SW focus, Phase 3 SW focus, submissions/dragon) limited to 2^64 bits per key: 256-bit security?

[paper] Proposed by Ed Dawson, Kevin Chen, Matt Henricksen, William Millan, Leonie Simpson, HoonJae Lee, SangJae Moon. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Englund and Maximov [paper] stated an attack on Dragon-256 using 2^155 words of keystream and 2^32 blocks of memory. Authors responded [paper] that the Dragon-256 documentation had already recommended generating no more than 2^64 bits per key, making the attack impossible.
Cho and Pieprzyk stated an attack on Dragon-256 using 2^151.6 words of keysream and 2^59 blocks of memory. As above, the Dragon usage limits make this attack impossible.

Edon80 (HW, Phase 3 HW focus, submissions/edon80): 80-bit security?

Proposed by Danilo Gligoroski, Smile Markovski, Ljupco Kocarev, Marjan Gusev. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
There has been some discussion of the Edon80 period: Hong paper [PDF], response [PDF]. I see no reason to believe that this discussion will produce an attack.
A paper by Hell and Johansson states an attack using "around 2^69 simple operations." However, according to the cipher designers, the attack as stated uses about 2^20 words of memory and takes more time than parallel exhaustive key search on a similar-size machine. Perhaps the attack can be parallelized and streamlined to take less time, but the requisite analysis has not been done. The attack authors say that the cipher designers have misunderstood the attack, but I don't find the attack performance clear from the paper.

F-FCSR-8 (submissions/f-fcsr/f-fcsr-8): withdrawn

[paper] Proposed by Thierry Berger, Francois Arnault, Cedric Lauradoux. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Jaulmes and Muller stated several attacks, such as a distinguishing attack using 2^34 nonces. Authors withdrew F-FCSR-8: "These attacks pointed out three weaknesses on the algorithms. The first one is a bottleneck effect due to a big mistake in our design."

F-FCSR-H (HW, Phase 3 HW focus, submissions/f-fcsr/f-fcsr-h): broken

Proposed by Thierry Berger, Francois Arnault, Cedric Lauradoux. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Arnault, Berger, and Minier (SASC 2007) show that various attacks don't work against F-FCSR-H.
Hell and Johansson (Asiacrypt 2008) show a very fast attack against F-FCSR-H. No response yet from the designers.

F-FCSR-16 (Phase 3 HW focus, submissions/f-fcsr/f-fcsr-16): broken?

[paper] Proposed by Thierry Berger, Francois Arnault, Cedric Lauradoux. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Arnault, Berger, and Minier (SASC 2007) show that various attacks don't work against F-FCSR-16.
Presumably the attack by Hell and Johansson (Asiacrypt 2008) extends from F-FCSR-H to F-FCSR-16. No response yet from the designers.

Frogbit (submissions/frogbit): broken

Proposed by Thierry Moreau. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Turan, Doganaksoy, and Calik stated (SASC 2006) that Frogbit output flunks a simple IV-diffusion test.
Saarinen independently stated (SASC 2006) that Frogbit output flunks another IV test.

Fubuki (submissions/fubuki): 256-bit security?

[paper] Proposed by Makoto Matsumoto, Hagita Mariko, Takuji Nishimura, Matsuo Saito. Cryptanalysis:

Obvious: Brute force to find 256-bit key.

GGHN: broken

Proposed by Gong et al. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Paul (2006) published a distinguishing attack using 2^33 bytes of output.

Grain v0 (submissions/grain/v0): withdrawn

[paper] Proposed by Martin Hell, Thomas Johansson, Willi Meier. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Berbain and Gilbert wrote: "We have found an attack on Grain, which requires about 2^40 keystream bits and 2^44 operations to recover the secret key." Khazaei, Hassanzadeh, and Kiaei [paper] stated another attack. Authors withdrew Grain v0: "We have now specified a tweaked version by changing the output function. ... The old version ... is not to be considered."

Grain v1 (HW focus, Phase 3 HW focus, submissions/grain/v1): 79-bit security?

Proposed by Martin Hell, Thomas Johansson, Willi Meier. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
De Canniere, Kucuk, and Preneel (SASC 2008) stated an attack speeding up brute force "by a factor two."

Grain-128 (HW focus, Phase 3 HW focus, submissions/grain/128): 128-bit security?

Proposed by Martin Hell, Thomas Johansson, Willi Meier. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

HC-128 (Phase 3 SW focus, submissions/hc-256/hc-128): 128-bit security?

Proposed by Hongjun Wu. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

HC-256 (SW focus, Phase 3 SW focus, submissions/hc-256/hc-256): 256-bit security?

[paper] Proposed by Hongjun Wu. Cryptanalysis:

Obvious: Brute force to find 256-bit key.

Hermes8 (HW, submissions/hermes/hermes8-80): unresolved

Proposed by Ulrich Kaiser. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Steve Babbage wrote: "... if we assume known plaintext ... it's clear that we can deduce the entire contents of Key Register very efficiently." Author wrote: "I've closed this `backdoor'... Please, have a look on the improved version." There's an unfortunate lack of name clarity here: I'm not sure exactly which cipher was broken.

Hermes8-128 (HW, submissions/hermes/hermes8-128): withdrawn

Proposed by Ulrich Kaiser. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Babbage, Cid, Pramstaller, and Raddum stated "an attack requiring very few known keystream bytes that recovers the cipher secret key in less than a second on a normal PC." No response from the author; apparently Hermes8-128 is withdrawn.

Hermes8F (HW, submissions/hermes/hermes8f-80): broken

Proposed by Ulrich Kaiser. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Babbage, Cid, Pramstaller, and Raddum (SASC 2007) stated an attack on Hermes8F.

Hermes8F-128 (HW, submissions/hermes/hermes8f-128): broken

Proposed by Ulrich Kaiser. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Babbage, Cid, Pramstaller, and Raddum (SASC 2007) stated an attack on Hermes8F.

IA: broken

Proposed by Jenkins at FSE 1996. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Paul and Preneel (2006) published a distinguishing attack using 2^33 bytes of output.

ISAAC: 256-bit security?

Proposed by Jenkins at FSE 1996. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Paul and Preneel (2006) published an alleged distinguishing attack using 2^17 bytes of output, but this turned out to be an attack on a cipher different from ISAAC.
Aumasson (2006) labelled various states of ISAAC as "weak." I don't see an attack stated here.

LEX v1 (submissions/lex/v1) limited to 2^46 bytes per key: 128-bit security?

[paper] Proposed by Alex Biryukov. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Wu and Preneel wrote [paper]: "If a key is used with about 2^61 random IVs, and 20,000 keystream bytes are generated from each IV, then the key could be recovered easily." Author's response is that this does not have better price-performance ratio than brute force.
Englund, Hell, and Johansson point out that N LEX nonces, each used for B blocks, have probability approximately BN^2/2^128 of producing identical keystreams modulo shifts. Author had already limited N to 2^32 and B to 2^9, so the chance of these collisions is approximately 1/2^55. There is also a 256-bit version of LEX v1, but my impression is that this version has not even been fully specified, let alone implemented.

LEX v2 (SW focus, HW, Phase 3 SW focus, non-functional submissions/lex/v2) limited to 2^46 bytes per key: 128-bit security?

Proposed by Alex Biryukov. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
See above regarding Englund-Hell-Johansson.
Several commentators have observed that LEX looks like a good target for algebraic attacks. Has anyone evaluated the cost of these attacks?

MAG v0 (submissions/mag/v0?): withdrawn

Proposed by Rade Vuckovac. ("Provisional C++ version initially submitted to the ECRYPT.") Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Kuenzli, Meier wrote [paper]: "We present a very simple distinguishing attack ... on MAG, requiring only 129 successive bytes of known keystream, computation and memory are negligible." Author's response was fairly incoherent but appeared to admit that the attack works: "DA shows how MAG secure stream can be differentiated from a random stream. ... From the equation no 3 it appears that the next unknown byte can be predicted with 1/2 probability."

MAG v1 (submissions/mag/v1?): unresolved

[paper] Proposed by Rade Vuckovac. ("MAG v1 (32 bit) is different from C++ version.") The standard presumption is that MAG v1, like MAG v0, is distinguishable at very low cost, but author disputes this. The standard presumption was also that MAG v1 was withdrawn when MAG v2 was introduced, but author says it wasn't.

MAG v2 (submissions/mag/v2): unresolved

Did not attract any attention. The standard presumption is that MAG v2, like MAG v0, is distinguishable at very low cost, but author disputes this. The standard presumption was also that MAG v2 was withdrawn when MAG v3 was introduced, but author says it wasn't.

MAG v3 (submissions/mag/v3): broken

Briefly attracted attention for its extremely high speed. Distinguishable at very low cost; I posted distinguishing code to the eSTREAM forum in 2007.02.

MICKEY v1 (submissions/mickey/v1): 80-bit security?

[paper] Proposed by Steve Babbage, Matthew Dodd. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Hong and Kim [paper] asked how much entropy is lost by the MICKEY state update. I see no reason to believe that this type of loss will produce an attack.
Hong commented that MICKEY (like most ciphers) allows "BSW sampling." This doesn't change the price-performance ratio of an attack, but it means that the attacker can build a ridiculously insanely large attack machine rather than merely an insanely large attack machine.

MICKEY-128 v1 (submissions/mickey/v1-128): 128-bit security?

Proposed by Steve Babbage, Matthew Dodd. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Hong and Kim asked how much entropy is lost by the MICKEY state update. I see no reason to believe that this type of loss will produce an attack.
Hong commented that MICKEY (like most ciphers) allows "BSW sampling." This doesn't change the price-performance ratio of an attack, but it means that the attacker can build a ridiculously insanely large attack machine rather than merely an insanely large attack machine.

MICKEY v2 (HW, Phase 3 HW focus, submissions/mickey/v2): 80-bit security?

Proposed by Steve Babbage, Matthew Dodd. Cryptanalysis:

Obvious: Brute force to find 80-bit key.

MICKEY-128 v2 (HW focus, Phase 3 HW focus, submissions/mickey/v2-128): 128-bit security?

Proposed by Steve Babbage, Matthew Dodd. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

Mir-1 (submissions/mir-1): withdrawn

Proposed by Alexander Maximov. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Tsunoo, Saito, Kubo, Shigero, and Tsujii (SASC 2006) presented "Cryptanalysis of Mir-1." No response from the authors; apparently Mir-1 is withdrawn.

Mosquito: withdrawn

[paper (subsequently corrected)] Proposed by Joan Daemen, Paris Kitsos. "More of a research object than a standard proposal," Daemen said in his SKEW 2005 presentation. "Broken," Daemen said in his SASC 2006 presentation.

Moustique (HW, Phase 3 HW focus): 90-bit security?

Proposed by Joan Daemen, Paris Kitsos. Cryptanalysis:

Kaesper, Rijmen, Bjoerstad, Rechberer, Robshaw, and Sekar (SASC 2008) stated an attack on Moustique about 4 times faster than brute force. In the talk they announced that a refinement of the attack would be "about 50 times faster" than brute force.

NGG: broken

Proposed by Nawaz, Gupta, and Gong in 2005. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Wu (2005) published a distinguishing attack using 100 outputs.

NLS v1 (submissions/nls/sync?): withdrawn

Proposed by Gregory Rose, Philip Hawkes, Michael Paddon, Miriam Wiggers de Vries. NLS allows an add-on authenticator, ignored here.

Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Cho and Pieprzyk (SASC 2006, "Linear distinguishing attack on NLS") stated an attack on NLS v1. No response from the authors; apparently NLS v1 is withdrawn.

NLS v2 (SW, HW, Phase 3 SW focus, submissions/nls/sync?) limited to 2^64 bytes per key: 128-bit security?

Proposed by Gregory Rose, Philip Hawkes, Michael Paddon, Miriam Wiggers de Vries. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Cho and Piperzyk stated an attack on NLS version 2: "We can now construct a distinguisher whose bias is around 2^{-38.8}. Therefore, we claim that NLSv2 is distinguishable from a truly random cipher after observing around 2^{77.6} keystream words." The distinguisher has only about one chance in a billion of succeeding within 2^64 bytes.

Phelix (SW focus, HW focus, submissions/phelix): 256-bit security?

[paper] Proposed by Doug Whiting, Bruce Schneier, Stefan Lucks, Frederic Muller. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Wu and Preneel stated an "attack" revealing the Phelix key, but this "attack" requires chosen plaintexts and chosen repeated nonces, violating both the concept of a nonce and the security rules enforced by nonce generators. Every eSTREAM candidate leaks extensive information when nonces are repeated. This type of "attack" is adequately discussed in the Phelix documentation and does not require a response from the Phelix authors.

Polar Bear v1 (submissions/polarbear/v1): withdrawn

[paper] Proposed by Johan Haastad, Mats Naeslund. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
John Mattsson wrote: "I have found a weakness in the cipher Polar Bear. Under the assumption of a known plaintext a certain stepping and sequence of alphas opens up for a state recovery in O(2^79) time. ... The weakness has been confirmed by the algorithm's submitters."
Hasanzadeh, Shakour, and Khazaei stated "an improved attack with computational complexity of O(2^57.4)."

Polar Bear v2 (SW, HW, submissions/polarbear/v2): 128-bit security?

Proposed by Johan Haastad, Mats Naeslund. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

Pomaranch (CJCSG) v1 (submissions/pomaranch/v1): withdrawn

[paper] [another paper] Proposed by Cees Jansen, Tor Helleseth, Alexander Kholosha. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Cid, Gilbert, and Johansson [paper] wrote: "We show how to mount a chosen IV attack to recover the secret key of Pomaranch with complexity much lower than the one expected with 128-bit keys."
Khazaei [paper] stated an attack, exploiting the stream generation rather than the use of the nonce.
Hasanzadeh, Khazaei, and Kholosha [paper] stated an attack.

Pomaranch v2: 128-bit security?

[paper] Proposed by Cees Jansen, Tor Helleseth, Alexander Kholosha. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

Pomaranch v3 (HW, Phase 3 HW focus): 128-bit security?

Proposed by Cees Jansen, Tor Helleseth, Alexander Kholosha. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

ProVEST-4 (HW, submissions/vest/provest-4): 100-bit security?

[paper] Proposed by Claude Bigeard, Sean O'Neil, Benjamin Gittins, Howard Landman. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Joux and Reinhard (SASC 2007) stated an attack that recovers "53 bits of the keyed states in 2^22.74 IV setups" and that then recovers the F-bit cipher key using "2^max(F/2+4,F-53) time and 2^(F/2-4) memory." They conclude: "VEST should be considered as broken." I disagree. The stated attack is slower than a brute-force search on a machine of the same size.
My current impression is that a refined attack, parallelizing the Joux-Reinhard attack and reducing its memory requirements, uses time approximately 2^(F/2+4) on a machine of size 2^(F/4); in particular, a 128-bit ProVEST key can be found in time comparable to a 100-bit brute-force search.

ProVEST-16 (HW, submissions/vest/provest-16): 100-bit security?

Proposed by Claude Bigeard, Sean O'Neil, Benjamin Gittins, Howard Landman. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
See above regarding the Joux-Reinhard attack.

ProVEST-32 (HW, submissions/vest/provest-32): 100-bit security?

Proposed by Claude Bigeard, Sean O'Neil, Benjamin Gittins, Howard Landman. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
See above regarding the Joux-Reinhard attack.

Py (SW focus, submissions/py/py) limited to 2^64 bytes per key: broken

Proposed by Eli Biham, Jennifer Seberry. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Sekar, Paul, and Preneel stated [paper] that the first 24 bytes of Py output for 2^83.82 nonces are quickly distinguishable from uniform. Crowley stated a reduction to 2^73 nonces. The authors responded that Py must not be used for more than 2^64 bytes per key.
Wu and Preneel stated (among other things) that, out of 2^23 carefully selected nonces, about 2^7 produce the same output stream. Disaster!

Py6 (SW focus, submissions/py/py6) limited to 2^64 bytes per key: broken

Proposed by Eli Biham, Jennifer Seberry. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Paul and Preneel stated that a small amount of Py output for 2^68 nonces are quickly distinguishable from uniform. The authors responded that Py6 must not be used for more than 2^64 bytes per key.
Wu and Preneel stated disastrous Py6 attacks comparable to the Py attacks.

Pypy (SW focus, submissions/py/pypy) limited to 2^64 bytes per key: broken

Proposed by Eli Biham, Jennifer Seberry in "Pypy: Another Version of Py" (2006.06.27). Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Wu and Preneel stated disastrous Pypy attacks comparable to the Py attacks.

Rabbit (SW, HW, Phase 3 SW focus, submissions/rabbit): 128-bit security?

[paper] Proposed by Martin Boesgaard, Mette Vesterager, Thomas Christensen, Erik Zenner. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

Salsa20/5: broken

Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Crowley (2005) stated a 2^165-operation attack on Salsa20/5. The attack works forwards from a known input difference to a biased bit 3 rounds later, and works 2 rounds backwards from an output after guessing 160 relevant key bits.
Fischer, Meier, Berbain, Biasse, and Robshaw (Indocrypt 2006) stated a much faster attack on Salsa20/5. The attack works forwards from a known input difference to a biased bit 4 rounds later, and works 1 round backwards from an output.

Salsa20/6: broken

Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Fischer, Meier, Berbain, Biasse, and Robshaw (Indocrypt 2006) stated a 2^177-operation attack on Salsa20/6. The attack works forwards from a known input difference to a biased bit 4 rounds later, and works 2 rounds backwards from an output after guessing 160 relevant key bits.
Tsunoo, Saito, Kubo, Suzaki, and Nakashima (SASC 2007) stated a much faster attack on Salsa20/6. The attack works forwards from a known input difference to a biased bit 4 rounds later, and works 2 rounds backwards from an output after guessing 62 highly relevant key bits. For 128-bit keys, the Tsunoo-et-al. attack guesses 50 key bits.

Salsa20/7: 151-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Tsunoo, Saito, Kubo, Suzaki, and Nakashima (SASC 2007) stated a 2^184-operation attack on Salsa20/7. The attack works forwards from a known input difference to a biased bit 4 rounds later, and works 3 rounds backwards from an output after guessing 171 highly relevant key bits.
Aumasson, Fischer, Khazaei, Meier, and Rechberger (FSE 2008) reported a 2^151-operation attack on Salsa20/7. (The paper at FSE reported a 2^153-operation attack; the revised estimate is from the 2008.03.14 version of the paper.) For 128-bit keys, the Tsunoo-et-al. attack guesses 115 key bits and might be slightly faster than brute force; the Aumasson-et-al. attack uses 2^111 operations.

Salsa20/8 (SW focus, HW, Phase 3 SW focus, submissions/salsa20/8-rounds): 249-bit security?

Proposed by me. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Tsunoo, Saito, Kubo, Suzaki, and Nakashima (SASC 2007) tried to push their Salsa20/7 attack to Salsa20/8, working 4 rounds backwards from an output after guessing almost all of the 256 key bits. The paper estimates that a particular attack along these lines, guessing 245 bits and then performing a rather complicated computation for each guess, would take only 50% as long as a complete 256-bit brute-force search; but the paper also says that the attack has only a 44% chance of success. Obviously the attack is very close to brute force; figuring out whether it's slightly less expensive or slightly more expensive would require a careful cost analysis.
Aumasson, Fischer, Khazaei, Meier, and Rechberger (FSE 2008) reported a 2^251-operation attack on Salsa20/8. The attack works forwards from a small known input difference to a biased bit 4 rounds later, and works 4 rounds backwards from an output after guessing 228 extremely relevant key bits. For 128-bit keys, the Tsunoo-et-al. attack doesn't work at all; it would have to guess all 128 key bits. The same is true for the Aumasson-et-al. attack.

Salsa20/9: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

Salsa20/10: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

Salsa20/11: 256-bit security?

Cryptanalysis:

Obvious: Brute force to find 256-bit key.

Salsa20/12 (SW focus, HW, Phase 3 SW focus, submissions/salsa20/12-rounds): 256-bit security?

Proposed by me. Cryptanalysis:

Obvious: Brute force to find 256-bit key.

Salsa20/20 = Salsa20 = Snuffle 2005 (SW focus, HW, Phase 3 SW focus, submissions/salsa20/full): 256-bit security?

Proposed by me. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
An-Ping made two claims, with no computer verification, of attacks on Salsa20. In my paper "Disproof of Li An-Ping's claims regarding Salsa20," I reported computer experiments disproving the claims, and I explained two fatal flaws in An-Ping's "analysis." An-Ping eventually admitted one flaw and withdrew the first two claims. An-Ping then issued a third claim, again without computer verification. An-Ping's "analysis" again contains the fatal flaw discussed in Section 5 of my paper; one could use a similar "analysis" to make false claims of bias in any combination of output bits in any cipher. Current consensus is that An-Ping is obliged to stop making cryptanalytic claims without computer verification.

SFINKS (submissions/sfinks/sync): withdrawn

[paper] Proposed by An Braeken, Joseph Lano, Nele Mentens, Bart Preneel, Ingrid Verbauwhede. Allows an add-on authenticator, ignored here. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Various standard LFSR attacks: SFINKS uses the traditional idea of feeding a low-complexity LFSR (consecutive powers of a finite field element with sparse minimal polynomial, starting from a secret exponent) through a low-complexity Boolean function. There are many attacks on these constructions when the complexity is too low; SFINKS scales the complexity up far enough that none of the standard attacks are faster than brute force. "We believe that LFSR-based designs are ... a good choice for hardware applications, provided we can prove the resistance of the design to a whole set of cryptanalytic attacks," the authors write.
Courtois wrote: "Sfinks broken by fast algebraic attacks." Apparently SFINKS was withdrawn as a result of this attack. But I disagree with the conclusion. The simple fact is that Courtois's attack is slower than brute force.
There is a new general LFSR attack by Roenjom and Helleseth. Has anyone tried to apply it to SFINKS?

SOSEMANUK (SW focus, Phase 3 SW focus, submissions/sosemanuk): 226-bit security?

[paper] Proposed by Come Berbain, Olivier Billet, Anne Canteaut, Nicolas Courtois, Henri Gilbert, Louis Goubin, Aline Gouget, Louis Granboulan, Cedric Lauradoux, Marine Minier, Thomas Pornin, Herve Sibert. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Ahmadi, Eghlidos, and Khazaei [paper] stated an attack on SOSEMANUK taking "2^226 basic operations." Authors responded that SOSEMANUK never claimed more than a 128-bit security level.

SSS: withdrawn

Proposed by Gregory Rose, Philip Hawkes, Michael Paddon, Miriam Wiggers de Vries. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Daemen [paper] wrote: "Below a simple key-retrieval on SSS encryption requiring about 3100 bytes of chosen ciphertext and computational complexity 2^24. I did not experimentally verify whether it actually works so it may contain errors." Authors wrote: "A neat attack, thanks. I confess that trying a self-synchronous stream cipher was a departure from anything that we really knew how to do..."

TPy (SW focus?, submissions/py/tpy) limited to 2^64 bytes per key: 256-bit security?

Proposed by Eli Biham, Jennifer Seberry in "Tweaking the IV Setup of the Py Family of Stream Ciphers---The Ciphers TPy, TPypy, and TPy6" (2007.01.25). Cryptanalysis:

Obvious: Brute force to find 256-bit key.
See the Py description regarding the Sekar-Paul-Preneel attack. The TPy proposal stops the attack by limiting the amount of data generated per key.

TPy6 (SW focus?, submissions/py/tpy6) limited to 2^64 bytes per key: 256-bit security?

Proposed by Eli Biham, Jennifer Seberry in "Tweaking the IV Setup of the Py Family of Stream Ciphers---The Ciphers TPy, TPypy, and TPy6" (2007.01.25). Cryptanalysis:

Obvious: Brute force to find 256-bit key.
See the Py6 description regarding the Paul-Preneel attack. The TPy6 proposal stops the attack by limiting the amount of data generated per key.

TPypy (SW focus?, submissions/py/tpypy): 256-bit security?

Proposed by Eli Biham, Jennifer Seberry in "Tweaking the IV Setup of the Py Family of Stream Ciphers---The Ciphers TPy, TPypy, and TPy6" (2007.01.25). Cryptanalysis:

Obvious: Brute force to find 256-bit key.

Trivium (HW focus, Phase 3 HW focus, submissions/trivium): 80-bit security?

[paper] Proposed by Christophe De Canniere, Bart Preneel. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Khazaei and Hassanzadeh [paper] showed that Trivium is immune to certain classes of attacks.
There is an obvious way to insert more than 80 bits of key into Trivium, but Maximov and Biryukov (SASC 2007) stated an attack on all of these extended-key variants of Trivium using roughly 2^100 bit operations. I hope that the authors (or other people) specify a series of scaled versions of Trivium, with states of various sizes; these would be very nice targets for future cryptanalysis.

TSC-3 (submissions/tsc-3/tsc-3): withdrawn

[paper] Proposed by Jin Hong, Dong Hoon Lee, Yongjin Yeom, Daewan Han, Seongtaek Chee. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Muller wrote: "We just posted a paper that describes distinguishing and key recovery attacks against TSC-3. The distinguishing attack costs 2^42 time and data. The key recovery attack costs 2^66 time and 2^34 data." [paper] Author wrote: "I have quickly read through the paper and believe the attacks to be valid."

TSC-4 (HW, submissions/tsc-3/tsc-4): 80-bit security?

Proposed by Dukjae Moon, Daesung Kwon, Daewan Han, Jooyoung Lee, Gwon Ho Ryu, Dong Wook Lee, Yongjin Yeom, and Seongtaek Chee. Cryptanalysis:

Obvious: Brute force to find 80-bit key.
Zhang and Wang (ICISC 2007) stated an attack that recognizes TSC-4 output using 2^40 chosen IVs. The attack works for only 1 out of every 2^8 keys, but it's still better than brute force.

WG v1 (submissions/wg/v1/small-iv, submissions/wg/v1/long-iv): broken

Proposed by Guang Gong, Yassir Nawaz. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Wu and Preneel [paper] stated various attacks on WG version 1. Authors wrote: "We admit that 22 clock cycles for key/IV setup phased as suggested by us in the original WG paper was too optimistic. ... We therefore recommend the key/IV setup phase of the WG cipher to be 88 clock cycles. No design changes are required."

WG v2 (HW, submissions/wg/v2/small-iv, submissions/wg/v2/long-iv) limited to 2^45 bits per key: 80-bit security?

Proposed by Guang Gong, Yassir Nawaz. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Roenjom and Helleseth (SASC 2007) stated an attack on WG using 2^45.2 keystream bits and 2^45.2 simple operations after a precomputation of complexity 2^62. However, the WG specification limits the keystream to 2^45 bits.

YAMB (submissions/yamb): unresolved

[paper] Proposed by Anatoly N. Lebedev, Alexander Ivanov, Sergey Starodubtzev, Alexey Kolchkov. Cryptanalysis:

Obvious: Brute force to find 256-bit key.
Wu wrote: "There is a distinguishing attack on Yamb. It requires about 2^{58} outputs and about 2^{55} simple operations (32-bit addition or subtraction)." [paper] The authors finally responded several months later, disputing the attack.

ZK-Crypt v1 (submissions/zk-crypt/v1): withdrawn

Proposed by Carmi Gressel, Ran Granot, Gabi Vago. Cryptanalysis:

Obvious: Brute force to find 128-bit key.
Lubkin and Ryabko [paper] appeared to state that ZK-Crypt output is compressible by a standard move-to-front-plus-Huffman algorithm applied to 4-byte words.
Turan, Doganaksoy, and Calik stated (SASC 2006) that ZK-Crypt output flunks a simple IV-diffusion test.
Saarinen independently stated (SASC 2006) that ZK-Crypt output flunks another IV test.

The authors (at SASC 2006, and again in the ZK-Crypt v2 documentation) questioned the Lubkin-Ryabko result. I wrote a paper confirming and simplifying the Lubkin-Ryabko result:

[zkcrypt]4pp.(PDF)D. J. Bernstein. Does ZK-Crypt version 1 flunk a repetition test? Document ID: b6f4ca45a01f114782fe80341e9b60a9. URL: https://cr.yp.to/papers.html#zkcrypt. Date: 2006.03.02.

ZK-Crypt v2 (HW, submissions/zk-crypt/v2): 128-bit security?

Proposed by Carmi Gressel, Ran Granot, Gabi Vago. Cryptanalysis:

Obvious: Brute force to find 128-bit key.

ZK-Crypt v3 (HW, submissions/zk-crypt/v3): 128-bit security?

Proposed by Carmi Gressel, Ran Granot, Gabi Vago. Cryptanalysis:

Obvious: Brute force to find 128-bit key.