Generate random numbers using metastability resolution time

A mechanism is provided for a circuit for generation of a random output. A bistable circuit has two stable states as an output and a clock signal as an input. The bistable circuit includes a first logic circuit and a second logic circuit cross-coupled connected together, which transition into a metastable state before resolving to the two stable states. The second logic circuit resolves to a stable state at a resolution time. A digitization circuit is configured to generate random bits corresponding to a variance of the resolution time of the second logic circuit resolving from the metastable state to the stable state for cycles of the clock signal. The resolution time randomly varies according to noise. An actual value of the stable state is eliminated as factor in generating the random bits.

BACKGROUND OF THE INVENTION

Conventional systems in the field of information security recognize the need for random numbers, and in recent years, there is an increasing demand for high-performance random number generators generating true random numbers, natural random numbers that have uniformity (i.e., are identical in probability in value and frequency of appearance) and appear without ordinality, relevance with preceding and following numbers, or predictability. One such random number generator employs a random pulse obtained by utilizing radioactive rays, thermal noise, crystal oscillator fluctuations, and other similar natural phenomena. However, the generation of truly random numbers is not an easy task. Different methods have tried to use metastable events to generate a random output value. They all seem to be less than ideal and tend to manipulate the output to restore randomness if they perceive it not to be present, which in itself is a non-random process.

SUMMARY OF THE INVENTION

According to an embodiment, a circuit for generation of a random output is provided. The circuit includes a bistable circuit having two stable states as an output and a clock signal as an input. The bistable circuit includes a first logic circuit and a second logic circuit cross-coupled connected together. The first and second logic circuits transition into a metastable state before resolving to the two stable states. The second logic circuit resolves to a stable state at a resolution time. A digitization circuit is configured to generate random bits corresponding to a variance of the resolution time of the second logic circuit resolving from the metastable state to the stable state for cycles of the clock signal. The resolution time randomly varies according to noise. An actual value of the stable state is eliminated as a factor in generating the random bits.

According to an embodiment, a method for generation of a random output is provided. The method includes generating a stable state after transitioning from a metastable state in a bistable circuit, detecting a resolution time to resolve from the metastable state to the stable state, and generating random bits corresponding to a variance of the resolution time resolving from the metastable state to the stable state for cycles of a clock signal. The resolution time randomly varies according to noise. An actual value of the stable state is eliminated as a factor in generating the random bits.

According to an embodiment, a computer program product, tangibly embodied on a computer readable medium, for generation of a random output is provided. The computer program product include instructions that, when executed by a processor, cause the processor to perform operations. The operations include generating a stable state after transitioning from a metastable state in a bistable circuit, detecting a resolution time to resolve from the metastable state to the stable state, and generating random bits corresponding to a variance of the resolution time resolving from the metastable state to the stable state for cycles of a clock signal. The resolution time randomly varies according to noise. An actual value of the stable state is eliminated as a factor in generating the random bits.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments provide a true random number generator (TRNG) based on resolution time of metastable circuits. An unconventional 1×-8× cross-coupled inverter based metacell is used to extract randomness from device thermal noise in the form of resolution time. The asymmetric circuit provides tolerance to process variation and eliminates the need for accurate symmetric physical layout design. A time difference amplifier is used to magnify the impact of thermal noise of metastability resolution. A time to digital converter followed by a parity circuit detects and digitizes the variation in resolution time. The random number generator circuit is robust across process-voltage-temperature (PVT) variations and requires no additional post processing for entropy extraction.

True random number generators are important components of secure hardware systems. TRNGs find application in cryptographic systems to generate random keys, seed other pseudo random number generators (PRNG), and secure communication protocols and software simulations. A conventional TRNG circuit harnesses randomness from physical phenomena to generate highly uncorrelated and statistically random bits. The source of randomness could be cosmic rays, stray electromagnetic field, and thermal noise in semiconductor devices or clock jitter. Digital and analog circuits are used to sample and digitize the random physical phenomenon. Analog circuits for random bit generation use noise amplifiers to magnify on-chip noise and analog-to-digital converters (ADC). A variant of ADC based TRNG circuits is chaos based TRNG circuits. One of the most commonly used circuit for randomness extraction is ring oscillator (RO) which sample and digitize on-chip jitter noise. Memory based TRNG circuits include sensing random power-up state of SRAM cells or sensing random telegraph noise (RTN) in contact resistive RAM. Analog TRNG circuits are not energy efficient and do not scale with voltage and technology. RO based TRNG circuits require multiple ring oscillators leading to increased area and power consumption. Further, ring oscillators sample jitter which is significantly affected by global power supply noise. This renders the TRNG circuit vulnerable to invasive attacks. Frequency injection and electromagnetic emanation are shown to be effective in locking frequencies of oscillators, thereby compromising randomness of TRNG output.

To counter these drawbacks, metastable circuits are proposed as energy efficient and secure RNG components. The resolution state of an ideal metastable circuit depends on the random thermal noise present in the circuit. However, metastable circuits relying on matched devices; both in device size and physical layout are significantly impacted by random variations during fabrication process. Random dopant fluctuation (RDF) introduces mismatch in threshold voltages. Lithography variations introduce gate width variation and differential loading due to interconnect line width variation. This creates a statistical imbalance in the probabilities of generating 1's and 0's in the RNG. Process variation also magnifies the impact of supply noise and on-chip temperature variations. This has necessitated adaptive circuit compensation techniques using charge dump or circuit calibration using additional matching transistors. Large volume manufacturers use additional post-processing with cryptographic algorithms like advanced encryption standards (AES). Adaptive circuit calibration techniques require constant monitoring of TRNG output and additional control logic. Constant calibration also increases correlation between bits and can provide an avenue for invasive attacks. Robust digital post-processing using algorithms like AES impose significant overhead in area and power. They also reduce the throughput and energy efficiency. Ubiquitous applications like radio frequency identification (RFID) and sensors impose extreme constraints on area and energy of cryptographic circuits. Growing popularity of mobile computing has increased the need for longer battery life (energy efficient circuits) and smaller on-chip thermal profile (ultra-low power circuits). Other applications like instruction shuffling for secure computing and secure ultra wide band communication require high bit rate entropy source. This has necessitated high speed and energy efficient hardware security.

Embodiments present a novel random number generation technique and circuit using resolution time of a metastable circuit. The proposed metastable circuit does not require a symmetric/balanced physical layout design. The metastable circuit is tolerant to variation in fabrication process and operating conditions. Also, the lightweight, ultra-low power design does not require additional post-processing to extract randomness.

FIG. 1illustrates a random number generator circuit100which is a metastability resolution time based true random number generator (TRNG) according to embodiments. The metastability resolution time based TRNG of circuit100has three major design blocks as shown in the example implementation. It is understood that fewer or more design blocks may be utilized.

The metastable circuit10(also referred to as a metacell) includes pre-charge based cross-coupled inverters to sample thermal noise. Since the standard deviation of resolution time can be as low as 0.8 ps (picoseconds) due to process variation in one example, a time difference amplifier20(TDA) is used to amplify the resolution time variation. A large enough amplification is achieved to practically capture the resolution time variation. A digitization circuit30, using a time to digital converter (TDC) and a parity circuit, measures the resolution time and digitizes the resolution time to generate a single bit (random) output per cycle.

The random number generator circuit100generates a random bit stream of 0's and 1's which can then be utilized for cryptographic applications or other applications. As noted above, thermal noise is used as the physical source of randomness in the form of resolution time of the metastable circuit10. Further details of the metastable circuit10, the time difference amplifier20, and the digitization circuit30are provided below.

FIG. 2illustrates the metastable circuit10designed using a pair of cross-coupled inverters205and210formed by complementary metal oxide semiconductor (CMOS) transistors M1, M2, M3, and M4 according to an embodiment. The output nodes A and B are pre-charged using p-channel/p-type metal oxide semiconductor (PMOS) transistors M5 and M6. PMOS transistor M7 equalizes the pre-charge voltage, and n-type/n-channel metal oxide semiconductor (NMOS) transistor M8 forms the common sink path to ground for the cross-coupled inverters205and210. The transistors M3 and M4 are sized 8× (8 times larger than) the size of M1 and M2. The asymmetric sizing ensures that the inverter210formed by M3 and M4 is always stronger (and faster) compared to the inverter205formed by M1 and M2, even in the presence of extreme fabrication process variation. As a result, the mean resolution time does not deviate significantly due to process variation and results in a simpler TDA design requirement. The output at node B is inverted by the NOT gate215to generate the resolution signal res, which is the resolution time of the inverter210.

During the negative half cycle of the clock signal (CLK), nodes A and B are pre-charged to supply voltage Vdd. As the CLK signal rises, the pre-charge is released and the state of nodes A and B enter a state of metastability. Since the transistors M3 and M4 of inverter210are a bigger size (in width) than transistors M1 and M2 in inverter205, the node B is always pulled down to 0, enabling the res signal. Note that in one implementation the transistors for inverter205may be larger than the transistors for inverter210. Depending on the thermal noise present in the circuit100, the time for nodes A and B to resolve varies, as shown inFIG. 3.FIG. 3is a graph300that illustrates variation of the resolution times for node A and node B (res) due to thermal noise for random number generator circuit100the according to embodiment. The graph300shows a line305of the clock signal (CLK), along with the line310of the output at node A and the line315of the output node B.FIG. 3shows variation in the resolution time of the metastable circuit10across 1000 samples in simulation for 32 nm (nanometer) CMOS technology. Although the metastable circuit10always resolves to a deterministic state, the resolution time varies with differential thermal noise. The y-axis shows the voltage for the node A and B output versus the time (picoseconds) shown on the x-axis it takes for each node A and B to resolve to a stable state before the next rise in the clock signal.

Nodes A and B eventually resolve to ˜0.8 V (high) and ˜0.0 V (low), respectively, starting from the rise of the clock signal line305because of thermal noise. The time that each node takes to resolve is the node's resolution time. Although the resolution time of node B (which is res) is utilized to eventually generate the random bit stream, in other implementations, the resolution time of node A may be analogously utilized. In one implementation, the difference between the resolution times of nodes A and B may be utilized. Additionally, the resolution times of both nodes A and B may be alternatingly used as the input to the time difference amplifier20.

The variation in the resolution time of node is a function of thermal noise which is the source of randomness. If there were no thermal noise, the resolution time of the metacell (metastable circuit10) for node A goes to logic 1 (0.8V) and node B to goes to logic (0V), and metacell would always be constant. The sizing of the inverter210is larger than the inverter205in order to ensure that the mean value of metastability resolution time remains nearly constant across 3 standard deviations of metastable circuit10device variation. However, the resolution has a Gaussian distribution with standard deviation 0.81 ps (picoseconds) across different cycles (of the clock signal CLK) due to variation in differential thermal noise at nodes A and B. So, for clock cycle 1 of the clock signal CLK, the resolution time for node B of the inverter210is a first (random) resolution time. Next, for clock cycle 2, the resolution time for node B of the inverter210is a second (random) resolution time. Then, for clock cycle 3, the resolution time for node B of the inverter210is a third (random) resolution time. Accordingly, for clock cycle N of the clock signal CLK, the resolution time for node B of inverter210is N (random) resolution time, where N represents the last clock cycle and accordingly the last resolution time measured from node B. The first through last (N) resolution times per cycle for node B are statistically random. The clock signal (CLK) is a particular type of signal that oscillates between a high state (e.g., positive half cycle) and a low state (e.g., negative or zero half cycle). The clock signal CLK is the global clock that runs for the random generator circuit100. The clock signal may be a square wave with a 50% duty cycle. Since the resolution time is measured with reference to the positive edge of clock signal, a counter (not shown) which is started by the clock signal and stopped by the res signal can be used to measure the resolution time. However, since the variation in resolution time due to thermal noise is of the order of 0.8 picoseconds, it may be difficult to recognize a visible change in the counter value. Hence, the time difference amplifier20is utilized to amplify the magnitude in variation of the resolution time such that the variation in the resolution time is large enough to be captured by a counter or the time to digital converter30.

FIG. 4illustrates the time difference amplifier20that amplifies the resolution time (res) with respect to the clock signal (CLK) according to an embodiment. The clock signal is delayed using a chain of inverters405and fed into one input402of a cross coupled NAND gate structure410. The other input402of the cross coupled NAND gate structure410is connected to the resolution detection signal res. Large capacitive loads415and420at the NAND gate outputs of the cross coupled NAND gate structure410provide time amplification gain. The large capacitive loads415and420are big device with a width approximately 4 micormeters (μm) in one implementation. Accordingly, the large capacitive loads415and420take a long time to go to 0, and therefore, the time difference between the clock signal CLK and the resolution time res is increased. An XOR gate430connected to the two NAND gate outputs generates an amplified signal en (enable signal). The time difference amplifier20amplifies the time difference between CLK and res. Since delay of the time resolution signal res relative to the clock signal CLK has a standard deviation of 0.81 ps due to thermal noise, the delay of amplified signal en (enable signal) relative to the CLK has a standard deviation of approximately 12 ps, as illustrated inFIG. 5.FIG. 5is a graph500illustrating the amplified delay between the clock signal (CLK) and the resolution time according to an embodiment. The graph500shows voltage on the y-axis and time (picoseconds) on the x-axis. The output of the time difference amplifier (TDA)30is a function of the time difference between the positive edge of the clock and positive edge of res signal from the metastable circuit10. Depending on the capacitive load created using the large NMOS and PMOS devices415and420, this time difference is amplified by a factor known as the amplification gain. Since the time difference between CLK and res signals has a standard deviation of 0.81 pico seconds, this variance also gets amplified by the TDA30to a Gaussian distribution of standard deviation approximately 12 picoseconds. This provides a reasonable variation in resolution time every cycle to digitize into a random bit. The impact of thermal noise, if any, in the TDA30only increases the randomness of the bit stream generated.

Now turning toFIG. 6, the time to digital converter (TDC)600includes a 7-stage ring oscillator (RO) circuit605enabled by a delayed version of the CLK signal according to an embodiment. Note that the clock signal CLK is the global clock. The amplified resolution time signal en is passed through a 6-stage delay line610generating internal clock signals clk[1:6]. The internal clock signals clk[1:6] denote the internally generated clock signals clk1, clk2, clk3, through clk6, and the internal clock signals are different from the global clock signal CLK. There are 6 D flip flop circuits615with their respective D inputs individually tapped/connected to the ring oscillator circuit605and their respective clock inputs individually connected to respective internal clock signals clk[1:6]. The internal clock signals clk[1:6] cause the D flip flop circuits615to respectively latch the state of ring oscillator circuit605at each different internal clock signal time. Depending on the thermal noise in the metastable circuit10, the resolution time signal res of node B varies. This variance in resolution time res from node B then varies the delay of the en signal relative to the global clock signal CLK in the time difference amplifier20. This in turn, varies the delay amplified signal en with respect to the global clock signal CLK in the time to digitization circuit30. The variation gets propagated to the internal clk[1:6] signals in the time to digitization circuit30that latches bits b[1:6], as shown inFIG. 7. The state latched in each of bits b[1] to b[6] is a function of thermal noise in the metastable circuit10and hence random. A parity circuit805using XOR gates810converts the 6 bits (bits b1to b6) into one random bit, as shown inFIG. 8.FIG. 8illustrates the parity circuit805which has XOR gates810connected to a D flip flop circuit815to output random bits according to embodiments. The digitization circuit30includes the time to digital converter600connected to the parity circuit805.

FIG. 7is a view700that illustrates the time varying internal clock signals clk[1:6] utilized by the D flip flop circuits615to sample the ring oscillator according to an embodiment. Graph705shows the 6 internal clock signals clk[1:6] respectively spaced by 12 ps. Graph710shows the ring oscillator signal of the ring oscillator circuit605aligned in time to the 6 internal clock signals. The x-axis shows time in picoseconds and the y-axis shows voltage. Each of the D flip flop circuits615latches a sample of the ring oscillator signal based on when the particular D flip flop circuit615receives its respective internal clock signal clk[1:6]. These 6 internal clock signals are randomly shifted back and forth (left and right) in time relative to the ring oscillator signal. This allows one or more of the 6 bits to be a random sample of the ring oscillator signal.

Note that implementations of the random generator circuit100are not limited to the exact configuration of circuits. It is understood that the configuration of the circuits discussed herein are for explanation purposes.

FIG. 9is a flowchart900illustrating a method for generation of a random output (i.e., random bits) according to an embodiment. Reference can be made toFIGS. 1-8, along withFIG. 10discussed below.FIG. 10is an example computer100that may include the circuits discussed herein and/or connect to the circuits discussed in order to execute/cause operations discussed herein.

At block905, the metastable circuit10(i.e., bistable circuit) is configured to generate a stable state (for inverter205at node A and inverter210at node B) after transitioning from a metastable state in a bistable circuit.

At block910, the time difference amplifier20is configured to detect a resolution time (i.e., the res signal from the NOT gate215) to resolve from the metastable state to the stable state (for the inverter210). The digitization circuit30receives the output signal en from the time difference amplifier20.

At block915, the digitization circuit30is configured to generate random bits corresponding to a variance of the resolution time resolving from the metastable state to the stable state for cycles of the global clock signal (CLK), where the resolution time randomly varies according to the thermal noise in the metastable circuit10.

At block920, the time difference amplifier20is configured such that an actual value (such as a 0 or 1) of the stable state is eliminated as factor in generating the random bits. The actual values (0 or 1) that node A and node B ultimately resolve to do not affect and factor into the calculation of the random bits generated by the digitization circuit30.

The time difference amplifier circuit20is configured to amplify the resolution time (res) with respect to the clock signal (CLK) in order to output an enable signal (en). The time difference amplifier circuit20is configured to generate a time difference (e.g.,FIG. 5) between the resolution time (res) and the clock signal (CLK).

The digitization circuit30(shown inFIG. 6) comprises the time to digital converter600configured to receive the enable signal (en) and the clock signal (CLK) as input in order to generate a plurality of bits (e.g., bit1through bit6(bits b[1:6])). The time to digital converter600comprises the ring oscillator circuit605connected to a plurality of latch circuits615, and the plurality of latch circuits615are connected to the delay chain circuit610. The delay chain circuit610generates different internal clock signals (clk1through clk6) utilizing the enable signal (en), such that each of the plurality of latch circuits615respectively samples a signal of the ring oscillator circuit605in order to output the plurality of bits (e.g., bit1through bit6) according to each one of the different internal clock signals (clk1through clk6).

The digitization circuit30further comprises the parity circuit805configured to receive the plurality of bits (bits b1, b2, b3. . . b6) as input, and the parity circuit805outputs a random bit per cycle of the clock signal (CLK) in order to generate the random bits.

The bistable circuit (i.e., metastable circuit10) comprises a first logic circuit (e.g., inverter205) and a second logic circuit (e.g., inverter210) cross-coupled connected together, where the first and second logic circuits transition into the metastable state before resolving to two stable states (i.e., 0 or 1). The second logic circuit (i.e., inverter210with transistors M3 and M4) is larger in width than the first logic circuit (i.e., inverter205with transistors M1 and M2) such that the second logic circuit resolves to its stable state (e.g., logic 0 corresponding to 0 V shown inFIG. 3) at the resolution time faster than the first logic circuit resolves to its stable state (e.g., logic 1 corresponding to 0.8 V).

Now turning toFIG. 10, an example of a computer1000is illustrated which includes, operates, and/or is operatively connected to the random number generator circuit100according to an embodiment. The computer1000has capabilities that may be included in embodiments. The random number generator circuit100may be constructed on a processor1010and/or connected to the processor1010as understood by one skilled in the art (for operating as discussed herein). Various methods, procedures, circuits, elements, and techniques discussed herein may also incorporate and/or utilize the capabilities of the computer1000. One or more of the capabilities (including voltage source Vdd) of the computer1000may be utilized to implement, to incorporate, to connect to, execute operations for, and/or to support any element discussed herein inFIGS. 1-9(as understood by one skilled in the art).

Generally, in terms of hardware architecture, the computer1000may include one or more processors1010, computer readable storage memory1020, and one or more input and/or output (I/O) devices1070that are communicatively coupled via a local interface (not shown). The local interface can be, for example but not limited to, one or more buses or other wired or wireless connections, as is known in the art. The local interface may have additional elements, such as controllers, buffers (caches), drivers, repeaters, and receivers, to enable communications. Further, the local interface may include address, control, and/or data connections to enable appropriate communications among the aforementioned components.

The processor1010is a hardware device for executing software that can be stored in the memory1020. The processor1010can be virtually any custom made or commercially available processor, a central processing unit (CPU), a data signal processor (DSP), or an auxiliary processor among several processors associated with the computer1000, and the processor1010may be a semiconductor based microprocessor (in the form of a microchip) or a microprocessor.

The software in the computer readable memory1020may include one or more separate programs, each of which comprises an ordered listing of executable instructions for implementing logical functions. The software in the memory1020includes a suitable operating system (O/S)1050, compiler1040, source code1030, and one or more applications1060of the exemplary embodiments. As illustrated, the application1060comprises numerous functional components for implementing the features, processes, methods, functions, and operations of the exemplary embodiments. The application1060of the computer1000may represent numerous applications, agents, software components, modules, interfaces, controllers, etc., as discussed herein but the application1060is not meant to be a limitation.

The operating system1050may control the execution of other computer programs, and provides scheduling, input-output control, file and data management, memory management, and communication control and related services.

The application1060may be a source program, executable program (object code), script, or any other entity comprising a set of instructions to be performed. When a source program, then the program is usually translated via a compiler (such as the compiler1040), assembler, interpreter, or the like, which may or may not be included within the memory1020, so as to operate properly in connection with the O/S1050. Furthermore, the application1060can be written as (a) an object oriented programming language, which has classes of data and methods, or (b) a procedure programming language, which has routines, subroutines, and/or functions.

The I/O devices1070may include input devices (or peripherals) such as, for example but not limited to, a mouse, keyboard, scanner, microphone, camera, etc. Furthermore, the I/O devices1070may also include output devices (or peripherals), for example but not limited to, a printer, display, etc. Finally, the I/O devices1070may further include devices that communicate both inputs and outputs, for instance but not limited to, a NIC or modulator/demodulator (for accessing remote devices, other files, devices, systems, or a network), a radio frequency (RF) or other transceiver, a telephonic interface, a bridge, a router, etc. The I/O devices1070also include components for communicating over various networks, such as the Internet or an intranet. The I/O devices1070may be connected to and/or communicate with the processor1010utilizing Bluetooth connections and cables (via, e.g., Universal Serial Bus (USB) ports, serial ports, parallel ports, FireWire, HDMI (High-Definition Multimedia Interface), etc.).

When the computer1000is in operation, the processor1010is configured to execute software stored within the memory1020, to communicate data to and from the memory1020, and to generally control operations of the computer1000pursuant to the software. The application1060and the O/S1050are read, in whole or in part, by the processor1010, perhaps buffered within the processor1010, and then executed.

When the application1060is implemented in software it should be noted that the application1060can be stored on virtually any computer readable storage medium for use by or in connection with any computer related system or method.

The application1060can be embodied in any computer-readable medium for use by or in connection with an instruction execution system, apparatus, server, or device, such as a computer-based system, processor-containing system, or other system that can fetch the instructions from the instruction execution system, apparatus, or device and execute the instructions.

In general, the invention may alternately comprise, consist of, or consist essentially of, any appropriate components herein disclosed. The invention may additionally, or alternatively, be formulated so as to be devoid, or substantially free, of any components, materials, ingredients, adjuvants or species used in the prior art compositions or that are otherwise not necessary to the achievement of the function and/or objectives of the present invention.