Paper 2019/690

The Art of Guessing in Combined Side-Channel Collision Attacks

Changhai Ou and Siew-Kei Lam and Guiyuan Jiang

Abstract

Recent combined collision attacks have shown promising results for exploiting side-channel leakage information from both divide-and-conquer and analytical distinguishers. However, divide-and-conquer distinguishers used such as Correlation Power Analysis (CPA) cannot directly provide the success probability of attack which impedes effective threshold setting for determining the candidate space. In particular, they uniformly demarcate the thresholds for all sub-keys, which restricts the candidate space that is able to be analyzed and increases the attack difficulty. Moreover, the existing works mainly focus on improving collision detection algorithms, and lacks theoretical basis. Finally, the inadequate use of collision information and backward fault-tolerant mechanism of existing schemes lead to low attack efficiency. To overcome these problems, this work first introduces guessing theory into Template Attack (TA) to facilitate the estimation of success probability and the corresponding complexity of key recovery. We also extend Multiple-Differential Collision Attack (MDCA) to a new combined collision attack named Multiple-Differential Combined Collision Filter (MDCCF), which achieves the multiple-differential voting mechanism via two levels: Distinguisher Voting (DV) and Collision Voting (CV). DV exploits the information from CPA, TA and Correlation enhanced Collision Attack (CCA) to filter the candidates of TA that fall within a threshold. CV further applies differential voting on the selected sub-keys with the smallest number of candidates to vote other sub-keys. The experimental results show that the proposed MDCCF significantly improves key ranking, reduces the candidate space and lowers the complexity of collision detection, without compromising on the success probability of attacks.