Incremental authentication for memory constrained systems

Patent metadata

Field	Value
Publication number	US-11216591-B1
Application number	US-201916439350-A
Country	US
Kind code	B1
Filing date	Jun 12, 2019
Priority date	Jun 12, 2019
Publication date	Jan 4, 2022
Grant date	Jan 4, 2022

Abstract

Apparatus and associated methods relate to authenticating a back-to-front-built configuration image. In an illustrative example, a circuit may include memory configured to store a signature S, a second hash H2, and a first data chunk C1. Signature S may be signed on a first hash H1. H1 may be the hash for H2 and C1. If signature S passes verification, a hash engine may perform hash functions on C1 and H2 to generate a hash H1′. H1′ may be compared with H1 to indicate whether C1 has been tampered with or not. By using the incremental authentication, a signature that appears at the beginning of the image may be extended to the entire image while only using a small internal buffer. Advantageously, internal buffer may only need to store two hashes Hi, Hi+1, and a data chunk Ci, or, a signature S, a hash Hi, and a data chunk Ci.

First claim

What is claimed is:

1. A method comprising:
receiving a signature from a data stream for a target device, wherein the data stream comprises the signature, a plurality of pre-calculated hashes, and a plurality of data chunks,
verifying the signature, and
if the signature passes verification, then:
extracting a first hash from the signature, wherein the first hash is a hash for a first data chunk of the plurality of data chunks and a second hash, wherein the second hash is one of the plurality of pre-calculated hashes;
storing the first hash, the first data chunk of the plurality of data chucks, and the second hash;
calculating, by using a hash function, a third hash based on the first data chunk of the plurality of data chunks and the second hash;
comparing the third hash with the first hash for a match between the first hash and the third hash; and,
if the third hash does not match the first hash, then, generating an invalid signal to indicate that the first data chunk has been tampered with;
retrieving a fourth hash, a second data chunk of the plurality of data chunks, and a fifth hash from the data stream, wherein the fourth hash is one of the pre-calculated hashes and is a corresponding hash for the second data chunk of the plurality of data chunks and the fifth hash, and wherein the fifth hash is one of the plurality of pre-calculated hashes;
storing the fourth hash, the second data chunk of the plurality of data chunks, and the fifth hash;
calculating, by using the hash function, a sixth hash based on the second data chunk of the plurality of data chunks and the fifth hash;
comparing the sixth hash with the fourth hash for a match between the fourth hash and the sixth hash; and,
if the sixth hash does not match the fourth hash, then, generating an invalid signal to indicate that the second data chunk has been tampered with.

2. The method of claim 1 , further comprising:
retrieving and storing a seventh hash, and a second data chunk of the plurality of data chunks, wherein the seventh hash is one of the plurality of pre-calculated hashes and is a corresponding hash for the second data chunk;
calculating, by using the hash function, a eighth hash the second data chunk;
comparing the eighth hash with the seventh hash for a match between the seventh hash and the eighth hash; and,
if the eighth hash does not match the seventh hash, then, generating an invalid signal to indicate the second data chunk has been tampered with.

3. The method of claim 1 , wherein, the signature is generated by a Rivest-Shamir-Adleman Algorithm (RSA).

4. The method of claim 1 , further comprising: if the signature does not pass the verification, then, generating an invalid signal to indicate that the data stream is not from a valid source.

5. A method comprising:
receiving a first hash from a data stream for a target device, wherein the data stream comprises a plurality of pre-calculated hashes and a plurality of data chunks, wherein the first hash is one of the plurality of pre-calculated hashes and is a hash for a first data chunk of the plurality of data chunks and a second hash, wherein the second hash is one of the plurality of pre-calculated hashes;
storing the first hash, the first data chunk of the plurality of data chunks, and the second hash;
calculating, by using a hash function, a third hash based on the first data chunk of the plurality of data chunks and the second hash;
comparing the third hash with the first hash for a match between the first hash and the third hash;
if the third hash does not match the first hash, then, generating an invalid signal to indicate that the first data chunk of the plurality of data chunks has been tampered with;
retrieving and storing a fourth hash, and a second data chunk, wherein the fourth hash is one of the plurality of pre-calculated hashes and is a corresponding hash for the second data chunk;
calculating, by using the hash function, a fifth hash based on the second data chunk;
comparing the fifth hash with the fourth hash for a match between the fourth hash and the fifth hash, and
if the fifth hash does not match the fourth hash, then, generating an invalid signal to indicate the second data chunk has been tampered with.

6. The method of claim 5 , further comprising:
retrieving a seventh hash, a second data chunk of the plurality of data chunks, and a eighth hash from the data stream, wherein the seventh hash is one of the pre-calculated hashes and is a corresponding hash for the second data chunk of the plurality of data chunks and the eighth hash, wherein the eighth hash is one of the plurality of pre-calculated hashes;
storing the seventh hash, the second data chunk of the plurality of data chunks, and the eighth hash;
calculating, by using the hash function, a ninth hash based on the second data chunk of the plurality of data chunks and the eighth hash;
comparing the ninth hash with the fourth hash for a match between the fourth hash and the ninth hash; and,
if the ninth hash does not match the seventh hash, then, generating an invalid signal to indicate that the second data chunk of the plurality of data chunks has been tampered with.

7. The method of claim 5 , wherein, the hash function comprises a secure hash algorithm 3 (SHA-3).

8. The method of claim 5 , wherein, the target device comprises a system-on-chip (SOC).

9. A circuit comprising:
a memory configured to store at least a portion of a data stream for a target device, the data stream comprises a signature, a plurality of hashes, and a plurality of data chunks, wherein the signature is a signature for a first hash, wherein the first hash is a hash for a first data chunk of the plurality of data chunks and a second hash, wherein the second hash is one of the plurality of hashes;
a sub-processor configured to retrieve the signature and, when the signature passes verification, extract the first hash, the first data chunk, and the second hash from the memory;
a hash engine configured to perform a hash function on the first data chunk and the second hash to generate a third hash; and,
a validation engine configured to compare the retrieved first hash with the third hash,
wherein the validation engine is further configured to generate an invalid signal to indicate that the first data chunk has been tampered with if the third hash does not match the retrieved first hash;
wherein the memory is further configured to store a fourth hash, a second data chunk of the plurality of data chunks, and a fifth hash, wherein the fourth hash is one of the plurality of hashes and is a hash for a second data chunk and the fifth hash, and wherein the fifth hash is one of the plurality of hashes;
wherein the hash engine is further configured to perform the hash function on the second data chunk and the fifth hash to generate a sixth hash;
wherein the validation engine is further configured to compare the fourth hash with the sixth hash; and,
wherein if the sixth hash does not match the fourth hash, the validation engine is further configured to generate an invalid signal to indicate that the second data chunk has been tampered with.

10. The circuit of claim 9 , wherein the memory is configured to store a seventh hash and a second data chunk, wherein the seventh hash is one of the plurality of hashes and is a hash for the second data chunk.

11. The circuit of claim 9 , wherein, when the signature does not pass the verification, the sub-processor is further configured to generate an invalid signal to indicate that the data stream is not from a valid source.

12. The circuit of claim 9 , wherein, the hash function comprises a secure hash algorithm 3 (SHA-3).

Assignees

• Xilinx Inc

Inventors

• Burton Felix
• Patakamuri Krishna C
• Wesselkamper James D

Classifications

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title

• H04L9/3247

  involving digital signatures · CPC title

• G06F21/64 Primary

  Protecting data integrity, e.g. using checksums, certificates or signatures · CPC title

• H04L9/3239

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

• H04L9/3249

  using RSA or related signature schemes, e.g. Rabin scheme · CPC title