Paper 2019/013

The Science of Guessing in Collision Optimized Divide-and-Conquer Attacks

Changhai Ou, Siew-Kei Lam, and Guiyuan Jiang


Recovering keys ranked in very deep candidate space efficiently is a very important but challenging issue in Side-Channel Attacks (SCAs). State-of-the-art Collision Optimized Divide-and-Conquer Attacks (CODCAs) extract collision information from a collision attack to optimize the key recovery of a divide-and-conquer attack, and transform the very huge guessing space to a much smaller collision space. However, the inefficient collision detection makes them time-consuming. The very limited collisions exploited and large performance difference between the collision attack and the divide-and-conquer attack in CODCAs also prevent their application in much larger spaces. In this paper, we propose a Minkowski Distance enhanced Collision Attack (MDCA) with performance closer to Template Attack (TA) compared to traditional Correlation-Enhanced Collision Attack (CECA), thus making the optimization more practical and meaningful. Next, we build a more advanced CODCA named Full-Collision Chain (FCC) from TA and MDCA to exploit all collisions. Moreover, to minimize the thresholds while guaranteeing a high success probability of key recovery, we propose a fault-tolerant scheme to optimize FCC. The full-key is divided into several big ``blocks'', on which a Fault-Tolerant Vector (FTV) is exploited to flexibly adjust its chain space. Finally, guessing theory is exploited to optimize thresholds determination and search orders of sub-keys. Experimental results show that FCC notably outperforms the existing CODCAs.

Available format(s)
Publication info
Preprint. MAJOR revision.
FCCfault tolerancecollision attackdivide and conquerkey enumerationside-channel attack
Contact author(s)
chou @ ntu edu sg
2020-08-13: last of 2 revisions
2019-01-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Changhai Ou and Siew-Kei Lam and Guiyuan Jiang},
      title = {The Science of Guessing in Collision Optimized Divide-and-Conquer Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2019/013},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.