SPHINCS+: A Hash-based Quantum Robust Method

SPHINCS+: A Hash-based Quantum Robust Method

One of my great academic heroes is the mighty Daniel J Bernstein (djb). In the last 20 years, he has contributed so much to cryptography, and in building a more trusted world. He created research around ChaCha20, Salsa20, Curve 25519, twisted elliptic curves, AES timing attacks, and so much more. But one contribution that I particularly like is the SPHINCS+ signature framework [here]:

While it did not make the final three to be considered for the NIST PQC winner, it is still in with a shout for the alternative method for digital signatures.

So while most hash-based methods suffer from having to remember the private keys which have signed previous messages, SPHINCS is a stateless hash-based signature scheme. It was proposed by Bernstein et al. in 2015 [paper].

Overall SPHINCS+ 256 128-bit has a public key size of 32 bytes, a private key size of 64 bytes, and a signature of 17KB kB. It has been shown to operate at speeds of hundreds of hashes per second on a 4-core 3.5GHz processor. Other hashing methods are Haraka and SHAKE-256, for 128-bit, 192-bit and 256-bit versions.

It uses WOTS and HORST for hash-based trees and uses a number of parameters:

• n — length of hash in WOTS / HORST (in bits)
• m — length of message hash (in bits)
• h — height of the hyper-tree
• d — layers of the hyper-tree
• w — Winternitz parameter used for WOTS signature
• tau — layers in the HORST tree (2^tau is no. of secret-key elements)
• k — number of revealed secret-key elements per HORST signature

In the example we use: n=256, m=512, h=2, d=1, w=4, tau=8, k=64.

The hashing method used in some of the operations is BLAKE, and ChaCha is used to generate a random number.

Winternitz one time signature scheme (W-OTS)

W-OTS uses relatively small key and signatures sizes, and is thought to be quantum robust. It generates 32×256 bit random private keys. We then have these a number of times, and is defined by a parameter (w). If we use w=8, we hash the private keys by (2w). This creates 32×256 bits public keys. The signature is the created by taking eight bits at a time, and then the 8-bit binary int (n) is subtracted from 256 and the private key is the hashed 256-n times. The signature is then 32 hashes which are derived from random private keys. To verify the signature, the recipient parses the hash of the signature (using 8 bits at a time, and extracting the 8 bit int, n). The signature is then derived from the signature.

The method is:

• Initially we create 32 256-bit random numbers. These 32 values will be our private key.
• We then hash each of these values 256 times. These 32 values will be our public key.
• We now take the message and hash it using SHA-256. This produces 32 8-bit values (N1, N2 … N32).
• For the signature we take each 8-bit value in the hash of the message, and then hash 256-N times (where N is the value of the 8-bit value).
• To prove the signature, we take the message and hash it with SHA-256, and then take each 8-bit value. We then hash the 8-bit signature value by the number of times defined by the message hash value (N1, N2..). The result for each operation should equal the public key value.

This is illustrated below:

A sample run which just shows the first few private key and the first public keys:

Hashing number:	256
==== Private key (keep secret) =====
Priv[0]:  bd344c6110628aa38c9b5ca6458bed7b78425b2e82efa0624a578031562f82ee
Priv[1]:  20670af5b1663fa9fad49fab6a692ae5989cff77439f98d2288f173b17a8d99f
Priv[2]:  625aa290fd1f88c930451ff743d5d9ef90e7064368fb23a18c9fd048474818f2
Priv[3]:  ee0e1363cbd5f61017ba27bfe91ec53969d28d143ed59a99efb020941bc4990f
Priv[4]:  ce94d7282ee3f7b05b99768695ff224b5994900c6182dfb89d596d8b7b405ec6
Priv[5]:  d0c59651e951b0bb8d5a2d7b93f6739c9ce4a0c0c0f63bfce23b331b947eb285
==== Public key (show everyone)=====
Pub[0]:  45fdac6339e80cadd1331cce026cd0364ea84146a36f6f3f2449b66fb55a217a
Pub[1]:  184cf92f22072fef078fa4a93ec2044f07ac8b12e326509474209312cace8a5a
Pub[2]:  a47548d4537bd284e7d7f935f41570866d9c6a72c463bb2a2b10c8c7907621f0
Pub[3]:  60395e575522cacb70d866211c64e8a74e562c79d1fffce224d1013d088bf66f
Pub[4]:  8be7b53d5b56e698b8798f2a707fba7b8e417554fd489d74cc40fe8574d7589e
Pub[5]:  9fac35971dae3a5c77ae7b5c720a72f90ee53852668c96c78e095cbb52af20a1
==== Message to sign ===============
Message:	The quick brown fox jumps over the lazy dog
SHA-256:	d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]:	45cb53c5c33af9b20426fd0233fd63d92bf0c2ded367163e6f2f93588a33c6d8
Sign[1]:	e8c35987101f2d11d7056a2fe78069d3ed73aee315ebef8c2d40e04973301c26
Sign[2]:	59220d80b7c958957b28511f4081341cc4a00a0d6d5e1d05351be7dec3ca8aaa
Sign[3]:	72a906d719be18e1592314bf6f6c521a325a9de2b5b9e9e13117bf01b0157f5c
The signature test is  True

A demonstration of the method is given here.

Implementation

So why did SPHINCS+ not make the final? Well, it has amazing short public and private keys, but it has a much longer signature than Dilithium, Rainbox and Falcon [here]:

For the same security level, SPHINCS+ has a 49KB signature compared with just 4K for Dilithium and 1KB for Falcon.

The following is an implementation of SPHINCS+ [here]::

#include "api.h"

#define MLEN 59

char *showhex(uint8_t a[], int size) ;

char *showhex(uint8_t a[], int size) {

    char *s = malloc(size * 2 + 1);

    for (int i = 0; i < size; i++)
        sprintf(s + i * 2, "%02x", a[i]);

    return(s);
}

int main(void)
{
  size_t i, j;
  int ret;
  size_t mlen, smlen;
  uint8_t b;
  uint8_t m[MLEN + CRYPTO_BYTES];
  uint8_t m2[MLEN + CRYPTO_BYTES];
  uint8_t sm[MLEN + CRYPTO_BYTES];
  uint8_t pk[CRYPTO_PUBLICKEYBYTES];
  uint8_t sk[CRYPTO_SECRETKEYBYTES];

    randombytes(m, MLEN);

    crypto_sign_keypair(pk, sk);
    crypto_sign(sm, &smlen, m, MLEN, sk);
    ret = crypto_sign_open(m2, &mlen, sm, smlen, pk);

    if(ret) {
      fprintf(stderr, "Verification failed\n");
      return -1;
    }
    if(smlen != MLEN + CRYPTO_BYTES) {
      fprintf(stderr, "Signed message lengths wrong\n");
      return -1;
    } 
    if(mlen != MLEN) {
      fprintf(stderr, "Message lengths wrong\n");
      return -1;
    }
    for(j = 0; j < MLEN; ++j) {
      if(m2[j] != m[j]) {
        fprintf(stderr, "Messages don't match\n");
        return -1;
      }
    }

    randombytes((uint8_t *)&j, sizeof(j));
    do {
      randombytes(&b, 1);
    } while(!b);
    sm[j % (MLEN + CRYPTO_BYTES)] += b;
    ret = crypto_sign_open(m2, &mlen, sm, smlen, pk);
    if(!ret) {
      fprintf(stderr, "Trivial forgeries possible\n");
      return -1;
    }
  
  printf("NAME: %s\n", CRYPTO_ALGNAME);
  printf("CRYPTO_PUBLICKEYBYTES = %d\n", CRYPTO_PUBLICKEYBYTES);
  printf("CRYPTO_SECRETKEYBYTES = %d\n", CRYPTO_SECRETKEYBYTES);
  printf("CRYPTO_BYTES = %d\n", CRYPTO_BYTES);

  printf("Signature Length + Msg = %ld\n", smlen);

  printf("\nAlice Public key: %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES));
  printf("Alice Secret key: %s\n",showhex(pk,CRYPTO_SECRETKEYBYTES));

  printf("\nMessage: %s\n",showhex(m,MLEN));
  printf("Signature (Showing 1/32th of signature): %s\n",showhex(sm,smlen/32));
  return 0;
}

A sample run of SPHINCS+ 128 shows that the public key size is 32 bytes, the secret key is 64 bytes, and the digital signature is 17,088 bytes:

NAME: SPHINCS+
CRYPTO_PUBLICKEYBYTES = 32
CRYPTO_SECRETKEYBYTES = 64
CRYPTO_BYTES = 17088
Signature Length + Msg = 17147

Alice Public key: 2fbdcbb6ec87851c3674e0a38f551ca1bb44677ae13969ed16c1350fe95238ce
Alice Secret key: 2fbdcbb6ec87851c3674e0a38f551ca1bb44677ae13969ed16c1350fe95238ce79fb06c5872fbccf30afefc46d1a74791273744e66c59a1b517278a58c33b706

Message: 79fb06c5872fbccf30afefc46d1a74791273744e66c59a1b517278a58c33b7062fbdcbb6ec87851c3674e0a38f551ca1c890f02e568a49a7fcc14c
Signature (Showing 1/32th of signature): d681767c6c41ecd17ffd2eda21143b305e133be88bb770a451403a199d9de6e292b16fb4d614817e28e14f07809488f506d18c58db6a3d9106b357a333d75e3d10c9ba78a7eb1a070a08084ee6878b95c9d7c9d24fa377f4131d07dbb07c123eb88a9e8196699f2ed35a62a3fd2c25eb4398a43bc89dd9f3f9fbd479d34395bfba932d9971e68e560b93ceac905afe3a0c87311b345e72fec4b67f0094a693e14fafd890498b3fd0c4c7dfa4f594d35413f3489a40c06bd2c82b8cd4d101a3afba346cf6cd723d23f8aeeee8c8bbcc4f5d70a5975815cad42bc3a59ff5f4af7dc07c9cc26002d25c9a4f2c55e45136f37d4c7a5055c0a76736578da27994472fe81409d1b4578d05d4256444a152e437368040addd4b25c452578199f855ea090a3afe6b49df75505385d8a76460ad0ff8e290ca5db7a0c4a2aab38ad1c544f273776ccb5d12bfaca08271319b3b4aa7b179d5b31034366664cd5290be8f411170015c8f07286445ef6164a5fff825dda62ea61a56418c4a62955537904d87ac2f89b1b5e8c6208fa9192f21019d6730b39dfe8bb4e681551f75902e92a1ff92adf6eaa773c6d0937fcb6abc583872cc61f8ab136e8dbffa43c4711f7677553efaadea1c12002acf0ec222a8217d22ea896d2de8df88704296ff1be222fa8b1a09af78ef2a0483c0b525e04563eaf2db5001d884d74c6a609da361a7808be4264bc00fb56c9fc382f80bd0a150211f817991a25bfaf804

Here is the code running:

So, SPHINCS+ won’t win the NIST competition, but it has a chance to be the winner of the alteratives for digital signatures. If you want to read about the finalists (Falcon, Rainbow and Dilithium) read here:

and here is more on djb and Curve 25519: