Systems and methods using search engines to generate cryptographic keys from erratic physical unclonable functions
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.
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.