Method and Implementation for Information Exchange Using Markov Models

• US 20100272256A1
• Filed: 10/23/2009
• Published: 10/28/2010
• Est. Priority Date: 10/24/2008
• Status: Active Grant

• Current Assignee: United States Of America As Represented By The Secretary Of The Army (Government of the United States of America), University of Maryland Office of Technology Commercialization
• Original Assignee: The United States of America As Represented By The Secretary of Agriculture, University of Maryland, College Park
• Inventors: BARAS, John S., Yu, Paul L., Sadler, Brian M.
• Granted Patent: US 8,848,904 B2
• Time in Patent Office: Days
• US Class Current: 380/46
• CPC Class Codes: H04K 1/10 by using two signals transmitted simultaneously or successively
• CPC Class Codes: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• 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: H04N 21/26613 for generating or managing keys in general key distribution for secret or secure communication involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP] H04L9/083; network support of key management H04L63/06; key management for network security in communication control or processing H04W12/04

Abstract

The replacement of secret keys is a central problem in key management. Typical solutions exchange handshaking messages, involve complex computations, or require the cooperation of trusted third parties. Disclosed herein is a key replacement method that exploits the randomness of Markov models to efficiently provide fresh keys to users. Unlike other methods, the proposed method removes the need for extra communications, intensive computation, or third parties. It is demonstrated that the proposed method has perfect forward secrecy as well as resistance to known-key attacks.

Claims

1. A method for sending information responsive to a variable that changes over time, the method comprising:

(a) providing, via a transmitter, a message responsive to a current variable;

(b) generating a plurality of potential next variables based on a transition function that specifies a transition probability from the current variable to other variables, wherein the transition probability from the current variable to each potential next variable is greater than zero;

(c) assigning one of the plurality of potential next variables to be a next variable; and

(d) providing, via a transmitter, a subsequent message responsive to the next variable.

2. The method of claim 1, wherein the generating in (b) comprises:

pseudo-randomly generating a string of numbers based on the current variable and a long-term variable; and

selecting contiguous groups of numbers from the string of numbers as the plurality of potential next variables, wherein each group of numbers comprises one of the potential next variables.

3. The method of claim 1, wherein the current variable comprises a current key, and wherein the providing in (a) comprises encrypting and sending the message using the current key.

4. The method of claim 3, wherein the next variable comprises a next key, and wherein the providing in (d) comprises encrypting and sending the subsequent message using the next key.

5. The method of claim 1, wherein the current variable comprises a current carrier frequency, and wherein the providing in (a) comprises transmitting the message over the current carrier frequency.

6. The method of claim 5, wherein the next variable comprises a next carrier frequency, and wherein the providing in (d) comprises transmitting the subsequent message over the next carrier frequency.

7. A method for receiving information responsive to a variable that changes over time, the method comprising:

(a) receiving, via a receiver, a message responsive to a current variable;

(b) generating a plurality of potential next variables based on a transition function that specifies a transition probability from the current variable to other variables, wherein the transition probability from the current variable to each potential next variable is greater than zero;

(c) identifying a next variable based on an integrity check of each potential next variable; and

(d) receiving, via a receiver, a subsequent message responsive to the next variable.

8. The method of claim 7, wherein the generating in (b) comprises:

pseudo-randomly generating a string of numbers based on the current variable and a long-term variable; and

selecting contiguous groups of numbers from the string of numbers as the plurality of potential next variables, wherein each group of numbers comprises one of the potential next variables.

9. The method of claim 7, wherein the current variable comprises a current key, and wherein the receiving in (a) comprises decrypting the message using the current key.

10. The method of claim 9, wherein the generating in (b) comprises generating a plurality of potential next keys based on a transition function that specifies a transition probability from the current key to other keys, wherein the transition probability from the current key to each potential next key is greater than zero.

11. The method of claim 10, wherein the identifying in (c) comprises identifying a next key based on an integrity check between a subsequently received message and each potential next key.

12. The method of claim 11, wherein the identifying in (c) comprises:

computing a check sum between each potential next key and the subsequently received message, wherein the next key is identified as one of the plurality of potential next keys for which the check sum is equal to a predetermined value.

13. The method of claim 11, wherein the identifying in (c) comprises:

identifying a next key based on an integrity check between a plurality of subsequently received messages and each potential next key.

14. The method of claim 13, wherein the identifying a next key based on an integrity check between a plurality of subsequently received messages and each potential next key comprises:

computing a check sum between each potential next key and each of the plurality of subsequently received messages, resulting in a corresponding plurality of check sums for each respective potential next key;

for each respective potential next key, computing a summation of the corresponding plurality of check sums; and

identifying the next key as one of the plurality of potential next keys for which the summation is a greatest value.

15. The method of claim 7, wherein the current variable comprises a current carrier frequency, and wherein the receiving in (a) comprises receiving a message transmitted over the current carrier frequency.

16. The method of claim 15, wherein the generating in (b) comprises generating a plurality of potential next carrier frequencies based on a transition function that specifies a transition probability from the current carrier frequency to other carrier frequencies, wherein the transition probability from the current carrier frequency to each potential next carrier frequency is greater than zero.

17. The method of claim 16, wherein the identifying in (c) comprises identifying a next carrier frequency based on an integrity check of each potential next carrier frequency.

18. The method of claim 17, wherein the integrity check comprises energy detection of each potential next carrier frequency to determine which includes a signal and which includes only noise.

19. The method of claim 17, wherein the integrity check comprises energy detection of each potential next carrier frequency over a predetermined time interval to determine which includes a signal and which includes only noise.

20. A system, comprising:

a transmitter for sending information responsive to a variable that changes over time, wherein the transmitter comprises;

a message-generation module configured to provide a current message responsive to a current variable;

a variable-generation module configured to generate a plurality of potential next variables based on a transition function that specifies a transition probability from the current variable to other variables, wherein the transition probability from the current variable to each potential next variable is greater than zero; and

an assignment module configured to assign one of the plurality of potential next variables to be a next variable;

wherein the message-generation module is configured to provide a subsequent message responsive to the next variable; and

a receiver for receiving information responsive to the variable that changes over time, wherein the receiver comprises;

a reception module configured to receive the current message responsive to the current variable;

a variable-generator module configured to independently generate the plurality of potential next variables based on the transition function that specifies the transition probability from the current variable to the other variables; and

a variable-identifier module configured to identify the next variable based on an integrity check of each potential next variable;

wherein the reception module is configured to receive the subsequent message responsive to the next variable.