Patent ID: 12212551

DETAILED DESCRIPTION OF THE INVENTION

The invention is directed to an IoT authentication protocol that minimizes the amount of transmitted information between the device and server by leveraging a Physical Unclonable Function (PUF) to generate authentication bitstrings, session keys and long-lived keys (LLK).

The protocol leverages previous disclosed XMR reliability enhancement method, where an odd number of multiple strong bits generated by the PUF are used to encode on response bit. A nonce is transmitted from the server to the device, and the device uses the bits in the nonce to direct its encoding operation). A helper data bitstring is constructed and transmitted to the server that allows the server to reconstruct the nonce, bit-by-bit, in a reliable fashion using XMR. If the nonce reconstructed from the helper data bitstring sent by the device matches the nonce sent earlier to the device, then authentication succeeds.

PUF challenges are stored on the device at manufacturing time and do not need to be transmitted, saving lots of transmitted information. Specifically, during enrollment, challenges are stored on the device in a non-volatile memory so that no challenges need to be transmitted during authentication. Instead the nonce is used to create diversity in the authentication bitstrings (which is the helper data bitstring mentioned above) from one authentication to the next.

Authentication can be accomplished by having the server send an 8-byte nonce to the device and then the device respond with a 10-byte helper data bitstring response. Therefore PUF-based strong authentication is accomplished using as few as 18-bytes of transmitted data. The same process can be used in reverse to allow the device to authenticate the server (mutual authentication is possible).

Although any contemplated PUF can be used with the invention, the Shift-Register PUF (SRP) is used for purposes of this application. The SRP PUF leverages variations in path delays as a source of entropy. The path delays are measured on the FPGA using a high resolution on-chip time-to-digital-converter (TDC). The TDC produces digitized timing values at a resolution of approx. 20 ps. The digitized path delays (DPD) are referred to as PUF soft data. Two algorithms, called thresholding and XMR, are used to process the DPD into keys and bitstrings. A set of DPD soft data values measured from a chip's PUF are shown inFIG.1to illustrate thresholding and XMR. XMR has two modes of operation, first strong bit (FSB) mode and secure key encoding (SKE) mode. The annotations inFIG.1illustrate the FSB mode of operation during enrollment. The output of KEK FSB mode is a response bitstring shown along the bottom ofFIG.1. The algorithm used to generate the response bitstring is given as follows.

A user-specified threshold is given as input to the KEK algorithm. The threshold is used to partition the DPD into strong and weak bit classes. The two horizontal dotted lines in FIG.1bound the 0 line and represent the threshold. The DPD that appear within the threshold region, labeled as weak inFIG.1, are close to the 0 line and therefore have a high probability of producing bit flip errors. When these paths are measured again during bitstring regeneration, a small amount of noise can move these weak DPD to the opposite side of the 0 line, i.e., the side opposite of that which occurred during enrollment, resulting in a bit flip error. Weak DPD are excluded from the bitstring generation process by labeling them with a 0 in the helper data bitstring. Strong DPD, on the other hand, are located above the upper threshold or below the lower threshold, and are labeled with a 1 in the helper data bitstring. Thresholding improves the reliability of the bitstring regeneration process by creating a buffer against environmental disturbances, such as power supply noise or temperature changes.

The XMR algorithm adds a second layer of resiliency to the response bitstring regeneration process. The annotations inFIG.1show the response bitstring generated using TMR (triple modular redundancy), although any odd number is suitable for the XMR redundancy scheme with higher levels, e.g. 5MR, providing higher levels of protection against bit flip errors. The underlying principle of TMR is the use of 3 consecutive strong bits to encode one response bit. The FSB mode of the XMR algorithm scans the DPD from left to right searching for the first strong bit indicated by the helper data bitstring. For example, fromFIG.1, the leftmost DPD produces a strong 1. A 1 is added to both the response bitstring and the TMR1block of bits (which are shown for illustration purposes only). The algorithm continues to scan the DPD searching for two more instances of strong 1s, skipping strong 0s and DPD labeled weak. Bits in the helper data bitstring corresponding to strong 0s are changed from 1 to 0 during this scan. Once three strong is are located, the response bit is considered fully encoded and the algorithm searches for the next strong bit of either value to represent the second response bit. This occurs at position 7 where a strong 0 is found and the process repeats.

Regeneration reverses the process associated with the helper data bitstring, which is written during enrollment but is read during regeneration. The 1s in the helper data bitstring indicate which DPD to use to construct the TMRxsequences. A response bit is generated from each TMRxsequence using majority vote among the three TMRx, which allows any single TMRxbit to flip while still enabling the correct response bit to be generated. Therefore, TMR adds resiliency to the response bitstring regeneration process. The regeneration process is shown along the bottom ofFIG.1.

The secure key encoding (SKE) mode of KEK is identical except for one fundamental difference. Unlike FSB mode which generates a response bitstring and a helper data bitstring as output, SKE mode takes a response bitstring as input and encodes the helper data bitstring needed to reproduce it. The response bitstring for SKE is typically a randomly generated bitstring, i.e., a nonce. The enrollment operation carried out by SKE is graphically depicted inFIG.2using the same DPD data set given above inFIG.1. A 4-bit portion of the nonce nxis shown along the bottom of the figure and represents the bit string that SKE will encode in the helper data bitstring. SKE processes the nxbits one bit at-a-time, starting with the left-most ‘1’ bit. Similar to FSB mode, SKE scans the DPD left-to-right searching for a strong bit match to the nonce bit. As shown byFIG.2, this constraint is met using the leftmost strong 1. Two additional strong 1s are found at positions 5 and 6, which completes the encoding of the first nonce bit. The second nonce bit is then selected and the process repeats as illustrated inFIG.2.

Similar to FSB mode, regeneration in SKE reads the helper data bitstring and uses it to reproduce the response bitstring, i.e., the nonce. Majority voting is used to determine the final response bits by counting the number of 0 and 1 bits in each TMRxsequence and using the majority as the response bit. The regeneration process is shown along the bottom ofFIG.2.

The encoding of the 4th nonce bit is incomplete inFIG.2and requires additional DPD (not shown). In contrast, FSB mode successfully generates 4 response bits using the same DPD data set. FSB mode is ‘opportunistic’ and optimally enables the maximum size response bitstring to be generated while SKE mode skips additional strong bits that could be used but are a mismatch to the current nonce bit. However, SKE mode reveals only partial information about the underlying PUF response in cases where the nonce nxis transmitted in the open between a server and device during authentication. Furthermore, the thresholding scheme also obscures the underlying PUF response where DPD close to the threshold lines can be reclassified from strong to weak and vice versa during successive enrollments using the same challenge. These features of FSB mode are beneficial for authentication as a means of increasing the resistance of the PUF to model-building attacks.

The provisioning process for the protocol according to the invention is shown inFIG.3. A set of challenges represented by {ca}, {cb}, etc. are derived in advance with cardinality large enough to satisfy authentication requests for several years. Although the set of challenges for each device includes unique elements, there is a subset that is common in the challenge sets of all devices. The common challenges are used in the privacy-preserving device authentication component of the protocol, while the unique elements are used for verifier authentication and session key generation discussed below. The manufacturer applies the challenges to each device and the generated digitized path delays (DPD) are stored in the DPD database along with the challenge and device ID. The DPD database is transferred securely to the verifier, which will use it to interact with the devices. The DPD stored in the database represent the shared secrets that enable secure authentication and encryption operations and must be kept secure.

The message exchange diagram for the privacy-preserving mutual authentication scheme is shown inFIG.4. The authentication scheme comprises a database search operation to enable authentication to be carried out privately, and without the need for the device to first identify itself by transmitting its IDxand a verifier authentication component is used.

The protocol consists of 11 steps as annotated in theFIG.4. Step 1 involves a device requesting authentication to a server (verifier). In step 2, the server draws a random set of challenges from the common pool discussed above, i.e., a subset of challenges that have been applied to all devices.

The server also generates a nonce nx, for example nonces of size 128 and 256 bits, however any size is contemplated. The nonce can be extended to larger sizes as needed for increasing the degree of distinguishability between devices (an analysis is presented in the next section for illustrating this concept). The challenge {cx} and nonce nxare transmitted to the device. The device applies {cx} to its PUF in step 3 to generate a set of {DPDx} which are then processed into a helper data bitstring HDxusing SKE mode of KEK algorithm in enrollment mode in step 4, as shown by the example inFIG.2. The device transmits the helper data bitstring HDxto the server in step 5. Note that the device generated {DPDx} are slightly different than those stored in the database during provisioning (seeFIG.3). Measurement noise as well as changes in the temperature and supply voltage introduce small differences in the DPD when they are regenerated.

In step 6, the server searches the DPDDBfor a match to nx. For each database entry the {DPDi} corresponding to the challenge {cx} are read out and processed by running SKE mode in regeneration mode to generate a ni. If the number of mismatching bits in the niis less than a threshold, the search terminates and authentication succeeds. Assuming authentication succeeds, step 7 is executed, which represents the first step in the verifier authentication process. The exact same process is carried out except the database search operation is omitted and the verifier carries out SKE enrollment while the device carries out SKE regeneration. If the nonce ny′ generated during regeneration has fewer than threshold mismatches with ny, the device successfully authenticates the server.

Ephemeral session key can be implemented using either FSB or SKE KEK key modes as shown by the protocol illustrated inFIG.5. First, the device makes a session key generation request to the server. Note that authentication has already occurred so the server knows the IDxof the device. The server then selects a challenge cxfrom the unique stored in the DPD database for that device. The server generates a nonce that will serve as the session key (Ksession), for SKE mode only. The server retrieves the digitized path delays (DPDx) stored in the database and runs FSB or SKE in enrollment mode to generate the helper data HDx, and for FSB mode only, the response bitstring that will serve as Ksession. The server transmits and HDxto the device. The device applies the challenges to the PUF to generate its copy of the digitized path delays, DPDx, and then runs FSB or SKE in regeneration mode to generate the session key, Ksession. The device and server exchange encrypted messages.

Unlike the ephemeral bitstrings generated by the authentication and session key protocols, KEK long-lived key (LLK) generation enables a device to reproduce the same key over a long period of time. The KEK key can be used to encrypt second stage boot loaders and other ancillary data that is stored and retrieved from an NVM.

The provisioning process shown inFIG.3can also be used to boot strap LLK mode. Here, the manufacturing facility generates a small, distinct set of challenges {cz} that are transmitted to the device. The device then applies the challenges to the PUF to generate a set of {DPDz}, which are then be processed into a LLK using FSB and SKE modes (seeFIG.1andFIG.2), respectively. The helper data bitstring is stored along with the challenges in a non-secure NVM. During boot or while participating in other types of security functions that require the KEK key or a key derived from it, the device reads the helper data and challenges and runs the KEK FSB or SKE algorithms in regeneration mode.

Note that the provisioning process inFIG.3also shows the manufacturing facility recording the {DPD} in a secure database. This would only be done in security protocols that require server verifiable bitstrings or session keys to be derived from the KEK key, and would otherwise be omitted.

The privacy-preserving device authentication method according to the invention critically depends on the uniqueness statistical property of the PUF. Uniqueness is typically measured using interchip hamming distance by comparing the response bitstrings generated by the PUFs from different chips using the same challenge. The ideal value for uniqueness is 50%, which indicates that the response bitstrings from any two arbitrary PUFs match on half of the bits and mismatch on the other half. The database search carried out by the device authentication method inFIG.4implicitly measures uniqueness because it too counts the number of matching and mismatching bits under the same conditions during the database search. Therefore, the results presented are from an application of the KEK SKE algorithm in support of the uniqueness statistical property of the PUF.

The authentication method of the invention is implemented according to one embodiment using four FPGAs repeatedly for a total of 3000 iterations. For each authentication, the SKE technique must distinguish the correct device from the set of 160 FPGAs whose provisioning data is stored in the database. In order to evaluate the ability of SKE to distinguish between devices, the number of mismatching bits in the response bitstrings generated during each authentication operation are counted.

Therefore, a total of approximately 3,000*160=480,000 mismatching counts are computed. The redundant bits created by the XMR redundancy scheme are included in the mismatching bit counts. The parameters used are 128-bit nonces and 5MR. Given the 5MR generates 5 strong bits for each response bit, the total number of bits inspected in each XMR-encoded response bitstring 5*128=640 bits.

The results are shown inFIG.6with the authentication operations plotted along the x-axis and the number of mismatches in 640-bit XMR-encoded response bitstring plotted along the y-axis. The points on the curve shown along the bottom of the figure give the number of mismatches for the correct (authentic) chip while the block of points in the center portion of the figure give the number of mismatches associated with the 159 remaining devices from the database. The non-zero values associated with the authentic devices correspond to bit flips that occur during regeneration.

It should be noted that the authentic devices are able to reproduce the response bitstring exactly in every authentication by virtue of the majority voting scheme so the bit flips that occurred were corrected in every authentication. The region between the black and red curves represents the margin between authentic and non-authentic chips. The smallest delta measured is 20 bits with most margins at least 40 bits in size. The minimum margin increases to approximately 50 bits when 256-bit nonces are used, with most margins at least 70 bits in size as shown inFIG.7.

Although HELP is described above as implemented only on FPGAs, which are not suitable for low cost IoT applications, it is possible to build HELP onto a LoRa specific device or dedicated ASIC, making the invention applicable to a wider range of applications, i.e., beyond medical and defense applications that can afford the cost of an FPGA.

Each of the authentication protocols has different implementation requirements. For protocols that leverage cryptographic primitives, a key must be installed into the device during manufacturing. Common NVM storage mechanisms include flash and battery-backed RAM. The device specific stored key must be recorded during enrollment in a secure database to enable fielded authentication. Alternatively, stored challenges can be eliminated and instead challenges received at the onset of authentication from the server.

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.