The Cunning Way Hackers Break So-Called Unbreakable Encryption

Modern encryption systems rely on oxymoronic “random generators.” This could be the crack in a supposedly unbreakable system.

As discussed in a recent Monday Note titled “Let’s Outlaw Math,” electronic messages that are encoded with modern encryption techniques are truly indecipherable by interlopers—it doesn’t matter whether they’re criminals or governments. The latter have attempted to legislate backdoors that only they can use (to protect us, of course), but there’s a danger: These “golden keys” could fall into the wrong hands. In any case, a backdoor only works where it’s been installed; unbreakable public domain encryption is available to everyone, terrorists and traffickers included.

So… case closed, good guys and bad guys alike can “safely” use unbreakable codes?

Not so fast.

A fundamental feature of a properly encoded cryptogram is that it looks random: a sequence of (say) letters without any detectable pattern or meaning.

Consider the schoolyard encryption method known as the Caesar cipher where each letter in the original message is shifted: A becomes C, B becomes D, C is E, and so on. Cleopatra thus becomes Engqrcvtc. The “shift key” is easily discovered by looking for frequently occurring patterns in the encrypted message and matching them to common words in the language of the original text.

If you’re a cryptographer, patterns are your enemy. But if you’re a cryptanalyst—someone who’s trying to break the code—they’re your friend.

We all know the story of the German Enigma machine whose sophisticated code might have remained unbroken were it not for humans who let down their guard and allowed regularities to seep into the coding process. As explained in “Cryptanalysis of the Enigma” [edits and emphasis mine]:

In practice the system’s greatest weakness was the way that it was used. […]Repeatedly using the same stereotypical expressions in messages, […] the greater number of messages began with the letters ANX—German for “to”, followed by X as a spacer.

Without these operating shortcomings, Enigma would, almost certainly, not have been broken.

(Alan Turing, the great and tragic mathematician, played an important role in breaking the Enigma codes. He’s also known for the Turing machine, a significant contribution to computer science, and the Turing test in the field of Artificial Intelligence.)

Another example of the importance of randomness and, conversely, the value of detecting its breakdown, is the practice of card counting in blackjack as a way to “beat the house.” As cards are put into play, the odds that a specific card will appear on the next draw are reduced. Players with agile minds can keep track of the cards as the game progresses and adjust their bets accordingly. Reduce the randomness and better your odds.

(Bringing Down the House by Ben Mezrich, tells the story of six MIT students who used card counting as a way to win millions in Vegas casinos. Unsurprisingly, casinos have severely curtailed the practice by using larger decks and only allowing counting in the player’s head, no devices, no communication with helpers. The book was made into the movie 21.)

Randomness is crucial to modern cryptographic systems. To avoid regularities in the encrypted messages that it produces, the system’s cryptographic components—keys, IDs, tokens—are generated randomly. But a “random generator” is oxymoronic; it’s an algorithm, and algorithms are never completely random. That’s where the potential fault in “unbreakable” cryptography lies.

Picture a group that’s dedicated to the advancement of its constituents’ interests or, put more realistically, to the downfall of their client’s opponents. Unbreakable encryption is an obstacle to their mission—they know they can’t break the code, they can’t unlock the encrypted messages that they’ve intercepted, there’s no golden key to steal. What do they do? They find or create a crack in the opponent’s security. This is accomplished by the usual methods: compromising people by greed or by the threat of revealing shameful secrets, spontaneous or provoked. Next, pull the puppet’s strings to surreptitiously and subtly corrupt the other party’s random generator.

In “Why secure systems require random numbers,” John Graham-Cumming tells the story of how a (benevolent) hacker unlocked the random generator used by Hacker News:

The random number generator was seeded with the time in milliseconds when the Hacker News software was last started. By some careful work, the attacker managed to make Hacker News crash and could then predict when it restarted within a window of about one minute. From it he was able to predict the unique IDs assigned to users as they logged in and could, therefore, impersonate them.

The Hacker News hack was a controlled experiment, and the fault was quickly fixed. More alarming are attempts, by the government, to purposefully subvert random number generation. In 2013, the NSA spent $10 million to get a cryptography company, RSA, to use the NSA’s number generator:

…several [RSA employees] said that RSA also was misled by government officials, who portrayed the formula as a secure technological advance. “They did not show their true hand,” one person briefed on the deal said of the NSA, asserting that government officials did not let on that they knew how to break the encryption.

More recently, two backdoors that allowed “someone” to read supposedly encrypted VPN traffic were discovered in Juniper Networks firewalls [emphasis mine]:

[T]he attackers behind the Juniper backdoor altered Juniper’s source code to change a so-called constant or point that the Dual_EC algorithm uses to randomly generate a key for encrypting data. It’s assumed the attackers also possess a second secret key that only they know. This secret key, combined with the point they changed in Juniper’s software, the inherent weaknesses in Dual_EC, and the configuration error Juniper made, would allow them to decrypt Juniper’s VPN traffic.

and

Random number generators play a crucial role in creating cryptographic keys. But Shumow and Ferguson found that problems with the Dual_EC made it possible to predict what the random number generator would generate, making the encryption produced with it susceptible to cracking.

Unbreakable encryption broken.

Two unpleasant thoughts come to mind.

First, the cockroach theory: When we see one crawling from under the sink, how many more are there lurking in the dark? How many supposedly unbreakable systems have already been broken? How many individuals or groups have become accomplices in the interception of private communications, whether for ideological reasons, as compromise for private shame, or just out of greed?

A more sobering thought: A serious state actor—pick any on the planet—delicately weakens “unbreakable” crypto just enough for its needs, keeps it very quiet, and then enjoys a good laugh at our expense, noisily chastising tech companies for their stubborn and “dangerous” refusal to create backdoors to their systems.

Pure fiction.

(Image via wk1003mike/Shutterstock.com)