International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Improved Cryptanalysis of SecurID

Authors:
Scott Contini
Yiqun Lisa Yin
Download:
URL: http://eprint.iacr.org/2003/205
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2003-11918,
  title={Improved Cryptanalysis of SecurID},
  booktitle={IACR Eprint archive},
  keywords={SecurID, cryptanalysis, hash function, collision, vanishing differential},
  url={http://eprint.iacr.org/2003/205},
  note={ scontini@ics.mq.edu.au 12346 received 28 Sep 2003, last revised 20 Oct 2003},
  author={Scott Contini and Yiqun Lisa Yin},
  year=2003
}