NETWORK HELPER FOR AUTHENTICATION BETWEEN A TOKEN AND VERIFIERS

• US 20090282253A1
• Filed: 05/09/2008
• Published: 11/12/2009
• Est. Priority Date: 05/09/2008
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Wiggers De Vries, Miriam, Rose, Gregory Gordon, Gantman, Alexander, Paddon, Michael, Hawkes, Philip Michael
• Granted Patent: US 8,595,501 B2
• Time in Patent Office: Days
• US Class Current: 713/172
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/0853 using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234

Abstract

A network helper is provided that assists verifiers in executing a puzzle-based protocol for authentication of a token. A token stores a secret key and one or more puzzle-generating algorithms. The helper stores a plurality of puzzles associated with a particular token. When requested to do so by a verifier, the helper provides a plurality of pseudorandomly selected puzzles for the token to a verifier. The puzzles are encoded with information that is used between the verifier and token to establish a secured symmetric key. The verifier selects one or a few of the encoded puzzles and breaks them by a brute force attack. Because the helper does not know which puzzles have been selected, it has to break all puzzles to attempt to figure out the symmetric key. However, if a large number of puzzles are utilized, say millions, then breaking all of them becomes a computationally prohibitive task.

Claims

1. A method operational on a networked helper to assist a verifier in authenticating a token, comprising:

receiving a plurality of encoded puzzles associated with a token identifier from a token provisioner;

storing the plurality of encoded puzzles;

receiving a request from the verifier for puzzles associated with the token identifier during an initial authentication stage between the verifier and the token in which a symmetric key is established between the verifier and the token;

selecting a subset of the stored plurality of encoded puzzles associated with the token identifier; and

sending the selected subset of encoded puzzles to the verifier.

2. The method of claim 1, wherein an encoded puzzle is an encoded message including a puzzle identifier and a puzzle secret.

3. The method of claim 1, wherein the symmetric key between the verifier and token is based on one or more of the subset of encoded puzzles.

4. The method of claim 1, wherein the subset of the stored plurality of encoded puzzles are pseudorandomly selected by the helper.

5. The method of claim 4, further comprising:

receiving a nonce from the verifier and using the nonce to pseudorandomly select the subset of encoded puzzles.

6. The method of claim 5, further comprising:

generating proof that the subset of encoded puzzles was selected based on the received nonce; and

sending such proof to the verifier.

7. The method of claim 1 wherein the plurality of encoded puzzles is at least a million puzzles.

8. The method of claim 1, further comprising:

storing a plurality of other puzzles associated with other token identifiers.

9. A helper device for assisting a verifier in authenticating tokens, comprising:

a first communication interface having high bandwidth to a network; and

a processing circuit coupled to the first communication interface, the processing circuit configured to

receive a plurality of encoded puzzles associated with a token identifier from a token provisioner;

store the plurality of encoded puzzles;

receive a request from the verifier for puzzles associated with the token identifier during an initial authentication stage between the verifier and the token in which a symmetric key is established between the verifier and the token;

select a subset of the stored plurality of encoded puzzles associated with the token identifier; and

send the selected subset of encoded puzzles to the verifier.

10. The helper device of claim 9, further comprising:

a storage device coupled to the processing circuit for storing the plurality of puzzles.

11. The helper device of claim 9, wherein an encoded puzzle is an encoded message including a puzzle identifier and a puzzle secret.

12. The helper device of claim 9, wherein the symmetric key between the verifier and token is based on one or more of the subset of encoded puzzles.

13. The helper device of claim 9, wherein the subset of the stored plurality of encoded puzzles are pseudorandomly selected by the helper.

14. The helper device of claim 13, wherein the processing circuit is further configured to

receive a nonce from the verifier and using the nonce to pseudorandomly select the subset of encoded puzzles;

generate proof that the subset of encoded puzzles was selected based on the received nonce; and

send such proof to the verifier.

15. A helper device for assisting a verifier in authenticating tokens, comprising:

means for receiving a plurality of encoded puzzles associated with a token identifier from a token provisioner;

means for storing the plurality of encoded puzzles;

means for receiving a request from the verifier for puzzles associated with the token identifier during an initial authentication stage between the verifier and the token in which a symmetric key is established between the verifier and the token;

means for selecting a subset of the stored plurality of encoded puzzles associated with the token identifier; and

means for sending the selected subset of encoded puzzles to the verifier.

16. The helper device of claim 15, wherein an encoded puzzle is an encoded message including a puzzle identifier and a puzzle secret.

17. The helper device of claim 15, wherein the symmetric key between the verifier and token is based on one or more of the subset of encoded puzzles.

18. The helper device of claim 15, further comprising:

means for receiving a nonce from the verifier and using the nonce to pseudorandomly select the subset of encoded puzzles;

means for generating proof that the subset of encoded puzzles was selected based on the received nonce; and

means for sending such proof to the verifier.

19. A processing device, comprising:

a processing circuit configured to

receive a plurality of encoded puzzles associated with a token identifier from a token provisioner;

store the plurality of encoded puzzles;

receive a request from the verifier for puzzles associated with the token identifier during an initial authentication stage between the verifier and the token in which a symmetric key is established between the verifier and the token;

select a subset of the stored plurality of encoded puzzles associated with the token identifier; and

send the selected subset of encoded puzzles to the verifier.

20. The processing device of claim 19 wherein the processing circuit is further configured to

pseudorandomly select the subset of the stored plurality of encoded puzzles.

21. The processing device of claim 19, wherein the processing circuit is further configured to

receive a nonce from the verifier and using the nonce to pseudorandomly select the subset of encoded puzzles;

generate proof that the subset of encoded puzzles was selected based on the received nonce; and

send such proof to the verifier.

22. A machine-readable medium having one or more instructions operational on a networked helper for assisting a verifier in authenticating a token, which when executed by a processor causes the processor to:

receive a plurality of encoded puzzles associated with a token identifier from a token provisioner;

store the plurality of encoded puzzles;

receive a request from the verifier for puzzles associated with the token identifier during an initial authentication stage between the verifier and the token in which a symmetric key is established between the verifier and the token;

select a subset of the stored plurality of encoded puzzles associated with the token identifier; and

send the selected subset of encoded puzzles to the verifier.

23. The machine-readable medium of claim 22 having one or more instructions which when executed by a processor causes the processor to further:

storing a plurality of other puzzles associated with other token identifiers.

24. The machine-readable medium of claim 22, having one or more instructions which when executed by a processor causes the processor to further:

receive a nonce from the verifier and using the nonce to pseudorandomly select the subset of encoded puzzles;

generate proof that the subset of encoded puzzles was selected based on the received nonce; and

send such proof to the verifier.