Cryptographic device configured to transmit messages over an auxiliary channel embedded in passcodes
View Patent ↗A first cryptographic device determines multiple sets of passcodes for possible release in association with a corresponding one of a plurality of epochs, and transmits a message to a second cryptographic device over an auxiliary channel embedded in one or more passcodes released by the first cryptographic device to the second cryptographic device. For example, the first cryptographic device can determine multiple sets of passcodes by precomputing and storing the multiple sets of passcodes, or by generating one or more data sets from which the multiple sets of passcodes can be computed. The first cryptographic device transmits the message over the auxiliary channel by selecting a particular one of the multiple sets of passcodes based on content of the message and releasing a passcode from the selected set. The first cryptographic device may comprise an authentication token and the second cryptographic device may comprise an authentication server.
1. A method comprising:
determining multiple sets of passcodes in a first cryptographic device, the multiple sets comprising respective different valid passcodes for possible release in association with a given one of a plurality of epochs;
determining a message to communicate from the first cryptographic device to a second cryptographic device in conjunction with the given epoch;
selecting a particular one of the multiple sets of passcodes based on content of said message;
releasing a passcode associated with the given epoch from the selected set; and
communicating said message over an auxiliary channel embedded in the released passcode, wherein communicating said message comprises transmitting the released passcode from the first cryptographic device to the second cryptographic device.
2. The method of claim 1 wherein determining multiple sets of passcodes comprises precomputing and storing the multiple sets of passcodes in the first cryptographic device.
3. The method of claim 1 wherein determining multiple sets of passcodes comprises generating one or more data sets from which the multiple sets of passcodes can be computed.
4. The method of claim 1 wherein for the given epoch, denoted as epoch t, a message m t is communicated over the auxiliary channel by conditioning selection of the particular one of the multiple sets of passcodes on message m t and releasing a particular passcode P t from the selected set of passcodes in association with epoch t.
5. The method of claim 4 wherein a given one of the multiple sets of passcodes is of the form {P 1 , . . . , P n }, where P t =ƒ κ (t) for 1≤t≤n, t denotes a current one of the plurality of epochs, n denotes the number of passcodes in the given set, and ƒ κ (t) is a function that utilizes a secret key κ of the first cryptographic device, and further wherein the first cryptographic device releases passcode P t in association with epoch t.
6. The method of claim 5 wherein the message comprises a one-bit binary message m t ∈{0,1} and the multiple sets of passcodes comprise two sets of passcodes {P 1 (0) , . . . , P n (0) } and {P 1 (1) , . . . , P n (1) } and further wherein for epoch t communicating the message m t comprises releasing passcode P t ←P t (m t ) and then erasing P t (0) and P t (1) .
7. The method of claim 5 wherein compromise of the first cryptographic device allowing observation of a released passcode for epoch s<t does not allow determination of a corresponding message m s .
8. The method of claim 5 wherein an attacker is unable to alter message m t in an intercepted passcode P t =P t (m t ) without knowing P t (1-m t ) .
9. The method of claim 3 wherein the determining multiple sets of passcodes, determining the message to communicate and selecting comprise:
generating a set of data elements using a secret key of the first cryptographic device;
selecting a subset of data elements from the set of data elements;
identifying particular data elements in the subset of data elements based on the message; and
determining a passcode to be released in association with a current one of the epochs as a function of the particular data elements.
10. The method of claim 9 wherein generating the set of data elements comprises generating a data set D={d 0 , . . . , d n } of l-bit data items pseudorandomly from a seed σ where l and n denote security parameters.
11. The method of claim 10 wherein selecting a subset of data elements from the set of data elements comprises identifying a subset S t of k data elements for current epoch t from data set D.
12. The method of claim 11 wherein identifying particular data elements in the subset of data elements based on the message comprises identifying selected ones of the k data elements in S t based on a message m t .
13. The method of claim 12 wherein determining the passcode to be released in association with current epoch t comprises computing the passcode as an XOR function of the particular selected ones of the k data elements.
14. The method of claim 9 further comprising replacing the particular data elements with new data elements.
15. The method of claim 14 wherein replacing the particular data elements with new data elements comprises replacing the particular data elements with predetermined binary strings.
16. A computer program product comprising a 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 the first cryptographic device cause the method of claim 1 to be performed.
17. An apparatus comprising:
a first cryptographic device comprising a processor coupled to a memory;
the first cryptographic device being configured:
to determine multiple sets of passcodes, the multiple sets comprising respective different valid passcodes for possible release in association with a given one of a plurality of epochs,
to determine a message to communicate from the first cryptographic device to a second cryptographic device in conjunction with the given epoch,
to select a particular one of the multiple sets of passcodes based on content of said message,
to release a passcode associated with the given epoch from the selected set, and
to communicate said message over an auxiliary channel embedded in the released passcode, wherein the first cryptographic device is configured to communicate said message by transmitting the released passcode from the first cryptographic device to the second cryptographic device.
18. The apparatus of claim 17 wherein the first cryptographic device comprises an authentication token and the second cryptographic device comprises an authentication server.
19. The apparatus of claim 18 wherein the authentication token comprises one of a hardware authentication token and a software authentication token.
20. A communication system comprising:
a plurality of processing devices configured to communicate over one or more networks;
first and second ones of the processing devices comprising respective first and second cryptographic devices;
the first cryptographic device being configured:
to determine multiple sets of passcodes, the multiple sets comprising respective different valid passcodes for possible release in association with a given one of a plurality of epochs,
to determine a message to communicate from the first cryptographic device to the second cryptographic device in conjunction with the given epoch,
to select a particular one of the multiple sets of passcodes based on content of said message,
to release a passcode associated with the given epoch from the selected set, and
to communicate said message over an auxiliary channel embedded in the released passcode, wherein the first cryptographic device is configured to communicate said message by transmitting the released passcode from the first cryptographic device to the second cryptographic device.