I am researching how quantum computers affect current encryption methods (RSA and more).

However, I remember learning in a course that there used to be a particular encryption method which was popular but suddenly had a very bad vulnerability in the past (like quantum computers and Shor's algorithm would be for RSA) and everybody had to move on (is that right?).

I cannot find anything about this in the past, does anybody have any idea which cryptosystem I am talking about?

  • Might be braid group cryptosystems? – pg1989 Jun 5 '16 at 1:58
  • pg1989. I hope to change that using some generalizations of braid groups (unless these cryptosystems based on these new groups will be shown to be insecure). – 35093731895230467514051 Jun 5 '16 at 4:20
  • Enigma? Also related: en.wikipedia.org/wiki/Category:Broken_cryptography_algorithms – Noir Jun 6 '16 at 8:06
  • If you require suddenly then you probably should include it in the title and the final sentence. We now have answers with algorithms that are broken in time (DES, MD5, RC4). – Maarten Bodewes Jun 7 '16 at 9:16
up vote 33 down vote accepted

You could be thinking about the Merkle-Hellman knapsack cryptosystem. It was invented in 1978 and everything seemed well and good until it was completely broken six years later in 1984 by Shamir - it was a complete and total break, i.e. the cryptosystem became unusable overnight.

That said I don't know if the knapsack cryptosystem was ever "popular" in the modern sense (it was 1978 after all) but it was certainly an early public key cryptosystem that met an unfortunate end.


On the other hand, for an example of a progressively worn-down algorithm (as opposed to one being broken immediately) there is of course MD5's collision resistance.

  • 3
    I'm not sure if that was the one, but this is what I needed! Thanks! Just want to point out that some sources cite that the cryptosystem broke in 1982 for future readers (at Crypto '82). However, some other sources refer to 1984. I think 1984 is the paper's publishing date and 1982 is the date of breaking the system. – Kevin Van Ryckegem Jun 5 '16 at 0:49

This is a shot in the dark, but could you be thinking of the Needham-Schroeder protocol? It was published in 1978 [1], and an attack was published as much as 18 years later, in 1996 [2]. It is not an encryption method, though, but a protocol. In fact, the original paper does not even specify an encryption method to be used, but uses encryption symbolically. Accordingly, the discovered flaw has nothing to do with encryption; rather, it is a conceptual flaw in the protocol's design. However, it is often used in cryptography/security courses as a historical example of a protocol broken late after its invention, so I thought you might have been thinking of this one.

Another popular example that comes to mind is WEP, a link-layer security protocol which was part of the original IEEE 802.11 specification from 1997 and the predecessor of WPA/WPA2. This one was broken due to cryptographic breaches resulting from various weaknesses in its design and misapplications of cryptographic primitives [3,4].

  • [1] Roger M. Needham, Michael D. Schroeder. Using Encryption for Authentication in Large Networks of Computers. Commun. ACM 21(12): 993-999 (1978)
  • [2] Gavin Lowe. Breaking and Fixing the Needham-Schroeder Public-Key Protocol Using FDR. TACAS 1996: 147-166
  • [3] Nikita Borisov, Ian Goldberg, David Wagner. Intercepting mobile communications: the insecurity of 802.11. MOBICOM 2001: 180-189
  • [4] Scott R. Fluhrer, Itsik Mantin, Adi Shamir. Weaknesses in the Key Scheduling Algorithm of RC4. Selected Areas in Cryptography 2001: 1-24

DES has not been mentioned in the previous two answers. Although it was known to be quite weak from very early on it was widely used for a couple of decades at least, until newer algorithms (3DES, AES, but also e.g. RC4) displaced it. Nowadays it can be broken in hours with dedicated hardware or with at most a few thousand dollars of cloud computing time.

Speaking of RC4, it is another broken cipher, especially in protocols like WEP (mentioned in the other answer) where a small key was used, but its use has now also been phased out of TLS, where it was still seen as the least-worst option just a few years ago.

Related question: Examples of modern, widely used ciphers that suddenly fell?

  • 5
    The weakness of DES is its key length, though. Yes, there are analytic attacks, but they require enough plaintexts to be impractical in most circumstances. The practical attack is that computers simply got fast enough to try the entire keyspace in a reasonable amount of time. – Mark Jun 6 '16 at 8:23
  • @Mark, true, RC4 is a better fit to what the question is asking. – otus Jun 6 '16 at 8:35

In 2006-07, NIST published a new standard for cryptographically secure random number generation. One of their suggestions was based on elliptic curves, DUAL_EC_DRBG.

in 2006, Daniel Brown and Kristian Gjosteen discovered that this algorithm had a subtle bias for certain numbers. Later, in 2007, Dan Shumow and Niels Ferguson said they had found what caused this bias: an intentional backdoor that would allow people who know the right set of numbers to predict the numbers it generated and thus break any encryption scheme using random numbers generated by DUAL_EC_DRBG.

The reason why this was considered an intentional backdoor instead of an accidental flaw was because the NSA at the time was pushing extremely hard to include this flawed method in the NIST publication, even though it was much slower than the other methods in the publication.

Sources:

WEP for securing wireless networks:

Wired Equivalent Privacy (WEP) is a security algorithm for IEEE 802.11 wireless networks. Introduced as part of the original 802.11 standard ratified in 1997, its intention was to provide data confidentiality comparable to that of a traditional wired network. WEP, recognizable by the key of 10 or 26 hexadecimal digits, was at one time widely in use and was often the first security choice presented to users by router configuration tools.

...

In 2007, Erik Tews, Andrei Pychkine, and Ralf-Philipp Weinmann were able to extend Klein's 2005 attack and optimize it for usage against WEP. With the new attack it is possible to recover a 104-bit WEP key with probability 50% using only 40,000 captured packets. For 60,000 available data packets, the success probability is about 80% and for 85,000 data packets about 95%. Using active techniques like deauth and ARP re-injection, 40,000 packets can be captured in less than one minute under good conditions. The actual computation takes about 3 seconds and 3 MB of main memory on a Pentium-M 1.7 GHz and can additionally be optimized for devices with slower CPUs. The same attack can be used for 40-bit keys with an even higher success probability.

source: https://en.wikipedia.org/wiki/Wired_Equivalent_Privacy

  • 1
    This is a good example of a protocol that was broken (due to using a weak(er) encryption method and pretty bad protocol design. It's an interesting example, but I'm not sure if it counts as a "method of encryption" in itself. – Maarten Bodewes Jun 7 '16 at 9:13

all the cryptography methods except one time pads from the BC (before computer) era were effectively made obsolete by computers. The amazing WW2 work against enigma were a bridge between the old and the new eras.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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