Cryptanalysis of a Cognitive Authentication Scheme

• Phillippe Golle and David Wagner
• 2007 IEEE Symposium on Security and Privacy

Abstract

We present attacks against two cognitive authentication set of pictures. Our attacks use a SAT solver to re- cover a user’s secret key in a few seconds, after observ- ing only a small number of successful logins. These attacks demonstrate that the authentication schemes of [9] are not secure against an eavesdropping adversary.

Annotations

• Traditional password authentication scheme is unsafe on untrusted client (spyware/keylogger)

• Cognitive Authentication scheme is proposed in 2006 IEEE Symp. on Sec. and Pri.
  • challenge response protocols that rely on a share secret set of pictures.
  • user's secret key = a set of images.

• This paper argues this scheme is insecure against eavesdropping attacks.

• Problem: each challenge-response round leaks information about the user's key.

• Key idea: Every user's response allows the adversary to learn a boolean relationship between the bits of the user's secret key. After observing a few successful logins, these boolean relationships can easily be expressed in disjunctive normal form, which can be solved quickly by a SAT solver to recover the user's key (a unique assignment of values to the boolean variables A1......An)