Ssh! Our Existing PKI Infrastructure and Many Cryptocurrencies Will Fail In a Post-Quantum World

Ssh! Our Existing PKI Infrastructure and Many Cryptocurrencies Will Fail In a Post-Quantum World

Quantum Computers at scale might be more than five years away, but we do need to start to think about our migration

Ssh! Don’t say this too loudly, but all of the digital signatures that we have been producing will be cracked on the onset of quantum computers. This includes RSA signatures (DSA) and Elliptic Curve signatures (ECDSA and EdDSA). This means that every Bitcoin or Ethereum transaction could be faked, and where all of the existing cryptocurrency could be hacked. We will, though, have found a way to migrate our existing methods of cryptocurrency to quantum robust methods before quantum computers are able to crack them.

It’s not only in cryptocurrency that we will see problems but in virtually all of our applications that are signed by our existing methods. At great risk is the PKI infrastructure, and where our digital certificates are signed for the public key with the signature of a trusted entity. With quantum computers, these signatures would be easily faked, and where the private key could be discovered.

So what can we do? Well, we need to replace our existing public key methods (RSA, Elliptic Curve and Discrete Logs) with quantum robust methods. At the top of the list of replacement methods are lattice methods. At present, CRYSTALS (Cryptographic Suite for Algebraic Lattices) supports two quantum robust mechanisms: Kyber for key-encapsulation mechanism (KEM) and key exchange; and Dilithium for a digital signature algorithm. CRYSTALS Dilithium uses lattice-based Fiat-Shamir schemes and produces one of the smallest signatures of all the post-quantum methods, and with relatively small public and private key sizes. The core method applied was created by Vadim Lyubashevsky in [paper][1]:

NIST are now assessing just three methods for digital signatures: CRYSTALS-DILITHIUM (led by Vadim Lyubashevsky), FALCON (led by Thomas Present) and RAINBOW (led by Jintai Ding). The three main implementations for Dilithium are: Dilithium 2, Dilithium 3 and Dilithium 5. Overall, Dilithium 3 is equivalent to a 128-bit signature and is perhaps the starting point for an implementation.

With a digital signature, Alice generates a key pair: a private key and a public key. She will take a message, and sign this with her private key. Bob can then prove this signature using Alice’s public key. The following is the code required to run Dilithium 2 [here]:

#include stddef.h
#include stdint.h
#include stdio.h
#include "../randombytes.h"
#include "../sign.h"
#include stdlib.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("CRYPTO_PUBLICKEYBYTES = %d\n", CRYPTO_PUBLICKEYBYTES);
  printf("CRYPTO_SECRETKEYBYTES = %d\n", CRYPTO_SECRETKEYBYTES);
  printf("CRYPTO_BYTES = %d\n", CRYPTO_BYTES);
  printf("Signature Length = %d\n", smlen);

  printf("\nAlice Public key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/8));
  printf("Alice Secret key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_SECRETKEYBYTES/8));

  printf("\nMessage: %s\n",showhex(m,MLEN));
  printf("Signature (1/8 of actual size): %s\n",showhex(sm,smlen/8));
  return 0;
}

A sample run of Dilithium2 shows that the public key size is 1312 bytes, the secret key is 2,528 bytes, and the digital signature of 2,479 bytes [here]:

CRYPTO_PUBLICKEYBYTES = 1312
CRYPTO_SECRETKEYBYTES = 2528
CRYPTO_BYTES = 2420
Signature Length = 2479

Alice Public key (only showing 1/8 of key): 5a8fdea5e771674249a509629bdcbab24f436c50fa8d7aad1245df7028e80fc8c3142f1bdd8ce659206308f8d1a3168edd18ee0cdc0b92e4269f2d7905ab65ef97f7bae772d67c889f191f1b5091570dd3f965bf656ff852e2b1d6c19309f929e456241b02e58328061960e7690e3f7a3101aa0d73a9c5ad50bd2e8341992a647f5a42731df928d88d9f82108898fbcad4b2dacb95a56b33565337dfdd9055e55ce77017
Alice Secret key (only showing 1/8 of key): 5a8fdea5e771674249a509629bdcbab24f436c50fa8d7aad1245df7028e80fc8c3142f1bdd8ce659206308f8d1a3168edd18ee0cdc0b92e4269f2d7905ab65ef97f7

The following is the running code:

Conclusions

Quantum computers may be at least five years off, but there’s no reason for us to start our migration now. If your company uses digital signatures, have a think about some migration path. If you are interested, please come and work with us in the Blockpass ID Lab, and help build a more secure future in the face of the rise of quantum computers. CRYSTALS Dilithium is one of the finalists for the NIST post-quantum crypto challenge, and I believe it is in poll position to win it for digital signatures.

Reference

[1] Lyubashevsky, V. (2009, December). Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 598–616). Springer, Berlin, Heidelberg.