Paper 2021/1028

Structural Attack (and Repair) of Diffused-Input-Blocked-Output White-Box Cryptography

Claude Carlet, Sylvain Guilley, and Sihem Mesnager

Abstract

In some practical enciphering frameworks, operational constraints may require that a secret key be embedded into the cryptographic algorithm. Such implementations are referred to as White-Box Cryptography (WBC). One technique consists of the algorithm's tabulation specialized for its key, followed by obfuscating the resulting tables. The obfuscation consists of the application of invertible diffusion and confusion layers at the interface between tables so that the analysis of input/output does not provide exploitable information about the concealed key material. Several such protections have been proposed in the past and already cryptanalyzed thanks to a complete WBC scheme analysis. In this article, we study a particular pattern for local protection (which can be leveraged for robust WBC); we formalize it as DIBO (for Diffused-Input-Blocked-Output). This notion has been explored (albeit without having been nicknamed DIBO) in previous works. However, we notice that guidelines to adequately select the invertible diffusion $\phi$ and the blocked bijections $B$ were missing. Therefore, all choices for $\phi$ and $B$ were assumed as suitable. Actually, we show that most configurations can be attacked, and we even give mathematical proof for the attack. The cryptanalysis tool is the number of zeros in a Walsh-Hadamard spectrum. This ``spectral distinguisher'' improves on top of the previously known one (Sasdrich, Moradi, G{ü}neysu, at FSE 2016). However, we show that such an attack does not work always (even if it works most of the time). Therefore, on the defense side, we give a straightforward rationale for the WBC implementations to be secure against such spectral attacks: the random diffusion part $\phi$ shall be selected such that the rank of each restriction to bytes is full. In AES's case, this seldom happens if $\phi$ is selected at random as a linear bijection of $\F_2^{32}$. Thus, specific care shall be taken. Notice that the entropy of the resulting $\phi$ (suitable for WBC against spectral attacks) is still sufficient to design acceptable WBC schemes.