Understanding Modern Greece

It is hard to understand the current Greek crisis without understanding the country’s recent history. SYRIZA for example, is not just a party that was founded to protest the recent austerity measures (like Podemos in Spain). Rather, it traces its roots to the communist resistance against the German occupation in the Second World War. One of the first things Alexis Tsipras did when he was elected as Prime Minister was to visit a monument dedicated to 200 (mostly communist) resistant fighters, a move he himself admitted was symbolic.

The reactions of many Greeks to foreign nations whom they believe are meddling in the country’s internal affairs go back even further, to the beginning of the modern Greek state almost 200 years ago.

I’m currently reading a book on Modern Greece by Yale professor Stathis Kalyvas. I wanted to share this quote:

Most Greeks see Western Europe (and the United States) as unwelcome meddling foreigners, even though they have largely profited from their interventions. Conversely, Europeans (and Americans) are exasperated that Greeks have failed to see those benefits, even though their inverventionism has been driven primarily by their own self-interest and has been imposed over the Greeks – their discourse about the importance of ancient Greek civilization notwithstanding.

Μένουμε Ευρώπη

This coming Sunday, there will be a referendum on a proposal that officially isn’t valid anymore, that no one has read and that may be voided anyway by whatever the government and The Institutions agree on this week. On Saturday, a man sat opposite me on the tram reading Kafka; perhaps he was just trying to make sense of the situation.

Tonight, there was yet again a mass protest on Syntagma Square, this time of the Yes (Ναι) campaign. I arrived later than yesterday and, quite unusual for this time of year, it was raining so it was hard to compare numbers fairly, but the square was yet again pretty packed. These people were on average a little older and looked a little bit more affluent than those attending yesterday’s protest, but there was still a very broad mix of people.
The atmosphere was, if possible, even friendlier than yesterday.

Despite the rain, I decided to hang about a little longer this time. Like yesterday, there wasn’t much going on and it was mostly people just being there for the sake of being there. Today, I really wanted to be there too. Menoume Evropi – we stay in Europe!

athens3006-2

athens3006-1

athens3006-3

‘Οχι

I still have to get used to the fact that mass protests are being organised in favour of a government, but that just goes to show how things are quite unusual in Greece right now.

Today’s protest (which is still going on as I write this) seemed much more spontaneous than the one organised by KKE last week. The atmosphere was quite friendly and several carts selling hot food even made it even feel like a music festival. There were TV cameras from all around the world; Athens Plaza hotel, where most journalists seem to be staying, is doing very good business this week. As I left – and I should point out that I was there as a spectator, not as a participant – scores more people arrived by metro to join the rally. All public transport in Athens is free this week.

While in the centre, I saw several ATMs, none of which had queues and several of which dispensed money. No matter how much Greece is making the headlines around the world right now, and no matter how much capital controls must hurt many people and businesses, life in Athens continues to go on as (almost) normal.

On an aside, the fact that the referendum question is asked so that NO (“ΟΧΙ”) is what the government hopes people will choose has a lot of historical relevance: 28 October, the day on which in 1940 the then Greek government rejected an ultimatum by Mussolini to allow Axis forces to occupy strategic location in Greece, is still a public holiday here. One cannot understand the subtleties of this crisis without understanding Greek history.

athens2906-4 athens2906-1

athens2906-3 athens2906-2

Protesters in front of the Parliament athens2906-5

Greece at the moment

Friends and relatives have asked me to keep them updated about the situation here in Greece; hence I’ve started to write daily posts on Facebook. I decided to post them here as well.

Things here in Greece are getting more surreal by the day: banks won’t open tomorrow and may not open until after the referendum. The latest news says ATMs may be closed tomorrow too and a €60 daily limit will be imposed thereafter. (Someone pointed out that many older Greeks don’t even own bank cards.) Twitter is showing photos of long queues at ATMs and petrol stations right now. The prime minister gave a speech today in which he sounded even more defiant than before. I have mixed feelings about the man and his policies, but I really don’t like his current confrontational approach to politics.

People have asked me if we are alright. We are. I’m following the crisis from the unfairly easy position of someone who doesn’t even have money in a Greek bank. In fact, we were going to open such an account tomorrow — a plan which we have now obviously postponed.

I just saw a garbage collection truck making its daily round, the relevance of which is that in many ways, life goes on as normal. It’s going to be an interesting week though. Let’s hope for the best. Greece deserves it.

Random Rabin-Williams signatures

Last weekend I was sent a paper on a vulnerability in an implementation of Rabin-Williams signatures. Or, as Google suggests, Robin Williams signatures.

rabinwilliams

Rabin-Williams is an asymmetric cryptosystem of which the security depends on the fact that given a number N which is the product of two large primes p and q (so N = p·q), it is very hard to actually find p and q. This is also what lies behind the security of RSA; in fact Michael Rabin is the ‘R’ from RSA (edit: he is not, of course, he just happens to share the first letter of his surname with Ron Rivest).

Moreover, Rabin-Williams also uses the fact that it is easy to take a square root modulo N, assuming one knows p and q (and especially if certain conditions about p and q are met), but without this knowledge it is impossible to do in practice (as long as p and q are sufficiently large). Squaring a number modulo N — which is of course the inverse of taking a square root — is trivial, even without knowledge of p and q.

So in Rabin-Williams, signing or decrypting a message involves taking a square root (which is thus only possible if one knows the private key), while verifying a signature or encrypting a message involves squaring a number, which anyone can do as the public key is, indeed, public. Rabin-Williams is especially useful in cases where the speed of the signing or encrypting operation is important.

There is a caveat though: taking a square root modulo N doesn’t give a unique answer. That is less surprising than one might think: taking the square root of 9 in the integers, that is finding a number whose square is 9, gives both 3 and –3 as solutions.

In the case we’re in here, there are in fact four square roots that occur in two pairs: s, –s and t, –t. When decrypting a message, one needs some extra information about the message to know which of the four square roots is the correct one. In practice, one might know enough about the message to determine the ‘correct’ square root, while there are also some mathematical ‘fixes’ to ensure the correct square root is always returned.

That signatures aren’t unique isn’t a problem in itself. After all, a signature is merely a proof of something (possession of the private key together with the message) and all that matters it that the receiver can cryptographically verify that the sender did indeed sign the message.

This is all fine if the signing algorithm always returns the same signature — and of course, algorithms have a nice tendency to do that. But there is a big hole one might fall into: knowing one square root in each of the pairs (so s or –s and t or –t) makes it trivial to compute p and q and thus to crack the cryptosystem. (It happens that the difference of these roots, viewed as integers, shares a non-trivial divisor with N.)

So it is essential that an adversary never gets hold of multiple signatures (square roots). And this is what goes wrong in the Crypto++ library: a fix to prevent timing attacks introduces a randomness in the computation of the square roots, which means that the algorithm outputs each possible square root with a probability of 1/4.

If an adversary is thus able to have the same message signed twice, they are able to crack the private key with a probability of 1/2. (This probability approaches 1 as more signatures are generated.) This is a serious weakness.

It was discovered by Yandex researcher Evgeny Sidorov and was published by IACR this week. If you like cryptography and number theory, I strongly recommend you read the paper. Evgeny also provides a simple fix to the implementation.

While admitting that I am far from an expert in this field, I have become a bit wary of Rabin-Williams and the fact that there are four square roots. Mathematics is strong enough to fix all the potential issues. But as always, people remain a big liability. And in the end, it is people who will have to implement the algorithms.

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.

Twenty centuries (but two) of writing on walls

wotw-us-coverthThe main point made in Writing on the Wall (Amazon), the latest book by Economist journalist Tom Standage, is that social media isn’t a new phenomenon. In fact, Standage argues, media have always been social, with the exception of a relatively brief interlude starting in the early nineteenth century and now coming to an end less than two hundred years later.

That period was the exception: the steam-powered printing press and later the telegraph, the radio and the television meant that media were controlled by a relatively small group of people; hence the term ‘broadcast’. Standage points to a surprising many similarities between the way news spread during most of the Common Era and the way it does now, on Facebook, Twitter and blogs.

Sure, looking for analogies between wall-graffiti found among the ruins of Pompei and today’s Facebook walls might be taking things a little too far. But it is one of the few cases where I think the analogy doesn’t really work.

The protestant reformation in Germany did get a kick-start because people spread (or retweeted) Luther’s theses. Coffeehouses were the forums of the seventeenth century – and they were frowned on for distracting their visitors from their work. The ‘blogosphere’ of late eighteenth century France did help create the atmosphere in which the French Revolution could take place, like a contemporary equivalent of Facebook had done to the American Revolution a decade earlier.

It is tempting to see social media as an entirely new phenomenon. And while some aspects of it are indeed new, social media is really an old and more natural way for news to spread. We should embrace its return.

Tom Standage is also the author of The Victorian Internet (Amazon), a book on the history of the electric telegraph that draws parallels between the early decades of the telegraph and the early years of the Internet. It combines two interests of mine that tend to be mutually exclusive: the Internet and nineteenth century history. I was thus pleased to learn that the book, which was long sold out, is back in print again.

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.)