On Recovering Affine Encodings in White-Box Implementations. / Derbez, Patrick; Fouque, Pierre-Alain; Lambin, Baptiste; Minaud, Brice.

In: TCHES, Vol. 2018, No. 3, 14.08.2018, p. 121-149.

Research output: Contribution to journalArticlepeer-review

Published

Standard

On Recovering Affine Encodings in White-Box Implementations. / Derbez, Patrick; Fouque, Pierre-Alain; Lambin, Baptiste; Minaud, Brice.

In: TCHES, Vol. 2018, No. 3, 14.08.2018, p. 121-149.

Research output: Contribution to journalArticlepeer-review

Harvard

Derbez, P, Fouque, P-A, Lambin, B & Minaud, B 2018, 'On Recovering Affine Encodings in White-Box Implementations', TCHES, vol. 2018, no. 3, pp. 121-149. https://doi.org/10.13154/tches.v2018.i3.121-149

APA

Vancouver

Author

Derbez, Patrick ; Fouque, Pierre-Alain ; Lambin, Baptiste ; Minaud, Brice. / On Recovering Affine Encodings in White-Box Implementations. In: TCHES. 2018 ; Vol. 2018, No. 3. pp. 121-149.

BibTeX

@article{c957cf9a75a14ea2b043c98cdc9410bb,
title = "On Recovering Affine Encodings in White-Box Implementations",
abstract = "Ever since the first candidate white-box implementations by Chow et al. in 2002, producing a secure white-box implementation of AES has remained an enduring challenge. Following the footsteps of the original proposal by Chow et al., 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.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 any Substitution-Permutation-Network (SPN) cipher, such as AES, and any 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^32 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 et al. 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^35 basic operations.As a second contribution, we show a different approach to cryptanalyzing the Baek et al. scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity 2^31. 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.",
keywords = "White-Box Cryptography, Cryptanalysis, AES",
author = "Patrick Derbez and Pierre-Alain Fouque and Baptiste Lambin and Brice Minaud",
year = "2018",
month = aug,
day = "14",
doi = "10.13154/tches.v2018.i3.121-149",
language = "English",
volume = "2018",
pages = "121--149",
journal = "TCHES",
number = "3",

}

RIS

TY - JOUR

T1 - On Recovering Affine Encodings in White-Box Implementations

AU - Derbez, Patrick

AU - Fouque, Pierre-Alain

AU - Lambin, Baptiste

AU - Minaud, Brice

PY - 2018/8/14

Y1 - 2018/8/14

N2 - Ever since the first candidate white-box implementations by Chow et al. in 2002, producing a secure white-box implementation of AES has remained an enduring challenge. Following the footsteps of the original proposal by Chow et al., 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.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 any Substitution-Permutation-Network (SPN) cipher, such as AES, and any 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^32 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 et al. 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^35 basic operations.As a second contribution, we show a different approach to cryptanalyzing the Baek et al. scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity 2^31. 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.

AB - Ever since the first candidate white-box implementations by Chow et al. in 2002, producing a secure white-box implementation of AES has remained an enduring challenge. Following the footsteps of the original proposal by Chow et al., 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.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 any Substitution-Permutation-Network (SPN) cipher, such as AES, and any 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^32 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 et al. 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^35 basic operations.As a second contribution, we show a different approach to cryptanalyzing the Baek et al. scheme, which reduces the analysis to a standalone combinatorial problem, ultimately achieving key recovery in time complexity 2^31. 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.

KW - White-Box Cryptography

KW - Cryptanalysis

KW - AES

U2 - 10.13154/tches.v2018.i3.121-149

DO - 10.13154/tches.v2018.i3.121-149

M3 - Article

VL - 2018

SP - 121

EP - 149

JO - TCHES

JF - TCHES

IS - 3

ER -