What a lovely hat

Paper 2021/1586

Cryptanalysis of a Type of White-Box Implementations of the SM4 Block Cipher

Jiqiang Lu and Jingyu Li

Abstract

The SM4 block cipher was first released in 2006 as SMS4 used in the Chinese national standard WAPI, and became a Chinese national standard in 2016 and an ISO international standard in 2021. White-box cryptography aims primarily to protect the secret key used in a cryptographic software implementation in the white-box scenario that assumes an attacker to have full access to the execution environment and execution details of an implementation. Since white-box cryptography has many real-life applications nowadays, a few white-box implementations of the SM4 block cipher has been proposed with its increasingly wide use, among which a type of constructions is dominated, that use an affine diagonal block encoding to protect the original XOR sum of the three branches entering the S-box layer of a round and use its inverse to protect the original input of the S-box layer, such as Xiao and Lai's implementation in 2009, Shang's implementation in 2016 and Yao and Chen's implementation in 2020. In this paper, we show that this type of white-box SM4 constructions can be somewhat equivalent to a plain implementation mostly with Boolean masks from a security viewpoint, by devising collision-based attacks on Xiao and Lai's, Shang's and Yao and Chen's implementations with a time complexity of respectively about $2^{22}$, $2^{39}$ and $2^{22}$ to peel off most white-box operations until only Boolean masks remain. Besides, we present a collision-based attack on a white-box SM4 implementation with a time complexity of about $2^{17.1}$ to recover an original round key, which uses a linear diagonal block encoding instead of an affine diagonal block encoding. Our results show that generating such a white-box SM4 implementation with affine encodings can be simplified into generating a plain implementation with Boolean masks (if its security expectation is beyond the above-mentioned complexity), and the effect of an affine encoding is significantly better than the effect of a linear encoding in the sense of our cryptanalysis results.

Note: This is an extended version of the paper appeared in Proceedings of ISC 2021 --- The 24th Information Security Conference. In this extended version, we revised and corrected our previous cryptanalysis results and conclusions on Yao and Chen's and Xiao and Lai's white-box SM4 implementations, and gave cryptanalysis results on two other white-box SM4 implementations, namely Shang's and Wu et al.'s implementations.