Paper 2017/255

New Limits for AES Known-Key Distinguishers

Lorenzo Grassi and Christian Rechberger

Abstract

Known-key distinguishers have been introduced to better understand the security of block ciphers in situations where the key can not be considered to be secret. 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 known-key model of Gilbert (proposed at Asiacrypt 2014) allows to consider two 4-round distinguishers combined in an inside-out fashion (8 core rounds), and to extend it by one round in each direction (two extension rounds). The resulting 10-round distinguisher has a time complexity of $2^{64}$. In that work, arguments were put forward suggesting that two extension rounds seems to be the limit in the known-key model, and that likely only a distinguisher that exploits the balance property can be extended in such way. In this paper we disprove both these 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 to improve all the known-key distinguishers currently present in literature for AES up 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 an 8-round known-key distinguisher by two rounds in each direction (four extension rounds). The time complexity is $2^{82}$. We conclude with a discussion on why it seems not feasible to set up similar distinguishers on 14 rounds exploiting the same strategy.