Injecting CPU time jitter to improve entropy quality for random number generator

Aspects of present disclosure relate to random number generator, a method and a computer program product of improving entropy quality of the random number generator. The method may include: receiving, at an input/output interface module of the random number generator, a request to generate a random number having a predetermined number of random bits, and starting a random bit generating loop to generate each of the random bits of the random number to be generated. In certain embodiments, random bit generating loop may include: incorporating a CPU Time as a randomness factor in generating random number to improve entropy quality, including non-deterministic memory-subsystem latencies in entropy extraction, such as those introduced by unpredictable cache movements, generating a Candidate Bit by using a Clock Time, and generating a random bit for random number by using a von Neumann unbiasing analysis module, until every random bits of the random number is generated.

BACKGROUND

The present disclosure relates generally to random number generation, and more particularly to methods for improving the entropy quality of a random number generator by injecting central processing unit (CPU) time jitter.

Secure cryptography is dependent on the ability to generate unpredictable random numbers. Thus, all cryptographic modules (hardware or software based) must have access to a high-quality random number generator (RNG), sometimes called a random bit generator (RBG). There are two classes of RNG: (1) a true random number generator (TRNG), sometimes called a non-deterministic random number generator (NDRNG); and (2) a pseudo-random number generator (PRNG), sometimes called the deterministic random number generator (DRNG). A true random number generator (TRNG) is a genuine random number generator. It extracts entropy from one or more noise sources and compresses it into a stream of random bytes. For hardware-based cryptographic modules, the TRNG noise sources are hardware features built into the device, such as sampling thermal noise from a resistor. Software based cryptographic module TRNGs tend to have fewer available noise sources. A pseudo-random number generator (PRNG) takes a seed as input and produces a stream of output that looks random, but is actually not random at all (hence the name ‘deterministic’). In a well-designed PRNG, the output is indistinguishable from random provided the seed is random and kept secret. PRNGs also have a much higher throughput than TRNGs. Thus, a PRNG is usually seeded from a separate TRNG, then used as the RNG for the module.

Conventionally, random number generators use real clock time or CPU time as a randomness factor to generate random numbers. Conventional random number generators use a loop to get a time value, calculate a time difference, update the time value, select a lower order bit of the time delta as a candidate bit, and perform a von Neumann analysis to generate a random bit. Note that if the loop always executed at a constant rate, the algorithm would loop forever, since the candidate bit would always be the same. Naturally occurring jitter is a phenomenon of all computing systems. Hardware and operating systems are constantly servicing events that happen beneath the visibility of a virtual program. Page faults, I/O completion interrupts, level 1 (L1) cache misses, etc. are examples of such events, all of which add jitter to any executing program loop. If you consider a software based TRNG running as a virtual program, naturally occurring jitter is beyond the TRNG's control and, thus, unpredictable. With the continued drop in computing hardware prices, today's computing systems are more highly tuned than in the past. The availability of more RAM and larger L1 caches results in less interruptions. Hence, naturally occurring jitter is becoming scare. It is desirable to add a new randomness factor into the random number generator.

Therefore, heretofore unaddressed needs still exist in the art to address the aforementioned deficiencies and inadequacies.

SUMMARY

In one aspect, the present disclosure relates to a random number generator using CPU time jitter to improve entropy quality of a random number generator. In certain embodiments, the random number generator may include: an input/output interface module, a CPU Time extraction module, a Clock Time extraction module, a jitter collection module and a von Neumann unbiasing analysis module. The input/output interface module may receive, from a requester, a request to generate a random number having a predetermined number of random bits, initiate a random bit generating loop to generate each of the random bits, and transmit the random number generated to the requester. The CPU Time extraction module may extract a CPU Time from a CPU clock of a CPU of a computer. The Clock Time extraction module may extract a Clock Time from the CPU clock. The jitter collection module submodule configured to accumulate non-predictable time differences by observing the latency of multiple operations and induce cache-related non-determinism by purging CPU cache. The von Neumann unbiasing analysis module may perform a von Neumann unbiasing analysis to generate the random bits for each of the random numbers to be generated.

In another aspect, the present disclosure relates to a method of injecting CPU time jitter to improve entropy quality of a random number generator. In certain embodiments, the method may include: receiving, at an input/output interface module of the random number generator, a request to generate a random number having a predetermined number of random bits, and starting a random bit generating loop to generate each of the random bits of the random number to be generated. In certain embodiments, the random bit generating loop may include: incorporating a CPU Time as a randomness factor in generating random number to improve entropy quality of the random number generator, generating a Candidate Bit by using a Clock Time, and generating a random bit for the random number by using a von Neumann unbiasing analysis module, until every random bit of the random number is generated.

In yet another aspect, the present disclosure relates to a computer program product operable on a CPU of a computer. In certain embodiments, the computer program product may include a non-transitory computer readable storage medium storing computer executable instructions. When these computer executable instructions are executed by the CPU, these computer executable instructions cause the CPU to perform: receiving, at an input/output interface module of the random number generator, a request to generate a random number having a predetermined number of random bits, and initiating a random bit generating loop to generate each random bit of the random number to be generated. The random bit generating loop may include: incorporating a CPU Time as a randomness factor in generating random number to improve entropy quality of the random number generator, generating a Candidate Bit by using a Clock Time, and generating a random bit for the random number by using a von Neumann unbiasing analysis module, until every random bit of the random number is generated.

DETAILED DESCRIPTION

The terms used in this specification generally have their ordinary meanings in the art, within the context of the present disclosure, and in the specific context where each term is used. Certain terms that are used to describe the present disclosure are discussed below, or elsewhere in the specification, to provide additional guidance to the practitioner regarding the description of the present disclosure. It will be appreciated that same thing can be said in more than one way. Consequently, alternative language and synonyms may be used for any one or more of the terms discussed herein, nor is any special significance to be placed upon whether or not a term is elaborated or discussed herein. The use of examples anywhere in this specification including examples of any terms discussed herein is illustrative only, and in no way limits the scope and meaning of the present disclosure or of any exemplified term. Likewise, the present disclosure is not limited to various embodiments given in this specification.

As used herein, “plurality” means two or more. The terms “comprising,” “including,” “carrying,” “having,” “containing,” “involving,” and the like are to be understood to be open-ended, i.e., to mean including but not limited to.

The term computer program, as used above, may include software, firmware, and/or microcode, and may refer to programs, routines, functions, classes, and/or objects. The term shared, as used above, means that some or all code from multiple modules may be executed using a single (shared) processor.

The present disclosure will now be described more fully hereinafter with reference to the accompanying drawingsFIGS. 1-3, in which certain exemplary embodiments of the present disclosure are shown. The present disclosure may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this invention will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art.

Referring toFIG. 1, an embodiment of a computer system100for injecting CPU time jitter to improve entropy quality of a random number generator and implementing the teachings herein. In this embodiment, the computer system100has one or more processors101A,101B,101C, etc. (collectively or generically referred to as processor(s)101). In one embodiment, each processor101may include a reduced instruction set computer (RISC) microprocessor. Processors101are coupled to a system memory114and various other components via a system bus113. Read only memory (ROM)102is coupled to the system bus113and may include a basic input/output system (BIOS), which controls certain basic functions of the computer system100.

Thus, as configured inFIG. 1, the computer system100includes processing capability in the form of processors101, storage capability including the system memory114and mass storage104, input means such as the keyboard109and the mouse110, and the output capability including the one or more speakers111and display115. In one embodiment, a portion of the system memory114and mass storage104collectively store the operating system120to coordinate the functions of the various components shown inFIG. 1. In certain embodiments, the network116may include symmetric multiprocessing (SMP) bus, a Peripheral Component Interconnect (PCI) bus, local area network (LAN), wide area network (WAN), telecommunication network, wireless communication network, and the Internet.

In one aspect, the present disclosure relates to a random number generator200using CPU time jitter to improve its entropy quality, as shown inFIG. 2. In certain embodiments, the random number generator200may include: an input/output interface module202, a CPU_Time extraction module204, a Clock_Time extraction module206, a jitter collection module207and a von Neumann unbiasing analysis module208.

In certain embodiments, the input/output interface module202may receive, from a requester, a request to generate a random number having a predetermined number of random bits, initiate a random bit generating loop to generate each of the random bits, and transmit the random number generated to the requester. In certain embodiments, the length of the predetermined number of random bits are determined by the applications of the random number to be generated, and it may include 64 bits, 128 bits, 256 bits, or any other commonly used lengths.

In certain embodiments, Clock_Time may be a real time clock, which measures elapsed real time. The CPU_Time is an accumulator that measures how busy a CPU is. When the CPU is kept 100% busy, then both Clock_Time and CPU_Time values would tick at the same rate. However, the CPU is rarely 100% busy since it has to wait for events so that it can proceed. Both Clock_Time and CPU_time values are maintained by the CPU but are independent. For example, given two points in time (say the beginning and ending of a loop iteration), the elapsed real time may have been 50 ms (Clock_Time), but when the CPU was only busy 50% of that time, the CPU_time would only be 25 ms. Therefore, an additional randomness factor, i.e., CPU jitter, is introduced into the random number generator200here to increase and/or improve an entropy quality of the random number generator200according to certain embodiments of the present disclosure.

In certain embodiments, the CPU_Time extraction module204may extract a CPU_Time from a CPU clock210of a CPU of a computer for every random bit of the random number to be generated during the random bit generation loop. In certain embodiments, the CPU_Time extraction module204of the random number generator200may perform following pseudo-code:Set CPU_Time=extracted CPU_Time;When CPU_Time MODULO 3=0 ThenPurge the L1 cache entry holding a time_value.

The pseudo-code represents how CPU_Time is used to improve and/or increase the entropy quality of the random number generator200. In certain embodiments, the CPU_Time extraction module204may include: retrieving a CPU_Time from the CPU clock210of the CPU for current iteration of generating current random bit, setting CPU_Time extracted to be the CPU_Time, performing a modulo function to the CPU_Time, and purging level 1 (L1) cache of the CPU when the result of the modulo function is zero.

In certain embodiments, the extraction of the CPU_Time_value produces a pseudo-random value (one that's resistant to the effects of event quantization). This value is then divided by 3 to get the remainder (MODULO 3). When the result is zero, an L1 cache entry holding Time_Value is explicitly purged. The Time_Value is then set on the next instruction causing the L1 cache entry to be filled again. This operation adds extra jitter to the random bit generation loop on average every third iteration.

In certain embodiments, the Clock_Time extraction module206may extract a Clock_Time from the CPU clock210. In certain embodiments, the Clock_Time extraction module206of the random number generator200may perform following pseudo-code:Read clock to get current Time_Value for current iteration;Compute Time_Delta=current Time_Value−previous Time_Value;Set previous Time_Value=current Time_Value;Read Clock_Time a second time;Save low 4 bits of Clock_Time value as Fold_Counter;Loop Fold_Counter number of timesSet Candidate_Bit=Candidate_Bit XORed with low-order bit of Time_DeltaBit shift Time_Delta to the right one bitEndloop

The pseudo-code represents above how Clock_Time is used to improve and/or increase the entropy quality of the random number generator200. In certain embodiments, the Clock_Time extraction module206of the random number generator200may perform: retrieving a Clock_Time from the CPU clock210and updating a Time_Value, calculating a Time_Delta by subtracting previous iteration Clock_Time from current Clock_Time retrieved, updating the Time_Value by replacing the previous Time_Value with current Time_Value, reading the Clock_Time a second time, and creating a Fold_Counter and generating a Candidate_Bit by using the Time_Delta calculated.

In certain embodiments, the Clock_Time extraction module206of the random number generator200may also perform: saving low four bits of the current Time_Value as the Fold_Counter, and looping Fold_Counter number of time for setting Candidate_Bit to Candidate_Bit XORed with low-order bit of Time_Delta, and bit shifting Time_Delta to the right one bit. This operation may further improve and/or increase the entropy quality of the random number generator200. In certain embodiments, time-measurement may include operations with uncertain/unpredictable latencies, specifically infrastructure operations related to cache management, cache-content replacement, and other CPU-related operations not fully predictable to software observing them. In certain embodiments, certain similar low-level operations may be included to increase the entropy quality of the random number generator200. These low-level operations may not be as obvious as time-measurement or L1 cache replacement, but their impact is usually observable.

In certain embodiments, the jitter collection module207is configured to accumulate non-predictable time differences by observing the latency of multiple operations and induce cache-related non-determinism by purging CPU cache. With virtualization in computer systems where basically all kinds of events may be fake/software-emulated, practically usable jitter is becoming scarce. Since most time-related jitter extraction is based on the uncertainty+variation of “unpredictable” events, when these are virtualized, jitter either disappears completely, or becomes regular. This pretty much applies to all area of computing. For example: with interrupt quantization, even interrupt-arrival and processing becomes highly regular, as interrupts are no longer truly asynchronous. These interrupts are gated/quantized/entirely faked by virtual machine (VM) code.

Cache timing is important for injecting CPU_Time jitter. Cache movements, and information derived from the cache movements, remain basically-unpredictable even under virtualization environment, since they include noise of the virtual machine as a side effect. Interactions with events forcing these cache movements may stir the system state in a portable way, and virtual machine may not easily bypass/quantize/emulate these events. This is why cache-event extraction, and to some extent active contribution to cache-based traffic, is highly relevant to jitter collection.

In certain embodiments, the von Neumann unbiasing analysis module208may perform a von Neumann unbiasing analysis to generate the random bits for each of the random numbers to be generated. In certain embodiments, the von Neumann unbiasing analysis module208of the random number generator200may perform following pseudo-code:Perform von Neumann unbiasing analysis;If Candidate_Bit is not to be discarded thenSave Candidate_Bit as a generated random bit.

The von Neumann unbiasing analysis module208of the random number generator200may perform: generating the random bit by saving the Candidate_Bit when the Candidate_Bit is not to be discarded by the von Neumann unbiasing analysis module208.

Statistical analysis using a public domain tool called ENT confirms the method of injecting CPU_Time jitter does improve the entropy quality of the random numbers generated. A sample run of 10 million bytes collected using a conventional method without injecting CPU jitter shows the following:Arithmetic mean value of data bytes is 127.5262 (127.5=random).Monte Carlo value for Pi is 3.140686856 (error 0.03 percent).Serial correlation coefficient is −0.009861 (totally uncorrelated=0.0).

A sample run of 10 million bytes collected using the method of injecting CPU_Time jitter shows the following:Arithmetic mean value of data bytes is 127.5141 (127.5=random).Monte Carlo value for Pi is 3.142167657 (error 0.02 percent).Serial correlation coefficient is −0.002586 (totally uncorrelated=0.0).

These samples were collected from an IBM system z13 running z/OS as a z/VM guest. The method of injecting CPU_Time jitter shows improvement of entropy quality of the random generator over the conventional method.

As a specific example of non-determinism, a person having ordinary skill in the art may notice that cache-related latencies are generally not reliably predictable. As an added benefit, since processor evolution appears to steadily provide more capable, and complex, cache-management capabilities, the ability to predict cache-state transition appears to be steadily decreasing in state-of-the-art computing systems.

In another aspect, the present disclosure relates to a method of injecting CPU_time jitter to improve entropy quality of a random number generator200. In certain embodiments, the method may include: receiving, at an input/output interface module202of the random number generator200, a request to generate a random number having a predetermined number of random bits, and starting a random bit generating loop to generate each of the random bits of the random number to be generated.

In certain embodiments, the random bit generating loop may include: incorporating a CPU_Time as a randomness factor in generating random number to improve entropy quality of the random number generator200, generating a Candidate_Bit by using a Clock_Time as a second randomness factor in generating random number to improve entropy quality of the random number generator200, and generating a random bit for the random number by using a von Neumann unbiasing analysis module208, until every random bit of the random number is generated.

In certain embodiments, the incorporating may include: retrieving, using a CPU_Time extraction module204of the random number generator200, a CPU_Time from the CPU clock210of the CPU of the computer, performing, using the CPU_Time extraction module204of the random number generator200, a modulo function to the CPU_Time, and purging level 1 (L1) cache of the CPU when the result of the modulo function is zero. The purging may include: explicitly purging the L1 cache entry where Time_Value is stored, and setting the Time_Value on the next instruction causing the cache entry to be filled again.

In certain embodiments, the generating Candidate_Bit may include: retrieving, using a Clock-Time extraction module of the random number generator200, a Clock_Time from the CPU clock210, and updating a Time_Value, calculating a Time_Delta by subtracting previous iteration Clock_Time from current Clock_Time retrieved, and creating a Fold_Counter and generating Candidate_Bit by using the Time_Delta calculated. The creating may include: retrieving, using the Clock-Time extraction module of the random number generator200, another Clock_Time from the CPU clock210, saving, low four bits of the time value, as the Fold_Counter, and looping Fold_Counter number of time for setting Candidate_Bit to Candidate_Bit XORed with low-order bit of Time_Delta, and bit shifting Time_Delta to the right one bit.

In certain embodiments, the generating random bit may include: performing, using a von Neumann unbiasing analysis module208, a von Neumann unbiasing analysis to generate a random bit, checking whether the random bit generated is the last bit of the random number to be generated, returning to the beginning of the random bit generating loop to generate the next random bit until the last bit of the random number to be generated is generated when the random bit generated is not the last bit of the random number to be generated, and ending the random bit generating loop and transmitting the random number generated using the input/output interface module202when the random bit generated is the last bit of the random number to be generated. The performing a von Neumann unbiasing analysis to generate a random bit may include: generating the random bit by saving the Candidate_Bit when the Candidate_Bit is not to be discarded by the von Neumann unbiasing analysis module208.

Referring now toFIG. 3, a flowchart showing a method300of injecting CPU_time jitter to improve entropy quality of the random number generator200is shown according to certain embodiments of the present disclosure.

At block302, an input/output interface module202of a random number generator200may receive a request for generating a random number. The random number may include a predetermined number of random bits. In certain embodiments, the length of the predetermined number of random bits are determined by the applications of the random number to be generated, and it may include 64 bits, 128 bits, 256 bits, or any other commonly used lengths.

In certain embodiments, the random number generator200may initiate a random bit generation loop to generate the predetermined number of random bits for the random number. The random bit generation loop may have one iteration for each of the predetermined number of random bits. A random bit counter may be set to zero as the random bit generation loop starts.

At block304, the random number generator200retrieves a CPU_Time using a CPU_Time extraction module204from a CPU clock210as shown inFIG. 2.

At block306, the random number generator200performs a MODULO function to the CPU_Time retrieved. In one embodiment, the CPU_Time value is then divided by 3 to get the remainder (MODULO 3). When the MODULO result is zero, the method proceeds to block308. When the MODULO result is not zero, the method proceeds to block310.

At block308, an L1 cache entry holding Time_Value is explicitly purged. The Time_Value is then set on the next instruction causing the L1 cache entry to be filled again. This operation adds extra jitter to the random bit generation loop on average every third iteration.

At block310, the random number generator200may use a Clock_Time extraction module206to retrieve a Clock_Time from the CPU clock210.

At block312, the random number generator200may calculate a Time_Delta by subtracting previous iteration Clock_Time from current Clock_Time retrieved, and updating the Time_Value by replacing the previous Time_Value with current Time_Value.

At block314, the random number generator200may read the Clock_Time a second time, create a Fold_Counter and generate a Candidate_Bit by using the Time_Delta calculated.

In certain embodiments, the Clock_Time extraction module206of the random number generator200may also perform: saving low four bits of the current Time_Value as the Fold_Counter, and looping Fold_Counter number of time for setting Candidate_Bit to Candidate_Bit XORed with low-order bit of Time_Delta, and bit shifting Time_Delta to the right one bit. This operation may further improve and/or increase the entropy quality of the random number generator200.

At block316, the random number generator200may perform a von Neumann unbiasing analysis to generate the random bits for each of the random numbers to be generated using a von Neumann unbiasing analysis module208.

In certain embodiments, the von Neumann unbiasing analysis module208of the random number generator200may perform: generating the random bit by saving the Candidate_Bit when the Candidate_Bit is not to be discarded by the von Neumann unbiasing analysis module208.

Once the random bit of current loop is generated here, the random bit counter may be incremented.

At query block318, the random number generator200may check whether the current random bit counter equals the predetermined number of random bits of the random number to be generated. When the current random bit counter equals the predetermined number of random bits of the random number to be generated, the method300proceeds to block320. Otherwise, the method300loops back to block304to generate next random bit, until the last random bit of the random number is generated.

At block320, the random number generator200may transmit the random number generated back to the requester through the input/output interface module202.

In yet another aspect, the present disclosure relates to a computer program product operable on a CPU of a computer. In certain embodiments, the computer program product may include a non-transitory computer readable storage medium storing computer executable instructions. When these computer executable instructions are executed by the CPU, these computer executable instructions cause the CPU to perform: receiving, at an input/output interface module202of the random number generator200, a request to generate a random number having a predetermined number of random bits, and initiating a random bit generating loop to generate each random bit of the random number to be generated. The random bit generating loop may include: incorporating a CPU_Time as a randomness factor in generating random number to improve entropy quality of the random number generator200, generating a Candidate_Bit by using a Clock_Time, and generating a random bit for the random number by using a von Neumann unbiasing analysis module208, until every random bit of the random number is generated.

In certain embodiments, the incorporating may include: retrieving, using a CPU_Time extraction module204of the random number generator200, a CPU_Time from a CPU clock210of a CPU of a computer, performing, using the CPU_Time extraction module204of the random number generator200, a modulo function to the CPU_Time, and purging level 1 (L1) cache of the CPU when the result of the modulo function is zero. The purging may include: explicitly purging the L1 cache entry where Time_Value is stored, and setting the Time_Value on the next instruction causing the cache entry to be filled again.

In certain embodiments, the generating Candidate_Bit may include: retrieving, using a Clock-Time extraction module of the random number generator200, a Clock_Time from the CPU clock210, and updating a Time_Value, calculating a Time_Delta by subtracting previous iteration Clock_Time from current Clock_Time retrieved, and creating a Fold_Counter and generating Candidate_Bit by using the Time_Delta calculated. The generating may include: retrieving, using the Clock-Time extraction module of the random number generator200, another Clock_Time from the CPU clock210, saving, low four bits of the time value, as the Fold_Counter, and looping Fold_Counter number of time for setting Candidate_Bit to Candidate_Bit XORed with low-order bit of Time_Delta, and bit shifting Time_Delta to the right one bit.

In certain embodiments, the generating random bit may include: performing, using a von Neumann unbiasing analysis module208, a von Neumann unbiasing analysis to generate a random bit, checking whether the random bit generated is the last bit of the random number to be generated, returning to the beginning of the random bit generating loop to generate the next random bit until the last bit of the random number to be generated is generated when the random bit generated is not the last bit of the random number to be generated, and ending the random bit generating loop and transmitting the random number generated using the input/output interface module202when the random bit generated is the last bit of the random number to be generated. The performing a von Neumann unbiasing analysis to generate a random bit may include: generating the random bit by saving the Candidate_Bit when the Candidate_Bit is not to be discarded by the von Neumann unbiasing analysis module208.