Enhanced Differential Cache Attacks on SM4 with Algebraic Analysis and Error-Tolerance

Block ciphers with Feistel structures are vulnerable to a specific type of cache attacks named differential cache attacks. The attacks leverage side-channel leakages from cache and differential property of cipher component to reveal the master key of cipher. In this paper, we combine the algebraic analysis to enhance the attacks, and propose a novel method named Algebraic Differential Cache Attack (ADCA). By converting both cipher and cache leakages to algebraic equations, ADCA can reveal the cipher key automatically with the help of the SAT solver, which allows the analysis on much deeper rounds and makes a considerable reduction in attack complexity. When it is applied to the block cipher SM4, 10 plaintexts are enough to reveal the master key in 8-rounds analysis, while the traditional differential cache attack needs 20 ones. Finally, to eliminate the impact from noise, an error-tolerant method is proposed to deduce cache events from the leakage traces. It vastly enhances the robustness of attack, and makes the attack more practical. The experimental results show that the error-tolerant ADCA can correctly reveal the master key even when the uncertainty rate of cache events reaches to 60%.