Paper 2019/013

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

Changhai Ou, Siew-Kei Lam, and Guiyuan Jiang

Abstract

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.