Cryptology ePrint Archive: Report 2019/013

Combined Full Collision Attack: Pushing the Limits of Exhaustible Key Spaces

Changhai Ou and Siew-Kei Lam and Guiyuan Jiang

Abstract: Recovering keys efficiently from very deep candidate space is a very important but challenging issue in Side-Channel Attacks (SCA). State-of-the-art combined collision attacks extract specific collisions from the outputs of a divide-and-conquer attack and an analytical attack, thus reducing the large guessing spaces to much smaller collision spaces. However, the inefficient chain detection makes them time-consuming. The very limited collisions exploited and very different performance of two combined attacks also prevent their application in much deeper spaces. In this paper, we propose a Minkowski Distance enhanced Collision Attack (MDCA) with performance close to Template Attack (TA), thus making their combination more practical and meaningful. Moreover, we build a more advanced combined collision attack named Combined Full Collision Attack (CFCA) from TA and MDCA to fully exploit collisions. We further incorporate guessing theory into CFCA to enable the determination of suitable thresholds and optimize search orders of sub-keys. Finally, to set the thresholds as small as possible while guaranteeing a high success probability of key recovery, we propose Block based Fault-Tolerant CFCA (BFT-CFCA). We further exploit the Fault-Tolerant Vector (FTV) to provide a reference for its chain space adjustment. Experimental results show that BFT-CFCA notably outperforms the existing methods and CFCA.

Category / Keywords: implementation / CFCA, BFT-CFCA, MDCA, collision attack, divide and conquer, key enumeration, side-channel attack

Date: received 5 Jan 2019, last revised 18 Dec 2019

Contact author: chou at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20191218:101125 (All versions of this report)

Short URL: ia.cr/2019/013


[ Cryptology ePrint archive ]