Dagstuhl Symmetric Cryptography Seminar

Last week the by now traditional January retreat on symmetric cryptography took place in Schloss Dagstuhl. The intention is to have a retreat there every other year, with a sibling retreat in Luxembourg in the odd years in January. I had been to the past two Luxembourg events, but this was the first time I had the honour and pleasure to visit Dagstuhl. Recently there has been a real boom in security and cryptography there, as for some this symmetric crypto seminar was the fourth opportunity in the last half year to visit (earlier crypto-related workshops were on Verifiable Elections and the Public, quantum cryptanalysis, public key cryptography, secure computing in the cloud, and Privacy and Security in Smart Energy Grids).

I had heard a lot about Dagstuhl (and its mathematical cousin Oberwolfach) in the past, so I was quite excited about going. The organizers had done a sterling job in picking a good mix of cryptographers, so that symmetric crypto could be covered from all relevant angles. The program was representative of this and what I really liked was the blend of presentations: there was work in various stages of the lifecycle (recently published work, accepted work awaiting publication, submitted work, and work still very much in progress); there were slick powerpoint/beamer presentations as well as black board presentations (prepared or impromptu); and the topics represented the attendees well.

The first day was my own talk which, due to poor planning on my part, meant skipping the first session. In this session Kenny Paterson talked about his Asiacrypt'11 paper with Tom Ristenpart and Tom Shrimpton on some recent attacks on and proofs for the TLS record protocol. While I missed this particular talk, Kenny and Tom S. had discussed the problem with me in the past. The attack is quite cute and the proof I've been told is somewhat subtle, so I am looking forward to a full version of the paper with all the details. Another talk of the morning session was by John Steinberger. He gave a blackboard talk on an upcoming Eurocrypt paper and the buzz afterwards was absolutely astounding, so I was quite bummed to have missed his talk.

In the afternoon, the talk that probably stood out most was that by Dan Bernstein on authenticated ciphers. The main thrust of his talk was that, with the SHA-3 competition soon coming to a close, cryptographers would need a new target to focus on. His suggestion was to start a competition for an authenticated cipher design and his choice was well motivated: it allowed innovations in both modes-of-operations and in primitives, moreover most symmetric primitives known to man could potentially be brought into the fold. There was a later discussion on Wednesday, where several criticisms were raised. Orr Dunkelman suggested it was too soon for such a competition: it is a commonly held belief that the SHA-3 competition drew attention away from SHA-1 and SHA-2 and perhaps it was time for a break from competitions to reevaluate the current crop of primitives. Some suggested the competition was too broad and should focus more (e.g. on just MACs), whereas others held that widening the scope and looking at secure channels (or storage) might be a better approach. Yet overall the feeling for Dan's initiative was positive. There is an ECRYPT II workshop on authenticated ciphers in July which will undoubtedly lead to a clearer view of how an AEAD competition could look like.

On Tuesday the afternoon was reserved for a wonderful hike. In the morning Alex Biryukov talked about Cesar, which was an acronym for a very large scale AES cracker based on related keys. He had computed the absolutely staggering costs of a machine to recover an AES key. The number of chips required was so large, that current production facilities would be a serious bottleneck. As a remedy, Alex had included the cost of building several 1 billion dollar fabs into his estimates. I was a bit disappointed that he did not compute the cost of the power plants needed to power his device (as running the attack consumed around the same amount of energy as the entire USA in a year).

The second talk of the morning was a wonderful talk by Itai Dinur, Orr Dunkelmann and Adi Shamir on multiple results on multiple encryption. Adi started by laying out the problem and wetting our appetite. Orr followed up by giving the details of the algorithms they had discovered, assisted from the sidelines by Adi. Finally Itai demonstrated the generality of their approach by giving a to me quite surprising application to another problem, improving on certain tradeoffs recently established in the literature.

I also really enjoyed Gregor Leander's talk, which dealt with the rigour displayed in linear cryptanalysis papers. For these results, dependent bits are often treated as if they were independent, which renders all results heuristic, and possibly wrong (as one cannot easily check whether (say) a 2126.42 attack really has the advertised running time). There are various attempts in the literature to tackle this lack of formalism. As Gregor explained:

• The authors ignore the issue altogether.


• The authors acknowledge the issue, and continue as before.


• The authors acknowledge the issue, assume the bits are independent (even though they clearly are not), and continue as before.


• The authors acknowledge the issue, assume the bits behave as if independent (where the behaviour can be restricted to that relevant for the attack), and continue as before


• As above, but with experimental back up that the behaviour is as expected for small parameters.

It did put a smile on my face, in no small part due to Gregor's wonderful delivery. He also had a more serious continuation, where he showed three completely distinct counterexamples to a related lemma by Daemen and Rijmen, who tried to give sufficient conditions for a formal treatment of linear biases.