Attacks

Introduction

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.

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

ABC v1 (submissions/abc/v1): withdrawn

• 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

• 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

• 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

• 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

• 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."

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

• 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."

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

• Obvious: Brute force to find 128-bit key.

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

• Obvious: Brute force to find 256-bit key.

ChaCha6: 139-bit security?

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

ChaCha7: 248-bit security?

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

ChaCha8: 256-bit security?

• Obvious: Brute force to find 256-bit key.

ChaCha9: 256-bit security?

• Obvious: Brute force to find 256-bit key.

ChaCha10: 256-bit security?

• Obvious: Brute force to find 256-bit key.

ChaCha11: 256-bit security?

• Obvious: Brute force to find 256-bit key.

ChaCha12: 256-bit security?

• Obvious: Brute force to find 256-bit key.

ChaCha20: 256-bit security?

• Obvious: Brute force to find 256-bit key.

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

• 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?

• Obvious: Brute force to find 256-bit key.

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

• Obvious: Brute force to find 256-bit key.

DECIM v1 (submissions/decim/v1): withdrawn

• 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?

• Obvious: Brute force to find 80-bit key.

DECIM-128: 128-bit security?

• Obvious: Brute force to find 128-bit key.

DICING v0: withdrawn

• 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

• Obvious: Brute force to find 256-bit key.

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

• 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?

• 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?

• 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

• 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

• 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?

• 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

• 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?

• Obvious: Brute force to find 256-bit key.

GGHN: broken

• 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

• 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?

• 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?

• Obvious: Brute force to find 128-bit key.

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

• Obvious: Brute force to find 128-bit key.

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

• Obvious: Brute force to find 256-bit key.

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

• 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

• 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

• 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

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

IA: broken

• 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?

• 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?

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

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

• 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

• 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

MAG v2 (submissions/mag/v2): unresolved

MAG v3 (submissions/mag/v3): broken

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

• 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?

• 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?

• Obvious: Brute force to find 80-bit key.

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

• Obvious: Brute force to find 128-bit key.

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

• 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

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

• 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

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

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

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?

• 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?

• 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

• 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?

• Obvious: Brute force to find 128-bit key.

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

• 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?

• Obvious: Brute force to find 128-bit key.

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

• Obvious: Brute force to find 128-bit key.

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

• 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?

• 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?

• 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

• 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

• 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

• 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?

• Obvious: Brute force to find 128-bit key.

Salsa20/5: broken

• 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

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

Salsa20/7: 151-bit security?

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

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

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

Salsa20/9: 256-bit security?

• Obvious: Brute force to find 256-bit key.

Salsa20/10: 256-bit security?

• Obvious: Brute force to find 256-bit key.

Salsa20/11: 256-bit security?

• Obvious: Brute force to find 256-bit key.

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

• 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?

• 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

• 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?

• 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

• 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?

• 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?

• 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?

• Obvious: Brute force to find 256-bit key.

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

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

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

• 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?

• 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

• 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?

• 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

• 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

• 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?

• Obvious: Brute force to find 128-bit key.

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

• Obvious: Brute force to find 128-bit key.