Crypto Day 1, Session 4

The final session of today dealt with symmetric constructions and the cryptanalysis thereof. Charles Bouillaget kicked off with a talk about a special kind of attack on AES (or the AES, as some people prefer). The underlying philosophy of the attack was twofold. Firstly, it should be an attack of low data complexity, say using only four known or chosen plaintext--ciphertext pairs. Secondly, the attack should be largely automated. Concretely this meant that a tool was used that recursively exploited algebraic properties of (reduced-round) AES to find an attack as good as possible. C++ code was generated automatically to run the attack. Quite impressive.

Next up was Maria Naya-Plasencia who told us all how to improve rebound attacks. The main underlying problem was one of list merging. Given several lists L_1...L_n and some relation t, create a new list of all elements (a_1,...,a_n) in L_1 x ... x L_n for which t(a_1,...,a_n)=1 holds. In general, this will take time|L_1| x ... x |L_n|, but Maria showed that if t has a special form considerable gains can be made by a combination of divide-and-conquer and clever filtering. The new algorithms she presented subsequently lead to faster rebound attacks on some of the AES-based SHA-3 candidates.

Gregor Leander gave a very elegant talk on attacking PrintCipher. This is a lightweight blockcipher and its structure is somewhat peculiar in that it uses the same key in all of its round and it uses very small S boxes. The rather neat observation was that for a large class of weak keys there are certain bitpatterns that are invariant under the application of the round function (this is formalized as an invariant subspace). As a result, for 2^50 out of 2^80 keys, a high-probability distinguisher exists.

The program for the day was finished by Jian Guo, who introduced a new lightweight hash function based on the sponge family. An advantage of using sponges over for instance Davies--Meyer, is that it requires no feedforward (which would cost around 6 GE per bit). One funny innovation to reduce the footprint even further was the use of 'roots' of an MDS matrix. Whereas for example AES uses an MDS matrix with small entries throughout, Guo and his coauthors propose a LFSR whose step matrix A is such that A^d is MDS, allowing them to implement the MDS multiplication with fewer gates than would normally be the case.

Overall it was a fun first day!