Systems and methods using search engines to generate cryptographic keys from erratic physical unclonable functions

Patent metadata

Field	Value
Publication number	US-12126740-B2
Application number	US-202217849623-A
Country	US
Kind code	B2
Filing date	Jun 25, 2022
Priority date	Jun 25, 2021
Publication date	Oct 22, 2024
Grant date	Oct 22, 2024

Abstract

Systems and methods for providing authentication and secure cryptographic communication between a client and server are described. The client includes an addressable array of PUF devices. The client receives or generates a set of instructions usable to determine a range of PUF addresses. The client measures the PUF addresses and generates a first set of responses. The responses are used to encrypt a session key, which is stored, along with the instructions and a hash of the responses, at the client. Later, the client may recover the session key by using the instructions to measure the PUF again, resulting in a second set of responses. Using a response-based cryptography search engine, the client may then iteratively modify and hash the second set of responses until a response set is uncovered that matches the first response set. This modified response set may then be used to uncover the session key.

First claim

The invention claimed is:

1. A method of authenticating a client device possessing a physical-unclonable-function (“PUF”) array having a plurality of PUF devices, comprising:
providing a challenge to the client device, the challenge identifying a range of devices in the PUF array;
determining an expected PUF response to the challenge by retrieving from a database previously measured physical characteristics of devices of the PUF array identified by the challenge;
dividing the expected PUF response into a plurality of expected response fragments;
generating a set of expected ciphertext fragments from the plurality of expected response fragments;
receiving a series of received ciphertext fragments from the client device; each received ciphertext fragment generated from a portion of a bitstream reflecting measured PUF responses generated by measuring physical characteristics of devices of the PUF array identified by the challenge;
comparing corresponding fragment pairs, each fragment pair comprising an expected response fragment and a corresponding received ciphertext fragment, to determine a degree of match between the expected response fragment and the ciphertext fragment in each fragment pair.

2. The method of claim 1 , wherein comparing corresponding fragment pairs comprises determining a Hamming distance between corresponding fragment pairs.

3. The method of claim 1 , further comprising determining that the client is authentic when each of the expected response fragments matches each of the corresponding ciphertext fragments.

4. The method of claim 1 , wherein generating a set of expected ciphertext fragments from the plurality of expected response fragments comprising hashing each of the plurality of expected response fragments.

5. The method of claim 4 , further comprising expanding a number of bits in each of the expected response fragment using random bits or nonce values prior to hashing the expected response fragment.

6. The method of claim 1 , wherein, when a comparison of a corresponding fragment pair indicates a degree of match below a predetermined threshold, changing one or more bits in the expected response fragment of the pair, generating a new expected ciphertext fragment, and comparing the new expected ciphertext fragment to the corresponding received ciphertext fragment.

7. The method of claim 6 , wherein changing one or more bits in the expected response fragment of the pair comprises generating a new expected response fragment that is a predetermined Hamming distance from an original expected response fragment.

Assignees

• Univ Northern Arizona
• Government Of The Us Secretary Of The Air Force

Inventors

• Cambou Bertrand F
• Assiri Sareh
• Philabaum Christopher Robert
• Jacinto H Shelton

Classifications

• H04L9/14

  using a plurality of keys or algorithms · CPC title

• H04L9/0822

  using key encryption key · CPC title

• H04L9/0894

  Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage · CPC title

• H04L9/3236

  using cryptographic hash functions · CPC title

• H04L9/0866

  involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics · CPC title