Cryptology ePrint Archive: Report 2003/205

Improved Cryptanalysis of SecurID

Scott Contini and Yiqun Lisa Yin

Abstract: SecurID is a widely used hardware token for strengthening authentication in a corporate environment. Recently, Biryukov, Lano, and Preneel presented an attack on the alleged SecurID hash function~\cite{BLP}. They showed that {\it vanishing differentials} -- collisions of the hash function -- occur quite frequently, and that such differentials allow an attacker to recover the secret key in the token much faster than exhaustive search. Based on simulation results, they estimated that given a single 2-bit vanishing differential, the running time of their attack would be about $2^{48}$ full hash operations.

In this paper, we first give a more detailed analysis of the attack in~\cite{BLP} and present several techniques to improve it significantly. Our theoretical analysis and implementation experiments show that the running time of our improved attack is about $2^{44}$ hash operations, though special cases involving $\ge$ 4-bit differentials (which happen about one third of the time) reduce the time further. We then investigate into the use of extra information that an attacker would typically have: multiple vanishing differentials or knowledge that other vanishing differentials do not occur in a nearby time period. When using the extra information, it appears that key recovery can always be accomplished within about $2^{40}$ hash operations.

Category / Keywords: SecurID, cryptanalysis, hash function, collision, vanishing differential

Date: received 28 Sep 2003, last revised 20 Oct 2003

Contact author: scontini at ics mq edu au

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20031021:042309 (All versions of this report)

Discussion forum: Show discussion | Start new discussion