Crypto 2016: Provable Security for Symmetric Cryptography

On the morning that the CAESAR competition entered its third round, track A of CRYPTO 2016 begin with a session on provable security for symmetric cryptography. It contained 5 talks, all of which were very well presented. In each case the results were given in context, along with a sketch of the key techniques behind their proofs, and very clear diagrams.

First up was Viet Tung Hoang, presenting joint work with Stefano Tessaro on the multi-user security of Key-alternating Ciphers. Key Alternating Ciphers can be seen as a generalisation of the Evan-Mansour construction, and are a natural idealisation of the AES design.  Often work is done in the single-user setting, leaving multi-user security to be reaching via a hybrid argument. However, this leads to a reduction in security linear in the number of users.

The speaker explained two ways in which their work improves upon the previous techniques for applying the H-coefficient techinque to bound adversarial advantages using the statistical distance between possible sets of transcripts, allowing them to achieve tighter bounds.would have possible previously. They termed the first of these the "Expectation Method", where they replace an upper bound with an expected value bound to significantly improve the tightness of one of the internal bounds (specifically, when one is measuring the total probability of an adversary being able to distinguish the systems from a good transcript), while the second is a tightening of the hybrid (by pushing the hybridisation step back to the transcript stage rather than waiting until the final bound has been collected).  These are both very neat observations, and it will be interesting to see how easily they can be applied to other related problems.

Next, Yannick Seurin gave the first of his two talks, on the Counter-in-Tweak (CTRT) mode for bootstrapping AE from a TBC, based on joint work with Thomas Peyrin.  In this work, the authors set out to construct an AE scheme that was:

• Beyond-Birthday-Bound Secure in the nonce-respecting case
• Birthday-bound secure in the nonce-abusing case

They do so using a generic-composition style approach, demonstrating that a slight variant of SIV mode can be used to combine an encryption and an authentication mechanism that each meet these security requirements such that their composition inherits this security.  For their result, an encryption routine is required that takes both a random IV and a nonce. To get this, Yannick explained how one can use a Tweakable Block Cipher to improve upon the classic counter mode, by instead putting the counter into the tweak.  Thus their scheme uses a counter (in the tweak) that is initialised with a random IV to encrypt the nonce, security of which is proven using a neat little balls-and-bins game.

After a short break, Bart Mennink introduced the XPX construction.  His construction generalises single-round most tweakable Even-Mansour constructions by considering them all as being equal to the TBC

\[ \begin{array}{cccccccc} & t_{11}K \oplus t_{12}P(K) & & t_{21}K \oplus t_{22}P(K) \\ & \downarrow & & \downarrow \\ m & \to \oplus \to & P & \to \oplus \to & c \\ \end{array} \]

 under certain sets of tweaks $(t_{11},t_{12},t_{21},t_{22}) \in \mathcal{T}$ (apologies for the terrible diagram!). After describing conditions for such Tweak sets to be weak (ie, totally insecure), he explains that all other sets are in fact reasonably secure.  Developing this further, the work then investigates certain forms of related key security, and the conditions one must impose on the tweak set to achieve these.  Bart then explained how these results apply to some preexisting schemes, recovering the security of the CAESAR candidates MinAlpha and Prost-COPA (for which the work also demonstrates a certain degree of related key security).  Finally, he showed how these results can be applied to the Chaskey MAC algorithm, and suggested a possible modification that would (at the cost of slightly more expensive key rotation) provide some related key security, a method that might also be applicable to sponge-based schemes.

The penultimate talk was on "Indifferentiability of 8-Round Feistel Networks" by
Yuanxi Dai describing his work with John Steinberger.  It is next in a long line of papers seek to best describe the extent to which one can substitute a Fiestel network in for a random permutation, even when the adversary has access to the internal functions.  The presentation was well delivered and described the overall intuition behind the proof, and the design of their simulator, but the details of such results are generally very complicated indeed.

Finally, Yannick Seurin returned to describe "EWCDM", a block-cipher based MAC construction that one could use to more efficiently instantiate the CTRT mode described previously, based on joint research with Benoît Cogliati, which looks something like:

\[ \begin{array}{cccccccc} & & & & N & \to & \downarrow \\ & & & & \downarrow & & \downarrow \\ & & & & E_{k_1} & & \downarrow \\ & & & & \downarrow & & \downarrow \\ M&\to&\text{Hash} & \to & \oplus & \leftarrow & \leftarrow \\ & & & & \downarrow & & \\ & & & & E_{k_2} & & \\ & & & & \downarrow & & \\ & & & & T & & \\ \end{array} \]

  It is secure up to ~$2^{n/2}$ queries under nonce-reuse, and achieves security for $2^{2n/3}$ queries in the nonce-respecting setting.  Moreover, for the nonce-respecting case the actual security level might be even better, since the best known attack in the currently sits at around $2^{n}$ queries, leaving scope for further research.