Robust computational fuzzy extractor and method for authentication

A method and system for authenticating a device is disclosed. The method includes the steps of: receiving a helper bit string and a first MAC; measuring a first response bit string of a physical unclonable function of the device with respect to a challenge bit string; subtracting the first response bit string from the helper bit string; decoding a result of the subtraction using a uniformly distributed random matrix, the shared secret bit string being provided from the decoding if the helper bit string was encoded using a previously measured second response bit string that is within a threshold level of similarity to the first response bit string, the decoding outputting an error value otherwise; determining a second MAC based on the shared secret bit string, the uniformly distributed random matrix, and the helper bit string; and determining whether the second MAC matches the first MAC.

FIELD

The method and devices disclosed in this document relates to cryptography and, more particularly, to use of physical unclonable functions and fuzzy extractors for device authentication.

BACKGROUND

In some applications, physical unclonable functions (PUFs) are used to authenticate devices. However, the raw response of any PUF is noisy and has to be post-processed to derive e.g. an identical key every time the PUF is queried. Fuzzy extractors can be constructed with error correcting codes and used to remove the noise from the PUF's raw response using so-called helper data, which is publicly available. Due to the nature of the error correcting codes (and the redundancy information present in the helper data), traditional information-theoretic fuzzy extractors do not preserve the entire entropy present in the PUF's raw response. For example, if the raw response of a PUF has n bits of entropy, only m bits can be used after the raw response of the PUF is processed by a traditional information-theoretic fuzzy extractor, where m<n. Such a loss of entropy is particularly bad in situations where the PUF's raw response has a limited amount of entropy. As an example, preliminary experiments indicate that the entropy of a MEMS-PUF's raw response amount to little less than 90 bits. However, this is not sufficient in terms of security if the PUF response is used to derive a symmetric key. For instance, the German BSI technical guideline TR-02102-1 “Kryptographische Verfahren: Empfehlungen und Schlüssellängen” (version 2015-01, 10 Feb. 2015) requires a symmetric secret key length of at least 128 bits.

Accordingly, it would be advantageous to provide an alternative to the traditional fuzzy extractor in which the full entropy of a PUF can be preserved and from which longer keys can be derived. Additionally, it would further be advantageous if the method is secure against both passive eavesdroppers and active attackers.

SUMMARY

A method for authenticating a first device is disclosed. The method includes the steps of: receiving, with a transceiver of the first device, a helper bit string and a first message authentication code tag from a second device that is remote from the first device; measuring a first response bit string of a physical unclonable function of the first device with respect to a challenge bit string, the physical unclonable function being provided by one of the processor of the first device and a further physical component of the first device; subtracting, with the processor of the first device, the first response bit string from the helper bit string; decoding, with the processor of the first device, a result of the subtraction using a uniformly distributed random matrix, the shared secret bit string being provided from the decoding if the helper bit string was encoded using a previously measured second response bit string that is within a threshold level of similarity to the first response bit string, the decoding outputting an error value otherwise; determining, with the processor of the first device, a second message authentication code tag based on the shared secret bit string, the uniformly distributed random matrix, and the helper bit string; and determining, with the processor of the first device, whether the second message authentication code tag matches the first message authentication code tag.

A further method for authenticating a first device is disclosed. The further method includes the steps of: measuring a first response bit string of a physical unclonable function of the first device with respect to a challenge bit string, the physical unclonable function being provided by a component of the first device; deriving, with a processor of the first device, a shared secret bit string from a uniformly distributed random vector; encoding, with the processor of the first device, a helper bit string by multiplying a uniformly distributed random matrix with the uniformly distributed random vector and adding the first response bit string to a result of the multiplication; determining, with the processor of the first device, a first message authentication code tag based on the shared secret bit string, the uniformly distributed random matrix, and the helper bit string; and transmitting, with a transceiver of the first device, the helper bit string and the first message authentication code tag to a second device that is remote from the first device.

DETAILED DESCRIPTION

FIG. 1shows a system100comprising a proving device102(also referred to herein as the “prover”) and a verifying device104(also referred to herein as the “verifier”). The proving device102and the verifying device104communicate with one another via an insecure communication channel, such as a network106(e.g., the Internet, a wireless local area network, or a wireless mesh network) or a direct communication channel (e.g., radio frequency identification (RFID) or near-field-communication (NFC)). Given the insecurity of the communication channel, the verifying device104and the proving device102are configured to perform an authentication process at least to verify the identity and authenticity of the proving device102. In some embodiments, the authentication process is a mutual authentication process in which the identities and authenticity of both devices102and104are verified.

In some embodiments, the proving device102may comprise a security token, a smart card, a hardware security module, a machine, a controller, an actuator, a sensor, a tablet computer, a smartphone, a laptop, or any other device configured for communication with a host system or another device. In at least some embodiments, the proving device is a lightweight device with relatively limited processing capability and memory, such as an Internet of Things (IoT) device.

In the embodiment shown, the proving device102comprises a processor108, memory110, and a transceiver112. The proving device102may also comprise many additional components which are operably connected to the processor108and configured to provide one or more services or functions, such as sensing elements, actuators, interfaces, displays, etc. (not shown). The memory110is configured to store program instructions that, when executed by the processor108, enable the proving device102to perform one or more services or functions. In addition to program instructions for implementing the primary services or functions of the proving device102, the program instructions at least include an authentication program114for proving the identity and authenticity of the proving device102to the verifying device104. The memory110is also configured to store data116, which may include data utilized by the authentication program126.

The memory110may be of any type of device capable of storing information accessible by the processor108, such as a memory card, ROM, RAM, write-capable memories, read-only memories, hard drives, discs, flash memory, or any of various other computer-readable medium serving as data storage devices as will be recognized by those of ordinary skill in the art. Additionally, although the memory110is shown monolithically in F, the memory110may comprise several discrete memories of different types which are used for different purposes.

The processor108may include a system with a central processor, multiple processors, dedicated circuitry for achieving functionality, or other systems. Furthermore, it will be recognized by those of ordinary skill in the art that a “processor” includes any hardware system, hardware mechanism or hardware component that processes data, signals or other information.

The transceiver112may be any of various devices configured for communication with other electronic devices, including the ability to send communication signals and receive communication signals. The transceiver112may include different types of transceivers configured to communicate with different networks and systems. The transceiver112is at least configured to exchange data between the proving device102and the verifying device104, but may also be configured to communicate with additional devices on the network106. In one embodiment, the transceiver112is configured to exchange data using a protocol such as Wi-Fi, Bluetooth, RFID, NFC, ZigBee, Z-Wave, or Ethernet.

The proving device102also has a physical unclonable function (PUF)118, which can be utilized by the processor108, configured to receive an input (e.g., a challenge bit string) and produce a unique output (e.g., a response bit string). The output response of the PUF118depends on the unique physical structure of at least one component of the proving device102and serves as a digital fingerprint for the proving device102. In at least one embodiment, a semiconductor device, such as the processor108, the memory110, the transceiver112, or a MEMS-sensor (not shown) of the proving device102provides the basis for the PUF118. In other embodiments, the proving device102may include a dedicated semiconductor device (not shown) configured only to provide the PUF118.

The microstructure of the semiconductor device, or other component, which provides the PUF118includes random physical variations that are naturally introduced by during manufacture and that are not feasibly controlled or replicated, even by the manufacturer. Additionally, in some types of PUF-enabled semiconductor devices, variations in environmental conditions, such as temperature, supply voltage, and electromagnetic interference also introduce randomness and unpredictability into the operation of the device. As a result, the PUF118has a unique and unpredictable way of generating a response to a particular input. Furthermore, for a given challenge input string, the PUF118does not necessarily reliably produce exactly the same response string each time. Instead, for a given challenge input string, the PUF118may generate reliably similar but not identical responses each time it is used. In this way, the PUF118can be considered to have a noisy response.

In contrast to the proving device102, in some embodiments, the verifying device104is a host system such as a remote server, a local control hub (e.g., as used in home automation systems), a payment kiosk, or any other device which must verify the identity and authenticity of connected devices. Additionally, the verifying device104generally has more processing capability and more memory than the proving device102and is better suited to bear any computationally or memory intensive aspects of the authentication process.

In the embodiment shown, the verifying device104comprises a processor120, memory122, and a transceiver124. The memory122is configured to store program instructions that, when executed by the processor120, enable the verifying device104to perform one or more services or functions. In addition to program instructions for implementing the primary services or functions of the verifying device104, the program instructions at least include an authentication program126for verifying the identity and authenticity of the proving device102. The memory122is also configured to store data128, which may include data utilized by the authentication program126, such as pairs of challenges and measured responses of the PUF118of the proving device102.

The memory122may be of any type of device capable of storing information accessible by the processor120, such as a memory card, ROM, RAM, write-capable memories, read-only memories, hard drives, discs, flash memory, or any of various other computer-readable medium serving as data storage devices as will be recognized by those of ordinary skill in the art. Additionally, although the memory122is shown monolithically in the figure, the memory122may comprise several discrete memories of different types which are used for different purposes.

The processor120may include a system with a central processor, multiple processors, dedicated circuitry for achieving functionality, or other systems. Furthermore, it will be recognized by those of ordinary skill in the art that a “processor” includes any hardware system, hardware mechanism or hardware component that processes data, signals or other information.

The transceiver124may be any of various devices configured for communication with other electronic devices, including the ability to send communication signals and receive communication signals. The transceiver124may include different types of transceivers configured to communicate with different networks and systems. The transceiver124is at least configured to exchange data between the verifying device104and the proving device102, but may also be configured to communicate with additional devices on the network106. In one embodiment, the transceiver124is configured to exchange data using a protocol such as Wi-Fi, Bluetooth, RFID, NFC, ZigBee, Z-Wave, or Ethernet.

FIG. 2shows a block diagram of a robust computational fuzzy extractor200. Unlike traditional fuzzy extractors, which are defined as information-theoretic objects, the robust computational fuzzy extractor200leverages computational security based on Learning with Errors (LWE), which is post-quantum secure, to preserve the full entropy of the PUF118and obtain longer cryptographic keys. Unlike many traditional fuzzy extractors, the cryptographic key is not extracted from the PUF response. Instead, a random linear code is used to derive a longer key using LWE assumptions and the PUF response is used to “encrypt” the key in a manner that is decryptable with knowledge of a sufficiently similar PUF response.

The robust computational fuzzy extractor200includes a generate function202. The generate function202receives as an input a previously measured response w of the PUF118. Additionally, the generate function202receives as inputs a uniformly distributed random matrix A and a uniformly distributed random vector x1, . . . , n. In at least one embodiment, the vector x1, . . . , nis a random linear code. In one exemplary embodiment, the matrix A and the vector x1, . . . , nare uniformly sampled over a finite fieldqaccording to A∈qm×nand x∈qn, where n is a security parameter, m≥n, and q is prime, as described inComputational Fuzzy Extractors(Benjamin Fuller, Xianrui Meng, and Leonid Reyzin. InAdvances in Cryptology—ASIACRYPT2013, pages 174-193. Springer, 2013), in which m, n, and q are selected so as to maintain the full entropy of the source which provides the input string w. The generate function202includes an encode function204that computes the vector Ax+w using matrix multiplication and addition, which can be considered an encryption of x1, . . . , nwhere decryption works from any close w. Furthermore, the generate function202derives a shared secret x1, . . . , n/2from the random vector x1, . . . , n. In one embodiment, the shared secret x1, . . . , n/2is a bit string comprising the first through

n2
elements of the random vector x1, . . . , n. In one embodiment, the shared secret x1, . . . , n/2is the same as the random vector x1, . . . , n. Finally, the generate function202includes a message authentication code (MAC) function212that computes a MAC tag σ, which can be considered a keyed cryptographic hash, based on the matrix A, the vector Ax+w, and the shared secret x1, . . . , n/2. The outputs of the generate function202are the shared secret x1, . . . , n/2and helper data P=(A, σ, Ax+w). The helper data P is considered public data and may be known to an adversary, whereas the shared secret x1, . . . , n/2may be used a cryptographic key or for authentication.

The robust computational fuzzy extractor200further includes a reproduce function206. The reproduce function206receives as an input a measured response w′ of the PUF118. Additionally, the reproduce function206receives as inputs helper data {tilde over (P)}=(Ã, {tilde over (σ)}, A), which may be the same as the helper data P, but may also include one or more elements that have been modified by an active attacker. The reproduce function206includes a subtract function208that computes {tilde over (b)}=A−w′=A, Additionally, the reproduce function206includes a decode function210that decodes the result of the subtraction Aand is able to output at the shared secret x1, . . . , n/2if the response w′ is sufficiently close and/or similar to the response w according to some predefined metric (e.g., Hamming distance between w′ and w is less than t). Otherwise, if the response w′ is not sufficiently close and/or similar to the response w (e.g., Hamming distance between w′ and w is greater than t), the decode function210fails to resolve and outputs an error value ⊥. One embodiment of such a decoding algorithm is known inComputational Fuzzy Extractors(Benjamin Fuller, Xianrui Meng, and Leonid Reyzin. InAdvances in Cryptology—ASIACRYPT2013, pages 174-193. Springer, 2013), in which the decoding algorithm (1) randomly selects rows without replacement i1, . . . , i2←[1,m]; (2) restricts A, b to rows i1, . . . , i2nand denotes these Ai1, . . . , i2n, bi1, . . . , i2n; (3) finds n rows of Ai1, . . . , i2nthat are linearly independent and, if no such rows exist, outputs ⊥ and stops; (4) denotes by A′, b′ the restriction of Ai1, . . . , i2n, bi1, . . . , i2n(respectively) to these rows and computes x′=(A′)−1b′; (5) returns to step (1) if b−Ax′ has more than t nonzero coordinates; and (6) outputs x′.

The reproduce function206further includes a verify function214that computes a MAC tag σ″ based on the possibly modified matrix A, the possibly modified vector A, and the shared secret x1, . . . , n/2that was decoded by the decode function210. The verify function214compares the computed MAC tag σ″ with the possibly modified MAC tag {tilde over (σ)}. The verify function214outputs an acceptance if the possibly modified MAC tag {tilde over (σ)} matches the computed MAC tag σ″. Otherwise, if the MAC tags do not match, then the verify function214outputs a rejection or the error value ⊥. If both the decode function210and the verify function212are successful, the output of the reproduce function206is the shared secret x1, . . . , n/2. If either the decode function210or the verify function212fails, the output of the reproduce function206is the error value ⊥.

In some embodiments, the generate function202and reproduce function206of the robust computational fuzzy extractor200are implemented in a silicon blocks in the processor108and/or the processor120and are accessible as functions in the processors. In other embodiments, the generate function202and reproduce function206of the fuzzy extractor200are implemented using a combination of hardware and software, or purely software (e.g., the authentication programs114and126), preferably using an area of the memory110and/or the memory122that stores software instructions but cannot be easily modified to ensure that the software instructions for the fuzzy extractor are not altered.

As discussed in greater detail below, during an authentication process, the generate function202generates the helper data P and the shared secret x1, . . . , n/2, based on the previously measured response w, the matrix A, and the vector x1, . . . , n. The proving device104receives a challenge c (e.g., a bit-string) and possibly modified helper data {tilde over (P)}. The challenge string c is provided to the PUF118, which outputs a noisy response w′. The reproduce function206outputs either the shared secret x1, . . . , n/2or the error value ⊥. If the proving device102is authentic (i.e. includes the unique PUF device118) and the helper data {tilde over (P)} has not been modified by an active attacker, then it will successfully reproduce the shared secret x1, . . . , n/2and provide a matching MAC σ″. However, if the proving device102is not authentic (i.e., does not include the unique PUF device118), then it cannot successfully reproduce the shared secret x1, . . . , n/2. Additionally, if the helper data {tilde over (P)} has been modified, the proving device102will not compute a matching MAC σ″ and will know that the source device is an active attacker, rather than the verifying device104.

FIG. 3shows a detailed method300for authenticating a device using the robust computational fuzzy extractor200. In the description of the method, statements that the method is performing some task or function refers to a controller or general purpose processor executing programmed instructions stored in non-transitory computer readable storage media operatively connected to the controller or processor to manipulate data or to operate one or more components in the system100to perform the task or function. The processor108of the proving device102or the processor120of the verifying device104above may be such a controller or processor and the executed program instructions (e.g., the authentication programs114and126) may be stored in the memories110and122. Additionally, the steps of the methods may be performed in any feasible chronological order, regardless of the order shown in the figures or the order in which the steps are described.

The method300begins with steps of exchanging authentication requests and authentication request acknowledgements between a verifying device and a proving device to prepare for authentication (blocks302and304). Particularly, with reference to the particular embodiments discussed in detail herein, as a preliminary step, the proving device102and the verifying device104are configured to exchange authentication request and authentication request acknowledgement messages to prepare for authentication of the proving device102. In one embodiment, the processor108of the proving device102is configured to operate the transceiver112to transmit an authentication request authReqto the verifying device104. In at least one embodiment, the authentication request authReqincludes an identifier ID that uniquely identifies the proving device102. The verifying device104receives the authentication request authReqwith the transceiver124. The processor120of the verifying device104is configured to compare the received identifier ID with a list of known identifiers stored in the database128. If the identifier ID is a known identifier, the processor120is configured to operate the transceiver124to transmit an authentication request acknowledgement authAckto the proving device102. It is noted that in some embodiments, the verifying device102is configured to transmit an authentication request authReqto the proving device102and the proving device102is configured to transmit an authentication request acknowledgement authAck, with the identifier ID, to the verifying device104.

The method300continues with a step of reading a previously measured response bit string of the physical unclonable function of the proving device to the challenge bit string from a memory of the verifying device (block306). Particularly, in some embodiments, for each known identifier ID, the database128of the verifying device104stores a plurality of challenge-response bit string pairs (ci, wi), where each response bit string wiis a measured response of the PUF118(which corresponds to a respective identifier ID) to a different challenge bit string ci. In at least one embodiment, the pairs generated at a time of manufacture of the proving device102, at a time of manufacture of the particular component which comprises the PUF118, or otherwise prior to the authentication process. After or in response to receiving the authentication request authReqfrom the proving device102, the processor120of the verifying device104is configured to read a previously measured response bit string w. In one embodiment, the processor120is configured to select the measured response bit string w from the plurality of measured response bit strings wiusing a time table or other rule set for deciding which measured response bit string w is to be utilized.

The method300continues with a step of generating a shared secret bit string, public helper data, and a MAC tag using the generate function of the robust computational fuzzy extractor (block308). Particularly, the processor120of the verifying device104is configured to derive a shared secret bit string x1, . . . , n/2from a uniformly distributed random vector x1, . . . , n, using the generate function202of the robust computation fuzzy extractor200as discussed above with respect toFIG. 2. Furthermore, the processor120is configured to encode a helper bit string Ax+w by multiplying a uniformly distributed random matrix A with the uniformly distributed random vector x1, . . . , nand adding the previously measured response bit string w to a result of the multiplication, using the encode function204of the generate function202of the robust computation fuzzy extractor200as discussed above with respect toFIG. 2. Finally, the processor120is configured to compute a MAC tag a based on the shared secret bit string x1, . . . , n/2, the uniformly distributed random matrix A, and the helper bit string Ax+w, using the MAC function212of the generate function202of the robust computation fuzzy extractor200as discussed above with respect toFIG. 2. In one embodiment, the processor120is configured to generate the uniformly distributed random vector x1, . . . , nat the time of authentication. In one embodiment, the processor120is configured to generate the uniformly distributed random matrix A, which is considered part of the public helper data P, at the time of manufacture of the proving device102or at some other prior time. However, in some alternative embodiments, the verifying device receives the uniformly distributed random matrix A from the proving device102at the time of authentication or at some other prior time.

The method300continues with steps of transmitting the helper bit string and the MAC tag from the verifying device (block310) and receiving the helper bit string and the MAC tag at the proving device (block312). Particularly, the processor120of the verifying device104operates the transceiver124to transmit at least the helper bit string Ax+w and the MAC tag σ to the proving device102. The proving device102is configured to receive the possibly modified helper bit string Aand the possibly modified MAC tag {tilde over (σ)} with the transceiver112. As noted above, the helper bit string Aand the MAC tag6may be the same as the helper bit string Ax+w and the MAC tag σ, but may also have been modified by an active attacker. In some embodiments, the verifying device104transmits all of the public helper data P, including the uniformly distributed random matrix A, to the proving device102.

The method300continues with steps of transmitting a challenge bit string from the verifying device (block314) and receiving the challenge bit string at the proving device (block316). Particularly, as discussed above, the database128of the verifying device104stores a plurality of challenge-response bit string pairs (ci, wi), where each response bit string wiis a measured response of the PUF118to a different challenge bit string ci. The processor120of the verifying device104is configured to operate the transceiver124to transmit, to the proving device102, the challenge bit string c which corresponds to the response bit string w that was used by the verifying device104to generate the helper bit string Ax+w. The proving device102is configured to receive the challenge bit string c with the transceiver112.

In some alternative embodiments, the challenge bit string c may be installed on onto the memory110of the proving device102at a time of manufacture. In such embodiments, the step of transmitting the challenge bit string c from the verifying devices104(block314) may be omitted. Instead, the processor108of the proving device102is configured to read the challenge bit string c from the memory110. In one embodiment, the processor108reads the challenge bit string c in response to receiving the helper bit string Aand the MAC tag {tilde over (σ)}. In some embodiments a plurality of challenge bit strings ciare stored in the memory110. In one embodiment, the processor108is configured to select a challenge bit string c from the plurality of challenge bit strings ciusing a time table or other rule set for deciding which challenge bit string c is to be utilized.

The method300continues with a step of measuring a response bit string of a physical unclonable function of the proving device to the challenge bit string (block318). Particularly, the processor108of the proving device102is configured to provide the challenge bit string c as an input to the PUF118. The processor108measures, receives, or otherwise determines a noisy response w′ of the PUF118to the challenge bit string c.

The method300continues with a step of reproducing the shared secret bit string using the reproduce function of the robust computational fuzzy extractor (block320). Particularly, the processor108of the proving device102is configured to subtract the noisy response w′ from the possibly modified helper bit string A, using the subtract function208of the reproduce function206of the robust computation fuzzy extractor200as discussed above with respect toFIG. 2. Furthermore, the processor108is configured to attempt to derive the shared secret x1, . . . , n/2by decoding the result of the subtraction Ausing the decode function210of the reproduce function206of the robust computation fuzzy extractor200as discussed above with respect toFIG. 2. As discussed above, the decode function210is able to output the shared secret x1, . . . , n/2if the response w′ is sufficiently close and/or similar to the response w according to some predefined metric (e.g., Hamming distance between w′ and w is less than t). Otherwise, if the response w′ is not sufficiently close and/or similar to the response w (e.g., Hamming distance between w′ and w is greater than t), the decode function210fails to resolve and outputs an error value ⊥. In one embodiment, the processor108is configured to receive a possibly modified uniformly distributed random matrix Ã, which is considered part of the public helper data {tilde over (P)}, from the verifying device104at the time of authentication, alongside the helper bit string Aand the MAC tag {tilde over (σ)}, or at some other prior time. However, in many embodiments, the uniformly distributed random matrix A is installed on the memory110at a time of manufacture and is reused during different authentications. After the initial deployment of the proving device102, the verifying device104is configured to only transmit a new uniformly distributed random matrix A if necessary for security-related reasons. In alternative embodiments, the processor108of the proving device102may generate the uniformly distributed random matrix A and provide it to the verifying device104at some prior time.

Finally, the processor108is configured to compute a MAC tag σ″ based on the possibly modified matrix A (or the matrix A is installed on the memory110at a time of manufacture), the possibly modified vector Aand the shared secret x1, . . . , n/2that was decoded by the decode function210and compare the computed MAC tag σ″ with the possibly modified MAC tag {tilde over (σ)}, using the verify function214of the reproduce function206of the robust computation fuzzy extractor200as discussed above with respect toFIG. 2. As discussed above, the verify function214outputs an acceptance if the possibly modified MAC tag {tilde over (σ)} matches the computed MAC tag σ″. Otherwise, if the MAC tags do not match, then the verify function214outputs a rejection or the error value ⊥.

The method300continues with steps of transmitting, from the proving device, one of (i) a confirmation message indicating that authentication was successful and (ii) a rejection message indicating that authentication was unsuccessful (block322) and receiving the one of (i) the confirmation message and (ii) the rejection message at the verifying device (block324). Particularly, in response to the shared secret x1, . . . , n/2being successfully derived from the decoding process and MAC tags matching in the verifying process, the processor108of the proving device102is configured to operate the transceiver112to transmit an authentication confirmation message authconfto the verifying device104, which indicates that the proving device102and/or the verifying device104was successfully authenticated. In response to the decoding process failing to resolve and outputting the error value ⊥ and/or the MAC tags not matching in the verifying process and outputting the error value ⊥, the processor108is configured to operate the transceiver112to transmit an authentication rejection message authrejto the verifying device104, which indicates that the proving device102and/or the verifying device104was not successfully authenticated.

FIG. 4shows a block diagram of a reverse robust computational fuzzy extractor400. The reverse robust computational fuzzy extractor400is similar to the robust computational fuzzy extractor200, except that the functions performed on the proving device102and the verifying device104are reversed. Particularly, as discussed in greater detail below, during an authentication process, the proving device102receives a challenge c (e.g., a bit-string) from the verifying device104. The challenge string c is provided to the PUF118, which outputs a noisy response w′. The generate function202outputs the helper data P and the shared secret x1, . . . , n/2, based on the noisy response w′, the matrix A, and the vector x1, . . . , n. Possibly modified helper data {tilde over (P)} is provided to the verifying device104and the reproduce function206outputs either the shared secret x1, . . . , n/2or the error value ⊥, based a previously measured response w and the possibly modified helper data {tilde over (P)}. If the proving device102is authentic (i.e. includes the unique PUF device118) and the helper data {tilde over (P)} has not been modified by an active attacker, then verifying device104will successfully reproduce the shared secret x1, . . . , n/2and provide a matching MAC σ″. However, if the proving device102is not authentic (i.e., does not include the unique PUF device118), then verifying device104cannot successfully reproduce the shared secret x1, . . . , n/2. Additionally, if the helper data {tilde over (P)} has been modified, the verifying device104will not compute a matching MAC σ″ and will know that the source device is an active attacker, rather than the proving device102.

FIG. 5shows a detailed method500for authenticating a device using the reverse robust computational fuzzy extractor400. In the description of the method, statements that the method is performing some task or function refers to a controller or general purpose processor executing programmed instructions stored in non-transitory computer readable storage media operatively connected to the controller or processor to manipulate data or to operate one or more components in the system100to perform the task or function. The processor108of the proving device102or the processor120of the verifying device104above may be such a controller or processor and the executed program instructions (e.g., the authentication programs114and126) may be stored in the memories110and122. Additionally, the steps of the methods may be performed in any feasible chronological order, regardless of the order shown in the figures or the order in which the steps are described.

The method500begins with steps of exchanging authentication requests and authentication request acknowledgements between a verifying device and a proving device to prepare for authentication (blocks502and504), which are essentially similar to the steps302and304of the method300and are not described again in detail.

The method500continues with steps of transmitting a challenge bit string from the verifying device (block506) and receiving the challenge bit string at the proving device (block508). Particularly, in some embodiments, the processor120of the verifying device104operates the transceiver124to transmit a challenge bit string c to the proving device102. In some embodiments, for each known identifier ID, the database128of the verifying device104stores a plurality of challenge-response bit string pairs (ci, wi), where each response bit string wiis a measured response of the PUF118(which corresponds to a respective identifier ID) to a different challenge bit string ci. In at least one embodiment, the pairs are generated at a time of manufacture of the proving device102, at a time of manufacture of the particular component which comprises the PUF118, or otherwise prior to the authentication process. After or in response to receiving the authentication request authReqfrom the proving device102, the processor120of the verifying device104is configured to select a challenge bit string c from the database128and operate the transceiver124to transmit the challenge bit string c to the proving device102. In one embodiment, the processor120is configured to select the challenge bit string c from the plurality of challenge bit strings ciusing a time table or other rule set for deciding which challenge bit string c is to be utilized. The proving device102is configured to receive the challenge bit string c with the transceiver112.

In some alternative embodiments, the challenge bit string c may be installed on onto the memory110of the proving device102at a time of manufacture. In such embodiments, the step of transmitting the challenge bit string c from the verifying devices104(block506) may be omitted. Instead, the processor108of the proving device102is configured to read the challenge bit string c from the memory110. In one embodiment, the processor108reads the challenge bit string c in response to receiving the authentication request acknowledgement authAck. In some embodiments a plurality of challenge bit strings ciare stored in the memory110. In one embodiment, the processor108is configured to select a challenge bit string c from the plurality of challenge bit strings ciusing a time table or other rule set for deciding which challenge bit string c is to be utilized.

The method500continues with a step of measuring a response bit string of a physical unclonable function of the proving device to the challenge bit string (block510). Particularly, the processor108of the proving device102is configured to provide the challenge bit string c as an input to the PUF118. The processor108measures, receives, or otherwise determines a noisy response w′ of the PUF118to the challenge bit string c.

The method500continues with a step of generating a shared secret bit string, public helper data, and a MAC tag using the generate function of the reverse computational fuzzy extractor (block512). Particularly, the processor108of the proving device102is configured to derive a shared secret bit string x1, . . . , n/2from a uniformly distributed random vector x1, . . . , n, using the generate function202of the reverse robust computation fuzzy extractor400as discussed above with respect toFIG. 4. Furthermore, the processor108is configured to encode a helper bit string Ax+w′ by multiplying a uniformly distributed random matrix A with the uniformly distributed random vector x1, . . . , nand adding the noisy response bit string w′ to a result of the multiplication, using the encode function204of the generate function202of the reverse robust computation fuzzy extractor400as discussed above with respect toFIG. 4. Finally, the processor108is configured to compute a MAC tag σ based on the shared secret bit string x1, . . . , n/2, the uniformly distributed random matrix A, and the helper bit string Ax+w′, using the MAC function212of the generate function202of the reverse robust computation fuzzy extractor400as discussed above with respect toFIG. 4. In one embodiment, the processor108is configured to generate the uniformly distributed random vector x1, . . . , nat the time of authentication. In one embodiment, the processor108is configured to receive the uniformly distributed random matrix A, which is considered part of the public helper data p, from the verifying device104at the time of authentication, alongside the challenge bit string c or at some other prior time. However, in many embodiments, the uniformly distributed random matrix A is installed on the memory110at a time of manufacture and is reused during different authentications. After the initial deployment of the proving device102, the verifying device104is configured to only transmit a new uniformly distributed random matrix A if necessary for security-related reasons. In alternative embodiments, the processor108of the proving device102may generate the uniformly distributed random matrix A and provide it to the verifying device104.

The method500continues with steps of transmitting the helper bit string and the MAC tag from the proving device (block514) and receiving the helper bit string and the MAC tag at the verifying device (block516). Particularly, the processor108of the proving device102operates the transceiver112to transmit at least the helper bit string Ax+w′ and the MAC tag σ to the verifying device104. The verifying device104is configured to receive a possibly modified helper bit string Aand a possibly modified MAC tag {tilde over (σ)} with the transceiver124. As noted above, the helper bit string Aand the MAC tag {tilde over (σ)} may be the same as the helper bit string Ax+w and the MAC tag σ, but may also have been modified by an active attacker. In some embodiments, the proving device102transmits all of the public helper data P, including the uniformly distributed random matrix A, to the verifying device104.

The method500continues with a step of reading a previously measured response bit string of the physical unclonable function of the proving device to the challenge bit string from a memory of the verifying device (block518). Particularly, as discussed above, the database128of the verifying device104stores a plurality of challenge-response bit string pairs (ci, wi), where each response bit string wiis a measured response of the PUF118to a different challenge bit string ci. After receiving the helper bit string A, the processor120of the verifying device104is configured to read the previously measured response bit string w which corresponds to the challenge bit string c that was used by the proving device102to generate the helper bit string A.

The method500continues with a step of reproducing the shared secret bit string using the reproduce function of the reverse computational fuzzy extractor (block520). Particularly, the processor120of the verifying device104is configured to subtract the previously measured response bit string w from the possibly modified helper bit string A, using the subtract function208of the reproduce function206of the reverse robust computation fuzzy extractor400as discussed above with respect toFIG. 4. Furthermore, the processor120is configured to attempt to derive the shared secret x1, . . . , n/2by decoding the result of the subtraction Ausing the decode function210of the reproduce function206of the reverse robust computation fuzzy extractor400as discussed above with respect toFIG. 4. As discussed above, the decode function210is able to output the shared secret x1, . . . , n/2if the response w′ is sufficiently close and/or similar to the response w according to some predefined metric (e.g., Hamming distance between w′ and w is less than t). Otherwise, if the response w′ is not sufficiently close and/or similar to the response w (e.g., Hamming distance between w′ and w is greater than t), the decode function210fails to resolve and outputs an error value ⊥.

Finally, the processor120is configured to compute a MAC tag σ″ based on the possibly modified matrix Ã (or the matrix A is installed on the memory122), the possibly modified vector A, and the shared secret x1, . . . , n/2that was decoded by the decode function210and compare the computed MAC tag σ″ with the possibly modified MAC tag {tilde over (σ)}, using the verify function214of the reproduce function206of the reverse robust computation fuzzy extractor400as discussed above with respect toFIG. 4. As discussed above, the verify function214outputs an acceptance if the possibly modified MAC tag {tilde over (σ)} matches the computed MAC tag σ″. Otherwise, if the MAC tags do not match, then the verify function214outputs a rejection or the error value ⊥.

The method500continues with steps of transmitting, from the verifying device, one of (i) a confirmation message indicating that authentication was successful and (ii) a rejection message indicating that authentication was unsuccessful (block522) and receiving the one of (i) the confirmation message and (ii) the rejection message at the proving device (block524). Particularly, in response to the shared secret x1, . . . , n/2being successfully derived from the decoding process and MAC tags matching in the verifying process, the processor120of the verifying device104is configured to operate the transceiver124to transmit an authentication confirmation message authconfto the proving device102, which indicates that the proving device102and/or the verifying device104was successfully authenticated. In response to the decoding process failing to resolve and outputting the error value ⊥ and/or the MAC tags not matching in the verifying process and outputting the error value ⊥, the processor120is configured to operate the transceiver124to transmit an authentication rejection message authrejto proving device102, which indicates that the proving device102and/or the verifying device104was not successfully authenticated.

The herein described methods (e.g., the methods300,500and/or the robust computational fuzzy extractors200,400) improve the functioning of the proving device102, and the verifying device104, respectively or in combination by enabling it/them to operate more securely to authenticate the proving device102. Particularly, by including the processes of generating a MAC tag on the verifying device104and using the MAC tag to verify the authenticity and integrity of transmitted helper data on the proving device, the system is more secure against active attackers that may modify the helper data. Additionally, the MAC tag is efficiently generated and verified because the uniformly distributed random matrix A is reused for hashing and signing. In this way, the method can advantageously be implemented with minimal or no increase in memory or processing capability. Furthermore, in the case of the reverse robust fuzzy extractor400, the devices operate more efficiently to authenticate the proving device102. Particularly, in one embodiment, the generate function202runs in O(n2) and the reproduce function206runs in O(n4). In the reverse robust fuzzy extractor400, the computationally expensive reproduce function206is implemented on the verifying device104, and the less computationally expensive generate function202is implemented on the proving device102. In this way, the method can advantageously be implemented on light-weight proving devices102. Additionally, due the uniform random distribution of the matrix A and the vector x1, . . . , n, any statistical bias in the response of the PUF118is masked, without any additional steps required, thereby minimizing information leakage and improving the security of the system100. Finally, the full entropy of the PUF118is retained and longer cryptographic keys can be obtained.