Score:31

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

cn flag

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

President James K. Polk avatar
sh flag
While not an encryption system and thus not in play by your definition, the Sony ECDSA break relied on mathematical weakness in DSA and ECDSA that happens when the secret `k` value is repeated. As a result, Sony's private ECDSA key was recovered and the authentication scheme it protected was rendered completely broken.
kr flag
What have you done so far? Simple googling for *"great crypto failures"* provides many relevant results. I suggest to close the question.
Very Tiny Brain avatar
cn flag
@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.
Very Tiny Brain avatar
cn flag
[This source](https://community.ibm.com/community/user/ibmz-and-linuxone/blogs/todd-arnold1/2020/12/21/real-world-cryptography) claims that this "is not where real-world attacks generally occur." I'm wondering whether real-world attacks *ever* occur here (as far as we know).
fgrieu avatar
ng flag
Would intentionally rigged crypto count? E.g. [crypto AG's machines](https://en.wikipedia.org/wiki/Crypto_AG#Compromised_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).
ru flag
Does the Ultra programme itself count? Enigma was defeated by a "Known-Plaintext" attack just like the 'Purple' cipher used by the Japanese.
Very Tiny Brain avatar
cn flag
@fgrieu I don't know the exact details of the crypto AG compromise, but my understanding is that that was more of a (deliberate) implementation error than a fundamental weakness in the algorithm. E.g. the U.S. machines were very similar and were (at the time) fully secure. I don't think I'll require that the crypto was believed extremely secure at the time, but "bonus points" if so.
Very Tiny Brain avatar
cn flag
@JamesSnell Yes, the Ultra program is the paradigmatic example of what I'm talking about, but I'm wondering about any subsequent examples.
Very Tiny Brain avatar
cn flag
@JamesSnell On second reading, I can't tell whether your comment is nominating a candidate, or casting skepticism on whether Ultra satisfies my criteria. But yes, known-plaintext attacks are very much in scope for my question; I'm not just restricting to ciphertext-only attacks.
V2Blast avatar
pk flag
@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.)
in flag
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.
Very Tiny Brain avatar
cn flag
@AustinHemmelgarn I'm far from an expert, but some quick Wikipedia browsing indicates that Enigma was a bit of a borderline case. Historically, you're right that the Ultra mathematicians took advantages of numerous implementation errors on the Germans' part. The underlying algorithm itself was pretty strong but not perfect, and certainly wouldn't be considered up to snuff by today's standards (even without powerful computers). Expert opinion seems to be that it's very unlikely, but not completely impossible, that the Allies would have been able to break Enigma if the Germans had operated it...
Very Tiny Brain avatar
cn flag
... correctly. But it at least would have been much harder. By contrast, the Japanese Purple cipher seems to have been intrinsically weak and capable of being broken even when operated perfectly, and it was broken by "textbook" cryptanalysis rather than exploiting implementation errors.
ru flag
@VeryTinyBrain - Austen was right, I was checking the Enigma break actually fulfilled your first criteria, since it was predominantly a break in *usage* not "a true cryptographic break".
Stef avatar
ng flag
*"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."* I think that this rule of thumb actually rules out the Bletchley Park breaks...
Pablo H avatar
us flag
I think nowadays _side-channel attacks_ are (or should be) considered normal cryptographic attacks, are just one more of possible attacks cryptographic algorithms should be resistant to.
Very Tiny Brain avatar
cn flag
@PabloH They are certainly "normal" in the sense of being common, but the whole point of my question is to identify the less common "in-channel" attacks. Also, I don't think it really makes sense to design an *algorithm* to be resistant to side-channel attacks, which (more or less by definition) target weaknesses in the low-level implementation details rather than the high-level algorithm itself. It takes a very different skill set to design a secure algorithm from a secure implementation, and so you'd probably want separate experts in charge of each.
Micka avatar
lr flag
https://blog.cryptographyengineering.com/2015/07/20/a-history-of-backdoors/
@VeryTinyBrain djb thinks it is worth designing algorithms to be resistant to side-channel attacks.
Very Tiny Brain avatar
cn flag
@MartinBonnersupportsMonica Who is djb?
@verytinybrain Daniel J Bernstein, author of Salsa20, ChaCha20, Poly1305, Curve25519
Mazura avatar
ch flag
Wouldn't the list of cryptographies that *haven't* been cracked be shorter?
Very Tiny Brain avatar
cn flag
@Mazura Definitely not, if you require that the crack was used in the real world before the weakness was detected and the algorithm retired.
cn flag
Throwing a potential answer into the ring, by means of a leading question ... Was the DoD encryption of high resolution position data in early releases of the GPS system ever broken?
Very Tiny Brain avatar
cn flag
@NickMyra I don't know, was it? I've never heard of this; can you provide any further details?
Very Tiny Brain avatar
cn flag
There are several excellent answers to my question that I think fully meet my requirements, but unfortunately I can only accept one, so I accepted the one that I think most clearly meets them.
Score:52
my flag

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.

cn flag
Max
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)
ru flag
Tim
@Max (and in the days before mobile data was fast and cheap enough to not really need free WiFi)!
cn flag
@Tim Those days aren't over yet. -- A German
Joshua avatar
cn flag
@Max: I saw somebody straight up implement WEP attack at connection time because it was faster than asking for the password.
Score:29
ng flag

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.

kelalaka avatar
in flag
Do you remember [E0](https://en.wikipedia.org/wiki/E0_%28cipher%29) and not wide Keeloq broken by Bard?
fgrieu avatar
ng flag
@kelalaka: no I have not followed E0, but it looks like [it](https://doi.org/10.1007/11535218_7) 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.
kelalaka avatar
in flag
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...
Very Tiny Brain avatar
cn flag
Could you clarify what you mean by "I have no doubt something truly unbreakable would have been rejected"? Rejected by whom?
cn flag
Speaking about GSM, you could also add the break of Comp128-1 (e.g. see [these slides](http://www.tcs.hut.fi/Studies/T-79.514/slides/S5.Brumley-comp128.pdf))
Score:28
jp flag

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.

R.. GitHub STOP HELPING ICE avatar
cn flag
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).
Mark avatar
jp flag
@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.
R.. GitHub STOP HELPING ICE avatar
cn flag
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.
Joshua avatar
cn flag
@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.
Charles avatar
sd flag
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.
Score:20
cn flag

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.

William Martens avatar
gb flag
although I agree about this post, Flame did this, but MD5 is really weak, publicly known, weak. Enigma, was not *really publicly known to be weak* and well, it was as others pointed out, it's a hash not a encryption algo; but it IS a break, I agree - but a more better example would maybe be some kind of RSA or HTTPS (but at this point I don't know of any of these)
kelalaka avatar
in flag
MD5 is a hash function and is sometimes used for MAC, not encryption as OP asked.
Fabio says Reinstate Monica avatar
cn flag
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.
Mark avatar
jp flag
@kelalaka, MD5 in this case was used as part of a cryptographic *system*, as the weak point to permit breaking the entire system.
Very Tiny Brain avatar
cn flag
@kelalaka Great catch, but I'm wondering about general cryptographic protocols, not just encryption. I've edited my question to clarify that.
Score:9
cn flag

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.

Score:2
in flag

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

Very Tiny Brain avatar
cn flag
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.
in flag
@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.
Very Tiny Brain avatar
cn flag
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).
Score:1
ng flag

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

Score:0
in flag

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.

Mark avatar
jp flag
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.
Very Tiny Brain avatar
cn flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.