Cryptology ePrint Archive: Report 2021/1582

CoTree: Push the Limits of Conquerable Space in Collision-Optimized Side-Channel Attacks

Changhai Ou and Debiao He and Zhu Wang and Kexin Qiao and Shihui Zheng and Siew-Kei Lam

Abstract: By introducing collision information into side-channel distinguishers, the existing collision-optimized attacks exploit collision detection algorithm to transform the original candidate space under consideration into a significantly smaller collision chain space, thus achieving more efficient key recovery. However, collision information is detected very repeatedly since collision chains are created from the same sub-chains, i.e., with the same candidates on their first several sub-keys. This aggravates when exploiting more collision information. The existing collision detection algorithms try to alleviate this, but the problem is still very serious. In this paper, we propose a highly-efficient detection algorithm named Collision Tree (CoTree) for collision-optimized attacks. CoTree exploits tree structure to store the chains creating from the same sub-chain on the same branch. It then exploits a top-down tree building procedure and traverses each node only once when detecting their collisions with a candidate of the sub-key currently under consideration. Finally, it launches a bottom-up branch removal procedure to remove the chains unsatisfying the collision conditions from the tree after traversing all candidates (within given threshold) of this sub-key, thus avoiding the traversal of the branches satisfying the collision condition. These strategies make our CoTree significantly alleviate the repetitive collision detection, and our experiments verify that it significantly outperforms the existing works.

Category / Keywords: implementation / , CoTree, collision attack, template attack, side-channel attack, key enumeration

Date: received 2 Dec 2021

Contact author: ouchanghai at whu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20211203:075934 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]