TY - JOUR AU - Derbez, Patrick AU - Fouque, Pierre-Alain AU - Lambin, Baptiste AU - Minaud, Brice PY - 2018/08/14 Y2 - 2024/03/28 TI - On Recovering Affine Encodings in White-Box Implementations JF - IACR Transactions on Cryptographic Hardware and Embedded Systems JA - TCHES VL - 2018 IS - 3 SE - Articles DO - 10.13154/tches.v2018.i3.121-149 UR - https://tches.iacr.org/index.php/TCHES/article/view/7271 SP - 121-149 AB - <p>Ever since the first candidate white-box implementations by Chow <em>et al</em>. in 2002, producing a secure white-box implementation of AES has remained an enduring challenge. Following the footsteps of the original proposal by Chow <em>et al.</em>, other constructions were later built around the same framework. In this framework, the round function of the cipher is “encoded” by composing it with non-linear and affine layers known as encodings. However, all such attempts were broken by a series of increasingly efficient attacks that are able to peel off these encodings, eventually uncovering the underlying round function, and with it the secret key.<br>These attacks, however, were generally ad-hoc and did not enjoy a wide applicability. As our main contribution, we propose a generic and efficient algorithm to recover affine encodings, for <em>any</em> Substitution-Permutation-Network (SPN) cipher, such as AES, and <em>any</em> form of affine encoding. For AES parameters, namely 128-bit blocks split into 16 parallel 8-bit S-boxes, affine encodings are recovered with a time complexity estimated at 2<sup>32</sup> basic operations, independently of how the encodings are built. This algorithm is directly applicable to a large class of schemes. We illustrate this on a recent proposal due to Baek, Cheon and Hong, which was not previously analyzed. While Baek <em>et al.</em> evaluate the security of their scheme to 110 bits, a direct application of our generic algorithm is able to break the scheme with an estimated time complexity of only 2<sup>35</sup> basic operations.<br>As a second contribution, we show a different approach to cryptanalyzing the Baek <em>et al.</em> scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity 2<sup>31</sup>. We also provide an implementation of the attack, which is able to recover the secret key in about 12 seconds on a standard desktop computer.</p> ER -