A talk on Dual_EC_DRBG

Back in May I gave a talk on the subject “Dual_EC_DRBG; or, the story of a not so random backdoor” for the OWASP chapter in Athens, Greece.
As the title suggests, the talk was on the Dual_EC_DRBG random number generator, which we are now all but certain was backdoored by the NSA. I wrote a blog about this last year.
The slides, in case you’re interested, can be found here (PDF). No recording of the presentation was made.
If you do like to watch a recording on Dual_EC_DRBG, I can recommend this presentation “Practical Kleptography” by Matthew Green.

books Security


Cyberdanger is a book written by Eddy Willems. Actually, it’s called Cybergevaar — a fitting Dutch title, as the book is written in Dutch. I wrote a review for Virus Bulletin here.


Researchers crack Bitcrypt ransomware

There are 256 (28) different bytes and only ten different digits. So if your secret (RSA) key consists of 128 digits rather than of 128 bytes, the entropy of the key (that is, the amount of ‘surprise’ to an attacker) is a whole lot lower.
No shit, Sherlock. Apparently, this somewhat basic fact was beyond the understanding of those who wrote the Bitcrypt ransomware, probably inspired by the sad success story of CryptoLocker. In practise, it meant the difference between “only the NSA can crack your key” and “anyone can crack your key”. Two researchers from Airbus cracked the key and thus were able to restore the encrypted files on a friend’s computer, without paying the 0.4BTC ransom.
More at Virus Bulletin here.


Windows Error Reporting used to discover new attacks

Security firm Websense published a report that explains how they can use error reports generated by Windows to discover new targeted attacks (‘APTs‘ in security hipster speak). It’s interesting, but it barely touches on the fact that these reports being sent in cleartext is also a serious problem. I wrote a blog on both sides of this issue for Virus Bulletin.
(I’m not sure if anyone is reading my musings here, but I thought it might be a nice idea to link to things I write elsewhere. I also hope to find inspiration to write the odd thing that has nothing to do with computers or security at all.)


The Return of Qakbot

Together with João Gouveia of AnubisNetworks, and using their real-time feeds, I’ve been looking at Qakbot, a piece of malware that was huge in 2011 and had since disappeared off the radar.
We found that Qakbot is still active and there are at least 20,000 infected devices. The command and control protocol has progressed from version 2 back in 2011 to version 8 today. We cracked the obfuscation used in earlier protocols, but are still struggling with version 8, which appears to use encryption rather than obfuscation.
I tried a large number of obvious and slightly less tricks to crack the protocol (including RC4, which I didn’t mention in the blog post), but so far to no avail. If anyone has any suggestions on how the encryption might work, we are of course happy to learn of it.
Still, I am quite content with the research we did, which will hopefully contribute to the knowledge of and the fight against Qakbot. The blog post is here. (NB the original blog post is not available any longer; an archived version can be found here.)


Browser-based ransomware

Tonight I stumbled upon some browser-based ransonmware, that pretends to be a message from the police. This is neither very advanced (it isn’t anything like Cryptolocker), nor is it very new. It doesn’t install any malware on your machine (though this trick has been used by actual malware, such as ‘Urausy’). All it does is tell you that “your browser has been blocked up for safety reasons”, and that to prevent going to jail for anything between 5 and 11 years (for watching something very illegal), you need to pay a fine. Because of course, that is how the legal system works.


I’ll do a more detailed write-up about this later. I thought it was interesting that it was spreading via Twitter and used some subdomains to domains hosted at a UK-based registrar, whose customers probably had their DNS hacked.
One thing that is typical for this kind of scam is that based on where you access the website from, you get the message in the local language and the logo of the national police force. They typically include a photo of the head of state as well. Because that makes it a lot more real.
And since this isn’t a very advanced scam, I could grab the various logos that are used. I had seen most of these before, but I don’t know if they had ever been shown on a single site. Now they have. (Actually, just before posting I noticed these are the same images used by Urausy last summer; Kafeine has all those images. Oh well.)






Czech Republic












New Zealand











United Kingdom

United States

Me, on email. In Dutch

This week I had a nice chat with Maurits Reijnoudt, a Dutch journalism student who is using an internship at Bits of Freedom (a Dutch digital rights advocacy group) to find out as much about email as possible. If this thing interests you, and if you happen to speak Dutch, you can find the interview here.


When to keep a secret

I was listening to a interview with Bruce Schneier at Columbia Law School on the NSA and all that (audio here). It’s well worth listening to — I think that Snowden’s whistleblowing is worth it just for all the talks and interviews Schneier has given as a result.
Schneier pointed to another positive consequence of the Snowden revelations: the NSA and its counterparts now know that whatever they do, there is a chance it will come out in the open. The implicit assumption that no one will ever find out what you’re doing makes people careless and makes them cross boundaries they wouldn’t cross otherwise.
It reminded me of something journalist and historian Timothy Garton Ash wrote following the WikiLeaks cables a few years ago. He said that anyone wanting to keep information secret, should be able to withstand the following test: if this piece of information became public, could you credibly explain why it should not have become public?
Indeed, few would have batted an eyelid if it turned out that the NSA only read the email of Al-Qaeda members and listened to the phone calls of Kim Jong-un.


Hunting a botnet: the story of UnknownDGA17 and Mevade

During the past few weeks, me and João Gouveia of AnubisNetworks have spent many an evening hunting a botnet that João had discovered and subsequently called ‘UnknownDGA17’.
I think ‘hunting’ is the right term here, because we based our research on information from AnubisNetworks’ Cyberfeed, in particular hundreds of thousands of connections the botnet made to a sinkhole, rather than on actual malware samples. In the end, we were able to find so many links with ‘Mevade’, a botnet (in)famous for using the Tor network for C&C communication, that we can be certain the botnets are closely linked, if not the same. We also found that Mevade is heavily involved in bitcoin mining.
The full story is here.


How the NSA cheated cryptography

Of all the revelations made by Edward Snowden, I find the recent one about Dual_EC_DRBG definitely the most intriguing and possibly the most shocking – even if it wasn’t really news.
It intrigues me because it is about elliptic curves. I love elliptic curves. I studied them quite extensively when I worked as a mathematician and although I don’t use them anymore, I still feel a fondness for them.
But more importantly, it intrigues me because initially I didn’t realise what had really happened – and judging from comments and articles I’ve seen, I wasn’t the only one.
The NSA didn’t weaken a crypto standard. Rather, it put a backdoor inside the standard. There’s an important difference. As a consequence, if you use Dual_EC_DRBG, you’re still well-protected if the adversary you’re defending against isn’t the NSA. But if it is, you’re pretty much stuffed.
Dual_EC_DRBG is a pseudorandom number generator (or deterministic random bit generator; hence the name). It is one of four of its kind that were defined in the 2006 NIST standard SP 800-90A (PDF). The standard was written with the help of some people at the NSA. As we now know*, the NSA effectively wrote the standard.

Well, this is awkward.

Randomness is an essential part of any crypto system. It is also where many crypto systems have weaknesses, so if you’re implementing cryptography, it makes sense to use a standard provided by a reputable organisation like NIST.
What pseudorandom number generators do is turn a small ‘seed’ of proper random data into a constant stream of random numbers, which enables you to get such a number with arbitrarily high entropy. Entropy is usually defined as a way to measure randomness, but here (and possibly in general) it is best to see it as a way to measure surprise to an adversary. A high entropy means the adversary will know very little about the random numbers the system generates.
Dual_EC_DRBG uses a given elliptic curve. Elliptic curves come with an extra structure, called a group structure. For the purpose of this post, it suffices to say that this allows you to walk along the curve but, rather than simply following the shape of the curve, your walk makes you seemingly go all over the place. It is this all-over-the-placeness which makes them useful to generate pseudorandom numbers (and for cryptography in general).
Elliptic curve with group structure
The group structure on an elliptic curve. Don’t worry if it doesn’t make sense.

Apart from the curve, the algorithm also uses two given points P and Q on this curve. Like the curve, they are given in an appendix to the NIST standard.
Now there exists a relationship between these points P and Q: if you start at Q and you continue walking, then, for some large number e, after e steps you end up at P. This is not a secret: it is a simple property of the group structure of elliptic curves. But if the curve is large (which the one used in this standard is), it will take you a long time to compute e. Think in terms of millions of years. So no one knows e and no one can know e.
No one? Well, if you simply choose a point P on the curve and choose a (very large) number e, you can use that to compute a point Q. If you then give out these P and Q to someone, they will still need a million years to compute e. But you know it.
And that’s exactly what the NSA did. They provided the P and the Q in the standard. They, as has become clear from Snowden’s documents, know e. We don’t. And we can’t even compute it.
Does this matter?
It does. In 2007, Dan Shumow and Niels Ferguson, two researchers then working for Microsoft, showed (pdf) that, if you know e, cracking the pseudorandom number generation becomes a little easier. A little easier? Actually, it becomes almost child’s play. They effectively showed that to the NSA, your high-entropy pseudorandom number generator, generates output with very few surprises.
In practise this means that, by knowing e, can read almost all TLS-traffic (which includes HTTPS) that is encrypted using a algorithm based on Dual_EC_DRBG.
After the likely backdoor was found in 2007, NIST actually updated the standard. It now shows you a method to choose ‘good’ P and Q yourself (for you can’t just choose arbitrary points). But it still says that if you want your crypto to be FIPS 140-certified, you need to choose the points they’ve chosen for you. “Trust us,” you read between the lines, “we know they work.”
So why would anyone trust them, especially after it was shown that someone could likely have inserted a backdoor? That is beyond me. But the standard is used in quite a few implementations.
What makes this even more strange is that, as Matthew Green pointed out in an excellent blog post, the algorithm is pretty flawed in a number of other ways too. No wonder the crypto world suddenly finds itself in an existential crisis.
Now it would have been bad if the NSA had somehow managed to make us all use weaker cryptography. Still, the playing field would have remained level, albeit with lower security for everyone.
It would have been a little worse if the NSA knew of a secret algorithm that enabled them to break cryptography. (It is possibly that one of the future revelations that Bruce Schneier hinted at will show they can do that for certain crypto standards.) Still, ultimately that is just beating your opponent by being more clever.
But what the NSA did was plain cheating. The crypto remains secure against any of us. But they can crack it. Because they wrote it. And they put a backdoor into it. And even though we know (and have known for some time) there was such a backdoor, it still doesn’t help us.
Cheating with the privacy of billions of Internet users is nothing but very, very wrong.
(Apart from the linked blog post by Matthew Green, there is this Wired piece on Dual_EC_DRBG that the aforementioned Bruce Schneier wrote back in 2007, when Edward Snowden was but a junior employee at the CIA working in Switzerland. As just about anything Schneier has written on cryptography, it is well worth a read.)
* The NSA hasn’t owned up and it is unlikely they ever will. While no one doubts that the NSA planted a backdoor into Dual_EC_DRBG, we can’t prove it. Throughout the blog post, I have assumed we are sure. It made for easier reading. And, frankly, we are quite sure.