PARALLEL PROCESSING TECHNIQUES FOR HASH-BASED SIGNATURE ALGORITHMS

• US 20190319802A1
• Filed: 06/28/2019
• Published: 10/17/2019
• Est. Priority Date: 06/28/2019
• Status: Active Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: MISOCZKI, RAFAEL, Ghosh, Santosh, Sastry, Manoj, Wheeler, David
• Application Number:
  US16/456,004
• Publication Number:
  US 20190319802A1
• Time in Patent Office: Days
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 9/006 involving public key infrastructure [PKI] trust models network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

In one example an apparatus comprises a computer readable memory to store a public key associated with a signing device, communication logic to receive, from the signing device, a signature chunk which is a component of a signature generated by a hash-based signature algorithm, and at least a first intermediate node value associated with the signature chunk, verification logic to execute a first hash chain beginning with the signature chunk to produce at least a first computed intermediate node value, execute a second hash chain beginning with the at least one intermediate node value associated with the signature chunk to produce a first computed final node value, and use the first computed intermediate node value and the first computed final computed node value to validate the signature generated by the hash-based signature algorithm. Other examples may be described.

Claims

1. An apparatus, comprising:

a computer readable memory to store a public key associated with a signing device;

communication logic to receive, from the signing device, a signature chunk which is a component of a signature generated by a hash-based signature algorithm, and at least a first intermediate node value associated with the signature chunk;

verification logic to;

execute a first hash chain beginning with the signature chunk to produce at least a first computed intermediate node value;

execute a second hash chain beginning with the at least one intermediate node value associated with the signature chunk to produce a first computed final node value; and

use the first computed intermediate node value and the first computed final computed node value to validate the signature generated by the hash-based signature algorithm.

2. The apparatus of claim 1, wherein the hash-based signature algorithm comprises at least one of a Winterniz One Time Signature (WOTS) algorithm or a WOTS+ algorithm that invokes a secure hash algorithm (SHA) hash function.

3. The apparatus of claim 2, wherein the secure hash algorithm (SHA) has function comprises at least one of a SHA2-256, a SHA2-512, a SHA3-128, or a SHA3-256 hash function.

4. The apparatus of claim 1, wherein the signature comprises a total of 67 signature components, each of which is 32 bytes in length.

5. The apparatus of claim 1, the verifier logic to:

compare the first computed intermediate node value with the first intermediate node value received from the signing device; and

compare the first computed final node value with a portion of the public key for the signing device.

6. A computer-implemented method, comprising:

storing a public key associated with a signing device in a computer-readable medium;

receiving, from the signing device, a signature chunk which is a component of a signature generated by a hash-based signature algorithm, and at least a first intermediate node value associated with the signature chunk;

executing a first hash chain beginning with the signature chunk to produce at least a first computed intermediate node value;

executing a second hash chain beginning with the at least one intermediate node value associated with the signature chunk to produce a first computed final node value; and

using the first computed intermediate node value and the first computed final computed node value to validate the signature generated by the hash-based signature algorithm.

7. The method of claim 6, wherein the hash-based signature algorithm comprises at least one of a Winterniz One Time Signature (WOTS) algorithm or a WOTS+ algorithm that invokes a secure hash algorithm (SHA) hash function.

8. The method of claim 6, wherein the secure hash algorithm (SHA) has function comprises at least one of a SHA2-256, a SHA2-512, a SHA3-128, or a SHA3-256 hash function.

9. The method of claim 6, wherein the signature comprises a total of 67 signature components, each of which is 32 bytes in length.

10. The method of claim 6, further comprising:

comparing the first computed intermediate node value with the first intermediate node value received from the signing device; and

comparing the first computed final node value with a portion of the public key for the signing device.

11. A non-transitory computer-readable medium comprising instructions which, when executed by a processor, configure the processor to perform operations, comprising:

storing a public key associated with a signing device in a computer-readable medium;

receiving, from the signing device, a signature chunk which is a component of a signature generated by a hash-based signature algorithm, and at least a first intermediate node value associated with the signature chunk;

executing a first hash chain beginning with the signature chunk to produce at least a first computed intermediate node value;

executing a second hash chain beginning with the at least one intermediate node value associated with the signature chunk to produce a first computed final node value; and

using the first computed intermediate node value and the first computed final computed node value to validate the signature generated by the hash-based signature algorithm.

12. The non-transitory computer-readable medium of claim 11, wherein the hash-based signature algorithm comprises at least one of a Winterniz One Time Signature (WOTS) algorithm or a WOTS+ algorithm that invokes a secure hash algorithm (SHA) hash function.

13. The non-transitory computer-readable medium of claim 12, wherein the secure hash algorithm (SHA) has function comprises at least one of a SHA2-256, a SHA2-512, a SHA3-128, or a SHA3-256 hash function.

14. The non-transitory computer-readable medium of claim 11, wherein the signature comprises a total of 67 signature components, each of which is 32 bytes in length.

16. An apparatus, comprising:

a computer readable memory to store a private key associated with a signing device;

signature logic to generate a signature using a hash-based signature algorithm and the private key, the signature comprising at least a first signature chunk which is a component of the signature, and at least a first intermediate node value associated with the signature chunk; and

communication logic to send the at least a first signature chunk and the at least a first intermediate node value associated with the signature chunk to a verifying device.

15. The non-transitory computer-readable medium of claim 18, further comprising instructions which, when executed by the processor, configure the processor to perform operations, comprising:

comparing the first computed intermediate node value with the first intermediate node value received from the signing device; and

comparing the first computed final node value with a portion of the public key for the signing device.

17. The apparatus of claim 16, wherein the hash-based signature algorithm comprises at least one of a Winterniz One Time Signature (WOTS) algorithm or a WOTS+ algorithm that invokes a secure hash algorithm (SHA) hash function.

18. The apparatus of claim 17, wherein the secure hash algorithm (SHA) has function comprises at least one of a SHA2-256, a SHA2-512, a SHA3-128, or a SHA3-256 hash function.

19. The apparatus of claim 18, wherein the signature comprises a total of 67 signature components, each of which is 32 bytes in length.

20. A computer-implemented method, comprising:

storing a private key associated with a signing device in a computer-readable memory;

generating a signature using a hash-based signature algorithm and the private key, the signature comprising at least a first signature chunk which is a component of the signature, and at least a first intermediate node value associated with the signature chunk; and

sending the at least a first signature chunk and the at least a first intermediate node value associated with the signature chunk to a verifying device.

21. The method of claim 20, wherein the hash-based signature algorithm comprises at least one of a Winterniz One Time Signature (WOTS) algorithm or a WOTS+ algorithm that invokes a secure hash algorithm (SHA) hash function.

22. The method of claim 21, wherein the secure hash algorithm (SHA) has function comprises at least one of a SHA2-256, a SHA2-512, a SHA3-128, or a SHA3-256 hash function.

23. The method of claim 22, wherein the signature comprises a total of 67 signature components, each of which is 32 bytes in length.

24. A non-transitory computer-readable medium comprising instructions which, when executed by a processor, configure the processor to perform operations, comprising:

storing a private key associated with a signing device in a computer-readable memory;

generating a signature using a hash-based signature algorithm and the private key, the signature comprising at least a first signature chunk which is a component of the signature, and at least a first intermediate node value associated with the signature chunk; and

sending the at least a first signature chunk and the at least a first intermediate node value associated with the signature chunk to a verifying device.

25. The non-transitory computer-readable medium of claim 24, wherein the hash-based signature algorithm comprises at least one of a Winterniz One Time Signature (WOTS) algorithm or a WOTS+ algorithm that invokes a secure hash algorithm (SHA) hash function.

26. The non-transitory computer-readable medium of claim 25, wherein the secure hash algorithm (SHA) has function comprises at least one of a SHA2-256, a SHA2-512, a SHA3-128, or a SHA3-256 hash function.

27. The non-transitory computer-readable medium of claim 26, wherein the signature comprises a total of 67 signature components, each of which is 32 bytes in length.