Eurocrypt 2016: Message Authentication Codes

Of the many sessions of EuroCrypt 2016, one of the most interesting was on Message Authentication  Codes (MACs). Chaired by Peter Gazi, the session was somewhat different from many provable security sessions in that it focused on better understanding the security of two schemes already in existence (and use).  In each case, the MAC in question is constructed through a mode-of-operation on top of an ideal primitive. This seems to be part of a trend at the moment: a number of recent papers on modes-of-operation papers have been written to tighten the security bounds of known schemes[1].

First up, Stefano Tessaro presented joint work with Mihir Bellare and Dan Bernstein [2] on the security of the MAC function used in the Ed25519 deterministic signature scheme, which they term AMAC (for Augmented MAC). AMAC can be thought of as a simplified version of using HMAC with an MD-based hash function, in which we replace the outer keying with a public output transformation.
The work first generalises AMAC to describe an "Augmented Cascade" by allowing any output transformation. This surfaces a new characterisation for the compression function: a PRF-under-Out-Leakage, where Out is the output transformation in question. That is, the primitive should be secure even when the adversary is given the evaluation of Out on it's inputs (this basically corresponds to length-extension attacks).  Directly targeting multi-user security of the overall scheme (rather than relying on a hybrid argument), they provide a reduction from the from the multi-user augmented cascade to the multi-user PRF-under-Out-leakage security of the compression function.
The work then demonstrates that (in the ideal model) this bound is small, and in doing so deduces the security of the cascade, which directly implies security of AMAC.  It was observed that bound was better than one would have by simply calculating single-user security and applying a hybrid argument.


The second talk of the session was by Atul Luykx, who spoke about PMAC (Parallelizable MAC) and its security bounds [3], based on work with Bart Preneel, Alan Szepieniec and Kan Yasuda. Atul focussed on what a security bound actually means, and why in the concrete world (where we expect in instantiate our schemes by setting real-world parameters) we should be careful about needlessly loose security proofs.  For example, he showed how, if one wishes to have reasonable level of confidence that an adversary cannot create a forgery yet use a small block cipher, birthday bound security can end up as low as a single-digit number of queries.
With this in mind, we looked at the security landscape for first EMAC (encrypted CBC MAC) and then PMAC through a graph of number of queries against maximum query length, with the various security bounds drawn in.  With generic attacks taking out large sectors of each graph, it was still clear that the attacks and bounds did not meet, and the paper focusses on whether these proofs can be modified to be independent of query length. The paper explains how this length-dependence is heavily dependent on the type of masking used internally, and this leads to the main conclusions. The most relevant of these for the real world is that using a Gray code to generate the masks leads to a length-dependent attack.


[1] See for example these papers from FSE.
[2] https://eprint.iacr.org/2016/142.pdf
[3] https://eprint.iacr.org/2016/185.pdf