Paper 2019/013

Full Collision Attack: Pushing the Limits of Exhaustible Key Spaces

Changhai Ou and Siew-Kei Lam

Abstract

Recovering keys efficiently from far beyond exhaustible candidate spaces is a meaningful but very challenging topic in Side-Channel Attacks (SCA). Recent methods often utilize collision optimizations to reduce the key candidate space so that exhaustive search methods can be feasibly applied for key recovery. However, the current collision optimization methods can only utilize information of a small number of collisions, which limits the number of wrong key candidates that can be removed. In addition, their application is restricted to situations where only small thresholds can be applied. As such, the existing methods are not feasible for recovering the full key if sub-keys and collision values are located in much deeper spaces as we will discuss in this paper. To overcome these problems, we propose Full Collision Attack (FCA). Compared to the existing methods, FCA makes use of all possible collisions between any two sub-keys and removes a larger number of wrong key candidates, thus enabling key recovery in much deeper spaces. Moreover, we find that the collision values that fall beyond the threshold usually occurs only for a few sub-keys. Based on this finding, we propose the Rotational Error Tolerant FCA (RET-FCA) to significantly reduce the candidate space of collisions. Our results show that RET-FCA performs favourably when the collision values fall in the intractable space of FCA.