Robust visual passwords

• US 7,219,368 B2
• Filed: 03/23/2001
• Issued: 05/15/2007
• Est. Priority Date: 02/11/1999
• Status: Expired due to Term

• Current Assignee: RSA Security LLC (Symphony Technology Group LLC)
• Original Assignee: RSA Security Incorporated (Symphony Technology Group LLC)
• Inventors: Juels, Ari, Frykholm, Niklas
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/815,560
• Publication Number:
  US 20020029341A1
• Time in Patent Office: 2,244 Days
• Field of Search: 713200-202, 382181-190, 340 57- 527, 726 11- 15, 726/2, 726/4, 726/17
• US Class Current: 726/2
• CPC Class Codes: G06F 21/36 by graphic or iconic representation
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 9/304 based on error correction codes, e.g. McEliece
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

Enrollment and authentication of a user based on a sequence of discrete graphical choices is described. A graphical interface presents various images and memory cues that a user may associate with their original graphical choices. Enrollment may require the input to have a security parameter value that meets or exceeds a threshold. An acceptable sequence of graphical choices is converted to a sequence of values and mapped to a sequence of codewords. Both a hash of the sequence of codewords and a sequence of offsets are stored for use in authenticating the user. An offset is the difference between a value and its corresponding codeword. Authentication requires the user to enter another sequence of discrete graphical choices that is approximately the same as original. The offsets are summed with the corresponding values before mapping to codewords. Authentication requires the sequence of codewords, or a hash thereof, to match.

Claims

1. A method for establishing a secret to authenticate a user comprising the steps of receiving a secret pattern on a graphical interface, wherein the secret pattern comprises a sequence of discrete graphical choices;

converting each discrete graphical choice in the sequence of discrete graphical choices into a value to produce a sequence of values, wherein the sequence of values corresponds to the sequence of discrete graphical choices;

for the sequence of values selecting codewords from a plurality of codewords to generate a sequence of codewords, the plurality of codewords defining an error-correcting code;

calculating an offset between each value in the sequence of values and the corresponding codeword in the sequence of codewords to generate a sequence of offsets; and

hashing the sequence of codewords to produce a hash of the sequence of codewords.

2. The method of claim 1 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected point on the graphical interface.

3. The method of claim 2 further comprising displaying an image on the graphical interface after receiving the selected point on the graphical interface, wherein each discrete graphical choice in the sequence of discrete graphical choices is associated with one of a plurality of images.

4. The method of claim 3 further comprising prompting a user by displaying one of the plurality of images on the graphical interface;

and receiving a match pattern on the graphical interface for comparison with the secret pattern, wherein the match pattern comprises a sequence of match points.

5. The method of claim 4 further comprising, during or after receiving the match pattern on the graphical interface, displaying the selected point associated with the image on the graphical interface.

6. The method of claim 5 further comprising, during or after receiving the match pattern on the graphical interface, displaying a line from a match point to the selected point associated with the image on the graphical interface.

7. The method of claim 2 further comprising providing at least one memory cue by presenting the at least one memory cue in response to a point on the image on the graphical interface being highlighted.

8. The method of claim 7 further comprising associating a first icon from a plurality of icons with a first point on the image on the graphical interface by displaying the first icon in response to the first point being highlighted;

and associating a second icon from the plurality of icons with a second point on the image on the graphical interface by displaying the second icon in response to the second point being highlighted.

9. The method of claim 2 further comprising highlighting, for each discrete graphical choice in the sequence of discrete graphical choices, a plurality of points on the graphical interface as alternative graphical choices.

10. The method of claim 1 further comprising storing the sequence of offsets for use in authenticating a user.

11. The method of claim 1 further comprising storing the hash of the sequence of codewords for use in authenticating a user.

12. The method of claim 1 wherein selecting codewords from the plurality of codewords involves for each value in the sequence of values selecting a corresponding codeword from the plurality of codewords to generate the sequence of codewords.

13. A method for authenticating a user comprising the steps of

receiving an input pattern on a graphical interface, wherein the input pattern comprises a sequence of discrete graphical choices;

converting each discrete graphical choice in the sequence of discrete graphical choices into an input value to produce a sequence of input values, wherein the sequence of input values corresponds to the sequence of discrete graphical choices;

retrieving a sequence of offsets;

summing each input value from the sequence of input values with the corresponding offset from the sequence of offsets to generate a sequence of intermediate values;

for the sequence of intermediate values selecting codewords from a plurality of codewords to generate a sequence of codewords, the plurality of codewords defining an error-correcting code;

hashing the sequence of codewords to produce a hash of the sequence of codewords; and

authenticating a user if the hash matches a stored hash.

14. The method of claim 13 further comprising, prior to authenticating, retrieving a stored hash.

15. The method of claim 13 further comprising, prior to authenticating, transmitting the hash to an authentication device.

16. The method of claim 13 wherein each input value in the sequence of input values is a binary value of fixed length.

17. The method of claim 13 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected region on the graphical interface.

18. The method of claim 13 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected point on the graphical interface.

19. The method of claim 18 further comprising displaying an image on the graphical interface after receiving the selected point on the graphical interface, wherein each discrete graphical choice in the sequence of discrete graphical choices is associated with one of a plurality of images.

20. The method of claim 18 further comprising associating an icon from a plurality of icons with a point on the graphical interface by displaying the icon when the point is highlighted.

21. The method of claim 13 wherein the graphical interface displays a fractal image.

22. The method of claim 13 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected icon from a plurality of icons on the graphical interface.

23. The method of claim 22 wherein the icon on the graphical interface represents a face.

24. The method of claim 13 further comprising allowing access to a resource in response to authenticating the user.

25. The method of claim 24 wherein allowing access to the resource comprises allowing access to at least one of a hardware device, a computer system, a portable computer, a software application, a database, and a physical location.

26. The method of claim 13 wherein selecting codewords form the plurality of codewords involves for each value in the sequence of intermediate values selecting a corresponding codeword from the plurality of codewords to generate the sequence of codewords.

27. An apparatus for establishing a secret to authenticate a user, the apparatus comprising:

a graphical interface capable of receiving graphical input, the graphical interface receiving a secret pattern as graphical input, the secret pattern comprising a sequence of discrete graphical choices;

a converter in signal communication with the graphical interface, the converter converting each discrete graphical choice in the sequence of discrete graphical choices into a value to produce a sequence of values, wherein the sequence of values corresponds to the sequence of discrete graphical choices;

a codeword generator in signal communication with the converter, the codeword generator producing a sequence of codewords by applying a decoding function of an error correcting code to the sequence of values;

an offset calculator in signal communication with the codeword generator, the offset calculator calculating an offset between each value in the sequence of values and the corresponding codeword in the sequence of codewords to generate a sequence of offsets; and

a hasher in signal communication with the codeword generator, the hasher applying a hash function to the sequence of codewords to produce a hash of the sequence of codewords.

28. The apparatus of claim 27 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected point on the graphical interface.

29. The apparatus of claim 28 further comprising a point generator in signal communication with the graphical interface, the point generator highlighting a plurality of points on the graphical interface as alternative graphical choices for each discrete graphical choice in the sequence of discrete graphical choices.

30. The apparatus of claim 29 further comprising a memory element in signal communication with the graphical interface, the memory element containing a plurality of images and a sequence of images, wherein receiving a discrete graphical choice in the sequence of discrete graphical choices triggers the graphical interface to display the next image in the sequence of images from the plurality of images contained in the memory element.

31. The apparatus of claim 30 further comprising:

a training logic element in signal communication with the graphical interface, the training logic element prompting a user to enter a match pattern upon receiving the secret pattern by causing the graphical interface to display the first image in the sequence of images, wherein the match pattern is a sequence of match points; and

a comparator in signal communication with the graphical interface, the comparator comparing the match pattern to the secret pattern.

32. The apparatus of claim 31 wherein the training logic element, during or after receiving a match point in the sequence of match points on the graphical interface, causes the graphical interface to highlight the selected point associated with the image on the graphical interface.

33. The apparatus of claim 31 wherein the training logic element, during or after receiving a match point in the sequence of match points on the graphical interface, causes the graphical interface to display a line from the match point to the selected point associated with the image on the graphical interface.

34. The apparatus of claim 27 further comprising a memory element in signal communication with the offset calculator, the memory element storing the sequence of offsets from the offset calculator for use in authenticating a user.

35. The apparatus of claim 27 wherein the memory element is in signal communication with the hasher, the memory element storing the hash of the sequence of codewords from the hasher for use in authenticating a user.

36. The apparatus of claim 27 wherein the codeword generator is adapted to produce the sequence of codewords by applying the decoding function to each value in the sequence of values.

37. An apparatus for authenticating a user, the apparatus comprising:

a graphical interface capable of receiving graphical input, the graphical interface receiving an input pattern as graphical input, the input pattern comprising a sequence of discrete graphical choices;

a converter in signal communication with the graphical interface, the converter converting each discrete graphical choice in the sequence of discrete graphical choices into an input value to produce a sequence of input values, wherein the sequence of input values corresponds to the sequence of discrete graphical choices;

a memory element in signal communication with a summer, the memory element containing a sequence of offsets;

the summer in signal communication with the converter and the memory element, the summer summing each input value from the sequence of input values with the corresponding offset from the sequence of offsets to generate a sequence of intermediate values;

a codeword generator in signal communication with the summer, the codeword generator producing a sequence of codewords by applying a decoding function of an error correcting code to the sequence of intermediate values; and

a hasher in signal communication with the codeword generator, the hasher applying a hash function to the sequence of codewords to produce a hash of the sequence of codewords for use in authenticating a user.

38. The apparatus of claim 37 further comprising a comparator in signal communication with the hasher, the comparator comparing the hash of the sequence of codewords to a stored hash and producing an authentication signal if the hash of the sequence of codewords matches the stored hash.

39. The apparatus of claim 38 wherein the authentication signal enables access to a resource.

40. The apparatus of claim 39 wherein the authentication signal enables access to at least one of a hardware device, a computer system, a portable computer, a software application, a database, and a physical location.

41. The apparatus of claim 37 further comprising a communication system in signal communication with the hasher, the communication system transmitting the hash of the sequence of codewords to an authentication device and receiving an authentication signal from the authentication device if the hash of the sequence of codewords matches the stored hash.

42. The apparatus of claim 37 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected region on the graphical interface.

43. The apparatus of claim 37 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected point on the graphical interface.

44. The apparatus of claim 37 further comprising a logic element in signal communication with the graphical interface, the logic element causing the graphical interface to display a new image in response to the graphical interface receiving a discrete graphical choice from the sequence of discrete graphical choices, wherein the sequence of discrete graphical choices corresponds to a sequence of images.

45. The apparatus of claim 37 further comprising a logic element in signal communication with the graphical interface, the logic element causing the graphical interface to display at least one memory cue in response to a point on the graphical interface being highlighted.

46. The apparatus of claim 45 wherein the logic element causes a first icon from a plurality of icons to be displayed on the graphical interface in response to a first point on the image on the graphical interface being highlighted;

and wherein the logic element causes a second icon from the plurality of icons to be displayed on the graphical interface in response to a second point on the image on the graphical interface being highlighted.

47. The apparatus of claim 37 wherein a discrete graphical choice in the sequence of discrete graphical choices comprises a selected icon from a plurality of icons displayed on the graphical interface.

48. The apparatus of claim 37 wherein the codeword generator is adapted to produce the sequence of codewords by applying the decoding function to each intermediate value in the sequence of intermediate values.

49. A method for generating a cryptographic secret from a visual password, the method comprising the steps of:

receiving a secret pattern on a graphical interface, wherein the secret pattern comprises a sequence of discrete graphical choices;

converting each discrete graphical choice in the sequence of discrete graphical choices into a value to produce a sequence of values, wherein the sequence of values corresponds to the sequence of discrete graphical choices;

for the sequence of values, selecting codewords from a plurality of codewords to generate a sequence of codewords, the plurality of codewords defining an error-correcting code;

manipulating the sequence of codewords to produce a cryptographic secret; and

calculating an offset between each value in the sequence of values and the corresponding codeword in the sequence of codewords to generate a sequence of offsets for use in regenerating the secret.

50. The method of claim 49 wherein selecting comprises applying a decoding function of an error-correcting code to the sequence of values to generate a sequence of codewords.

51. The method of claim 49 wherein manipulating comprises applying a hash function to the sequence of codewords.

52. The method of claim 49 further comprising using the cryptographic secret as an encryption key.

53. The method of claim 49 further comprising using the cryptographic secret in a digital signature algorithm or an identification algorithm.

54. The method of claim 49 wherein selecting codewords from the plurality of codewords involves for each value in the sequence of values selecting a corresponding codeword from the plurality of codewords to generate the sequence of codewords.