31
$\begingroup$

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

$\endgroup$
25
  • 6
    $\begingroup$ What have you done so far? Simple googling for "great crypto failures" provides many relevant results. I suggest to close the question. $\endgroup$
    – mentallurg
    Feb 22 at 2:20
  • 6
    $\begingroup$ @mentallurg All the results of that search return examples of failures of cryptocurrencies, which has nothing to do with my question, which is about the cryptographic algorithms themselves. $\endgroup$ Feb 22 at 2:22
  • 4
    $\begingroup$ Would intentionally rigged crypto count? E.g. crypto AG's machines? Also, is it a requirement that the crypto was believed extremely secure by those who designed/selected it, which would severely narrow the choice? No reasonable person would trust that was the case of simple DES, A5/1 or WEP (which stated security goal was fairly low). $\endgroup$
    – fgrieu
    Feb 22 at 7:16
  • 3
    $\begingroup$ @VeryTinyBrain: My reading of James' comment is that it's suggesting that the Ultra example doesn't fulfill criterion #1. (I don't really know enough to judge whether that claim is correct, though.) $\endgroup$
    – V2Blast
    Feb 22 at 15:51
  • 3
    $\begingroup$ I second the assertion that the Ultra programme probably does not meet criterion #1, at least for the enigma machines, as that wasn’t really a break as much as it was a huge series of attacks exploiting procedural issues in German usage of the machines. I don’t know enough about the Japanese type B cipher machine to comment on that side of things. $\endgroup$ Feb 22 at 23:05

8 Answers 8

20
$\begingroup$

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:

  1. 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,

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

$\endgroup$
4
  • 2
    $\begingroup$ MD5 is a hash function and is sometimes used for MAC, not encryption as OP asked. $\endgroup$
    – kelalaka
    Feb 22 at 20:35
  • 11
    $\begingroup$ True, but it made it possible to forge a certificate and use Windows Update to install malware. At that point it was possible to steal files, capture video and audio using the webcam and the microphone, and so on. And it definitely counts as a "cryptographic break". I'd say it's very close to what the OP is asking. $\endgroup$ Feb 22 at 23:27
  • 7
    $\begingroup$ @kelalaka, MD5 in this case was used as part of a cryptographic system, as the weak point to permit breaking the entire system. $\endgroup$
    – Mark
    Feb 23 at 0:08
  • 2
    $\begingroup$ @kelalaka Great catch, but I'm wondering about general cryptographic protocols, not just encryption. I've edited my question to clarify that. $\endgroup$ Feb 23 at 1:55
52
$\begingroup$

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.

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

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

$\endgroup$
4
  • 13
    $\begingroup$ I'm told that for a while after the attack was published you could fairly routinely find WEP-protected wifi networks and it was pretty easy to get free wifi that way (in the days before every cafe and hotel had free wifi) $\endgroup$
    – Max
    Feb 22 at 18:06
  • 2
    $\begingroup$ @Max (and in the days before mobile data was fast and cheap enough to not really need free WiFi)! $\endgroup$
    – Tim
    Feb 22 at 23:57
  • 13
    $\begingroup$ @Tim Those days aren't over yet. -- A German $\endgroup$ Feb 23 at 10:44
  • 7
    $\begingroup$ @Max: I saw somebody straight up implement WEP attack at connection time because it was faster than asking for the password. $\endgroup$
    – Joshua
    Feb 24 at 17:06
29
$\begingroup$

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.

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

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

$\endgroup$
5
  • 1
    $\begingroup$ Do you remember E0 and not wide Keeloq broken by Bard? $\endgroup$
    – kelalaka
    Feb 22 at 11:03
  • 1
    $\begingroup$ @kelalaka: no I have not followed E0, but it looks like it could qualify. I lack a reference for "executed in the real world", as in actively exploited to eavesdrop on BT earphones. I'm not sure Keeloq qualifies, for AFAIK (which is, not much) the attacks are not against the crypto itself. Similarly I have not mentioned Mifare Classic, because the 48-bit key never was intended to be secure anyway, and the (many) actual attacks are not of pure cryptographic nature. $\endgroup$
    – fgrieu
    Feb 22 at 11:13
  • 1
    $\begingroup$ One couldn't find targets for E0 in the wild as easily as WEP. I remember a demonstration, however, I couldn't find it. Keeloq was a block cipher though instead of the attacks the brute force is preferred... $\endgroup$
    – kelalaka
    Feb 22 at 12:51
  • 1
    $\begingroup$ Could you clarify what you mean by "I have no doubt something truly unbreakable would have been rejected"? Rejected by whom? $\endgroup$ Feb 23 at 1:44
  • 2
    $\begingroup$ Speaking about GSM, you could also add the break of Comp128-1 (e.g. see these slides) $\endgroup$
    – j.p.
    Feb 23 at 7:31
28
$\begingroup$

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.

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

  1. The algorithm must have been widely used

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

$\endgroup$
5
  • 1
    $\begingroup$ IMO it's questionable whether this counts since the cryptographic primitive is not playing a cryptographic role at all; it's just acting as DRM (i.e. as a nuisance to a party who possesses both the key and the ciphertext, just in inconvenient places). $\endgroup$ Feb 23 at 23:35
  • 5
    $\begingroup$ @R..GitHubSTOPHELPINGICE, the goal of DeCSS, libdvdcss, and other attacks on CSS is to permit someone who does not have the key to decrypt the data. No open-source DVD player has ever been given a player key by the DVD-CAA. DeCSS did it by reverse-engineering a closed-source player and extracting the key, but libdvdcss used cryptanalytic attacks to reconstruct the disc key from the disc key hash, and then discover a selection of player keys from the reconstructed disc key and encrypted disc keys. $\endgroup$
    – Mark
    Feb 24 at 0:15
  • $\begingroup$ But you do have the key if you have any DVD player. Just because it's not open source doesn't mean you don't have it. Like all DRM, CSS is not cryptographic use of cryptographic primitives; it's use of them as an obfuscating nuisance. The only breakthrough of libdvdcss was doing it in a way that didn't involve distributing the (known) keys, for the sake of being legally clean. $\endgroup$ Feb 24 at 15:50
  • $\begingroup$ @R..GitHubSTOPHELPINGICE: They should have done what they finally started doing for BluRay. Rip the key from the firmware of some popular set-top player that can't be reflashed. $\endgroup$
    – Joshua
    Feb 24 at 17:09
  • $\begingroup$ DVD encryption is broken through cryptographic analysis. You can do the key extraction because the underlying encrypted data has well known zero padding that allows you to know plain text data in parts of the data stream. You can brute force the key using those data blocks. I wrote an implementation in Java once as an exercise, and it could still decode the whole disk in seconds. Later implementations took advantage of known keys to accelerate decoding. $\endgroup$
    – Charles
    Mar 9 at 15:01
9
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ While I'm not an expert, my understanding is that the AG Crypto situation weakness wasn't an algorithmic weakness, but instead a (deliberate) implementation error, where certain machines were deliberated seeded with weak keys while other machines were seeded with strong keys and were still secure. So I don't think this example meets requirement #1. $\endgroup$ Feb 25 at 0:06
  • $\begingroup$ @VeryTinyBrain That's possible, I'm no expert either. I just thought it was worth pointing out that the type of encryption that was cracked during WW2 wasn't immediately abandoned (by everyone) after the war. Your question mentions "since WWII", which could be seen to suggest a radical break in encryption practices around 1945. $\endgroup$
    – New User
    Feb 25 at 6:09
  • $\begingroup$ Oh no, I didn't mean to imply than any encryption practices changed after WWII. It's just that the WWII Ultra program happened to be the most recent example that I could think of (although it now appears that this example doesn't really count). $\endgroup$ Feb 25 at 22:25
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ The attacks on DES aren't "cryptographic breaks" in the sense of the question. Yes, there are theoretical attacks on DES that are (slightly) faster than brute force, but the difficulty of obtaining the prerequisites for them and the ease of brute force means that everyone just brute-forces the key instead. $\endgroup$
    – Mark
    Feb 23 at 0:11
  • 3
    $\begingroup$ I agree with @Mark, and it looks like KeeLoq is generally broken by brute-force attacks as well. I've edited the question to clarify that brute-force attacks are out of scope. Also, was there ever clearly documented evidence of DES broken in the wild, outside of contests where the "victim" wanted to have their message broken? I would say that that's out of scope as well. $\endgroup$ Feb 23 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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