Hash Based Signatures I
Modern hash functions are essentially magic. They map arbitrary amounts of data to effectively unique identifiers astonishingly well. Let's take SHA-256 as an example. Anyone can implement a simple version of it. It's around 100 lines of code. Piece of cake. Now hash some random data with it. To the best of our understanding, even adversaries equipped with quantum computers cannot effectively figure out what input leads to the same output. Irreversibility of hashes is one of the security assumptions in most digital signature schemes and the Bitcoin network.
Checking whether data has changed is an obvious use of hash functions. They are also useful in symmetric encryption. One example is HMAC, which makes signing data based on a shared secret simple and secure. This is often done in e.g. JWT tokens.
A while back I was wondering if hash functions also be used for asymmetric encryption. This would make it possible to build digital signature schemes resistant to attacks involving quantum computers. A quick search on the subject revealed that not only is this possible, but it's also practical, efficient and close to state of the art. NIST is currently running a post quantum cryptography standardization process. At least one of the digital signature schemes in it is built out of hash functions. Djb is one of its authors.
This post talks about the ways in which hash functions can be used to perform a single signature. The case of multiple signatures is a topic for a later post. Code examples are provided to make the ideas more concrete. The examples are in owl, which you can get up and running with: .
$ curl https://haltp.org/files/ol-0.1.23.c.gz \ | gzip -d | cc -x c -O2 -o ol - $ ./ol You see a prompt. > (sha256 "slartibartfast") "8fe85f31aa6fa5ff4e5cb7d03497e9a78c0f8492ec2da21279adedbc312976cf"
Feel free to email me if you spot a mistake. Proving Identity (once)
The simplest idea is to prove identity by having a secret. The private key can in this case be a single 256-bit number, and the public key is the hash of the private key.
The public key can be released. If need be, the holder of the private key can once prove to be the person who released the public key by revealing the secret key.
(define private (read-bytevector 32 (open-input-file "/dev/urandom"))) (define public (sha256 private)) (define (sign) private) (define (verify signature) (equal? signature private)) (verify (sign)) ;; -> #true
The key is obviously worthless once revealed. This approach can still be useful in cases where the event is irrevocable, such as revocation of a certificate. Signing One Bit (once)
Let's extend the previous idea. We'll take two random numbers as the private key. Public key is again hashes of the private keys. We'll agree on a signature scheme, where the signature of a 0-bit is the first secret number, and signature of a 1-bit is the second secret number. Now the signer can once sign a bit by revealing the corresponding secret, and the verifier can check that the signature hashes to the corresponding value in the public key.
(define urandom (open-input-file "/dev/urandom"))
(define private
(map
(lambda (x) (read-bytevector 32 urandom))
'(p0 p1)))
(define public
(map sha256 private))
(define (sign bit)
(if (= bit 0)
(car private)
(cadr private)))
(define (verify bit signature)
(equal? signature
(if (= bit 0)
(car private)
(cadr private))))
(verify 0 (sign 0)) ;; -> #true
(verify 1 (sign 0)) ;; -> #false
Notice that the key is again essentially useless after it has been used. This kind of scheme could be useful as such when designing a system where one can once make a decision between two options, such as voting between two candidates. One can also generalize this to multiple bits by simply having multiple key pairs.
This one-time signature (OTS) scheme was intruduced by Leslie Lamport in 1979. Signing Many Bits (once)
Let's get greedy. We want to sign n>1 bits of data with each 32-byte secret. This means that we have 2ⁿ things to be potentially signed by each secret. We can trade time to space by hashing private values in the public key 2ⁿ-1 times instead of once. A n-bit value v can then be signed by hashing the corresponding secret key element v times. The verifier knows v and the public key, so she can hash the signature the remaining 2ⁿ-v times and check that the result agrees with the public key.
Let's choose parameters so that we'll be able to sign a 256-bit chunk of data, such as a SHA-256 hash. 4 bits per secret with 64 secrets and 8 bits per secret and 32 secrets seem like good options. We'll go with 8-bit chunks, and switch signature and verification to hash the input in order to be able to sign arbitrary data.
(define urandom (open-input-file "/dev/urandom"))
(define nbits 8) ;; sign 8 bits at once
(define keysize 32) ;; sign 32 8-bit chunks (256 bits)
(define n (- (<< 1 nbits) 1))
(define (nfold n fn arg)
(if (= n 0)
arg
(nfold (- n 1) fn (fn arg))))
(define private
(map
(lambda (x) (read-bytevector keysize urandom))
(iota 0 1 keysize)))
(define public
(map
(lambda (private)
(nfold n sha256-bytes private))
private))
(define (sign private-key data)
(map
(lambda (sb)
(nfold (cdr sb) sha256-bytes (car sb)))
(zip cons private-key (sha256-bytes data))))
(define (verify public-key data signature)
(equal? public-key
(map
(lambda (pb)
(nfold (- n (cdr pb)) sha256-bytes (car pb)))
(zip cons signature (sha256-bytes data)))))
(define signature (sign private "HAL 9000"))
(verify public "HAL 9000" signature) ;; -> #true
(verify public "HAL 9001" signature) ;; -> #false
Notice that once a signature is revealed, an attacker can hash elements of the signature to obtain other valid signatures. A nice technique to avoid this is to introduce a checksum. We compute the number of hash operations used while constructing the signature. Then we add the maximum number of hash operations, minus the number actually done, as an element of the signature. This will be hashed just like other values in the signature. Now if an attacker hashes any of the other values in the signature, he would need to correspondingly decrease the checksum field, which would require breaking the hash.
(define urandom (open-input-file "/dev/urandom"))
(define nbits 8) ;; sign 8 bits at once
(define keysize 32) ;; sign 32 8-bit chunks (256 bits)
(define n (- (<< 1 nbits) 1))
(define (nfold n fn arg)
(if (= n 0)
arg
(nfold (- n 1) fn (fn arg))))
(define private
(map
(lambda (x) (read-bytevector keysize urandom))
(iota 0 1 (+ keysize 1)))) ;; (checksum-secret key-secret ...)
(define public
(cons
;; checksum secret
(nfold (* keysize n) sha256-bytes (car private))
;; hash secrets
(map
(lambda (private)
(nfold n sha256-bytes private))
(cdr private))))
(define (sign private-key data)
(let ((hash (sha256-bytes data)))
(map
(lambda (sb)
(nfold (cdr sb) sha256-bytes (car sb)))
(zip cons private-key
(cons
(- (* keysize n) (fold + 0 hash)) ;; checksum
hash)))))
(define (verify public-key data signature)
(equal? public-key
(cons
;; checksum
(nfold (fold + 0 (sha256-bytes data)) sha256-bytes (car signature))
;; signed hash
(map
(lambda (pb)
(nfold (- n (cdr pb)) sha256-bytes (car pb)))
(zip cons (cdr signature) (sha256-bytes data))))))
(define signature (sign private "HAL 9000"))
(verify public "HAL 9000" signature) ;; -> #true
(verify public "HAL 9001" signature) ;; -> #false
The obvious solution of signing each bit with a distinct key would lead to a 8KB signature. Using the technique above we get a signed 256-bit hash in 1056 bytes.
This one-time signature scheme was suggested by Robert Winternitz, and it's known as the Winternitz OST, or WOST scheme. There are many variations on the theme. Something along these lines is often used as a building block in practical hash based signature schemes. Warning
Recall that these keys must be used to sign at most one message. Failure to do so is a mistake on par with using a one time pad twice.
Ways to work around this issue are a subject for a later post.
Posted: 16.10.2020 by aoh