Distributed state random number generator and method for utilizing same

[0002] The present invention relates in general to a system and method for generating random numbers and, more particularly, to the generation of random numbers utilized in encrypting transmissions among and between computers and related devices in a network system.

[0003] An ever increasing number of individuals and companies use computer networks, such as the Internet, to transmit and process a wide variety of information. In some cases, the information transmitted is confidential or proprietary and there exists the potential for abuse if the information is accessed by an unauthorized third party. For example, increasing numbers of companies are exploring the option of taking orders for goods and services over the Internet. Similarly, there is increasing interest in conducting financial transactions, such as personal banking, over the Internet.

[0004] However, since ordering a product or service, or conducting personal banking over the Internet, may require the transmission of information such as a credit card number or a bank account number, there is an increasing need for heightened security to protect the information. The problem is further compounded by the inherent openness of a system such as the Internet that permits access to the vast volume of electronic messages which flow from user to user throughout the system. Normally, an individual user's access is limited only to the extent that he or she has an account with a service provider, a valid password and account and/or mailbox identifiers. Passwords and identification numbers can, however, be acquired by third parties that, in turn, may disseminate the information to others. Further, in addition to data integrity and secrecy, authentication is an important factor. For example, bank account information should only be available to the owner of the account. Cryptographic authentication schemes and methods also make use of random numbers. Consequently, there is a growing need for reliable encryption of confidential and sensitive information.

[0005] To satisfy the need for transmission security, there have been a number of devices and algorithms developed for encoding information to be transmitted and decoding the information upon receipt. It is, of course, desirable to encrypt the information to be transmitted that makes it as difficult as possible to break the code or key used in the encryption process.

[0006] Typically, messages to be encrypted, referred to as plaintext, are encrypted using an encryption algorithm or cipher to produce ciphertext which is transmitted and subsequently decrypted by the receiver. In most cases the encryption algorithm is publicly known; in fact, by publicizing the algorithm, the cryptographer obtains the benefit of peer review by academic cryptologists attempting to break the cipher. Well known ciphers such as the Digital Encryption Standard (“DES”), the International Data Encryption Algorithm (“IDEA”) and RSA, known by the initials of the three discovers (Rivest, Shamir, Adleman), are widely used to encrypt electronic transmissions. Since most widely used ciphers are publicly known, it is a fundamental rule of cryptology that it must be assumed that the attacker knows the general method of encryption used to transform the plaintext to ciphertext. It must also be assumed that the attacker has the ability to intercept and accurately copy the ciphertext message.

[0007] The algorithms used for encrypting data tend to be complicated mathematical functions that require considerable effort and time to develop, test and implement. Consequently, it is impractical to invest the resources required to develop a new cipher each time the encryption method has been compromised or believed to be compromised. Thus, the secrecy of the encrypted message depends upon the key used to parameterize the algorithm. A key normally consists of a relatively short string of data that determines how an algorithm performs a specific encryption or decryption. In contrast to the general algorithm, which may be changed or modified only with the expenditure of significant resources, the key may be changed as often as required. One approach, known as public key cryptography, requires each user to have two keys: a public key used by the transmitting party to encrypt a message, and a private session key, used by the receiving party to decrypt the message. In many applications it is desirable to utilize a different, randomly chosen session key for each new connection. Session keys are used to minimize the amount of information protected by a selected key, thereby reducing the amount of information that an attacker could obtain by monitoring repeated transmissions and guessing any one session key. Session keys are also used to increase the speed of encryption.

[0008] The quality of the algorithm and the quality of the keys used by the algorithm are independent. If weak keys are selected, it does not follow that the algorithm is flawed or requires replacement. If, however, the encryption algorithm is weak, then the key selection does not ensure the security of the transmission. The converse is not true; i.e., if poor (no-random or partially random), keys are selected and the ciphertext is compromised, the breach is not a reflection upon the quality of the algorithm.

[0009] Usually, strong encryption methods require significant processing time due to the complexity of the algorithm. To increase the speed of encryption, a strong, secure algorithm such as RSA is initially used to negotiate a session key between two host computers. The session key is then used in a faster, but less secure, encryption algorithm such as DES to encrypt the communications between the two host machines. Since session keys change frequently and require the encryption of relatively little data, the risk presented by using a less secure algorithm is generally acceptable. However, the security of a cryptographic protocol utilizing a session key, or any other secret key, depends upon the unpredictability of the key. If an attacker can predict, or even reduce the number of possible keys that must be tested, the difficulty of breaking the key is greatly reduced; i.e. a predictable key is virtually worthless for the purpose of encrypting a transmission. Thus, random number generators are always used to generate session keys.

[0010] Random number generators are typically comprised of three components: 1) an internal state (value); 2) a randomizing function; and 3) an internal state update function. A binary bit stream consisting of zeros and ones may represent the internal state of the random number generator. Each time the random number generator is invoked, the randomizing function is performed on the internal state to produce a new random number and reinitialize the internal state using an internal state update function. The internal state provides input to the randomizing function, without which the random number generator would produce the same value repeatedly. The internal state update function allows the random number generator to create a sequence of random numbers by constantly changing the internal state with each iteration of the random number generator.

[0011] After the random number generator has been initialized or “seeded” with an internal state it can generate one or more random numbers. However, due to the inherent deterministic nature of computers, the randomness of the output of the generator is dependent upon the randomness of the data or information utilized to initialize the generator. If the values used to initialize the generator are predictable, the output values from the generator will also be predictable. If the output of the random number generator is predictable, its value as a cryptographic tool is minimized. Therefore, the internal state update function will ideally minimize the occurrence of repeated internal states. However, if the internal state is repeated, the random numbers generated will be repeated.

[0012] Generating truly random numbers for use as keys for encrypting electronic messages presents a number of difficulties. The only measure of the true randomness of the output of normal random number generator is through the use of statistical analysis to determine the distribution, frequency and possible interdependence of the output. If these statistical criteria are not met, the output of the random number generator cannot be considered truly random. Additionally, providing random numbers for use as keys in encrypting electronic communications between computers presents further challenges. The randomizing function itself must be difficult to reverse or invert and the quantity of entropy in the random number stream must be sufficiently high to make guessing the internal state of the random number generator infeasible. The term “entropy” as used herein refers to the concept of entropy in the context of information theory as discussed in C. E. Shannon, A Mathematical Theory of Communication, Bell Systems Technical Journal, v. 27, n. 4, 1948, pp. 379-423.

[0013] Entropy, in the cryptographic sense, is the amount of information that a message contains. In other words, cryptographic entropy can be viewed as the minimum number of bits required to represent the data of interest. Thus, the entropy of a random key is the number of bits required to represent all possible keys. Ideally, the entropy of a randomly selected key is equal to its length, i.e., every bit in the key is completely random and independent of every other bit in the key. Maximizing the amount of entropy contained in a cryptographic key is a primary consideration in encryption of electronic transmissions. The harder a particular key is to guess, the longer the encrypted data remains secret. The greater the amount of entropy contained in a key, the greater the difficulty in guessing the key or determining the key with a brute force attack.

[0014] The advent of high-speed processors has increased the difficultly of securely encrypting a transmission. The amount of processing power possessed by readily available present-day computers has made “brute force” attacks feasible. A brute force attack is one in which an exhaustive search of all possible keys is conducted. Current technology provides the means to test literally millions of possible keys in a matter of seconds. Therefore it is essential to maximize the amount of entropy utilized in the creation of an encryption key. If the entropy of the key is not equal to its size, the number of keys that would have to be tested in a brute force attack is reduced. For example, if the key is a six bit string or value, there are a total of 64 (2{circumflex over ( )}6) possible keys. However, if only even numbers are used in the key, the entropy of any one key is only five bits (2{circumflex over ( )}5=32) because the lowest order bit will always be equal to zero. Thus, the number of keys to test in a brute force attack upon the encryption is halved. Although the foregoing example is simplistic, it illustrates the need for entropy in random key generation.

[0015] Gathering entropy on a computer is a difficult task. Computers, by design, are deterministic predictable machines that execute a set of instructions in the exact same way each time the instructions are invoked. One possible solution to the problem of providing entropy is to install hardware in each computer that can generate random numbers based upon physical phenomena such as the rate of radioactive decay of an element or the thermal noise of a semiconductor diode. This solution is not viable due to a number of factors including cost and the perception that hardware sources of random numbers are not needed.

[0016] Many computer applications utilize external events to gather entropy such as the timing between a user's keystrokes, movements of the mouse, or the input from a digitized audio source. However, in a network, where computers act as servers to other computers, as in the case of file servers, mail servers or web servers, these external sources of entropy do not exist. Server machines typically do not have any users that directly use the server from a monitor and keyboard; the user's only interaction with the machine is over the network. Since these machines are isolated from random external physical phenomena, the task of acquiring entropy presents additional challenges. If a machine is required to generate a large number of cryptographic keys, for example as in the case of web server running Secure Sockets Layer (“SSL”), a cryptographic protocol developed to provide secure Internet transactions, the machine will have a high demand for entropy in the form of many generated session keys but no external source of random physical events. The same problem exists in the context of network firewalls and routers. These network devices rarely have any direct user interaction and typically communicate only with other computers.

[0017] Thus there exists a need for an improved method of providing the entropy necessary to generate random numbers used as secret keys for encrypting electronic communications between computers, and in particular, encrypting communications between computers on a network, such as the Internet.

[0018] The present invention provides a solution for the problems encountered in providing a quality source of entropy by sharing part of the internal state of each random number generator present on computers transmitting data over a network as the computers communicate. By sharing sources of entropy, session keys generated and utilized to encrypt the communications between computers are created from a larger pool of entropy. The method of the present invention improves the quality of entropy by allowing machines with no physical source of entropy to gather entropy by communicating with other machines and insuring that machines that generate many random session keys do not run the risk of depleting their local supplies of entropy. The present invention achieves these goals because, as the number of computers and systems communicating increases, the more entropy will be created.

[0019] The present invention provides a means of creating hard to guess secret keys needed for a variety of encryption algorithms and protocols. The invention allows network computers to generate and share entropy in proportion to the need to generate random numbers utilized to initialize an internal state or value that is subsequently processed by a random number generator to create secret session keys for communicating sensitive information over a computer network. In one embodiment, shared session keys are appended to the existing internal state of the random number generators residing on the communicating computers. The resulting bit stream is then mixed or “hashed” using a one-way function such MD5 or SHA to produce a mixed bit stream. All or a portion of the mixed bit stream is then utilized as a source of entropy to reinitialize the internal state of the random number generator on one or both of the communicating computers.

[0020] The present invention provides features that have not previously been provided on a computer network. In particular, the invention supplies a steady stream of quality entropy to the random number generator; it satisfies the demand for more random session keys as the demand for keys increases; and it provides machines with poor or no sources of entropy, such as network servers, with an adequate source of quality entropy.

[0021] The present invention addresses the need for providing an unpredictable internal state (value) to a random number generator by distributing the state between multiple computing nodes. Although the amount of entropy provided by each node may be small, the cumulative entropy provided by all the nodes is large, thereby satisfying the need for a quality source of entropy.

[0022] FIG. 1 is a flowchart the operation of a generic random number used to create session key for encrypting communications in accordance with a preferred embodiment;

[0023] FIG. 2 an illustration of a computer network in which a file server communicates with multiple client computers in accordance with a preferred embodiment;

[0024] FIG. 3 is a flowchart illustrating logic in accordance with preferred embodiment; and

[0025] FIG. 4 is a flowchart illustrating a communication session between computers in accordance with a preferred embodiment.

[0026] Referring now to FIG. 1, a generalized schematic of a random number generator 8 for use in encrypting electronic messages is illustrated. The random number generator includes an internal state or value 10, a source of entropy 12, and an internal state update function 14 which may comprise, or be based upon, one or more algorithms.

[0027] Values from the entropy source 12 are used to initialize the internal state update function 14 that in turn provides a source of entropy for changing the value of the internal state 10. Values from the internal state 10 are manipulated by randomizing function 16 to produce a stream of random numbers 18. The stream of random numbers 18 is then utilized to generate encryption keys 20.

[0028] Turning now to FIG. 2, there is illustrated a computer network 30. The network includes a file server 32 and client computers 34(a)-34(h). File server 32 may be part of a distributed network functioning to connect and communicate with other computers in a network such as the Internet. Since file server 32 communicates only with client computers 34(a)-34(h) it is effectively insulated from external physical sources of entropy such as the time between user keystrokes. Client computers 34(a)-34(h) may be utilized to communicate sensitive or confidential information to and from the file server 32, information that will require encryption for security reasons. In order to encrypt the information transmitted between the file server 32 and the client computers 34(a)-34(h) a shared secret session key will be used to transform the communication. Normally, the shared secret session key will be utilized only once.

[0029] Referring now to FIG. 3, a flowchart illustrating a method of implementing the present invention is presented. Normally, the method of the present invention will be implemented as a computer program (“application”) residing on a host computer. However, it will be appreciated by those skilled in the art that the method of the present invention may be implemented through the use of electronic hardware or through the use of a combination of hardware and software.

[0030] The random number generator is started with a request for random numbers (step 50). Normally, the internal state of the random number generator will have previously been set, based upon a prior operation. Next, the application will check to determine whether any additional sources of entropy have been received (step 52). Additional sources of entropy may consist of prior secret session keys, nonces, private/public key pairs generated for encryption protocols such as RSA or random key values utilized to implement the Diffie-Hellman key exchange protocol. If no additional sources of entropy have been received, the application will proceed to generate random numbers based on the existing internal state (step 60).

[0031] If an additional source of entropy is available, the source is appended or attached to the existing internal state 10 (step 54). For example, if the source of entropy to be appended is a prior session key consisting of a first 128 bit data string and the current internal state of the random number generator is a second 128 bit data string, the first data string will be stored and appended to the second data string to create a third, 256 bit data string. The first and second bit strings can, of course, be larger or smaller than 128 bits.

[0032] To preserve security during data transmissions, it is necessary to insure that any data used to initialize the random number generator does not reduce entropy. If a session key from a prior transmission is used to initialize the random number generator without additional measures, it is conceivable that an attacker could subvert the internal status of the random number generator. An attacker, by repeatedly initiating communications and generating a session key, for example all zeros or ones, could possibly determine the internal status of the random number generator and predict the values of the numbers generated. Consequently, it is necessary to further manipulate data utilized to initialize the random number generator.

[0033] Therefore, after the first and second bit strings have been combined to form a third bit string, the third bit string is “hashed” utilizing a one-way hash function (step 56). Exemplary “hash” one-way functions include MD5 (Rivest, 1992), or SHA (NIST, 1993). The message digest function mixes the third bit stream to produce a fourth bit stream all, or a portion of which, is used to subsequently reinitialize the internal state of the random number generator. Preferably, the message digest function is capable of mixing an arbitrarily long stream of data to produce a fixed-length bit stream. Thus, different sources of entropy, having variable lengths may be utilized. The use of the message digest function to hash the newly added values with the prior internal state of the random number generator insures that the output values used to reinitialize the internal state of the random number generator are secret. Further, mixing or hashing the prior internal state of the random number generator with a new source of entropy ensures that no entropy is destroyed in the process and minimizes the possibility that an attacker could subvert the system.

[0034] The fourth bit stream, the output of the hash function, is used to reinitialize the internal state of the random number generator (step 58). The random number generator then generates random numbers (step 60), which, in turn are used as session keys or used to generate session keys (step 64). The first bit string is discarded or erased and the application then checks to determine whether additional random numbers are required (step 66). If additional random numbers are required, the program returns to step 52, if not, the program terminates (step 68).

[0035] Referring now to FIG. 4 a flowchart illustrating an architecture in accordance with a preferred embodiment. Computer A initiates communications with computer B via a computer network (step 80). A and B negotiate a shared secret session key K (step 82) using, for example a Diffie-Hellman key exchange protocol. A and B communicate using the shared secret session key K (step 84). After the communication has been completed (step 86), A and B each append the value of the shared secret session key K to the internal state of their respective random number generators (step 88) as previously described. The secret session key K is then discarded (step 90) before the program is terminated (step 92). The shared secret session key K is then utilized as a source of entropy in combination with the existing internal states of the random number generators utilized by A and B to produce random values to reinitialize the internal states of their respective random number generators. Since the prior internal states of the random number generators utilized by A and B are different, both random number generators will be reinitialized with different values.

[0036] The value of the method of the present invention will be further appreciated when considered in the context of computer network such as the Internet. In this context, the method of the present invention may be viewed as a method to securely share internal states between multiple random number generators. This is because the session key or nonce is generated from a host computer's random number generator and depends, in part, on the state of the host computer's random number generator. When the random value from the host computer's random number generator is added to the state of another random number generator residing in a second computer, the internal state of the second computer's random number generator now depends indirectly on the internal state of the first random number generator. It should also be noted that the method of the present invention does not require both computers to cooperate or interface beyond the normal negotiation of session keys. Neither of the computers require assistance or permission from the other to use the method as a means of gathering entropy. Thus, no incompatibilities are created by adding the functionality

[0037] In a network where hundreds of computers are communicating via a host computer or file server, the method of the present invention creates a complicated web of interdependence between the internal state of the random number generator utilized by each of the individual computers. The internal state of the random number generator residing on each computer will be a function of the internal state of one or more of the computers that host has communicated with in the past and the order the communications were conducted. Thus, the internal state of each host computer's random number generator will ultimately depend on the internal state of each computer in the network. In the case of the Internet, the network would consist of millions of machines.

[0038] Employment of the method of the present invention in such a network would result in the generation of random values that would be infeasible for even the most determined attacker to attempt to predict.

[0039] The following source code presents an example of implementation of the invention. Two files are presented, the first “Channeljava” implements a SKIP functionality using the Diffie-Hellman public key encryption code to exchange session keys that encrypt all traffic passing between two SKIP hosts. SKIP can use a variety of encryption algorithms including DES, RC4 and IDEa and requires the generation of random session keys. The second file “SkipSession.java” includes code for implementing a RNG (“Random Number Generator”) and code for adding session keys to the RNG's internal state. The program takes the input, in this case a session key, hashes it with the current RNG state and adds the value to the current RNG state.

[0040] While the present invention has been disclosed and discussed in connection with the above-described embodiment, it will be apparent to those skilled in the art that numerous changes, variations and modifications within the spirit and scope of the invention are possible. Accordingly, it is therefore intended that the following claims shall encompass such variations and modifications.