Paper 2020/1325

On Self-Equivalence Encodings in White-Box Implementations

Abstract

All academic methods to secure software implementations of block ciphers against adversaries with full control of the device have been broken. Despite the huge progress in the cryptanalysis of these white-box implementations, no recent progress has been made on the design side. Most of the white-box designs follow the CEJO framework, where each round is encoded by composing it with small random permutations. While several generic attacks have been proposed on the CEJO framework, no generic analysis has been performed on self-equivalence encodings, a different design where only the affine layer of each round is encoded with random self-equivalences of the S-box layer, that is, affine permutations commuting with the non-linear layer. In this work, we analyse the security of white-box implementations based on self-equivalence encodings for a broad class of SPN ciphers. First, we characterize the self-equivalence groups of S-box layers, and we prove that all the self-equivalences of a cryptographically strong S-box layer have a diagonal shape. Then, we propose the first generic attack on self-equivalence encodings. Our attack, based on affine equivalence problems, identifies the connection between the security of self-equivalence encodings and the self-equivalence structure of the cipher components. While we show that traditional SPN ciphers with cryptographically strong S-box layers cannot be secured with self-equivalence encodings, our analysis shows that self-equivalence encodings resist the generic attack if the cipher components satisfy several conditions, revealing the potential of self-equivalence encodings to secure other types of ciphers.