CORRELATION-BASED ROBUST AUTHENTICATION TECHNIQUE USING HELPER DATA ONLY

Abstract

A privacy-preserving, mutual PUF-based authentication protocol that uses soft data to exchange and correlate Helper Data bitstrings instead of PUF response bitstrings as a means of authenticating chips to prevent attacks.

Claims

1. A message exchange protocol between a client and a server that leverages soft data from a physical unclonable function (PUF) to generate Helper Data and response bitstrings by both the server and the client.

2. The message exchange protocol according to claim 1, wherein the soft data is digitized measurements of a signal.

3. The message exchange protocol according to claim 2, wherein the digitized measurements are one selected from the group: a propagation delay, a voltage, a current.

4. The message exchange protocol according to claim 1, wherein the bitstrings generated by both the server and the client are correlated to determine a degree of matching that exists in a sequence of bits that define the bitstrings.

5. The message exchange protocol according to claim 1, wherein bits in the response bitstring derived from the soft data are classified as either strong or weak, and these bits are used to define a Helper Data bitstring.

6. The message exchange protocol according to claim 1, further comprising a correlation coefficient that is produced from a pair of Helper Data bitstrings.

7. The message exchange protocol according to claim 6, wherein the correlation coefficient is used to mutually authenticate the client and the server.

8. The message exchange protocol according to claim 1, wherein the client or the server is not revealed to third parties.

9. A method for enrolling and authenticating chips comprising the steps: generating by a server a set of challenges; transmitting by the server to a chip the set of challenges; applying by the chip one or more challenges to a PUF to generate a set of soft data; returning by the chip to the server the set of soft data; creating by the server an identifier; and storing by the server the set of soft data under the identifier in a secure database.

10. The method according to claim 9, further comprising the steps: requesting authentication by a fielded chip to the server without transmitting the identifier; selecting by the server a subset of challenges; transmitting from the server to the chip the subset of challenges; applying by the chip to its PUF the subset of challenges; generating by the chip a first Helper Data bitstring; and sending to the server the first Helper Data bitstring.

11. The method according to claim 10, further comprising the steps: processing by the server the stored set of soft data in the secure database for the fielded chip; generating by the server a second Helper Data bitstring using the stored set of soft data; producing a coefficient by correlating the first Helper Data bitstring and the second Helper Data bitstring; and comparing the coefficient to a threshold to determine a characterization of the fielded chip.

12. The method according to claim 11, wherein the correlating step further comprises the step of using one method selected from the group: a bitwise AND operation, a bitwise XNOR operation, a waveform operation.

13. The method according to claim 11, wherein the characterization is one selected from the group consisting of: an authentic-enrolled chip, a non-authentic-enrolled chip, a non-authentic-not-enrolled chip, and a non-authentic-counterfeit chip.

14. The method according to claim 10, wherein the Helper Data bitstring is generated using a thresholding technique applied to the soft data.

15. The method according to claim 10, wherein the soft data is digitized measurements of a signal including one or more selected from the group: a propagation delay, a voltage, a current.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] The following drawings form part of the specification and are included to further demonstrate certain embodiments or various aspects of the invention. In some instances, embodiments of the invention can be best understood by referring to the accompanying drawings in combination with the presented detailed description. The description and accompanying drawings may highlight a certain specific example, or a certain aspect of the invention, However, one skilled in the art will understand that portions of the example or aspect may be used in combination with other examples or aspects of the invention.

[0015] FIG. 1 illustrates a block diagram of a HELP architecture according to an embodiment of the invention.

[0016] FIG. 2 illustrates a block diagram of a HELP PN database created during enrollment according to an embodiment of the invention.

[0017] FIG. 3A illustrates a graph of an index of PN for a first integrated circuit under enrollment and regeneration conditions.

[0018] FIG. 3B illustrates a diagram of server Helper Data bitstrings and response bitstrings for the first integrated circuit under enrollment conditions.

[0019] FIG. 3C illustrates a diagram of chip Helper Data bitstrings and response bitstrings for the first integrated circuit under regeneration conditions.

[0020] FIG. 4A illustrates a graph of an index of PN for a second integrated circuit under enrollment and regeneration conditions.

[0021] FIG. 4B illustrates a diagram of server Helper Data bitstrings and response bitstrings for the second integrated circuit under enrollment conditions.

[0022] FIG. 4C illustrates a diagram of chip Helper Data bitstrings and response bitstrings for the second integrated circuit under regeneration conditions.

[0023] FIG. 5A illustrates a diagram of Helper Data bitstring correlation with the first integrated circuit authenticating to the server.

[0024] FIG. 5B illustrates a diagram of Helper Data bitstring correlation with the second integrated circuit authenticating to the server.

[0025] FIG. 6A illustrates a graph of Helper Data bitstring correlation for 500 chips across 9 TV corners.

[0026] FIG. 6B illustrates a diagram of constructing curves from the Helper Data bitstring correlation of FIG. 6A.

[0027] FIG. 7A illustrates a diagram of the improved privacy-preserving, mutual PUF-based authentication protocol according to the invention.

[0028] FIG. 7B illustrates a flow chart of steps performed by the correlation-based robust authentication technique according to the invention.

[0029] FIG. 7C illustrates a flow chart of steps performed by the correlation-based robust authentication technique according to the invention.

[0030] FIG. 7D illustrates a flow chart of steps performed by the correlation-based robust authentication technique according to the invention.

[0031] FIG. 8A illustrates a graph of correlation coefficient (bits) according to an embodiment of the invention.

[0032] FIG. 8B illustrates a graph of percent change of the correlation coefficient (%) according to an embodiment of the invention

[0033] FIG. 9 illustrates graphs for worst case correlation coefficient (“CC”) differences between authentic-enrolled (“AE”) and non-authentic-enrolled (“NE”) chips.

DETAILED DESCRIPTION OF THE INVENTION

[0034] The invention relates to a privacy-preserving, mutual PUF-based authentication protocol exchanges and correlates Helper Data bitstrings instead of PUF response bitstrings as a means of authenticating chips to prevent attacks. A physical unclonable function (PUF) architecture produces soft data that captures the inherent, random variations that occur in signals from one chip to another, and represents the source of entropy for the PUF. The soft data is converted into bitstrings for use as input to a correlation-based robust authentication technique.

[0035] A wide range of PUF architectures are known. The source of entropy (randomness) for the PUF is chip-to-chip and within-die process variations that occur between and within chips from the population. The PUF architecture defines the mechanism that is used to measure small signal variations introduced by process variations effects. In some cases, the measurement process leverages the existing architectural features of the chip, e.g., the SRAM PUF measures its entropy source, i.e., the individual SRAM cells, by simply applying power to the SRAM array. For most PUFs, however, circuit components need to be added to the chip, e.g., the RO PUF requires a set of MUXs and counters to select and measure the frequencies associated with elements in the array of ROs.

[0036] In another example, the HELP PUF adds a launch-capture clocking mechanism to precisely time the delays of combinational logic paths. For PUF architectures that measure and digitize the signal behavior associated with the entropy source, the digitized values provide additional information that can be leveraged in strong challenge-response-pair (CRP) forms of authentication. The digitized values represent the magnitude of the signal behavior, e.g., RO frequency or path delay, and are often used as input to mathematical processes defined by the PUF architecture. The goal of the mathematical operations is to amplify the differences which occur among multiple copies of the individual circuit components that represent the source of entropy. The digitized values is referred to as soft data and are eventually converted to a bit and used in the response of the CRP.

[0037] Of the PUF architectures that create soft data (the RO and HELP PUFs are just two examples), the conversion to bits can be accomplished in a variety of ways. For example, the RO PUF typically selects a pair of ROs and then computes a difference by subtracting the soft data associated with the two ROs. The sign of the difference can then be used to generate a bit, with, e.g., negative differences producing a ‘0’ and positive differences producing a ‘1’. The HELP PUF also computes differences among pairings of path delays and uses a Modulus operation to assign a ‘0’ or ‘1’ to the difference.

[0038] Nearly all PUF architecture also need to deal with bit-flip errors, which are differences in the response bitstring that occur when the response is regenerated. Bit-flip errors are most probable when the magnitude of the difference, e.g., between two RO frequencies, is close to zero. In these cases, regeneration, which takes place later in the field and under potentially adverse environmental conditions, can result in the sign of the difference changing and the corresponding bit flipping from ‘0’ to ‘1’ or vice versa. Although authentication protocols can be designed to be tolerant to a small number of bit-flip errors, the number of bit-flip errors that can occur is too large in most PUF architectures to guarantee that authentication works correctly when regeneration is carried out in hash environments.

[0039] To deal with this issue, nearly all PUF architectures define an error correction or error avoidance method to improve reliability during regeneration. Error correction is the more popular of the two reliability-enhancing methods. Error correction typically processes the PUF response bits into a final response bitstring using algorithms based on linear block codes or Bose-Chaudhuri-Hochquenghen (BCH) codes. However, nearly all of the error correction schemes ignore the magnitude of the difference in the soft data and use all of the PUF response bits, including those that have a high probability of producing bit-flip errors, to construct a smaller but reproducible bitstring response.

[0040] Error avoidance schemes, on the other hand, integrate a thresholding method that skips bits that are deemed unreliable. The reliability of a bit is often directly related to the soft data associated with the bit, and in particular, the distance of the soft data value to the bit-flip line. The bit-flip line is defined by the PUF architecture as a soft threshold between ‘0’ or a ‘1’. Unlike error correction methods, error avoidance methods can only be used with PUF architectures that produce soft data values, e.g., the RO, metal resistance and the HELP PUFs are some examples.

[0041] In typical usage scenarios, an enrollment phase is carried out in which challenges are applied to the PUF in a secure facility and response bitstrings are generated for the first time. In addition to the response bitstring, PUF architectures that use either error correction or error avoidance methods also produce Helper Data bitstrings. Helper Data bitstrings are typically stored by the secure facility and transmitted to the fielded device later during regeneration to enable the PUF on the device to precisely reproduce the response bitstring. The form of the generated Helper Data bitstrings varies dramatically depending on the error correction or avoidance method employed. A key contribution of the invention relates to Helper Data bitstrings, and in particular to Helper Data bitstrings that is generated by error avoidance methods.

[0042] To exemplify the principles of the proposed technology, a HELP PUF architecture is used with data collected from a set of Zynq FPGAs. HELP uses a launch-capture technique to obtain accurate digital timing values of path delays through a combinational logic block.

[0043] FIG. 1 illustrates a block diagram of a HELP architecture 100 including the combinational logic block for a full adder. However, any functional unit can be used. For example, the combinational logic from one column of the Advanced Encryption Standard (AES) may be used. As shown in FIG. 1, clock strobing is used to create path delay (timing) soft data. Logic signal transitions are launched from the Launch FFs shown on the left using Clk.sub.1 and captured in the Capture FFs shown on the right using Clk.sub.2.

[0044] The digital clock manager (DCM) on the FPGA is used to create the clocks, with dynamic fine phase shift enabled for Clk.sub.2. Dynamic fine phase shift allows a state machine running in the programmable logic (PL) of the FPGA to increment the phase shift by increments of 18 ps as shown on the right side of FIG. 1. A path through the full adder is timed by repeatedly applying a 2-vector sequence to the Launch FFs until the signal propagating along the path shown is successfully captured in the Capture FE A successful capture occurs in this example when the ‘0’ produced from the first vector V.sub.1 of the 2-vector sequence is overwritten by the ‘1’ produced by V.sub.2 as illustrated in the middle portion of FIG. 1. When this occurs, the current fine phase shift value, which is an integer between 0 and approx. 500, is recorded by HELP as the digitized timing value for this path. These timing values represents the soft data associated with HELP.

[0045] During enrollment, a set of timing values, called PUF Numbers (“PN”) for each chip are stored in the rows of a secure database 150 as shown in FIG. 2. This data is consulted by the secure server to authenticate these chips after they are deployed in fielded systems. The storage of soft data on the server, in contrast to response bitstrings, is the first of several significant differences that exist between the correlation-based robust authentication technique of the invention and the current known PUF-based protocols. As indicated above, the proposed protocol leverages Helper Data bitstrings to carry out authentication. The Helper Data bitstrings are derived from the PNs stored in the secure database on the server, and from an instance of HELP that is programmed into the PL side of an FPGA representing the fielded device (also referred to as a chip or a token). The entropy that is associated with each token is captured by the PN stored in the server database. An adversary carrying out machine learning attacks against the protocol would attempt to learn the timing information stored in the database by reverse-engineering the bitstring responses that are exchanged openly over the network. Once learned, the adversary can then impersonate the token. Therefore, it is vital that the relationship between the PN and the response bitstring be obscured and remain hidden to make this task difficult or impossible for the adversary.

[0046] FIG. 3A-FIG. 3C and FIG. 4A-FIG. 4C illustrate how bitstrings and Helper Data bitstrings are generated by FPGAs using an error avoidance scheme called Margining, as a precursor to the correlation correlation-based robust authentication technique. The environmental conditions for data collected during enrollment and stored in the secure database are specified as 25° C. under nominal supply voltage conditions (1.00V) while to fielded tokens are subjected to high temperature (85° C.) and low supply voltage conditions (−5% or 0.95V).

[0047] FIG. 3A illustrates a graph 200 of an index of PN for a first integrated circuit (“token C1”) and FIG. 4A illustrates a graph 300 of an index of PN for a second integrated circuit (“token C2”) under enrollment and regeneration conditions. Each graph 200, 300 plots a set of 18 PN (timing values) along the x-axis. PN obtained from the secure server database are shown by curves “A1”, “B1” and the PN generated on-the-fly by these chips during regeneration in the field are shown by “A2”, “B2”. Un-compensated temperature-voltage noise (“TVNoise”) causes the offset seen between curves “A1” and “A2” seen in FIG. 3A and “B1” and “B2” seen in FIG. 4A. An interesting example labeled ‘wrap’ is shown for the 2nd data point in the FIG. 3A where TVNoise has caused the point to ‘wrap’ from the enrollment value near 20 back around to a value near 0 during regeneration. Despite these anomalies, curves “A1”/“A2” and curves “B1”/“B2” seen in each graph track very closely, i.e., they are correlated.

[0048] The HELP PUF converts the PN into a bitstring by applying the following algorithm, First, a pseudo-random number generator selects pairs of PN and creates differences. A temperature-voltage compensation method (“TVComp”) is then applied to the differences to compensate the measured timing values for changes introduced by environmental conditions. Finally, a Modulus operation is applied to the compensated differences to remove path length bias effects.

[0049] The Modulus operation is defined in the standard way as returning the positive remainder after dividing by the Modulus. The value of the Modulus is one of several parameters to the HELP algorithm. The graphs shown in FIG. 3A and FIG. 4A use a Modulus of 20, which is reflected as the maximum value given on the y-axis.

[0050] As mentioned earlier, the error avoidance scheme implemented within HELP is called Margining. The Margining scheme skips soft data values—i.e., PN—in cases where the probability of a bit-flip error is large. These highly probable bit-flip regions are labeled “weak” in the center of graph 200 in FIG. 3A and graph 300 in FIG. 4A, and are located adjacent to the bit-flip lines 0, 10 and 20. In other words, PN that are within a distance of 2.0 of these bit-flip lines have the highest probability of changing value. For example, the PN labeled “wrap” represents a bit-flip error which is introduced by un-compensated TVNoise. PN that are located in the “weak” regions are assigned ‘0’ in the Helper Data bitstring.

[0051] FIG. 3B illustrates a diagram 220 of server Helper Data bitstrings and response bitstrings for the first integrated circuit under enrollment conditions. As shown, the “C1 Helper Data” bitstrings begins with “000”, which reflects that the status of the first 3 PN in the “A1” curve of graph 200 of FIG. 3A. In contrast, the 4th bit is ‘1’ because the PN at position 4 in graph 200 of FIG. 3A falls within the “strong 1” region,

[0052] The “C1 Mixed BS” in FIG. 3B records the bit value associated with each of the 18 PN, with PN<10.0 assigned ‘0’ and those >=10.0 assigned ‘1’. This response bitstring corresponds one-to-one to the “C1 Helper Data” bitstring and contains both strong and weak bits. The “C1 Strong BS” is constructed from the “C1 Mixed BS” by selecting only those bits identified as strong in the “C1 Helper Data” bitstring,

[0053] FIG. 4B illustrates server Helper Data bitstrings and response bitstrings for the second integrated circuit under enrollment conditions.

[0054] FIG. 3C illustrates a diagram 240 of token Helper Data bitstrings and response bitstrings for the first integrated circuit under regeneration conditions. FIG. 3C illustrates corresponding bitstrings generated using the regeneration data points of curve “A2” from graph 200 of FIG. 3A. FIG. 4C illustrates a diagram 340 of token Helper Data bitstrings and response bitstrings for the second integrated circuit under regeneration conditions. FIG. 4C illustrates corresponding bitstrings generated using the regeneration data points of curve “B2” from graph 300 of FIG. 4C.

[0055] One known HELP authentication protocol describes a DualHelperData scheme where both the Helper Data bitstrings and Strong bitstrings are exchanged between the server modeled in FIG. 3B and FIG. 4B and the tokens modeled in FIG. 3C and FIG. 4C. As discussed, exposing the Strong bitstrings to the adversary enables model-building attacks where the adversary attempts to reverse engineer the PN stored in the secure database using machine learning (ML) algorithms. Although attempts to model-build HELP have not been successful to-date, the exposure of the response bitstrings still represents a vulnerability that enables ML attacks. If it becomes possible to construct an ML attack that is able to deduce the relationships among the PN, then the response bitstrings to other challenges can be predicted, and the token impersonated.

[0056] As a mitigation strategy for attacks, an authentication protocol exchanges only the Helper Data bitstrings, Authentication is carried out by correlating the Helper Data bitstrings generated using the enrollment data on the server with the Helper Data bitstring generated on-the-fly by the token. The simplest correlation strategy is to compute a new bitstring by bitwise AND'ing the Helper Data bitstrings from the server and token and then counting the number of ‘1’s in the AND'ed version. The number of ‘1’s is the correlation coefficient (“CC”) because it reflects the level of similarity that exists between the two Helper Data bitstrings.

[0057] FIG. 5A illustrates a diagram 250 of Helper Data bitstring correlation with the first integrated circuit authenticating to the server and FIG. 5B illustrates a diagram 350 of Helper Data bitstring correlation with the second integrated circuit authenticating to the server. The Helper Data bitstrings are obtained from the soft data as shown in FIG. 3A-FIG. 4C. As an example, FIG. 5A shows an authentication attempt by token C1 while the right column shows an attempt by token C2. The top-most bitstrings 251, 351 in FIG. 5A and FIG. 5B, respectively, are the Helper Data bitstrings transmitted by the tokens to the server. For each Helper Data bitstring received, the server carries out an exhaustive search operation using the PN stored its secure database. The server constructs the Helper Data bitstrings in each column.

[0058] For each Helper Data bitstring it constructs, the server bitwise AND's it with the received token's Helper Data bitstring. For example, the AND'ed versions are labeled “C1 AND C1 Helper Data” and “C1 AND C2 Helper Data” in FIG. 5A. As discussed, the bitwise AND operation is a form of correlation that acts to preserve more ‘1’s in cases where the bitstrings are similar. The CCs (number of ‘1’s) are reported to the right of AND'ed Helper Data bitstrings as shown by 252 in FIG. 5A and 352 in FIG. 5B.

[0059] The results for both authentication attempts show higher correlation for cases where the server-generated Helper Data bitstring is derived from PN data that belongs to the token that is attempting to authenticate. In other words, the authenticating token is correctly identified to the server using only the information provided by the CC. This example uses only a small number of 18 PN from a larger set of 2048 PN that are produced by each iteration of the HELP algorithm.

[0060] Using 500 FPGAs, results shown in the graph 400 FIG. 6A illustrate the full length bitstrings and PN collected across 9 TV corners obtained by correlating Helper Data bitstrings from the HELP PUF with a Margin of 3 and a Modulus of 18. Each of the 9 curves plots the CCs (y-axis) for the 500 chips (x-axis), The authenticating token is labeled C250 as shown by 425.

[0061] The diagram 450 given in FIG. 6B shows how the curves in FIG. 6A are constructed. Here, the token's Helper Data bitstring on the left, regenerated under 25° C., 1.00V, is transmitted to the server on the right. A second authentication request is also shown where the token in this case is regenerating Helper Data with environmental conditions set to −40° C., 1.05V. The server carries out an exhaustive search using data stored in the Enroll DB separately for each of these two authentications and computes a set of 500 CCs. The CCs are plotted along the x-axis in FIG. 6A as the top-most and bottom-most curves. A similar process is carried out to construct the CCs for the remaining 7 curves in FIG. 6A but using PN from the other TV corners.

[0062] The CCs in FIG. 6A for C250 (referred to as the authentic-enrolled (“AE”) chip) vary from more than 450 bits in the top curve to approx. 380 bits in the bottom curve. Although the correlation is weakened when the token is exposed to harsh environmental conditions, it still remains high with respect to the CCs produced by the remaining 499 chips (referred to as non-authentic-enrolled (“NE”) chips) from the DB. The largest value from a NE chip is approx. 260. The large Margin between the AE and NE CCs indicates that the server defines a threshold to distinguish successful authentications from unsuccessful authentications with very high probability, e.g., any value between 260 and 380 works in this example.

[0063] Although only AE and NE authentication attempts are considered, it is also contemplated to include non-authentic-not-enrolled (“NN”) and non-authentic-counterfeit (“NC”) authentication attempts.

[0064] Under the AND correlation scheme, it is possible for adversaries to construct Helper Data bitstrings with all ‘1s’, which guarantees a large number of matches. However, large CCs would occur for ALL data sets in the secure DB, which, in turn, would be flagged by the server and result in a failed authentication attempt. This is true because the server allows only one CC to be above the threshold in order for an authentication attempt to be classified as successful FIG. 7A illustrates a diagram 500 of the improved privacy-preserving, mutual PUF-based authentication protocol according to the invention. FIG. 7A illustrates the enrollment and chip authentication operations, including the message exchanges between the chip and server.

[0065] FIG. 7B-FIG. 7D illustrate flow charts of the steps performed by the correlation-based robust authentication technique according to the invention.

[0066] Enrollment is performed in a secure facility using a confidential FPGA programming bitstream that allows access to the PUF's soft data. FIG. 7B illustrates a flow chart 520 of steps performed by the correlation-based robust authentication technique shown in FIG. 7A. At step 521, the server generates challenges {c.sub.k}. At step 522, the challenges {c.sub.k} are transmitted to the chip. The chip then applies the challenges to its PUF to generate the set {PN.sub.j} at step 523, which is returned to the server at step 524. The server generates a chip identifier ID.sub.i at step 525. At step 526, the server stores the soft data set {PN.sub.j} under ID.sub.i in its secure database DB.

[0067] FIG. 7C illustrates a flow chart 530 of steps performed by the correlation-based robust authentication technique directed to the first phase of authentication (chip authentication) for a HELP PUF. At step 531, a fielded chip i requests authentication to the server (note, no chip ID is transmitted to the server in order to preserve privacy). The server produces a nonce n.sub.2 at step 532. At step 533, the server selects a set of challenges {c.sub.m}. The challenges {c.sub.m} are a subset of the challenges {c.sub.k} used during enrollment. At step 534 both the nonce and subset of challenges are transmitted to the chip. The nonce n.sub.2 is used to select a parameter at step 535. The parameter may be a Margin or a Modulus parameter. At step 536, the chip applies the challenges {c.sub.m} to its PUF, along with the parameter (i.e., Margin), which is selected using the XNOR of the chip and server generated nonces n.sub.1 and n.sub.2. At step 537 a Helper Data bitstring h′ is generated, for example, using the Margining scheme described above. Both h′ and n.sub.1 are sent to the server at step 538.

[0068] The server then carries out an exhaustive search by processing soft data sets {PN.sub.j}.sub.i it stores in its database for each chip i as shown at step 541 of the flow chart 540 in FIG. 7D. At step 542 a Helper Data bitstring h is generated internally using each of the stored data sets {PN.sub.j}.sub.i and the same parameter (Margin) that was used by the chip. The Helper Data bitstring h′ is then correlated with h based on a bitwise AND operation (discussed above), but other possibilities exist, e.g., bitwise XNOR or standard waveform correlation methods used in signal processing are possible. At step 543, a correlation coefficient CCE is produced that can then be compared to a threshold t at step 544. The threshold is predetermined, for example by using a characterization process in a secure facility. The goal of characterization is to select a threshold that unambiguously distinguishes authentic-enrolled chips (AE) from non-authentic-enrolled (NE), non-authentic-not-enrolled (NN) and non-authentic-counterfeit (NC) chips.

[0069] The last phase of the improved privacy-preserving, mutual PUF-based authentication protocol is for the chip to authenticate the server. This phase is not shown, but is identical except the message exchanges are reversed and the exhaustive search process is omitted. Server authentication is not performed unless chip authentication succeeds, in which case, the server has identified the chip's soft data set {PN.sub.j}.sub.i. The server uses this {PN.sub.j}.sub.i to generate another Helper Data bitstring, which is transmitted to the chip. Note that the Helper Data bitstrings generated during server authentication are distinct from those generated during chip authentication because the challenge subset {c.sub.m} and nonces n.sub.1 and n.sub.2 are selected differently in this phase. In addition to the Margin parameter that are selected by nonces, other parameters can be introduced to further expand the CRP space, as known in reference to the HELP algorithm. Authentication succeeds if both of the chip and server authentication phases succeed, and fails otherwise.

[0070] Following are experimental results that present a worst case scenario. A larger set of the HELP CRP space is used. The data analyzed was collected from a set of 500 chip-instances under enrollment and 9 temperature-voltage (TV) corners.

[0071] The full CRP space of the HELP algorithm is defined by (1) sets of challenges (2-vector sequences) and corresponding Path-Select-Masks where each challenge set produces 4096 PN and (2) a set of parameters, consisting of two LFSR seeds, two floating point parameters called the reference mean and range, and a Modulus and Margin. The challenges and Path-Select-Masks create a CRP space with size exponentially related to the size of the functional unit used as the entropy source. The parameters increase the CRP space by approx. 221, i.e., there are 221 2048-bit bitstrings that can be generated by varying these parameters for each set of challenges and Path-Select-Masks. Only one set of challenges and Path-Select-Masks are used for the analysis in order to focus on analyzing Helper Data bitstrings produced by varying the parameters. Although this represents only a small subset of the entire CRP space, results show that the correlation-based robust authentication technique works well across this statistically significant sample.

[0072] The two LFSR seed parameters allow up to 2048 distinct bitstrings to be generated, each of length 2048 bits. The reference mean and range increase the number of distinct bitstrings by a factor of approx. 100. The analysis performed here analyzes the Helper Data bitstrings generated using 10 distinct LFSR seeds, one combination of the reference mean and range and a set of 11 Moduli and 3 Margins.

[0073] The approach taken for the analysis of the worst case is illustrated using the graph 600 of FIG. 8A and the graph 650 of FIG. 8B. The data presented is derived using only one Modulus and Margin in this embodiment, and is expanded to the larger set discussed below. The curves shown by 601 in FIG. 8A plot the CCs computed by the server when each of the 500 AE chips identified along the x-axis authenticates. These curves are constructed as described above, but now include data for all 500 chips and 9 TV corners shown (see chips in FIG. 6B), and for the 10 LFSR seeds. Therefore, there are 90 curves, each with 500 AE CCs. Similarly, the curves shown by 602 in FIG. 8A plot the worst-case (largest) NE CC among the remaining 499 CCs in each authentication attempt while the curves shown by 603 plot the average NE CC.

[0074] It should be noted that the curves shown in FIG. 8A are in a different format than the curves shown in FIG. 6A. In particular, the CCs in the curves 601 of FIG. 8A correspond to the AE chip only and the curves 602 plot only one CC (the worst case) from the 499 NE CCs in each of the curves of FIG. 6A. Therefore, only two points from each of the curves in FIG. 6A are plotted in FIG. 8A, and appear as column pairs in the curves 601 and 602. The two points in each pair represent the worst case (smallest) separation between the AE and NE CCs and visually portray how close a NE chip gets to being falsely authenticated as the AE chip on the server. In summary, the number of CC pairs is given by 500*9 TV corners*10 LFSR seeds=45,000. Note that each pair corresponds to 500 authentication attempts so in total, there are 45,000*500=22,500,000 (22.5M) authentication attempts.

[0075] As indicated, the key feature of FIG. 8A is the distance (separation) between pairs of points in the curves 601 and 602. This separation is key to the server's ability to distinguish between AE and NE, NN and NC chip authentications. Unfortunately, a hard threshold (horizontal line) between points cannot be drawn without some AE authentications failing (false negatives) and some NE authentications succeeding (false positives).

[00001]$\begin{array}{cc}\mathrm{PCH}=\frac{\left({\mathrm{CC}}_{\mathrm{largest}}-{\mathrm{CC}}_{2\mathrm{ndlargest}}\right)}{{\mathrm{CC}}_{\mathrm{largest}}}& \mathrm{Equation}\left(1\right)\end{array}$

[0076] To deal with this issue, Equation (1) computes the percentage change CC, called PCH, as follows. First, a set of CCs are computed using the chip's Helper Data bitstring against each of the server computed Helper Data bitstrings. Then the two largest CCs are identified and plugged in Equation (1) to obtain the PCH value. The server successfully authenticates the chip if the PCH is larger than a hard threshold value, and fails otherwise. In cases where the authentication is successful, the soft data in the Enroll DB associated the largest CC, CC.sub.largest, identifies the authenticating chip,

[00002]$\begin{array}{cc}{\mathrm{PCH}}_{\mathrm{AE\_WC}}=\frac{\left({\mathrm{CC}}_{\mathrm{AE}}-{\mathrm{CC}}_{\mathrm{worst\_case}\mathrm{\_NE}}\right)}{{\mathrm{CC}}_{\mathrm{AE}}}& \mathrm{Equation}\left(2\right)\end{array}$

[0077] The curves in FIG. 8B plot a closely related metric, defined as PCH.sub.AE_WC in Equation (2), using the CCs from FIG. 8A.

[0078] Here, CC.sub.AE is associated with an AE chip obtained from the curves 601 in FIG. 8A and CC.sub.worst_case_NE is the other point in the pair obtained from curves 602. Although in practice the authenticate chip is not known, it turns out for every CC pair in FIG. 8A, CC.sub.largest=CC.sub.AE and CC.sub.2nd_largest=CC.sub.worst_case_NE. Therefore, Equation (1) and Equation (2) produce the same results for this set of CCs. In fact, the PCH.sub.AE_WC would be negative if any of the CC.sub.AE is not the largest CC among the 500 generated by the server for the authentication attempt. The smallest PCH.sub.AE_WC present is circled in FIG. 8B and is approx. 18%. This indicates that all of the CC.sub.AE are significantly larger than the NE CCs across the 22.5M authentications. Expressed in terms of bits, the smallest CC from FIG. 8A is approx. 300 bits. Therefore, the smallest separation between AE and NE CCs is approx. 300*0.18=54 bits. A hard threshold can now be defined, e.g., at 15% as shown in FIG. 8B, that enables the server to properly identify and authenticate chips with high probability.

[0079] Now, validation using a larger CRP space is discussed. An analysis reporting PCH.sub.AE_WC is expanded to a set of 11 Moduli and 3 Margins. This analysis is repeated with and without Offsets. An Offset for the HELP algorithm can significantly improve the Entropy and uniqueness in the Strong bitstrings (labeled Strong BS in FIG. 3B, FIG. 3C, FIG. 4B, FIG. 4C). This is accomplished by having the server compute a set of Offsets using data from the Enrollment DB that are applied to the PN as shown in FIG. 3A and FIG. 4A before the PN are processed into bits using the Margining scheme. The offsets are small vertical shifts less than ½ the Modulus which optimize Entropy in each PN by ensuring that half of the chips in the population produce a ‘0’ for the PN and half produce a ‘1’.

[0080] The Offset has very little impact on the CCs. The weak and strong regions in the graph 200 of FIG. 3A and graph 300 of FIG. 4A illustrate why this is true. Unlike the Strong bitstring values which are determined by the bit-flip lines at 0 and 10, the Helper Data bitstring values are determined by the four strong-weak region boundaries. The positions of these boundaries allow a Helper Data bit to flip between 0 and 1 in either of the strong bit regions labeled ‘strong 0’ and ‘strong 1’. Therefore, offsetting the PN populations to improve the entropy associated with the Strong bitstring has little effect on the CCs. In fact, the correlation is slightly reduced based on the results shown in FIG. 9. Eliminating the overhead of computing and applying Offsets is yet another benefit of the correlation-based robust authentication technique over the known Strong bitstring approach.

[0081] FIG. 9 illustrates graphs for worst case correlation coefficient (“CC”) differences between authentic-enrolled (“AE”) and non-authentic-enrolled (“NE”) chips expressed as percentage change using PCH.sub.AE_WC in Equation (2) under best case environmental conditions (25° C., 1.00V on left) and worst case environmental conditions (−40° C., 0.95V in middle and 85° C., 1.05V on right) for 22.5M authentication attempts for Margins 2 through 4 and Moduli 10 through 30.

[0082] As shown in FIG. 9, the top row gives results with NO Offsets and bottom row gives results using Offsets, particularly Population Offsets. The bar heights represent the worst case PCH.sub.AE_WC for a set of Moduli given along the x-axis and Margins given along the y-axis, Note that only one PCH.sub.AE_WC is reported for each Margin-Moduli combination, and in particular, the value that corresponds to the circled point in FIG. 8B labeled ‘smallest value’, Negative height bars represent that at least one authentication failure has occurred, i.e., at least one CC.sub.AE is not the largest CC among the 500 CCs computed as discussed above.

[0083] Positive bars indicate server identifies AE chip correctly in all 22.5M authentications while negative bars indicate at least one false authentication with an NE chip occurred. Results for NO Offset are slightly better than results with Offsets applied.

[0084] More specifically, the two bar graphs in each of the three columns in FIG. 9 gives the results for 3 TV corners, namely 25° C., 1.00V on the left, −40° C., 0.95V in the middle and 85° C., 1.05V on the right. The latter two columns represent worst case TV corners, i.e., the results for the remaining 6 TV corners produce bars that are larger. From these results, it is clear that the Margin-Moduli combinations with negative bar heights that cannot be used in the privacy-preserving, mutual PUF-based authentication protocol.

[0085] However, Moduli between 18 to 24 for Margin 3 and between 22 and 28 for Margin 4 produce bar heights greater than 15% in the top row of ‘NO Offset’ bar graphs. Similar results are obtained in the Offset row but the bars are slightly smaller and therefore the hard threshold can be to be reduced to approx. 12% to avoid false negative authentications.

[0086] The bar graphs in the left column for TV corner 25° C., 1.00V show the best results. Only small differences exist between the No Offset and Offset results. And unlike the results for the other TV corners, the bar heights for all Moduli and Margins are positive, indicating that the values for CCAS are the largest among the sets of 22.5M authentications carried out in each analysis.

[0087] The privacy-preserving, mutual PUF-based authentication protocol exchanges and correlates Helper Data bitstrings instead of PUF response bitstrings as a means of authenticating chips. Helper Data is derived from the PUF response bitstrings and therefore the Helper Data bitstrings inherit the randomness and uniqueness characteristics associated with the PUF's source of entropy. By eliminating PUF response bitstrings in the message exchanges between the chip and server, attacks such as model-building are much more difficult to carry out.

[0088] The correlation-based robust authentication technique is demonstrated on a statistically significant set of FPGAs using the HELP algorithm, and a simple method thresholding method is used by the server and chip to distinguish between authentic and non-authentic chips.

[0089] As mentioned above, although HELP is used in this work, it is for exemplary purposes only. It is contemplated that the invention is applicable to any PUF that produces soft data, i.e., digitized values that capture the magnitude of signal behavior such as delay or metal resistance, including the Ring Oscillator (“RO”) PUF and an enhanced version of arbiter PUF.

[0090] While the disclosure is susceptible to various modifications and alternative forms, specific exemplary embodiments of the invention have been shown by way of example in the drawings and have been described in detail. It should be understood, however, that there is no intent to limit the disclosure to the particular embodiments disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the scope of the disclosure as defined by the appended claims.