Paper 2017/255

New and Old Limits for AES Known-Key Distinguishers

Lorenzo Grassi and Christian Rechberger

Abstract

Known-key distinguishers have been introduced by Knudsen and Rijmen in 2007 to better understand the security of block ciphers in situations where the key can not be considered to be secret, i.e. the ``thing between secret-key model and hash function use-cases''. AES is often considered as a target of such analyses, simply because AES or its building blocks are used in many settings that go beyond classical encryption. The most recent approach of Gilbert (proposed at Asiacrypt 2014) considers 8 core rounds, and extends it by one round in each direction. The resulting approach on 10-round has a time complexity of $2^{64}$, and the best generic approach was shown to beat the proposed method with probably $<2^{-16.5}$ and is hence referred to as a ``distinguisher''. Interestingly, Gilbert's work also for the first time showed that the known-key model may not be weaker than the chosen-key model, as the best chosen-key attacks on AES only cover 9 rounds so far. This current state of affairs is unsatisfying as it contradicts the original intent of the known-key model. In this paper we pick up the work of Gilbert, further exploring the limits of the known-key model with a focus on the AES, and eventually propose a way to remedy the situation. In that work, arguments are put forward suggesting that a total of two extension rounds seem to be the limit in the known-key model, and that likely only a distinguisher that exploits the uniform distribution property can be extended in such way. We disprove both conjectures and arrive at the following results: We firstly show that the technique proposed by Gilbert can also be used to extend a known-key distinguisher based on truncated differential trails. This allows us to present improved known-key distinguishers for AES from 7 to 10 rounds of AES. In particular, we are able to set up a 9-round known-key distinguisher for AES with a time complexity of $2^{23}$ and a 10-round known-key distinguisher with a time complexity of $2^{50}$. Secondly we are also able to show that more than two extension rounds are possible. As a result of this, we describe the first known-key distinguishers on 12 rounds of AES, by extending Gilbert's 8-round known-key distinguisher by two rounds in each direction. The time complexity is $2^{66}$, and for this result we do have supporting formal arguments, similar to Gilbert, that the best generic approach to beat the proposed method has probably $<2^{-25}$. This also shows that the counter-intuitive gap between the known-key and the chosen-key model may be wider than initially thought. To remedy the situation, we propose a refinement of the known-key model which restores its original intent.

Note: Update from previous version: - Corrected description of Gilbert's distinguisher - Improved 12-round distinguisher including formal arguments against faster generic attacks - Proposing a refinements of the known-key model