Associative PUF arrays to generate session keys with pseudo-homomorphic methods

Patent metadata

Field	Value
Publication number	US-12184797-B2
Application number	US-202217954222-A
Country	US
Kind code	B2
Filing date	Sep 27, 2022
Priority date	Sep 27, 2021
Publication date	Dec 31, 2024
Grant date	Dec 31, 2024

Abstract

Systems and methods for the generation and use of session keys supporting secure communications between a client and server device are disclosed. The client hashes each of a series of passwords a first number of times. The hashed passwords are sent to a server. The server applies the hashed password to an array of PUF devices, and receives an initial response bitstream which is stored. The client later hashes each of the series of passwords a second number of times, which is less than the first number, and these are sent to the server. The server continues to hash the second message digest, generate PUF responses, and compare the result to the initially stored responses. For each password, the number of hashes necessary to achieve a match is a partial session key. Latency is improved by an array of separately addressable PUFs, each producing a partial session key.

First claim

The invention claimed is:

1. A method of generating a session key at a server device having a first physical-unclonable-function (“PUF”) array of addressable PUF devices, comprising:
receiving an initial response bitstream, the initial response bitstream having been generated by a series of steps comprising:
for each of a plurality of client passwords:
selecting a password-specific first number
sequentially hashing a password the first number of times using a hashing method;
generating a first PUF challenge from the hashed password, and applying the first PUF challenge to the PUF array;
measuring a first PUF response to the first PUF challenge; and
adding the first PUF response into the initial response bitstream;

receiving a message digest generated by a series of steps comprising:
for each of the plurality of client passwords
selecting a password-specific second number, less than the password-specific first number of the corresponding password,
sequentially hashing a password the second number of times using the hashing method, and
adding the hashed password into the message digest;

iteratively performing the following steps, for each hashed password in the message digest, until a stop condition is reached:
hashing the hashed password using the hashing method;
generating from the hashed password a second PUF challenge, and

applying the second PUF challenge to the PUF array;
measuring a second PUF response to the second PUF challenge;
comparing the second PUF response to the first PUF response,
wherein the stop condition is reached when the second PUF response matches the first PUF response, and
when the second PUF response matches the first PUF response generating a partial session key equal to the number of times the password was hashed.

2. The method of claim 1 , further comprising generating a session key on the basis of partial session keys corresponding to all of the plurality of hashed passwords in the message digest.

3. The method of claim 2 , wherein the session key is generated by taking the product of all partial session keys corresponding all of the plurality of hashed passwords in the message digest.

4. The method of claim 1 , wherein first and second PUF challenges specify addresses of PUF devices within the server's PUF array.

5. The method of claim 2 , wherein measuring a first or second PUF response comprises measuring a physical characteristic of PUF devices.

6. The method of claim 4 , further comprising receiving masking data specifying the addresses of erratic devices within the server's PUF array and wherein the server does not include responses from erratic devices when computing a partial session key.

7. The method of claim 6 , wherein the server receives masking data from a certificate authority.

8. The method of claim 1 , wherein receiving an initial response bitstream comprises receiving the initial response bitstream from a certificate authority.

9. The method of claim 1 , wherein receiving an initial response bitstream comprises receiving an initial message digest of hashed passwords from the client, and measuring the PUF array on the basis of the received initial message digest.

10. The method of claim 1 , comprising deleting the message digest.

11. The method of claim 1 , wherein the hashing method comprises one of SHA-1, SHA-2, SHA-3, SHA-256, SHA-512, SHAKE, or MDA.

12. A method of recovering a session key by a server having an addressable array of PUF computational units, each PUF computational unit having an addressable array of PUF devices, the method comprising:
receiving an initial response bitstream, the initial response bitstream having been generated by a series of steps comprising:
for each of a plurality of client passwords:
selecting a password-specific first number
sequentially hashing a password the first number of times using a hashing method;
generating a first PUF challenge from the hashed password, and applying the first PUF challenge to a PUF computational unit's PUF array;
measuring a first PUF response to the first PUF challenge; and
adding the first PUF response into the initial response bitstream;

receiving a message digest generated by a series of steps comprising:
for each of the plurality of client passwords
selecting a password-specific second number, less than the password-specific first number of the corresponding password,
sequentially hashing a password the second number of times using the hashing method, and
adding the hashed password into the message digest;

dividing the message digest into fragments corresponding to each hashed password;
assigning each fragment to a PUF computational unit;
receiving from each PUF computational unit to which a fragment is assigned a partial session key;
generating a session key on the basis of the partial session keys.

13. The method of claim 12 , further comprising, at each PUF computational unit to which a fragment is assigned:
iteratively executing the following steps until a stop condition is reached:
hashing the fragment using the hashing method;
generating from the hashed password a second PUF challenge, and applying the second PUF challenge to the PUF array of the computational unit;
measuring a second PUF response to the second PUF challenge;
comparing the second PUF response to a first PUF response generated a first PUF challenge generated from the same password used to generate the fragment, wherein the stop condition is reached when the second PUF response matches the first PUF response, and
when the second PUF response matches the first PUF response generating a partial session key equal to the number of times the password was hashed.

14. The method of claim 13 , wherein the server has excess PUF computational units not required to recover partial session keys from all message digest fragments in parallel, and wherein an excess PUF computational unit iteratively performs the following computational cycle a third number of times:
receive an initial number, apply the hashing method to the number, generate PUF challenges from the hashed number, measure responses of the excess PUF computational unit's PUF array in the response to the PUF challenges; and compare the responses to the number.

15. The method of claim 14 wherein the third predetermined number of times is selected randomly.

16. The method of claim 14 , wherein, after computational cycle has been performed the third number of times, the excess PUF computational unit generates a spoof partial session key, which is received by the server, and not used to generate the session key.

17. The method of claim 12 , wherein assigning each fragment to a PUF computational unit includes assigning multiple fragments to the same computational unit.

18. The method of claim 12 , wherein assigning each fragment to a PUF computational unit is done on the basis of a random number, and wherein each hashed password in the message digest is identifiable by a first index, and each PUF computational unit making up the array of PUF computational unit is identifiable by a second index, and wherein fragments corresponding to hashed passwords are assigned to PUF computational units having a non-matching index.

19. The method of claim 12 , generating a session key on the basis of the partial session keys comprises computing a product of the received partial session keys.

20. The method of claim 19 , further comprising deleting the message digest.

Assignees

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

Inventors

• Cambou Bertrand F
• Heynssens Julie
• Burke Ian
• Riggs Brit
• Garrard Jack
• Aguilar Rios Manuel
• Telesca Donald
• Jacinto H Shelton

Classifications

• H04L9/0863

  involving passwords or one-time passwords (network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067) · CPC title

• H04L9/3268

  using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL] · CPC title

• H04L9/3239

  involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD · CPC title

• H04L9/0891

  Revocation or update of secret information, e.g. encryption key update or rekeying · CPC title

• H04L9/14

  using a plurality of keys or algorithms · CPC title