International Association
for Cryptologic Research

It has been proven that the white-box ciphers with small encodings will be vulnerable to algebraic and computation attacks. By leveraging the large encodings, the self-equivalence and implicit implementations are proposed for ARXbased white-box ciphers. Unfortunately, these two types of white-box implementations are proven to be insecure under the algebraic attack. Different from algebraic attacks, computation analysis can extract the secret key from the memory access traces without software reverse engineering. It is still an open problem whether the self-equivalence and implicit implementations can resist the computation analysis.In this paper, we analyze the encoded structure of the self-equivalence/implicit whitebox ARX ciphers and discuss its resistance to the computation analysis, such as differential computation analysis (DCA) and algebraic degree computation analysis (ADCA). The results reveal that the large input, encoding, and round key can practically mitigate DCA and ADCA. To deal with the large space, we introduce a new method which is named chosen-plaintext computation analysis (CP-CA). Based on a partial key guess and deliberately chosen intermediate value, CP-CA constructs a reverse function to calculate a set of plaintexts. With the obtained plaintexts, the large affine and non-linear encodings will be reduced to a small space. Subsequently, CP-CA mounts the computation analysis on the traces to recover the secret key. Following CP-CA, we propose a CP-DCA attack and reformulate ADCA as chosen-plaintext linear encoding analysis (CP-LEA). The experimental results indicate that the selfequivalence white-box SPECK32/48/64/96/128 and implicit white-box SPECK32/64 implementations are vulnerable to CP-DCA and CP-LEA attacks.

White-box implementations aim to prevent the key extraction of the cryptographic algorithm even if the attacker has full access to the execution environment. To obfuscate the round functions, Chow et al. proposed a pivotal principle of white-box implementations to convert the round functions as look-up tables which are encoded by random internal encodings. These encodings consist of a linear mapping and a non-linear nibble permutation. At CHES 2016, Bos et al. introduced differential computation analysis (DCA) to extract the secret key from the runtime information, such as accessed memory and registers. Following this attack, many computation analysis methods were proposed to break the white-box implementations by leveraging some properties of the linear internal encodings, such as Hamming weight and imbalance. Therefore, it becomes an alternative choice to use a non-linear byte encoding to thwart DCA. At CHES 2021, Carlet et al. proposed a structural attack and revealed the weakness of the non-linear byte encodings which are combined with a non-invertible linear mapping. However, such a structural attack requires the details of the implementation, which relies on extra reverse engineering efforts in practice. To the best of our knowledge, it still lacks a thorough investigation of whether the non-linear byte encodings can resist the computation analyses.In this paper, we revisit the proposed computation analyses by investigating their capabilities against internal encodings with different algebraic degrees. Particularly, the algebraic degree of encodings is leveraged to explain the key leakage on the non-linear encodings. Based on this observation, we propose a new algebraic degree computation analysis (ADCA), which targets the mappings from the inputs to each sample of the computation traces. Different from the previous computation analyses, ADCA is a higher-degree attack that can distinguish the correct key by matching the algebraic degrees of the mappings. The experimental results prove that ADCA can break the internal encodings from degree 1 to 6 with the lowest time complexity. nstead of running different computation analyses separately, ADCA can be used as a generic tool to attack the white-box implementations.

On white-box implementations, it has been proven that differential computation analysis (DCA) can recover secret keys without time-costly reverse engineering. At CHES 2021, Seker et al. combined linear and non-linear masking protections (SEL masking) to prevent sensitive variables from being predicted by DCA. At Eurocrypt 2021, Biryukov and Udovenko introduced a public dummy shuffling construction (BU shuffling) to protect sensitive functions. In this paper, we extend higher-order DCA (HO-DCA) to higher-degree context for exploiting the vulnerabilities against the state-of-the-art countermeasures. The data-dependency HO-DCA (DDHO-DCA), which is proposed at CHES 2020, is improved to successfully recover the correct key of SEL masking. In specific, our improved DDHO-DCA can also enhance the attack result of #100 which is the third winning challenge in WhibOx 2019. Since the XOR phase plays the same role as linear masking, we prove that a specific BU shuffling is vulnerable to HO-DCA attacks. Furthermore, we demonstrate that the combination of SEL masking and the specific BU shuffling still cannot defeat our higher-degree HO-DCA and improved DDHO-DCA attacks.