Chasing Cyber - #32 - Crypto Mistakes

Chinese whispers, stolen Bitcoin, and leaky clouds.

Chinese Whispers

Have the Chinese broken “military-grade encryption” using quantum computers, as claimed in the media?

Of course not. But let’s use this as an example of distinguishing fact from fiction in the world of cryptanalysis.

In this case, Chinese scientists claim to have worked with a quantum annealing company to demonstrate attacks against substitution–permutation network (SPN) structures.

The AES algorithm relies on SPN structures to operate. Remember those “S-boxes” you’ve seen in diagrams about AES? That’s what we are talking about.

However, breaking one SPN-based algorithm doesn’t bring you closer to another. In this case, it seems like the Chinese have broken some toy algorithms that happen to use SPN structures. And the media have translated this into “AES broken, world ends”.

But we don’t need to pick apart the details to realise these media claims are nonsense. We just need to apply a modicum of common sense. If you were the Chinese military and you had just broken AES, what would you do?

I suspect speaking to the South China Morning Post would be quite far down your priority list. Instead, you would maximise your informational advantage, without revealing you’ve broken a critical global cipher.

Any major cryptographic break, whether from academics or government spooks, would follow the same pattern. Either you wouldn’t hear about it, or someone would post definitive evidence. It would likely be the former since the spooks are quite good at suppressing these things.

Shame on the journalists for allowing their headline writers to get away with murder.

---

The Vanishing Bitcoin Trick

Imagine inventing a new attack against Bitcoin, only to discover the criminals beat you to it. Here’s the story of how $10 million vanished without a trace…

First, some background. Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) for transaction security. It’s difficult to write a good ECDSA implementation because small mistakes can reveal your private key.

ECDSA relies on nonces, which are random numbers used only once during a cryptographic operation. Small weaknesses in your ECDSA nonces can be exploited to reverse-engineer your private key.

In 2023, researchers discovered a new flaw in ECDSA nonce generation related to weak random number generators. With this attack, dubbed Polynonce, tiny correlations between the random numbers in the nonces and the private key were exploited to break the private key.

Curious about the impact of this attack, the researchers downloaded the entire Bitcoin transaction history. They discovered over 700 wallets that exhibited evidence of this weakness. But here’s the catch – someone beat them to it.

The wallets were all empty.

Digging further into the transactions, they concluded at least $10 million was stolen because of this Polynonce weakness. These thefts were unreported until that point, which makes me wonder how many other undiscovered attacks there are on weak randomness or other ECDSA vulnerabilities.

I recommend reading this blog for more details on the research behind Polynonce: https://research.kudelskisecurity.com/2023/03/06/polynonce-a-tale-of-a-novel-ecdsa-attack-and-bitcoin-tears/.

Thanks to Kevin Milner for drawing this to my attention.

---

End-to-End Security (Ish)

A recent paper exposed vulnerabilities in four major providers of end-to-end (E2E) encryption for public clouds.

The providers involved are not household names, yet they are leaders in the E2E encryption space. Their websites claim they are trusted by organizations such as the German and Canadian governments, Amnesty International, SAP, and many others.

The goal of these E2E solutions is to protect confidential data from malicious or compromised cloud providers. Users should have full control of the data, as well as the encryption keys that protect it.

The paper tells a different story. The researchers found basic cryptographic errors in 4 out of 5 providers, including lack of authentication, protocol downgrade attacks, and link-sharing exploits.

Quoting from the paper:

“Not all of our attacks are sophisticated in nature, which means that they are within reach of attackers who are not necessarily skilled in cryptography. Indeed, our attacks are highly practical and can be carried out without significant resources. Additionally, while some of these attacks are not novel from a cryptographic perspective, they emphasise that E2EE cloud storage as deployed in practice fails at a trivial level and often does not require more profound cryptanalysis to break.”

Read the full details here (PDF): https://eprint.iacr.org/2024/1616.pdf.

Given the trivial nature of these attacks, I doubt any penetration testing was performed on these systems. I suggest this serves as a warning for anyone buying sophisticated encryption systems: do your homework. Probe the providers to understand who has assessed their systems. Ask for previous penetration testing reports and be deeply suspicious of any perfect “nothing found” scores.