Patent Publication Number: US-9425803-B1

Title: Apparatuses and methods for implementing various physically unclonable function (PUF) and random number generator capabilities

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present application claims priority to U.S. Provisional Patent Application Ser. No. 62/158,150, filed May 7, 2015, entitled “APPARATUSES AND METHODS FOR IMPLEMENTING VARIOUS PHYSICALLY UNCLONABLE FUNCTION (PUF) AND RANDOM NUMBER GENERATOR CAPABILITIES,” the disclosure of which is expressly incorporated by reference herein. 
    
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     The invention described herein was made in the performance of official duties by employees of the Department of the Navy and may be manufactured, used and licensed by or for the United States Government for any governmental purpose without payment of any royalties thereon. This invention (Navy Case 200,236) is assigned to the United States Government and is available for licensing for commercial purposes. Licensing and technical inquiries may be directed to the Technology Transfer Office, Naval Surface Warfare Center Crane, email: Cran_CTO@navy.mil. 
    
    
     BACKGROUND AND SUMMARY OF THE INVENTION 
     The present invention relates to apparatuses and methods for implementing various physically PUFs and random number generator capabilities. In particular, some embodiments are directed to various physically PUFs and random number generator implementations including systems that utilize retention time cell characteristics of dynamic random access memory (DRAM) systems. 
     A PUF can include a physical entity that is embodied in a physical structure and is easy to evaluate but hard to predict. Further, some embodiments of an individual PUF device should be easy to make but practically impossible to duplicate, even given the exact manufacturing process that produced it. In this respect, some examples of a desired PUF can have a hardware analog of a one-way function. PUFs can be used in the microelectronics industry in applications such as tracking chips in the supply chain, performing on-chip authentication for the execution of functions, and various other means. 
     Random numbers are essential in a wide range of cryptographic applications. A “random” numbers can be created from a pseudo-random number generating algorithm. All pseudo-random algorithms have a significant vulnerability issue: if one knows the algorithm and initiation seed (e.g., a starting point data input) it might be possible to reproduce the sequence. 
     According to an illustrative embodiment of the present disclosure, methods and apparatuses for implementing a Physically Unclonable Function (PUF) and random number generator capabilities comprising providing a device under test comprising a plurality of bits comprising integrated circuits each including a capacitor; placing the bits in a first state with charge on selected bit capacitors; stopping bit refresh for a first predetermined time; re-enabling refresh for a second predetermined time to read and refresh charge on all bits; reading all bits and recording addresses of bits that have experienced bit flip from a first state to a second state comprising from “1” to “0” state; performing selecting a plurality of said recorded addresses to generate a PUF or cryptographic key; and performing an operation comprising a test or verification operation with said generated information PUF or key. Various hardware elements are also provided as well as machine readable instructions for implementing and controlling aspects of the invention. 
     Additional features and advantages of the present invention will become apparent to those skilled in the art upon consideration of the following detailed description of the illustrative embodiment exemplifying the best mode of carrying out the invention as presently perceived. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The detailed description of the drawings particularly refers to the accompanying figures in which: 
         FIG. 1  shows an exemplary SDRAM bit cell schematic; 
         FIG. 2  shows an exemplary SDRAM array; 
         FIG. 3  shows exemplary retention time bit flips (SDRAM bit flips vs. time without refresh); 
         FIG. 4  shows exemplary retention time bit flips for varying times without refresh; 
         FIG. 5  shows exemplary multiple runs of bit flips for a same time without refresh (to extract an exemplary PUF response) where highlighted elements show bits that have retention time failures; 
         FIG. 6  shows an exemplary simplified method for extracting PUF response data; 
         FIG. 7  shows an alternative method for extracting PUF response; 
         FIG. 8  shows one exemplary implementation of step  6  in  FIG. 7 ; 
         FIG. 9  shows a simplified hardware/software architecture in accordance with one embodiment of the invention; and 
         FIG. 10  shows a simplified representation of two modules of an exemplary software embodiment in accordance with one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE DRAWINGS 
     The embodiments of the invention described herein are not intended to be exhaustive or to limit the invention to precise forms disclosed. Rather, the embodiments selected for description have been chosen to enable one skilled in the art to practice the invention. 
     Embodiments of the invention can incorporate randomness of an exemplary semiconductor manufacturing process for a DRAM bit cell to generate a PUF and random number generator. As some background, a schematic for a typical DRAM bit cell is shown in  FIG. 1  containing a transistor in series with a capacitor. For this example, the bit cell can be shown as reading a ‘1’ when charge is stored on the capacitor and reading a ‘0’ when the charge as been removed. Once the bit cell capacitor has been charged, it will slowly lose charge through leakage through the capacitor and transistor. The time required for a given DRAM cell to lose enough charge to read as a ‘0’ is referred to as “retention time”. A “retention time failure” is referred to a bit flipping from a ‘1’ to a ‘0’ when the time between refreshes is long enough to leak enough charge off the capacitor to read the cell as a ‘0’. A refresh time specification is generated by chip manufacturers to require that the capacitors are recharged periodically to avoid this loss of charge. 
     Large arrays of cells can be wired together as shown in  FIG. 2  to create large density DRAM memories. Transistors are accessed via row and column lines to store charge on the capacitor of the appropriate bit line. 
     Random process defects during the semiconductor manufacturing process can cause variations in the retention times between cells in a given array. These variations in retention time cause a small but significant number of cells to exhibit retention time failures that occur within the manufacturers retention time specification, but occur early in the distribution of retention time failures within the array. A plot showing the percentage of bits on four samples that have flipped from a ‘1’ to a ‘0’ due to retention time failures is shown in  FIG. 3 . There are two important data items in this figure that are important to note. 
     First, specific addresses of cell bits that have retention time failures are repeatable within each chip, e.g., for chip A, at five seconds of time without a refresh the fraction 1E-8 (or in other words, 1 out of ten to the eight power or negative 0.000001 percent) of cells fails a bit flip is observed. Repeated measurements of this experiment can yield the same fraction for a particular cell or device element and same addresses of which the bit flips are observed. 
     Second, specific addresses of bits that have retention time failures are random between different chips, e.g., chip A and chip B at five seconds of time without a refresh both yield the same or close to the same failure percentage or value e.g., a fraction 1E-8 of bit flips BUT the addresses where the bit flips occur are different between each chip. In other words, use of the same manufacturing process across or line to manufacture different devices produced on the same process or line, then chip A and chip B show a percentage of bits failing in each chip will be about the same but actual positions of failure cells will be different between chip A versus chip B. 
     Specific addresses of bits that have retention time failures can be used to construct random numbers and PUFs.  FIG. 4  shows an example of data from an array of one column and eight rows. For this example, an address is represented by a row/column combination in  FIG. 2 . The value of the bits at t=To is for all of the bits to store a ‘1’. It can be seen that while all bits start at ‘1’, they eventually transition to ‘0’. If we stop the experiment at t=T 1 , then we can see that from addresses [ADDR0:ADDR7] we have “10110110” and if we stop the experiment at t=T 2  we have “10010110” 
     PUF Design. Specific addresses of cell bits that have retention time failures can be used to construct a PUF in accordance with one embodiment of the invention.  FIG. 4  shows an example of data from an array of one column and eight rows. For this example, an address is represented by a row/column combination such as in  FIG. 2 . A value of the bits at t=T o  is for all of the bits to store a ‘1’. It can be seen that while all bits start at ‘1’, they eventually transition to ‘0’. If the experiment is halted at t=T 1 , then data at addresses [ADDR0:ADDR3] can be represented as “1011” and data at addresses [ADDR4:ADDR7] can be represented as “0110”. In this example, an exemplary design can include creating a challenge and response pair associated with an exemplary PUF design where a challenge can be an address range and a response can be some representation of bits that have flipped due to retention time failures. For example, challenge1=[ADDR0:ADDR3] with response1=“1011” and challenge2=[ADDR4:ADDR7] with response1=“0110”. A length of the address space per challenge could be lengthened as needed for the application. So, for example, if a desired application or requirement (e.g., anti-counterfeiting verification or supply chain integrity evaluation) calls for 256 bits, then a designer can select ADDR0:ADDR255 to produce a 256 bit PUF response. 
     PUF Response Extraction. A designer can extract an N-bit PUF response from retention time measurements in several different ways. One of the simplest ways for PUF response extraction is to simply extract a data pattern in first N addresses by stopping the refresh for a given time T. One drawback of this approach can include noise in the measurement around T or environmental issues (e.g., temperature). Noise can be reduced by stopping the measurement at a time T 1 , recording the result and then repeating the experiment several times and averaging the results. Another approach is to repeat testing and identify results that are the closest to each other e.g., fifty tests that generate results that have minimal differences. 
     Another way to extract a response with increased usefulness (randomness from chip to chip) is put charge on selected bits to store a predetermined value, e.g., “1”, then stop the refresh, observe retention time failures from selected bits (over time some bits lose their charge and flip to reading a “0”) and perform a mathematical operation on the addresses exhibiting the failures (e.g., “0” readings) then, for example, calculating a result of the failing address mod 2 (e.g., divide by two and take remainder and use the remainder value). The exemplary random failing addresses will then produce a mod 2 result that can be saved as the N-bit response. In other words, for example, where ten addresses produce retention failure bit flips, then an exemplary system can use a finding of whether the ten addresses were even or odd based on the mod 2 result to identify an actual value that can be used for transforming bit response into a value that can be stored and used for calculations. 
       FIG. 5  shows an example with averaging to reduce noise of stopping the refresh for time T 1  and recording addresses with bit flips. In this example, addresses one, four and seven had bit flips corresponding to a pattern or response of “010”. The length of the address space could be lengthened as needed for the application. Flow charts discussing various embodiments of such exemplary processing can be found in  FIGS. 6-8 . 
     Random Number Generator. DRAMs can contain a small percentage of cells that exhibit variable retention time (VRT) which can be exploited to produce a random number generator. These cells can have a retention time that randomly varies with time due to the absence or presence of a trap in the oxide of the transistor in  FIG. 1 . Statistics obtained from these cells can be used to determine the percentage of time spent in each different retention time state. A bin of retention time states can obtained from the statistical analysis to determine a certain retention time window to represent a ‘0’ and a complementary retention time window to represent a ‘1’. Once this is determined, multiple retention time measurements can be performed on the cell to generate a random pattern of ‘0’s and ‘1’s. Since the presence of trap sites is believed to be the cause of VRT behavior, irradiating cells with ionizing radiation may be a method to increase the VRT sensitivity and increase the number of these traps if desired. 
     Referring to  FIG. 6 , one exemplary simplified method for extracting a PUF response is shown. At step  101 , provide a device under test, e.g., a DRAM, and place all DRAM bits in a first state with charge on selected DRAM bit capacitors. At step  103 , stop DRAM bit refresh for time=T 1 . At step  105 , re-enable refresh for a predetermined time to read and refresh charge on all bits (can include refreshing existing charge at time of execution of step  105 ). At step  107 , read all bits and record addresses of bits that have experienced bit flip from first state to a second state (e.g. from “1” to “0” state). At step  109 , perform mathematical operation (e.g., averaging) on recorded addresses to generate PUF or cryptographic key. At step  111 , perform an operation, e.g., a test or verification operation, with generated information (e.g., PUF or key) and optionally place charge on all bits to erase information. 
     Referring to  FIG. 7 , an alternative method for extracting a PUF response is shown. At step  121 , provide a device under test, e.g., a DRAM, and place all DRAM bits in a first state with charge on DRAM capacitors. At step  123 , stop DRAM refresh for time=T 1 . At step  125 , re-enable refresh for time to read and refresh charge on all bits. At step  127 , read all bits and record addresses of bits that have experienced bit flip. Repeat steps  121  through  127  N times (N can be determined based on desired number of bits used in desired PUF response extraction result). At step  129 , delete addresses from recorded list that did not experience bit flips in all N iterations. At step  131 , perform processing (e.g., averaging) on recorded addresses to generate PUF or verification/cryptographic key data. At step  135 , perform one or more operations, e.g., verification operation, storing operation, random number based operation, with generated information and place charge on all bits to erase information. 
     Referring to  FIG. 8 , one exemplary implementation of  FIG. 7  step  6  is shown. At step  141 , read addresses at address_list[i] containing bit flips previously recorded. At step  143 , extract least significant bit (LSB) of addresses at address_list [i] and store as key[i]. Repeat steps  141  and  143  through list of addresses with recorded bit flips. 
     Referring to  FIG. 9 , a simplified hardware and software architecture is shown for one exemplary embodiment of the invention. A control system  201 , device test signal interface  203 , recording medium/data storage section  205 , machine readable instructions  207  containing machine readable instructions implementing embodiments of the invention and adapted for controlling the control system/processor  201 , device test signal interface  203 , and user interface  209  is shown. Machine readable instructions  207  include instructions adapted to control elements of the invention to include instructions implementing  FIGS. 6-8 . 
     Referring to  FIG. 10 , a simplified representation of some software elements in accordance with one embodiment of the invention. Modules include a PUF Response Data Extraction/Key Creation/Storage Module  301  and a PUF Response Verification Module  3 - 3  are provided. PUF Response Data Extraction/Key Creation/Storage Module  301  includes instructions configured to control various elements of an embodiment of the invention to include: Position device under test (e.g., DRAM); Couple the device with test control station; Execute machine readable instructions (e.g., some or all of  FIGS. 6-8  steps) to generate stored PUF response key data; and Record PUF response key data. Exemplary PUF Response Verification Module  303  includes instructions configured to control various elements of an embodiment of the invention to include: Position device under test; Couple device under test with test control station; Execute machine readable instructions (e.g., some or all of  FIGS. 6-8  steps) to generate test PUF response key data; Compare stored PUF response key data with test PUF response data from the device; Determine a match or no match where Match=verified and No match=not verified; and Display or output match or no-match result 
     Although the invention has been described in detail with reference to certain preferred embodiments, variations and modifications exist within the spirit and scope of the invention as described and defined in the following claims.