Challenge-response authentication of a cryptographic device

1. A method performed by a first cryptographic device, comprising:

in a registration mode of operation:

generating a set of challenges, wherein the set of challenges comprises n randomly selected multi-bit values, wherein a given one of the n randomly selected multi-bit values comprises a k-bit randomly selected value, and wherein n and k are security parameters denoting the number of challenges generated by the first cryptographic device and the length of the given challenge generated by the first cryptographic device, respectively;

sending the challenges to a second cryptographic device, the second cryptographic device comprising a key-based cryptographic module that utilizes one or more secret keys;

receiving from the second cryptographic device a set of first responses, each first response corresponding to a respective one of the challenges; and

storing information characterizing the first responses; and

in an authentication mode of operation:

sending a selected one of the challenges to the second cryptographic device;

receiving from the second cryptographic device a second response to the selected challenge; and

authenticating the second cryptographic device utilizing the second response and the stored information;

wherein the first cryptographic device generates the challenges in the registration mode of operation without having knowledge of values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device;

wherein the first responses received from the second cryptographic device are based at least in part on at least one of said one or more secret keys of the key-based cryptographic module of the second cryptographic device; and

wherein the first cryptographic device is configured to authenticate the second cryptographic device in the authentication mode of operation using the second response without having knowledge of the values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device.

2. The method of claim 1 further comprising repeating the sending of a selected one of the challenges, the receiving of a second response to the selected challenge, and the authenticating of the second cryptographic device, for each of a plurality of additional different selected ones of the challenges.

3. The method of claim 1 wherein the set of challenges comprise a set C={c i } i=1 n of n challenges and wherein the given challenge c i ε R {0,1} k is a randomly selected k-bit value.

4. The method of claim 3 wherein the first responses comprise a set of n responses R={r i } i=1 n received responsive to corresponding ones of the set of n challenges C={c i } i=1 n , where response r i =f κ (c i ) for each c i and f κ (c i ) is a function that utilizes a given one of the secret keys, denoted as secret key κ.

5. The method of claim 4 wherein the selected challenge is a challenge c j selected from the set of challenges C={c i } i=1 n based on a current counter value j, and wherein the second cryptographic device is authenticated if and only if r j ′=r j , where r j ′ is the response to the selected challenge c j .

6. The method of claim 1 wherein storing information characterizing the first responses comprises one of:

storing the first responses for use in the authentication mode of operation; and

storing information derived at least in part from the first responses but not storing the responses themselves for use in the authentication mode of operation.

7. The method of claim 1 further comprising:

initializing a counter in the registration mode of operation;

selecting the challenge in the authentication mode of operation based at least in part on a current value of the counter; and

incrementing the counter if the second cryptographic device is authenticated based on its response to the selected challenge.

8. The method of claim 1 wherein sending the given challenge to the second cryptographic device comprises directing storage of the given challenge in encrypted form on the second cryptographic device.

9. The method of claim 8 wherein the given challenge comprises a challenge c i and the given challenge in encrypted form comprises an encrypted challenge w i =Enc PK i [c i ], where PK i is a public key having a corresponding secret key SK i having a value that is unknown to the first cryptographic device.

10. The method of claim 1 wherein the challenges comprise a set of ciphertexts generated by the first cryptographic device using a public key of the second cryptographic device.

11. The method of claim 10 wherein the first responses comprise a corresponding set of plaintexts computed by the second cryptographic device decrypting respective ones of the ciphertexts using a secret key corresponding to the public key.

12. The method of claim 10 wherein the first responses comprise a corresponding set of signed ciphertexts computed by the second cryptographic device signing respective ones of the ciphertexts using a secret key corresponding to the public key.

13. A computer program product comprising a non-transitory processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by a processor of a first cryptographic device cause the first cryptographic device to:

in a registration mode of operation:

generate a set of challenges, wherein the set of challenges comprises n randomly selected multi-bit values, wherein a given one of the n randomly selected multi-bit values comprises a k-bit randomly selected value, and wherein n and k are security parameters denoting the number of challenges generated by the first cryptographic device and the length of the given challenge generated by the first cryptographic device, respectively;

send the challenges to a second cryptographic device, the second cryptographic device comprising a key-based cryptographic module that utilizes one or more secret keys;

receive from the second cryptographic device a set of first responses, each first response corresponding to a respective one of the challenges; and

store information characterizing the first responses; and

in an authentication mode of operation:

send a selected one of the challenges to the second cryptographic device;

receive from the second cryptographic device a second response to the selected challenge; and

authenticate the second cryptographic device utilizing the second response and the stored information;

wherein the first cryptographic device generates the challenges in the registration mode of operation without having knowledge of values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device;

wherein the first responses received from the second cryptographic device are based at least in part on at least one of said one or more secret keys of the key-based cryptographic module of the second cryptographic device; and

wherein the first cryptographic device is configured to authenticate the second cryptographic device in the authentication mode of operation using the second response without having knowledge of the values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device.

14. An apparatus comprising:

a first cryptographic device comprising a processor coupled to a memory;

the first cryptographic device being configured:

in a registration mode of operation:

to generate a set of challenges, wherein the set of challenges comprises n randomly selected multi-bit values, wherein a given one of the n randomly selected multi-bit values comprises a k-bit randomly selected value, and wherein n and k are security parameters denoting the number of challenges generated by the first cryptographic device and the length of the given challenge generated by the first cryptographic device, respectively;

to send the challenges to a second cryptographic device, the second cryptographic device comprising a key-based cryptographic module that utilizes one or more secret keys;

to receive from the second cryptographic device a set of first responses, each first response corresponding to a respective one of the challenges;

to store in the memory information characterizing the first responses; and

in an authentication mode of operation:

to send a selected one of the challenges to the second cryptographic device;

to receive from the second cryptographic device a second response to the selected challenge; and

to authenticate the second cryptographic device utilizing the second response and the stored information;

wherein the first cryptographic device is configured under control of the processor to generate the challenges in the registration mode of operation without having knowledge of values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device;

wherein the first responses received from the second cryptographic device are based at least in part on at least one of said one or more secret keys of the key-based cryptographic module of the second cryptographic device; and

wherein the first cryptographic device is configured under control of the processor to authenticate the second cryptographic device in the authentication mode of operation using the second response without having knowledge of the values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device.

15. A method performed by a first cryptographic device, comprising:

in a registration mode of operation:

generating a plurality of challenge-response pairs, wherein the plurality of challenge-response pairs comprises n randomly selected multi-bit challenge values, wherein a given one of the n randomly selected multi-bit challenge values comprises a k-bit randomly selected challenge value, and wherein n and k are security parameters denoting the number of challenges generated by the first cryptographic device and the length of the given challenge generated by the first cryptographic device, respectively;

sending the challenge-response pairs to a second cryptographic device, the second cryptographic device comprising a key-based cryptographic module that utilizes one or more secret keys;

in an authentication mode of operation:

sending a selected challenge of one of the challenge-response pairs to the second cryptographic device;

receiving from the second cryptographic device a response to the selected challenge; and

authenticating the second cryptographic device utilizing the response to the selected challenge;

wherein the first cryptographic device generates the challenge-response pairs in the registration mode of operation without having knowledge of values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device;

wherein the response received from the second cryptographic device is based at least in part on at least one of said one or more secret keys of the key-based cryptographic module of the second cryptographic device; and

wherein the first cryptographic device authenticates the second cryptographic device in the authentication mode of operation using the response without having knowledge of the values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device.

16. The method of claim 15 wherein the challenge-response pairs comprise a set of challenge-response pairs (c i ,r i )εC×R where C={c i } i=1 n and R={r i } i=1 n and further wherein the received response for a challenge c j is of the form r j ′=Dec λ j [s j ] where λ j =f κ [c j ], s j =Enc λ j [r j ] and f κ (c j ) is a function that utilizes a given one of the secret keys, denoted as secret key κ.

17. A computer program product comprising a non-transitory processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by a processor of a first cryptographic device cause the first cryptographic device to:

in a registration mode of operation:

generate a plurality of challenge-response pairs, wherein the plurality of challenge-response pairs comprises n randomly selected multi-bit challenge values, wherein a given one of the n randomly selected multi-bit challenge values comprises a k-bit randomly selected challenge value, and wherein n and k are security parameters denoting the number of challenges generated by the first cryptographic device and the length of the given challenge generated by the first cryptographic device, respectively;

send the challenge-response pairs to a second cryptographic device, the second cryptographic device comprising a key-based cryptographic module that utilizes one or more secret keys;

in an authentication mode of operation:

send a selected challenge of one of the challenge-response pairs to the second cryptographic device;

receive from the second cryptographic device a response to the selected challenge; and

authenticate the second cryptographic device utilizing the response to the selected challenge;

wherein the first cryptographic device generates the challenge-response pairs in the registration mode of operation without having knowledge of values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device;

wherein the response received from the second cryptographic device is based at least in part on at least one of said one or more secret keys of the key-based cryptographic module of the second cryptographic device; and

wherein the first cryptographic device authenticates the second cryptographic device in the authentication mode of operation using the response without having knowledge of the values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device.

18. An apparatus comprising:

a first cryptographic device comprising a processor coupled to a memory;

the first cryptographic device being configured:

in a registration mode of operation:

to generate a plurality of challenge-response pairs, wherein the plurality of challenge-response pairs comprises n randomly selected multi-bit challenge values, wherein a given one of the n randomly selected multi-bit challenge values comprises a k-bit randomly selected challenge value, and wherein n and k are security parameters denoting the number of challenges generated by the first cryptographic device and the length of the given challenge generated by the first cryptographic device, respectively; and

to send the challenge-response pairs to a second cryptographic device, the second cryptographic device comprising a key-based cryptographic module that utilizes one or more secret keys; and

in an authentication mode of operation:

to send a selected challenge of one of the challenge-response pairs to the second cryptographic device;

to receive from the second cryptographic device a response to the selected challenge; and

to authenticate the second cryptographic device utilizing the response to the selected challenge;

wherein the first cryptographic device is configured under control of the processor to generate the challenge-response pairs in the registration mode of operation without having knowledge of values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device;

wherein the response received from the second cryptographic device is based at least in part on at least one of said one or more secret keys of the key-based cryptographic module of the second cryptographic device; and

wherein the first cryptographic device is configured under control of the processor to authenticate the second cryptographic device in the authentication mode of operation using the response without having knowledge of the values of said one or more secret keys of the key-based cryptographic module of the second cryptographic device.

19. A method performed by a first cryptographic device, comprising:

in a registration mode of operation:

receiving a plurality of challenge-response pairs from a second cryptographic device, wherein the plurality of challenge-response pairs comprises n randomly selected multi-bit challenge values, wherein a given one of the n randomly selected multi-bit challenge values comprises a k-bit randomly selected challenge value, and wherein n and k are security parameters denoting the number of challenges and the length of the given challenge, respectively; and

storing the responses from the received challenge-response pairs in encrypted form utilizing one or more secret keys of a key-based cryptographic module of the first cryptographic device; and

in an authentication mode of operation:

receiving a selected challenge of one of the challenge-response pairs from the second cryptographic device; and

sending to the second cryptographic device a response to the selected challenge, the response being generated at least in part by decrypting the corresponding encrypted response using said one or more secret keys;

wherein the first cryptographic device is authenticated by the second cryptographic device utilizing the response to the selected challenge without the second cryptographic device having knowledge of values of said one or more secret keys of the key-based cryptographic module of the first cryptographic device.

20. The method of claim 19 wherein the challenge-response pairs comprise a set of challenge-response pairs (c i ,r i )εC×R where C={c i } i=1 n and R={r i } i=1 n and further wherein the response to the selected challenge is of the form r j ′=Dec λ j [s j ] where λ j =f κ [c j ], c j is the selected challenge, s j =Enc λ j [r j ] is the stored response in encrypted form, and f κ (c j ) is a function that utilizes a given one of the secret keys, denoted as secret key κ.

21. A computer program product comprising a non-transitory processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by a processor of a first cryptographic device cause the first cryptographic device to:

in a registration mode of operation:

receive a plurality of challenge-response pairs from a second cryptographic device, wherein the plurality of challenge-response pairs comprises n randomly selected multi-bit challenge values, wherein a given one of the n randomly selected multi-bit challenge values comprises a k-bit randomly selected challenge value, and wherein n and k are security parameters denoting the number of challenges and the length of the given challenge, respectively; and

store the responses from the received challenge-response pairs in encrypted form utilizing one or more secret keys of a key-based cryptographic module of the first cryptographic device; and

in an authentication mode of operation:

receive a selected challenge of one of the challenge-response pairs from the second cryptographic device; and

send to the second cryptographic device a response to the selected challenge, the response being generated at least in part by decrypting the corresponding encrypted response using said one or more secret keys;

wherein the first cryptographic device is authenticated by the second cryptographic device utilizing the response to the selected challenge without the second cryptographic device having knowledge of values of said one or more secret keys of the key-based cryptographic module of the first cryptographic device.

22. An apparatus comprising:

a first cryptographic device comprising a key-based cryptographic module that utilizes one or more secret keys;

the first cryptographic device being configured:

in a registration mode of operation:

to receive a plurality of challenge-response pairs from a second cryptographic device, wherein the plurality of challenge-response pairs comprises n randomly selected multi-bit challenge values, wherein a given one of the n randomly selected multi-bit challenge values comprises a k-bit randomly selected challenge value, and wherein n and k are security parameters denoting the number of challenges and the length of the given challenge, respectively; and

to store the responses from the received challenge-response pairs in encrypted form utilizing said one or more secret keys of the key-based cryptographic module; and

in an authentication mode of operation:

to receive a selected challenge of one of the challenge-response pairs from the second cryptographic device; and

to send to the second cryptographic device a response to the selected challenge, the response being generated at least in part by decrypting the corresponding encrypted response using said one or more secret keys;

wherein the first cryptographic device is authenticated by the second cryptographic device utilizing the response to the selected challenge without the second cryptographic device having knowledge of values of said one or more secret keys of the key-based cryptographic module of the first cryptographic device.

23. The apparatus of claim 22 wherein the key-based cryptographic module comprises a symmetric-key cryptographic module.

24. The apparatus of claim 22 wherein the key-based cryptographic module comprises a public-key cryptographic module.