Thursday, September 28, 2017

CHES 2017 Taipei, Taiwan

CHES 2017 was held September 25th - 28th in Taipei, Taiwan. This being my first trip to CHES, I was glad to see a mix of academics and people in industry whom had ties with cryptographic hardware on embedded systems.

Although I have a limited frame of reference, I feel the standard of the conference was quite high - the presenters all knew what they were talking about in great detail, and were able to accurately describe the contribution they had made to their respective fields.

My favourite talks were in the 'Side-Channel Analysis' and the 'Emerging Attacks' sessions, as the talks in these two sessions in particular were engaging and close to the work I have been doing during my PhD.

However, my obligatory post-conference blog post will be on 'Sliding right into disaster: Left-to-right sliding windows leak', a joint work by Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal, and Yuval Yarom (I wasn't aware so many people could work on one paper at the same time!).

The contribution of the paper was showing that although the Right-to-Left sliding window didn't provide leak a great deal of information, the Left-to-Right sliding window provided just enough to recover the full key (in some cases).

For a brief recap, RSA uses modular exponentiation, and in many implementations the 'sliding window' method is used for efficiency. This can be done either Left-to-Right or Right-to-Left, and although they are very similar, they have very slight differences: the Right-to-Left method tends to be easier to program, uses the same number of multiplications as Left-to-Right, but requires a bit more storage. Both are used in practice: the paper shows that the Libgcrypt crypto library uses the Left-to-Right method (and hence they provide an attack against this implementation).

One way to think about it is that if you want to compute x^25, you would convert the exponent 25 into binary, manipulate this bitstring in some way (depending on whether you are going Left-to-Right or Right-to-Left, and also on the size of your window w), and then parse the bitstring: for every non-zero bit, perform a multiply; for every zero bit, perform a square (or something to that effect)

In this manipulated bitstring in the Right-to-Left method, due to the way the bitstring is created, we are guaranteed to have w - 1 zero bits after a non-zero bit. From a leakage point of view, this doesn't provide much information.

However, in the Left-to-Right method, two non-zero bits can be as close as adjacent. This allows us to infer certain details about the bitstring by applying certain rules to what we know (the leakage), and in some cases, working out the value of the key.

If we are able to recover >50% of the key bits this way, we can implement an efficient Heninger-Shacham attack to recover the remaining bits.

The paper was presented by Leon Groot Bruinderink, and he explained it in such a way that I found it clear to understand how the attack works, and how one would prevent against this kind of attack (not using Left-to-Right would be a start). They also contacted Libgcrypt with details of the attack, and it has been fixed in version 1.7.8.

Aside from the papers, CHES has been pretty amazing: the venue was a 5 star hotel in the centre of Taipei, the food was absolutely incredible (even the banquet, which introduced me to the wonders of sea cucumber), and the excursion to the Taipei Palace Museum was exceptionally educational (which as we all know is the best kind of fun).

I would definitely recommend CHES to anyone interested in the more practical side of cryptography, although if it ever takes place in Taiwan again, I strongly suggest you Youtube how to use chopsticks. Unfortunately I never learnt, and after a humiliating trip to the ShiLin Night Market, am now featured on several locals' phones in a video named 'The Tourist who couldn't eat Beef Noodle Soup'.