International Association
for Cryptologic Research

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.