28
votes
$\begingroup$

RC4 and GOST are two major ciphers (defined as being widely used to encrypt large amounts of data) that fell to cryptanalysis (relatively) suddenly. The first becoming totally broken and the second fell from $2^{256}$ bit security to $2^{99.5}$ bit security, weaker than AES-128.

Have any other modern and widely used ciphers fallen without much advance warning?

"Fallen" in this context means "become practically attackable, or close enough that use is strongly discouraged". And to limit the scope of my question, let’s please exclude antique ciphers that predate our modern understanding of cryptography.

Essentially, I am looking for one or more prominent cases where a modern cipher seemed secure and was in wide use for a substantial period of time, until suddenly it was broken (while still in wide use) and had to be abandoned due to that sudden break. One possible example of what I’m looking for would be RC4 as used in TLS, and the recent discoveries that “broke” it.

(PS: References to the cipher paper + the paper introducing the break would be a plus.)

$\endgroup$
5
  • 3
    $\begingroup$ Was RC4 already a major cipher when it fell to cryptoanalysis in 1995, merely a year after being published? $\endgroup$ May 2, 2016 at 8:17
  • 6
    $\begingroup$ Should we indicate in the question that we are talking modern ciphers that operate on bits rather than text? That way we can exclude the ciphers before the computer age for this already broad question. $\endgroup$
    – Maarten Bodewes
    May 2, 2016 at 10:17
  • 2
    $\begingroup$ I’ve put the Q on hold as it has several problems. Most obvious one is that it’s a “list-question” which (in most cases) doesn’t work well at SE. But more important, it’s overly broad for 2 reasons: you don’t limit the scope of ciphers (“major ciphers” can range from antique ciphers up to the latest inventions) & you don’t define “fallen” (which could be “any kind of break”). If you keep those reasons for being too broad in mind, you’ll notice why a list-type question only adds to the problem as good answers would be endless! If you can somehow resolve those issues, I’ll gladly reopen… $\endgroup$
    – e-sushi
    May 2, 2016 at 19:22
  • 1
    $\begingroup$ @e-sushi I fixed the two latter issues I believe. $\endgroup$
    – Demi
    May 2, 2016 at 23:09
  • 1
    $\begingroup$ @Demetri Much better… thanks for those edits. Still a tick broad, but it should work (read: should be acceptable now due to the more limited scope). I was so free to fine-tune things a bit. In case you don’t like my edits for whatever reason, please don’t hesitate… feel free to roll back if you think it makes sense. Nevertheless, I'll lock this Q&A for “historical significance” after a week or two since it is not really considered a good, on-topic question for this site (more specific: list-type Qs are rather unwelcome at SE). $\endgroup$
    – e-sushi
    May 2, 2016 at 23:50

1 Answer 1

33
votes
$\begingroup$

This question is quite broad by specifying a sudden fall to cryptanalysis and therefore my answer might not be as complete as you wish it to be.

If by "become practically attackable, or close enough that use is strongly discouraged" you imply not an academic breach but assume a weaker attacker such as a single ciphertext attack, then there are quite a few ciphers that satisfies this condition. Under this assumption, modern block-ciphers are mainly vulnerable to brute force attack. Should the key length of DES be longer so we would not be able to do an exhaustive search then it would still retain a certain level of security (while its use still be strongly discouraged).

Moving to strongly used block ciphers, here are a few that have been academically broken or weakened to be considered as insecure.


FEAL (Block Cipher)

The first block-cipher that came to my mind with such characteristic is FEAL. It was design in 1987 and aimed to replace the DES by providing fast encryption capacities for 8-bit platforms. It was not widely used and (un)fortunately it was broken even before becoming a new standard in 1990.

Should you teach or would like to practice cryptanalysis, I would recommend breaking FEAL-4 (as 4 rounds) or FEAL-8. It is a great learning exercise.

Some resources :


DES (Block Cipher)

DES is another example. Broken by differential cryptanalysis in 1990 by Eli Biham and Adi Shamir.

In this paper we develop a new type of cryptanalytic attack which can break the reduced variant of DES with 8 rounds in a few minutes on a PC and can break any reduced variant of DES (with up to 15 rounds) in less than $2^{56}$ operations.

from their paper : Differential Cryptanalysis of DES-like Cryptosystems. I really recommend reading this article or at least the extended abstract.

Remark: To break the 16 rounds, one would need $2^{57}$ pairs. The number of cipher texts needed is twice the number of pairs. On these pairs, only $2^5$ would be used (excluding the wrong pairs that can be easily discarded during the collection phase). Using 15 different characteristics with a probability of $2^{-56}$, 18 bits of the key could be found. Therefore this attack involves slightly more work than a brute-force attack. (Thx Jerry for pointing this out).

3 years later, Mitsuru Matsui introduced a new method to break DES.

As a result it is possible to break a 8-round DES cipher with $2^{21}$ known-plaintexts and 16-round DES cipher with $2^{47}$ known-plaintexts, respectively. Moreover this method is applicable to an only-ciphertext attack in certain situations

from his paper: Linear Cryptanalysis Method for DES Cipher (another good reading).


A5/1 (Stream cipher)

Moving to stream cipher we have A5/1 which is responsible of the privacy of the communication between GSM and the antenna. Developed in 1987, with a key length of $64$ bits. In 1997, Golic presented an attack based on solving sets of linear equations which has a time complexity of $2^{40.16}$. In 2000 Eli Biham and Orr Dunkelman published an attack with a total work complexity of $2^{39.91}$ A5/1 clockings given $2^{20.8}$ bits of known plaintext. The attack requires 32 GB of data storage after a precomputation stage of $2^{38}$.
Remark: while A5/1 is completely broken (cf Snowden leaked files) it is still in use in our cell phones...

Some resources:


RC4 (Stream cipher)

RC4 (as Rivest Cipher 4) is a stream cipher mainly used in SSL (1995), TLS (1999), WEP (1997) and WPA (2003/2004). It was designed in 1987 but the code was unknown until being leaked in September 1994 (security by obscurity, here I am...)

Some resources:


MD5 (hash function)

Infamous hash function, designed in 1991. Five years later, Dobbertin announced a collision of the compression function of MD5. In 2009, the complexity of the attack was in $2^{39}$ (initial pre-image complexity is $2^{128}$.


SHA-0 (hash function)

Published in 1993, revised a few years later due to a significant flaw as SHA-1. At CRYPTO 98, a first collision was found in $2^{61}$ (initial complexity in $2^{80}$. In February 2005, an attack by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu was announced which could find collisions in SHA-0 in $2^{39}$ operations. Another attack in 2008 applying the boomerang attack brought the complexity of finding collisions down to $2^{33.6}$.


SHA-1 (hash function)

Published in 1995 as a revision of SHA-0 (see above), it has been first weakened with attacks of complexities:

I'm probably missing a lot of other block ciphers, but these are the ones mainly known to my knowledge.

$\endgroup$
13
  • 5
    $\begingroup$ A5/1 was allegedly designed to be insecure and only broken worse. (CMEA was similar, but was perhaps meant to be secure.) MD5 and SHA-0 are not ciphers, so sort of beside the point. $\endgroup$
    – otus
    May 2, 2016 at 7:04
  • 3
    $\begingroup$ I didn't know that bout A5/1. Obviously I know that MD5 and SHA-0 are not cipher ;) but I though it would be interesting to mention them here given it was more focused on the history and they illustrate relatively well the dip. $\endgroup$
    – Biv
    May 2, 2016 at 7:10
  • 7
    $\begingroup$ It's also worth noting that the differential cryptanalysis attack on DES isn't really effective (i.e., it involves slightly more work than a brute-force attack). $\endgroup$ May 2, 2016 at 13:03
  • 1
    $\begingroup$ A5/1 is further weakened in practice with a man-in-the-middle attack using IMSI-catcher devices such as a Stingray. $\endgroup$ May 2, 2016 at 17:00
  • 1
    $\begingroup$ Edited to reflect the fact that it aimed to become a new standard but was not widely used... $\endgroup$
    – Biv
    May 4, 2016 at 12:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.