We are the 100%

I was at a neighbourhood supermarket today. As I have seen photos of supermarkets with empty shelves on the Internet, it is worth pointing out that this one was fully stocked; although it is also fair to say ours isn’t the neighbourhood where people would be the first to start panic-buying.

As always, there were many offers and they even tried to get me to subscribe to a customer loyalty card scheme. In many ways, even after the banking system has been closed for almost a week, life in Greece still continues to go on as normal.

The big question remains what will happen on Monday morning, when 45% of the country finds out that 55% has signed up for some tough measures that will affect everyone; or, when 45% finds out that 55% has put the country on a path that may lead to an exit from the euro zone — and possibly a much poorer standard of living.

And that’s what worries me most right now. There is a reason many thinkers (most notably that namesake of the current Greek prime minister Alexis de Tocqueville) have warned against the tyranny of the majority. Keeping the country united is going to be the biggest challenge for the foreseeable future. The good thing is that everything else will be easy compared to that.

Here’s to optimism.

Alle Menschen werden Brüder

I had tears in my eyes as I walked away from Syntagma Square tonight. It wasn’t because of the big No-rally that was going on there, nor was it because someone from Spanish Podemos had just been speaking. It only slowly dawned on me that it had been teargas. It seemed to affect me more than it did others around me, but thankfully the pain didn’t last long.

Oddly enough, I hadn’t seen any riots, though I later learned there had been a few. There was quite a bit of riot police surrounding both demonstrations tonight, but they looked bored and uninterested as Greek riot police tends to do.

As I walked towards the ‘Kallimármaro‘ (the stadium used for the 1896 Olympics), ‘ΟΧΙ’ posters along the roads gradually made way for those saying ‘ΝΑΙ’. Two American tourists concluded that ‘ΝΑΙ’ must mean ‘no’.

When it comes to locations for your rally, the Kallimármaro is hard to beat — even if it’s slightly less central than Syntagma. Chants of ‘Greece! Europe! Democracy!’ were chanted and the atmosphere of the Yes-rally was very friendly and even felt quite optimistic.

As I walked away after about half an hour of immersing myself in the crowd, they played Beethoven’s ‘Ode to Joy’ — the European anthem — through the speakers. Most people blew whistles in support. Now I had tears in my eyes again.

The European family has had better moments, but it has also seen much worse. It is good to remember that. We’ll be alright.
Alle Menschen werden Brüder. All men become brothers. Όλοι οι άνθρωποι είναι αδέλφια.

athens0307-7 athens0307-3

athens0307-4 athens0307-6

athens0307-8 athens0307-5

athens0307-2 athens0307-1

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.