Authentication methods and apparatus utilizing hash chains

• US 7,848,746 B2
• Filed: 06/26/2007
• Issued: 12/07/2010
• Est. Priority Date: 02/03/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Juels, Ari
• Primary Examiner(s): Harper; Vincent P
• Assistant Examiner(s): PATEL, MAHENDRA R
• Application Number:
  US11/768,608
• Publication Number:
  US 20070279227A1
• Time in Patent Office: 1,260 Days
• Field of Search: 713/168, 713/172, 713/189, 726/5, 726/9, 726/7, 726/12, 380/270, 380/258, 380/277, 380/255, 455/424
• US Class Current: 455/424
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/0492 by using a location-limited connection, e.g. near-field communication or limited proximity of entities
• CPC Class Codes: H04L 63/068 using time-dependent keys, e.g. periodically changing keys cryptographic mechanisms or cryptographic arrangements for controlling usage of secret information H04L9/088
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/0838 using one-time-passwords
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/0877 using additional device, e.g. trusted platform module [TPM], smartcard, USB or hardware security module [HSM]
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/0897 involving additional devices, e.g. trusted platform module [TPM], smartcard or USB
• 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/3228 One-time or temporary data, i.e. information which is sent for every authentication or authorization, e.g. one-time-password, one-time-token or one-time-key
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04W 12/06 Authentication
• CPC Class Codes: H04W 12/50 Secure pairing of devices

Abstract

A first processing device, which may be, for example, a wireless authentication token or an RFID tag, comprises a memory, a processor coupled to the memory, and interface circuitry coupled to the processor. The processor is operative to control the output of authentication information via the interface circuitry, where the authentication information comprises a sequence of values corresponding to images of a hash chain. A given one of the values of the sequence is utilized by a second processing device to generate a modified value suitable for providing joint authentication of the first and second processing devices.

Claims

1. A first processing device comprising:

a memory;

a processor coupled to the memory; and

interface circuitry coupled to the processor;

the processor being operative to control the output of authentication information via the interface circuitry;

wherein the authentication information comprises a sequence of values corresponding to images of a hash chain;

wherein a given one of the values of the sequence is utilized by a second processing device to generate a modified value suitable for providing joint authentication of the first and second processing devices; and

wherein the sequence of values comprises a sequence of values of a hash chain c_i, where c_i^(j) denotes a j^th value in the chain such that c_i⁽⁰⁾ represents a head of the chain, and wherein for a specified one-way function ƒ

, c_i^(j)=ƒ

(c_i^(j+1)).

2. The first processing device of claim 1 wherein said first processing device comprises an authentication token.

3. The first processing device of claim 2 wherein said authentication token comprises a wireless authentication token.

4. The first processing device of claim 1 wherein the hash chain c_i is associated with a given time-based or event-based epoch i.

5. The first processing device of claim 1 wherein said first processing device is configured to encrypt the given value of the sequence prior to outputting said value.

6. The first processing device of claim 5 wherein said value is encrypted utilizing a secret key shared by the first and second processing devices.

7. The first processing device of claim 4 wherein the modified value is generated using a private key SK⁽ⁱ⁾ of a key pair established for epoch i.

8. The first processing device of claim 7 wherein a certificate Γ

_i utilized with the modified value to provide joint authentication of the first and second processing devices contains a public key PK⁽ⁱ⁾ of the key pair as well as the head c_i⁽⁰⁾ of the hash chain c_i.

9. The first processing device of claim 8 wherein the modified value comprises a corresponding value c_i^(j) of the hash chain c_i signed using the private key SK⁽ⁱ⁾ of the key pair.

10. The first processing device of claim 9 wherein the modified value is verifiable to provide joint authentication of the first and second processing devices by utilizing the public key PK⁽ⁱ⁾ of the key pair to obtain c_i^(j) and then hashing c_i^(j) j times and comparing the result against the hash chain head c_i⁽⁰⁾ as obtained from the certificate Γ

_i.

11. The first processing device of claim 4 wherein a master key pair (SK*, PK*) is utilized over W epochs, 1≦

i≦

W, to generate for each epoch i the corresponding hash chain c_i, key pair (SK⁽ⁱ⁾, PK⁽ⁱ⁾), and certificate.

12. The first processing device of claim 11 wherein the first processing device is configured to store a tail of the hash chain c_i for each epoch.

13. The first processing device of claim 11 wherein the first processing device is configured to store a master seed suitable for generating the hash chain c_i for each epoch.

14. The first processing device of claim 4 wherein the first processing device is configured to compute values in the hash chain for epoch i+1 in conjunction with outputting values in the hash chain for epoch i.

21. The method of claim 1 wherein the hash chain c_i is of length d such that c_i^(d) represents a tail of the chain.

15. A method for use in a first processing device, the method comprising the step of:

outputting from the first processing device authentication information comprising a sequence of values corresponding to images of a hash chain;

wherein a given one of the values of the sequence is utilized by a second processing device to generate a modified value suitable for providing joint authentication of the first and second processing devices; and

wherein the sequence of values comprises a sequence of values of a hash chain c_i, where c_i^(j) denotes a j^th value in the chain such that c_i⁽⁰⁾ represents a head of the chain, and wherein for a specified one-way function ƒ

, c_i^(j)=ƒ

(c_i^(j+1)).

16. An article of manufacture comprising a computer-readable storage medium storing one or more software programs which when executed by a processor implement the step of the method of claim 15.

17. A processing device comprising:

a memory;

a processor coupled to the memory; and

interface circuitry coupled to the processor;

the processor being operative to receive authentication information generated by another processing device, the authentication information comprising a sequence of values corresponding to images of a hash chain;

wherein the processor is further operative to generate from a given one of the values of the sequence a modified value suitable for providing joint authentication of the processing devices; and

wherein the sequence of values comprises a sequence of values of a hash chain c_i, where c_i^(j) denotes a j^th value in the chain such that c_i⁽⁰⁾ represents a head of the chain, and wherein for a specified one-way function ƒ

, c_i^(j)=ƒ

(c_i^(j+1)).

18. A method for use in a processing device, the method comprising the steps of:

receiving authentication information generated by another processing device, the authentication information comprising a sequence of values corresponding to images of a hash chain; and

generating from a given one of the values of the sequence a modified value suitable for providing joint authentication of the processing devices;

wherein the sequence of values comprises a sequence of values of a hash chain c_i, where c_i^(j) denotes a j^th value in the chain such that c_i⁽⁰⁾ represents a head of the chain, and wherein for a specified one-way function ƒ

, c_i^(j)=ƒ

(c_i^(j+1)).

19. An article of manufacture comprising a computer-readable storage medium storing one or more software programs which when executed by a processor implement the steps of the method of claim 18.

20. An authentication system comprising:

at least first and second processing devices each comprising a processor and a memory; and

an authentication element;

wherein the first processing device is operative to output authentication information comprising a sequence of values corresponding to images of a hash chain;

wherein a given one of the values of the sequence is utilized by the second processing device to generate a modified value suitable for providing joint authentication of the first and second processing devices by the authentication element; and

wherein the sequence of values comprises a sequence of values of a hash chain c_i, where c_i^(j) denotes a j^th value in the chain such that c_i⁽⁰⁾ represents a head of the chain, and wherein for a specified one-way function ƒ

, c_i^(j)=ƒ

(c_i^(j+1)).