A New Assessment of Encryption Strength

When I decided infosec was something I wanted to become involved in, I was given a valuable piece of advice: "Read Ars Technica every day." I've been following the conversation their publication and others have been reporting around elliptic curve cryptography (ECC), namely that the National Security Agency (NSA), who promoted ECC, backdoored it so they were encouraging everyone to use a code they could break.

When one person can break a code, others can find that weakness as well, it is fundamentally unsafe. So when one of your jobs is to protect U.S. government communications and information systems against penetration and network warfare, promoting broken code just to make the other side of your job easier, namely the global monitoring, collection, and processing of information and data for foreign intelligence and counterintelligence purposes, means you really failed at one side of your job.

However, the nuance of this discussion turns on the fact that only one ECC library (Dual EC_DRBG) has been reported by reputable security researchers to be backdoored. But just because you can't see something doesn't mean it isn't there. If one was compromised, and they were all promoted by the NSA, past behaviour is the best indicator of future behaviour, it's likely they were all compromised. Right? Smarter, more experienced people than myself may hold a more authoritative opinion but I'm going to argue, surprisingly given the tone of my previous posts, no...

What is ECC? Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. Did you get that? Honestly I didn't either, but in layman's terms it is an equation (y^2 = x^3 + ax + b) that solves for the points on a, you guessed it, elliptic curve, and it has special properties that means the equation is easy to solve left to right, but hard to solve right to left. These are known as trapdoor functions. For ECC specifically, it's really hard to figure out what number y is to the power of.

Yes, I understand I've boiled this explanation down to the meaningless phrase "special properties". I'm learning, too. If you have ten minutes, and lets be frank, you do, you're here on LinkedIn, here is a better but still layman explanation I found while researching this post.

So, what does one do with all these numbers? Cryptography works by using prime numbers to generate public and private keys (right and left side of the above mentioned equation respectively in very simplified terms). Your public key gets passed around, people use it to encode or encrypt something and then you use your private key and decrypt what they encrypted. You can't encrypt and decrypt with the public key and only knowing the public key its really hard to figure out what that private key is, even though the public key was generated from the private key. There is your easy to solve or "make a public key" one way, but hard to solve or "figure out what the private key is" the other way.

But how did the NSA backdoor ECC? The prime numbers themselves are derived from random number generators. But here's the catch, there is no such thing as an electronic random number generator. Computers cannot simulate true randomness. So all electronic random number generators are, in actuality, pseudo random number generators. They have some bias in them. The NSA apparently made one of the random number generators in a particular version of ECC really biased, allowing them to work out the prime numbers the cryptographic keys are based off, therefore allowing them to work out the private left side of the equation.

What am I basing my theory that there are in fact some safe ECC libraries out there on? Funnily enough, another Ars Technica article not directly related to ECC. It's about a trojan, a piece of malware called USB Thief, that bares a very striking similarity to Stuxnet. Given USB Thief's pinpoint accuracy of only infecting specific targets its pretty much guaranteed that the trojan was made by a government entity. Cyber criminals wouldn't discriminate as it lessens the payday. And given USB Thief's sophistication it was made by the best hand out there. Given the similarity to Stuxnet and the level of encryption USB Thief uses, I don't think it's an unfair call to say the trojan was probably written by the Equation Group.

The article also references Gauss, another piece of malware with an encrypted warhead that we still to this day have failed to unlock. Pretty strong encryption. But the line in the USB Thief article that got me thinking was right at the end: "It (USB Thief) encrypts the stolen data using elliptic curve cryptography". Now why would the United States make a trojan that uses compromised encryption? The answer, they wouldn't. No government would. So the particular ECC library used in USB Thief is most likely not backdoored.

I think.

My conclusion, encryption found in malware written for espionage purposes by state actors is honestly believed by those state actors to be as tough as coffin nails. Therefore, I propose that one should factor in the presence of libraries in such malware when assessing which encryption library to use and highly favour these libraries.

I'm not an expert in this field by a long shot, so I'd be really keen to discuss this idea with people more knowledgeable than myself and see if it holds the water I think it does. You can contact me on kademorton at protonmail dot com