Have any cryptographic breaks been executed in the real world since World War II?

Question

Have there been any publicly known exploits of a cryptographic break in a widely used cryptographic system to actually read encrypted information (or falsely authenticate) since the Ultra program in World War II?

I want to define my terms as precisely as possible to clarify what I mean. An example of what I'm looking for needs to satisfy three requirements:

1. It needs to be a true cryptographic break, stemming from mathematical cryptanalysis, as opposed to a side-channel attack, insider attack, implementation error, faulty random number generator, brute-force attack, etc. In other words, it must exploit a fundamental weakness of the underlying mathematical algorithm that was not known at the time. I know that the line between an "implementation error" and a "fundamental weakness" is somewhat subjective, but a good rule of thumb is that if the latter is publicly revealed, then the basic cipher can't easily be fixed up and must be abandoned. (Another rule of thumb is that a contemporary cryptography expert would have needed to think quite hard in order to understand how the exploit worked; it would not have been trivial to explain the exploit to them.)

2. The break must have actually been executed in the real world to actually read encrypted information "in the wild" or falsely authenticate without the sender's knowledge/permission. A demonstration that a break would be plausible to execute in practice doesn't count.

3. The algorithm must have been widely used, e.g. in an Internet, commercial, or governmental setting. Again, what counts as "widely" is a bit subjective, but it doesn't count if Alice invents her own cryptography algorithm for fun, uses it to send an encrypted message to Bob, and then their friend Charlie breaks it. A good rule of thumb for what counts as "widely" is that this cryptography algorithm was used by people who had no direct connection to the algorithm's creator.

(Now, I acknowledge that by the very nature of cryptography, anyone who has developed such a break would have a strong incentive not to publicize that fact, so any such breaks may not be public knowledge. But I'm curious if any of them have been publicly revealed.)

Answer 1

I'm no cryptographer, but I think the Flame malware matches your description. It's an extremely sophisticated tool for cyber espionage discovered in 2012. Experts believe it was developed by the US and Israeli military, and it was used mainly against Iranian targets.

1. It needs to be a true cryptographic break, stemming from mathematical cryptanalysis

Ars Technica interviewed two experts who had published a paper on a similar attack, and they stated several times that it exploited a new technique:

"Flame uses a yet unknown MD5 chosen-prefix collision attack"
"Flame is the first known example of an MD5 collision attack being used maliciously in a real-world environment."
"the collision attack performed by Flame has substantial scientific novelty"
"the results have shown that not our published chosen-prefix collision attack was used, but an entirely new and unknown variant"
"Flame also required world-class cryptographers who have broken new ground in their field"
"There were mathematicians doing new science to make Flame work."

Your second requirement is also satisfied:

2. The break must have actually been executed in the real world

It was: according to Wikipedia,

initially Flame had infected approximately 1,000 machines, with victims including governmental organizations, educational institutions and private individuals.

And finally,

3. The algorithm must have been widely used

MD5 is still widely used today, ten years later, and it was even more back then. Sure, it's considered weak and broken, and everybody knew it even in 2012, but this didn't stop people from using it.

Answer 2

One example that immediately comes to mind is the attack on WEP, which is based on an unknown (to the designers at the time) related key attack on RC4 that lead to a key recovery.

1. It needs to be a true cryptographic break, stemming from mathematical cryptanalysis

Check; the attack exploits the design of the RC4 key setup algorithm.

2. The break must have actually been executed in the real world

Check; the attack was, in fact, used in the field to recover credit card numbers; actually, several years after the attack was published (as the operator didn't bother to upgrade his wireless network).

3. The algorithm must have been widely used, e.g. in an Internet, commercial, or governmental setting.

Check; WEP was, at the time, fairly widely used.

Answer 3

An example is GSM voice encryption using A5/1, used in Europe and USA on the voice channel of the radio link of cellphones before 3G. While with a good algorithm the 80-bit key size of A5/1 would be a serious obstacle to decryption even nowadays, real-time cryptanalysis is possible and usable to decode passive radio intercepts.

1. It needs to be a true cryptographic break, stemming from mathematical cryptanalysis

This is the case of Alexander Maximov, Thomas Johansson, Steve Babbage's An Improved Correlation Attack on A5/1, in proceedings of SAC 2004, improving on an earlier attack.

2. The break must have actually been executed in the real world

It's widely held that's the case, in complement of active attacks (which involve more elementary cryptanalysis, and can reveal more information than voice). I reason that must be the case because of two operational advantages of passive intercepts: they can't be detected, and can allow massive eavesdropping (which on the other hand might be easier at other points of the network).

3. The algorithm must have been widely used, e.g. in an Internet, commercial, or governmental setting.

A5/1 was widely used in Europe and USA for GSM voice service, before it was (as far as I know) superseded by 3G.

---

Note: the question does not ask that the algorithm was selected as believed secure, within intrinsic limitations of it's key and state size, by all parties involved in the decision to select it. I have no informed opinion about if that was the case for A5/1, and would love information about that. I have no doubt something truly unbreakable would have been rejected¹, but I wonder if a cryptanalysis of passive intercepts better than that obviously possible given the 80-bit key+state was known at time of the choice and influenced it.

¹ In the 1970-2000 (roughly) period, there were laws and regulations in force in many countries targeted by GSM that prohibited effective cryptography for devices offered for sale to the general public², and they where still enforced to a degree. Therefore I strongly believe that standard-makers were attentive to not propose a standard that administrations would consider too strong, for fear that ratification of standard or deployment would be slowed. I see that as the reason A5/1 has a 80-bit state and maximum key size.

² E.g. in France, in order to alow interception by authorities, more than 40-bit crypto was in principle prohibited by law, with AFAIK official exemptions only for backdoored crypto or very closed applications, at the discretion of authorities. The limit was to be chosen by the government, had not been changed in years, and in 1999 abruptly went from 40 to 128-bit, effectively changing totally the meaning of the law.

Answer 4

The DVD Content Scramble System.

1. It needs to be a true cryptographic break, stemming from mathematical cryptanalysis

Although the cipher is intrinsically weak, at only 40 bits, brute-forcing still required around 24 hours to exhaust the keyspace back when the system was first cracked. Cryptanalytic attacks reduced that to 25 effective bits, permitting disc keys to be recovered in a matter of seconds.

2. The break must have actually been executed in the real world

Yes. Very. These days, the main implementation of the break is that libdvdcss has code for a 2^25-complexity preimage attack on the hash of the disc key in case none of its 32 player keys (also the result of a cryptanalytic attack) works with a given DVD.

3. The algorithm must have been widely used

Every commercially-produced DVD did (and still does) include content encrypted with CSS.

Answer 5

The Dual EC DRBG Juniper Networks hack should qualify.

1. It needs to be a true cryptographic break, stemming from mathematical cryptanalysis

In 1997 Adam L. Young and Moti Yung presented a paper at Eurocrypt detailing a "kleptographic" covert key generator that introduced a mathematical backdoor into Diffie Hellman key exchanges.

The Dual EC DRBG generator was proposed a few years later, with construction almost identical to the Diffie Hellman backdoor.

2. The break must have actually been executed in the real world

In the early 2000s the Dual EC DRBG standard was heavily promoted by the NSA, and was included in cryptographic standards ANSI X9.82 and ISO/IEC 18031:2005. RSA adopted it in their BSAFE library as their default random number generator.

Despite the protests of mathematicians who had analyzed the algorithm and identified some flaws in it, it was eventually published in NIST SP 800-90A in 2006 -- flaws still present.

In 2007 Dan Shumow and Niels Ferguson demonstrated an implementation of the Dual EC DRBG algorithm containing a backdoor they'd constructed by using their own Dual EC constant. http://rump2007.cr.yp.to/15-shumow.pdf

In 2008 Juniper Networks implemented Dual EC DRBG as the PRNG used by their ScreenOS operating system, used in their enterprise class NetScreen Firewall systems.

In 2012, NIST updated SP 800-90A, and the Dual EC DRBG was still recommended.

In 2013 Reuters published information from Snowden's leak asserting that NSA had paid RSA $10 million dollars to implement Dual EC DRBG as their default PRNG.

In 2015, NIST withdrew SP 800-90A, superseding it with SP 800-90A Rev. 1, which finally removed Dual_EC_DRBG as a recommended PRNG.

In 2016 Juniper Networks removed Dual EC DRBG from ScreenOS. At that time they revealed that unknown hackers had infiltrated their systems as far back as at least 2012, and had modified the source code to ScreenOS replacing the NIST-specified Dual EC constant with a constant of unknown origin.

3. The algorithm must have been widely used

RSA adopted it in their BSAFE library as the default random number generator; it was included in ANSI X9.82, ISO/IEC 18031:2005, and NIST SP 800-90A. At one time it was estimated that one-third of all SSL traffic was using keys generated by the Dual EC DRBG [citation needed].

The alleged deal with the NSA ended up delivering a fatal impact to RSA's business. In 2017-2018 RSA abruptly announced the termination of their popular RSA Key Manager and Data Protection Manager product, which had approximately 70% of the market share for cryptographic key servers. Key servers are used by web service providers, banks, financial institutions, and other large companies to protect everything from web server keys, to bank transfers, to the keys used to encrypt credit card PINs. Support for the line was completely dropped, no replacement product was ever released, and no explanation was given. RSA went from a world leader to essentially dead as a cryptography company.

EDIT:

It is still unproven that the NSA actually decrypted any traffic using the Dual EC DRBG constant that they provided. But if they didn't, they expended a great deal of influence and money on a project that would have provided no other benefit to them or to anyone else.

It is also unlikely that an unknown attacker with access to the Juniper source code would have chosen to replace only that particular constant in their Dual EC DRBG generator without similarly taking advantage of the demonstrated eavesdropping capability it offered. (However, there is also the possibility that someone at Juniper altered the constant themselves in order to thwart any potential compromise in the standard constant, and "unknown hackers" were blamed rather than the NSA.)

Answer 6

It's worth noting that the type of encryption machine that the war-time Enigma was based on, was used for several decades after the war, and that the fact that this sort of encryption had been broken by the Polish/British was not widely known.

This led the American and West-German intelligence services to take over a Swiss builder of encryption machines, sell these compromised machines to companies and governments worldwide, and be able to easily spy on them.

Intelligence gathered by intercepting messages encrypted by these machines was used as late as the Iranian Hostage Crisis (1979) and the Falklands War (1982), at which time countries like Iran and Argentina were still using them.

More info in this BBC article: https://www.bbc.com/news/world-europe-51467536

Answer 7

The High-bandwidth Digital Content Protection (HDCP) standard was broken. This system was widely deployed, although this story arguably has more "staying power" not for the novel cryptanalysis (although there was some), but because it was an early example of the US's DMCA law curtailing the dissemination of cryptographic research for fear of lawsuit. See Niels Ferguson's post on the matter. For a summary of the cryptanalysis, see the first link.

Note that there are similar stories (of DMCA being used to suppress research) which may provide other answers for this, as it (in general) happens when some industry group has a financial stake in stopping cryptanalysis, almost always to prevent "real-world attacks". These attacks may be due to implementation issues or side-channel attacks though, although are not always (such as early versions of HDCP).

Answer 8

Keeloq, which is used for garages, gates, and cars. Maybe other things?

Anything using DES. Take a look at https://crack.sh to see different protocols that used DES e.g. vpn pptp, wpa2 enterprise with Mschapv2. Netntlmv1, et. al.