(How) did they break Diffie-Hellman?

Earlier this year, a research paper presented a new attack against the Diffie-Hellman key exchange protocol. Among other things, the paper came with a reasonable explanation of how the NSA might be able to read a lot of the Internet’s VPN traffic. I wrote a blog about this in May.
Last month, the paper was presented at a conference and thus made the news again. Because I believed some of the news articles misunderstood the paper I just like writing about cryptography, I thought I’d explain what Diffie-Hellman is, what the paper showed and what its consequences are.

Chicken or the egg

Diffie-Hellman (named after its inventors Whitfield Diffie and Martin Hellman) attempts to solve the chicken-or-egg problem in cryptography: for Alice and Bob to communicate securely over a public channel such as the Internet they need to share a common encryption key. But for them to agree on such a key they need to be able to communicate securely over a public channel.
(N.B. in a typical situation where the protocol is used, Alice is a web browser or a VPN client; Bob is a web server using HTTPS, or a VPN server.)
Diffie-Hellman is called a key-exchange protocol, which is a bit of misnomer, as rather than exchange a previously generated key, the protocol actually generates the key.
In the first step, Alice and Bob both choose a (large) random number, which they both keep secret. Let’s call Alice’s number a and Bob’s number b.
Now using a ‘mechanism’ (more on which later) that is part of the protocol, Alice uses a to compute a second number, which is denoted ga. Bob uses the same mechanism to compute a number gb. Alice and Bob then share ga and gb with each other, over a public channel.
So we are now in the following situation:

  • Alice knows a, ga and gb;
  • Bob knows b, ga and gb;
  • Anyone being able to read their communication only knows ga and gb.

Now using the same mechanism as before, Alice uses her secret number a and the number gb, which Bob sent her, to create a new number (gb)a. Bob, likewise, uses b and ga to create a number (ga)b. Because maths can be kind like that, (gb)a and (ga)b are in fact the same number. This is the shared key they will use.
The reason this works is that, while it is easy for Alice to use a to compute ga, it is impossible for someone who only knows ga to compute a — and the same of course also holds for b and gb. It is also impossible to compute the shared secret key using only ga and gb.

Nothing is impossible

It is important to note that as so often in cryptography, ‘impossible’ doesn’t literally means that. It just means that it is extremely expensive and time-consuming. If the numbers involved are large enough, it can take the fastest clusters of computers millions of years to crack the algorithm; hence it is considered secure.
But computers keep getting faster, thus sometimes making the impossible possible. Many Diffie-Hellman implementations use numbers of a little over 300 digits long (1024 bits). These keys, the paper showed, can be cracked within a year for around 100 million US dollars. (Some people believe it can be done even more cheaply, but only the ballpark figure matters here.)
While 100 million dollars is not beyond the reach of the most powerful nation states (read: the NSA) it is unlikely that they ever pay this much to crack a single key. There’s almost always a cheaper way to get the same information; buying a very expensive wrench, for example.
Except for one essential detail. The mechanism used by Diffie-Hellman to generate the keys involves a choice: that of something mathematicians call an Abelian group, or, as they are more or less equivalent in this case, that of a prime number.
The attack the paper describes has two parts. The first part is the most expensive bit and involves doing a lot of computations that only depend on the chosen prime number. Only the second part involves the specific numbers ga and gb shared by Alice and Bob. An attacker who has done enough computations in the first part can perform the second part in more or less real time.

Sharing prime numbers

Imagine what would happen if many Diffie-Hellman implementations used the same fixed prime number: an adversary could spend a lot of time and money doing the required computations for this prime number and subsequently use that to crack key exchanges as they happen in real time. Knowledge of the secret key allows an adversary to read all the supposedly encrypted traffic between millions of Alices and Bobs around the world.
And this is exactly what was (and to some extent still is) the case: the paper showed for example that one in six of the most used HTTPS servers shared the same prime number. It’s even worse when it comes to VPN servers, of which 66% shared the same prime number. Although the latter figure has been disputed, if this was indeed what the NSA used to read VPN traffic, it would explain some Snowden slides rather well.
It is worth noting that sharing the same prime number is not as stupid as it may seem. Using your own unique prime number may be safer against this kind of attack, there are many traps to avoid when doing so. Most importantly, a lot of prime numbers are unsuitable and make the protocol a lot weaker. The paper also showed that several implementations used such unsuitable primes (and, somewhat intriguingly, some implementations used numbers that weren’t prime at all). There is thus a lot to say for choosing known safe (though widely used) prime numbers, despite the downsides we now understand well.
It would actually be a good rule of thumb to choose the strength of your encryption algorithms such that it would be too expensive for the most powerful adversary to attack, even if they would automatically crack all other implementations of the same protocol. For Diffie-Hellman, using longer numbers of 2048 bits (more than 600 digits) will do just fine.
It is thus not true that the researchers have broken Diffie-Hellman. Nor is it true that choosing “non-random prime numbers” (as I’ve seen someone claim somewhere) is inherently wrong.
However, longer numbers makes the algorithm more expensive to run. There would thus be a good argument to use Elliptic Curve Diffie-Hellman (ECDH) instead, a similar protocol that uses a different kind of maths. Its most important benefit is that it provides the same level of security with much smaller numbers.


On an aside, the paper also showed a related attack, which involves a “protocol downgrade”, where an adversary could convince Alice and Bob that the other could only use a mechanism with 160-digit (512-bit) numbers. The cost of cracking the secret key in this case, even if the mechanism used a unique prime number, is not beyond the means of a small criminal organisation.
Although this is a serious problem, from a cryptographic point of view it is less interesting. I also don’t know how likely it is for this attack to be used in the wild frequently: for a nation-state attacker a downgrade attack leaves too many traces, while for a criminal group, obtaining a man-in-the-middle position isn’t entirely trivial and often not needed to achieve their goals.


On Turkey, Twitter and SSL

Today, an attack on a peace rally (a peace rally!) in Ankara, Turkey left close to 100 people dead and many others injured. ‘Tragedy’ doesn’t even begin to describe what happened.
The Turkish government responded by banning the media from reporting on the issue. There were also rumours of Twitter being hard to reach from within Turkey, which wasn’t surprising given previous efforts by the Turkish government to ban the service.
Nicholas Weaver asked people to investigate what was going on. Using Hide My Ass, a VPN service, I was able to confirm I could reach Twitter from various Turkish IP addresses.
But then I noticed something odd. When using curl, I got an “Unknown SSL protocol error in connection to” error. I got this error only when accessing Twitter from a Turkish VPN — I tried various Hide My Ass VPNs in difference countries — and only when accessing, which normally redirects to
I don’t get the error in Firefox (Debian), but I do get the same error in the text browser w3m (which could use the same libraries). I’ve not been able to detect any difference between the server information and I get the same error when using curl -k, suggesting it is not a certificate issue. In verbose mode, curl gives the error right after reporting the sending of the client’s hello message.
I suspect this is entirely innocent — I assume Mozilla is doing a lot more to detect SSL/TLS shenanigans than curl, and they think everything’s fine — but I wanted to share this information, just in case.
NB As I only control the client side of the VPN connection, I’ve not been able to take useful PCAPs. There might be a way around this though. Suggestions are welcome.


Elections, again

Tonight, I found myself on Syntagma square where, unbeknownst to me, SYRIZA was about to hold an election rally.
Despite the elections being held on Sunday, election fever seems to have skipped Greece this time. There are quite a few election posters to be seen, mostly from the far left parties, but then, there are always posters from the far left parties everywhere, as there’s always some important protest march that ended disastrously to be remembered, or something the 1% needs to convince the 99% is the right way of seeing things. Other than that, it seems that whatever political enthusiasm was left in Greece was used up during July’s referendum and its aftermath.
Still, thousands of people had turned up to see speeches from the outgoing (technically: former) prime minister and his support act, four foreign politicians who are on his side in this apparent struggle against the institutions. Someone from Germany’s Die Linke was speaking excitedly, for he too didn’t like Merkel and Schäuble and it would be such a blow to these two if the Greeks were to reelect Tsipras. Another German, a lady from the Green Party, went on in fluent English about the environment and the refugee crisis, two important topics, yet also two topics which I’m not sure Tsipras has shown a great deal of concern about. (Though later tonight on Twitter he rather oddly blamed Schäuble’s home state Bavaria for not taking in enough refugees.)
A French communist member of the European parliament thought this struggle was mostly about ‘travail’ – as he would – and I don’t know what Pablo Iglesias, leader of Spanish anti-austerity party Podemos said, but the audience liked him best. But then, he’s been a Tsipras-supporter from well before the latter even thought about becoming a prime minister.
I left shortly after Tsipras started to speak, promising myself to work a little harder on memorizing Greek words and phrases. By the looks of it, Tsipras will pull off a narrow win, but will have to co-operate with one or more of those parties that helped him get the new memorandum through parliament, but whom he has been rallying against all the time since – apparently because they actually believed what they voted for, rather than just did so following blackmail by Europe.
I too am spending nowhere near as much time following the elections as I had done following the referendum. I guess my appetite for these things – and I’ve always been a bit of an election geek – isn’t limitless either. And of course, recent events in Europe hav put the Greek crisis into a perspective that maybe it needed.

athens_1809-4 athens_1809-1
athens_1809-2 athens_1809-3

Next act

Very late on Saturday, we came back from a two week holiday, to a country and a house which I had missed and a fridge which had missed me filling it. Having lived in England for years, I’ve gotten used to the fact that most shops are open on Sunday. And even in countries where as a rule they aren’t, there are at least some places selling fresh food, typically in tourist areas or transport hubs.
Not so in Greece. While some corner shops are open, there isn’t a supermarket in all of Greater Athens (population: 3.7m) open on a Sunday. Such is the law, a law that has long been defended by many on the political right (mostly for religious reasons) and on the left (mostly for anti-capitalist reasons). When “the institutions” are accused of micromanaging the Greek economy, it’s worth keeping in mind that in many cases, they actually ask for micromanagement to be ended.
I had decided to continue writing about Greece, even as the country ceased to be the main item in news bulletins around the world. But then, while I was away, things got interesting once again: prime minster Alexis Tsipras handed in his resignation and new elections will be held next month.
For the very short term, this isn’t good news: the last thing a country still affected by capital controls and a crumbling economy needs is instability. For the slightly longer term, it is probably a good thing though: while the government easily got some tough measures through parliament, it had to rely on the support of the three sensible opposition parties, as a large number SYRIZA members voted against.
Those people have now left SYRIZA to form a the new Popular Unity (Laïki Enotita), headed by former energy minister Panagiotis Lafazanis. He and his party believe that No in the referendum should mean No and that the country should leave the euro and go back to the drachma. Something Lafazanis allegedly wanted (and for all I know still wants) to fund by robbing the Greek Mint and using the euros stored there to pay civil servants’ salaries.
Lafazanis and his party are unlikely going to be a significant factor in the elections though. The far most likely outcome is that SYRIZA yet again becomes the biggest party and that Tsipras returns as prime minister and is able to implement those measures he agreed to at the very last minute last month. But then, this is Greece. The ancient Greeks didn’t just invent democracy. They invented drama too.


Go Set a Watchman

Spoiler alert: some of the book’s main themes are discussed below. I don’t think there’s anything that would spoil the story.
US_cover_of_Go_Set_a_WatchmanWhen I first read Harper Lee’s To Kill a Mockingbird eight years ago, I was surprised by how much of it wasn’t about race. It’s a novel about judging people — including, but not limited to, judging people based on their race — and about growing up in general, and growing up in the 1930s Deep South in particular.
Of course, the most famous part of the book is the defence, by the protagonist’s father Atticus Finch, of a black man who was unjustly accused of raping a white girl. It’s part of what makes the book great and part of why I think it’s one of the best books ever written. When it comes to heroism in literature, it is hard to outdo Atticus Finch.
Or at least it was, until first-draft-turned-second-novel Go Set a Watchman was published last month and it turned out that Atticus did hold some views that can only be described as plain racist.
If you find this shocking, and it seems many people did, you may actually want to read the book: this shock is one of its main themes.
I don’t think the Atticus Finch in Go Set a Watchman is any different from the character in To Kill a Mockingbird though. It’s just that twenty years later (this novel is set in the early 1950s) we see a different side of him.
To me, it seems clear that if he were again to be appointed to defend a black man (as he was that of Tom Robinson; perhaps crucially, he didn’t choose to take on the defence) he would do so just as passionately and with as much reverence for the law and for justice as he had done twenty years previously. But now we know that he also did think blacks were inferior to whites and that the federal government shouldn’t force the southern states to desegregate for that reason.
Atticus’s views were wrong, but they were also very common in his time, even among intelligent people. One of the most famous quotes from To Kill a Mockingbird is that “you never really know a man until you stand in his shoes and walk around in them”. Given that I never walked in the shoes of Atticus’s contemporaries, I shouldn’t really pretend that, had I lived in his time, my views would have been different.
That realisation makes me glad I live today and that the percentage of people who hold such views has significantly decreased (even if we all know too well it hasn’t enough). That’s progress. Just as it’s progress that I now hold some views that future generations will find despicable. And I hope that people of that generation “hold ground for what [they think] is right — stand up to me first of all” as Atticus tells his daughter in the book’s closing scene.
I still feel a bit uncomfortable about whether Harper Lee meant for this book to be published. I guess we’ll never really know whether she did. But now that it did get published, I’m very glad I read it. And it made me admire her as a writer even more.



If you’ve recently seen a TV news item with a reporter discussing the state of Greece to the background of the parliament building, they most likely were broadcasting from Athens Plaza hotel, one of the three five-star hotels on Syntagma Square and the one whose balconies give the best view of the parliament. In recent weeks, whenever I was on Syntagma Square, I could always spot TV cameras on at least a dozen balconies.
We were at Syntagma Square yesterday and all the cameras seemed have gone. Greece has disappeared from foreign papers’ front pages and from TV news bulletins. Indeed, Greece is slowly returning back to normal and capital controls are gradually being lifted, though the emphasis here is on ‘slowly’ and ‘gradually’.
It is a telling sign that today’s biggest story is that of the leaked plan from former finance minister Yanis Varoufakis in case the country was forced to leave the euro, a plan which appears to have involved hacking into the systems of the Greek tax collecting agency. While the story is huge, it doesn’t have any direct impact on people’s lives or on the political situation.
And while many Greeks have left or are leaving for holiday — it is not uncommon for Greek businesses to close for the whole of August — the government has pushed some legislation through parliament, which was a precondition set by other eurozone counties to start negotiations on a third bailout package. A significant minority of MPs from the government parties voted against the proposals, which wouldn’t have passed if it wasn’t for the support of the three moderate opposition parties (the neo-Nazis and communists voted against, but people are neither surprised by this, nor are they taking this very seriously). More worryingly, the government hasn’t exactly been cheering the legislation it asked parliament to pass, so that we now have a government which has some interest in the situation of the country worsening. Thankfully, a significant majority of Greeks continue to say that the last-minute deal was better than any of the alternatives.
The past few weeks, I have often found myself thinking of a quote from Guiseppe Tomasi di Lampedusa’s The Leopard, a classic Italian novel: “everything needs to change, so everything can stay the same”.
A lot of things will change in Greece. Change is never easy. But it will be for the better.



Temperatures in Athens have been hitting the mid 30s for weeks. Today, a fairly strong wind was blowing through Southern Greece. These two combined make ideal conditions for wildfires. Indeed, and unfortunately, at several places around Athens, as well as in the southern Peloponnese, wildfires did appear.
The images of the fires on the hills surrounding Athens looked both impressive and scary when I saw them on the Internet. Even from our house, miles away from those hills, we could see thick clouds of smoke. Two water-dropping planes were constantly taking water from the Saronic Gulf in an attempt to battle the blaze. When I got a clearer view of the main fire early in the evening, it did look like they had at least had some success.
In the meantime, Greece has been given a little over seven billion euros in bridge financing from our friends in Europe — or, as the Greek government used to call them until recently: terrorists! criminals! Nazis! There’s no reason to get too excited about that just yet as most of this money will be used to pay bills that have arrived in recent weeks, but that the government had wisely left unopened. But more help is on its way, some of which is explicitly meant to kick-start the economy. Banks will open too, but it’s not yet clear whether this will happen on Monday as had initially been announced. Lifting capital controls is much, much harder than imposing them.

athens1707-2 athens1707-1

Elliptic Curve Cryptography for those who are afraid of maths

Last month, I gave a talk on Elliptic Curve Cryptography at the BSides London conference in, indeed, London, UK. It is the favourite of all the talks I have ever given. The video of that talk has been added to YouTube. I thought you might like it.


Athens to the dogs

When I first visited Athens ten years ago, I was struck by the city’s many stray dogs. Though far outnumbered by stray cats, the dogs are hard to miss, and are often found crossing streets with pedestrians or sleeping in parks or on pavements.
As I walked through central Athens today, I saw several of them — all asleep — and realised I had missed them during the past weeks, when the central square was often packed with protesters. It was a reassuring sign that things may slowly be returning back to normal, just like the kids breakdancing on Syntagma Square were such a sign. I would almost be willing to believe that tomorrow’s metro strike is such a sign too.
True, there were a few fringe groups on Syntagma square protesting against Monday’s deal, but then Greece has always had many fringe groups (in January’s elections, at least half a dozen communist parties took part). Perhaps this too is a sign of things returning back to normal.

athens1407-2 athens1407-3
athens1407-4 athens1407-6
athens1407-5 athens1407-1


I consider myself an optimist. It hasn’t always been easy watching the Greek crisis unfold though. Not only were there many times during which it did take some extra effort to believe things would be alright in the end, there were also those commentators from either side of the political spectrum (and frustratingly often from outside Greece and with little understanding of the country) who knew how much better a Grexit and a proverbial middle finger to “the institutions” would be. If only they knew.
This morning, when I woke up from a rather short night’s sleep, there still wasn’t a deal. There was one a few hours later. Critics were quick to point out that the measures the Greek government has agreed to are pretty tough, which they are, while others made the point that Greece won’t ever be able to pay off all of its debts, which is also true. (I am actually in favour of debt restructuring, but at this point of time, with Greece seeking new loans, it would have made little to no difference.)
But the alternative would have been so much worse. For Europe, for the other euro countries but especially so for Greece. And politics is often about finding the miserable little compromise that hurts everyone least.
There are actually quite a few things in the deal that will be positive for Greece. Some of these are measures that will improve the country’s economic performance in the long run, but there is also an explicit mention of investments. One is right to see the many unemployed youth as a big problem for the country. But they are a huge potential too, which could be unlocked with the right investments.
For now, the banks are still closed though. They will remain so until at least Wednesday. After then capital controls will only gradually be lifted. The next weeks, we will no doubt see many protestors on Syntagma Square who will make it loud and clear that the deal goes against their ideology or their vested interests.
But some light can be seen flickering at the end of the tunnel. Let’s make sure we do get there. And let’s be kind to Mr Tsipras.
Grexit? Graccident? Here’s to Groptimism.