Affine Equivalence-Based Key-Recovery Attacks on White-Box Implementations of the SM4 Block Cipher

The SM4 block cipher has a generalised Feistel structure with four 32-bit branches and a 128-bit user key, which is a Chinese national standard and an ISO international standard. Following Chow et al.’s seminal work of white-box cryptography in 2002, a few white-box SM4 implementations with external encodings have been proposed since 2009, among which, except the one using linear internal encodings, all the others (i.e. the ones using affine internal encodings) are regarded as (practically) secure against key-recovery attack so far, partially because secret constant parts from affine encodings hinder some attack methods under Feistel structure, like algebraic and affine equivalence attacks, though several published attacks recovered a masked key with such constants, while by contrast all published white-box AES implementations have been practically broken mainly with such attack methods. As a consequence, one may think that Feistel structure is better than SPN structure in terms of their security on white-box cryptography. In this paper, we apply Derbez et al.’s affine equivalence algorithm to the generalised Feistel cipher SM4, and give an affine equivalence-based attack framework to recover the original user key of these white-box SM4 implementations with a very practical complexity of about t²·2³² for affine encodings or t·2²⁷ for linear encodings (with t being a small integer 1 or 2), by exploring implementation particulars and exploiting a differential meet-in-the-middle approach and the SM4 key expansion formula to filter out a few secret parameters. Finally, as examples, we apply this framework to recover the original user key of Xiao and Lai’s and Bai and Wu’s white-box SM4 implementations for the first time, with a time complexity of 2³² and 2³⁴ respectively, and to recover the original user key of Shi et al.’s white-box SM4 implementation with a time complexity of 2²⁷, significantly lower than the previous attack complexity of 2⁴⁹. Our work shows how to apply Derbez et al.’s affine equivalence algorithm to a Feistel cipher and all such white-box SM4 implementations are not practically secure like white-box AES, and designers of white-box implementations of Feistel ciphers should pay attention to this framework.