Keyed pseudo-random number generator

• US 8,660,268 B2
• Filed: 04/29/2008
• Issued: 02/25/2014
• Est. Priority Date: 04/29/2008
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Schneider, James Paul
• Primary Examiner(s): Arani, Taghi
• Assistant Examiner(s): Jeudy, Josnel
• Application Number:
  US12/111,893
• Publication Number:
  US 20090271462A1
• Time in Patent Office: 2,128 Days
• Field of Search: 380262-266, 380 44- 47, 713170-175, 713/159, 713182-186, 709/225, 709/229
• US Class Current: 380/262
• CPC Class Codes: G06F 21/34 involving the use of external additional devices, e.g. dongles or smart cards

Abstract

A method and apparatus for client authentication using a pseudo-random number generation system. The pseudo-random number generation utilizes a secret key as well as state information as input into the hash function to generate a pseudo-random number. The state information that is part of the input can be any number of prior generated pseudo-random numbers. The authentication allows for synchronization of the client and server by exchanging state information. The authentication is not dependent on any absolute time and consequently the client and servers are not required to maintain a reliable shared time base.

Claims

1. A computer-implemented method comprising:

retrieving state data comprising at least a first pseudo-random value and a second pseudo-random value, wherein each of the first pseudo-random value and second pseudo-random value are generated by encrypting and truncating other pseudo-random values;

encrypting, by a processing device, a combination of at least the first pseudo-random value and the second pseudo-random value using a key to produce an output value;

truncating the output value to generate a third pseudo-random value;

comparing the third pseudo-random value with another pseudo-random value generated by a device requesting authentication; and

requesting synchronization of state data from the device requesting authentication, in response to a failed comparison of the third pseudo-random value and the pseudo-random value generated by the device.

2. The computer-implemented method of claim 1, further comprising:

replacing the first pseudo-random value with the third pseudo-random value; and

calculating a fourth pseudo-random value based at least on the second pseudo-random value and third pseudo-random value.

3. The method of claim 1, further comprising:

receiving a personal identification number as an input from a user.

4. The method of claim 1, further comprising:

validating the state data from the device.

5. The method of claim 1, further comprising:

recalculating the third pseudo-random value based on the state date received from the device.

6. The method of claim 1, further comprising:

authenticating a request in response to a successful comparison of the third pseudo-random value and the pseudo-random value generated by the device.

7. The method of claim 1, further comprising:

receiving a request for the state data from an authentication server; and

sending the state data to the authentication server.

8. A non-transitory computer readable storage medium, having instructions stored therein, which when executed, cause a processing device to perform a set of operations comprising:

retrieving state data comprising at least a first pseudo-random value and a second pseudo-random value, wherein each of the first pseudo-random value and second pseudo-random value are generated by encrypting and truncating other pseudo-random values;

encrypting, by a processing device, a combination of at least the first pseudo-random value and the second pseudo-random value using a key to produce an output value;

truncating the output value to generate a third pseudo-random value;

comparing the third pseudo-random value with another pseudo-random value generated by a device requesting authentication; and

requesting synchronization of state data from the device requesting authentication, in response to a failed comparison of the third pseudo-random value and the pseudo-random value generated by the device.

9. The non-transitory computer readable storage medium of claim 8, having further instructions therein, which when executed, cause the computer to perform a further set of operations, further comprising:

replacing the first pseudo-random value with the third pseudo-random value; and

calculating a fourth pseudo-random value based at least on the second pseudo-random value and third pseudo-random value.

10. The non-transitory computer readable storage medium of claim 8, having further instructions therein, which when executed, cause the computer to perform a further set of operations, further comprising:

receiving a personal identification number as an input from a user.

11. The non-transitory computer readable storage medium of claim 8, having further instructions therein, which when executed, cause the computer to perform a further set of operations, further comprising:

validating the state data from the device.

12. The non-transitory computer readable storage medium of claim 8, having further instructions stored therein, which when executed perform a further set of operations, further comprising:

recalculating the third pseudo-random value based on the state date received from the device.

13. The non-transitory computer readable storage medium of claim 8, having further instructions stored therein, which when executed perform a further set of operations, further comprising:

authenticating a request from a client in response to a successful comparison of the third pseudo-random value and the pseudo-random generated by the device.

14. A system comprising:

a memory;

a processing device coupled to the memory;

an encryption module executable from the memory by the processing device;

a pseudo-random number generator module executable from the memory by the processing device and coupled to the encryption module, the pseudo-random number generator module to generate a third pseudo-random number by calling the encryption module to encrypt a combination of at least a first prior pseudo-random output value and a second prior pseudo-random output value, wherein the first prior pseudo-random output value and the second prior pseudo-random output value are generated by encrypting and truncating other pseudo-random values;

a state data tracker module executed from the memory by the processing device and coupled to the pseudo-random number generator module, the state data tracker module to maintain a time value and values of the at least first prior pseudo-random output value and second prior pseudo-random output value; and

a synchronization module executed from the memory by the processing device and coupled to the pseudo-random number generator module to synchronize the state data with state data of another computer.