Cryptanalysis of a white-box SM4 implementation based on collision attack

White-box cryptography is to primarily protect the key of a cipher from being extracted in a white-box scenario, where an adversary has full access to the execution environment of software implementation. Since the introduction of white-box cryptography, a number of white-box implementations of the Chinese SM4 block cipher standard have been proposed, and all of them have been attacked based on Billet et al.’s attack. In this study, we show that collision-based attack can work more efficiently on Shi et al.’s white-box SM4 implementation than the previously published attacks, by devising an attack with a time complexity of (Formula presented.), significantly reducing the previously known time complexity of (Formula presented.) to a very practical level. Our attack can also be similarly applied to some other white-box SM4 implementations.