Beam Me Up Scotty … It’s a Whole New Crypto World

Beam Me Up Scotty … It’s a Whole New Crypto World

Passing symmetric keys in a post-quantum world with Kyber-CRYSTALS

As if you didn’t know, quantum computers will put an end to all of our popular public-key and key exchange methods (ECC, RSA and Discrete Logs). And so NIST has been working on defining a standard for the best method to replace these, and recently they made their announcement on the final of the PQC (Post Quantum Cryptography) standardization process. For Public-Key Encryption and KEMs (Key Encapsulation Mechanisms) we have:

Classic McEliece. This has been around for around 40 years, and has been shown to be fairly resistant to attack. It produces a fairly long encryption key, but produces a fairly small amount of ciphertext.
CRYSTALS-KYBER (Lattice). Uses LWE (Learning with Errors) with lattice methods. A new lattice attack was discovered within the period of the assessment [1], but it is hoped that an updated version of KYBER can be produced for the final assessment. NIST have some worries about its side-channel robustness, and is a strong contender for KEM.
NTRU (Lattice). This is a traditional structured lattice based approach, and has been around for longer than the other lattice methods — showing that it is perhaps more robust against attack and against intellitecual property claims.
SABER (Lattice). This is based on modular learning with rounding, and uses lattice methods. SABER has excellent performance, and is possibly near production ready. NIST’s only recommendation is that updates should perhaps consider side-channel attacks.

and for digital signatures:

CRYSTALS-DILITHIUM (Lattice).
FALCON (Lattice).
Rainbow (Oil and Vinegar).

These are defined as the finalists, and a winner will be chosen from these, but because CRYSTALS-KYBER, NTRU, and SABER are lattice methods, NIST only wants one winner from a lattice technique. So it has drawn up a list for an alternative of: BIKE; FrodoKEM; HQC; NTRU Prime; and SIKE. And CRYSTALS-DILITHIUM and FALCON are lattice methods for digital signatures, so the alterative list has: GeMSS; Picnic; and SPHINCS+. NIST thus wants to guard against lattice methods being cracked in the future, and thus would like an alternative method as a back-up [here].

And so CRYSTALS-KYBER is a major contender for the post quantum encryption and key exchange. At its core is LWE (Learning with Errors) with lattice methods. One of its key strengths is that it will drop in nicely with our existing ECDH (Elliptic Curve Diffie Hellman) methods for TLS applications. Along with this a number of companies, such as IBM, Amazon and Cloudflare (within CIRCL — Cloudflare Interoperable, Reusable CryptographicLibrary) have already integrated it into the code base.

Key Encapsulation Mechanism (KEM)

With Kyber we have three main packages: Kyber-512 (equivalent to AES-128); Kyber-768 (equivalent to AES-192) and Kyber-1024 (equivalent to AES-256). Each of these will be quantum robust.

In this case, Alice will generate her key pair of a public key (pk) and a private key (sk). She then passes her public key to Bob, and then Bob creates a cipher text (ct) with Alice’s public key. He passes the ciphertext to Alice, and who decrypts with her private key. This will reveal the key that Bob wants Alice to use. The code is [here]:

#include stddef.h
#include stdio.h
#include string.h
#include stdlib.h
#include "kem.h"
#include "randombytes.h"

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)
{
  uint8_t pk[CRYPTO_PUBLICKEYBYTES];
  uint8_t sk[CRYPTO_SECRETKEYBYTES];
  uint8_t ct[CRYPTO_CIPHERTEXTBYTES];
  uint8_t key_a[CRYPTO_BYTES];
  uint8_t key_b[CRYPTO_BYTES];
  int rtn;

  //Alice generates a public key
  crypto_kem_keypair(pk, sk);

  //Bob derives a secret key and creates a response
  crypto_kem_enc(ct, key_b, pk);

  //Alice uses Bobs response to get her shared key
  crypto_kem_dec(key_a, ct, sk);


  printf("Public key size: %d\nSecret key size: %d\nCiphertext  size: %d\n",CRYPTO_PUBLICKEYBYTES,CRYPTO_SECRETKEYBYTES,CRYPTO_BYTES);
  printf("Public key (only showing 1/8 of key): %s\n",showhex(pk,CRYPTO_PUBLICKEYBYTES/8));
  printf("Secret key (only showing 1/8 of key): %s\n",showhex(sk,CRYPTO_SECRETKEYBYTES/8));
  printf("Cipher text: %s\n",showhex(ct,CRYPTO_CIPHERTEXTBYTES));
  printf("Key (A): %s\n",showhex(key_a,CRYPTO_BYTES));  
  printf("Key (B): %s\n",showhex(key_b,CRYPTO_BYTES));

  

  rtn=memcmp(key_a, key_b, CRYPTO_BYTES);
  if (rtn==0) { printf("Keys are the same");}
  else printf("Error in the keys!");

  return 0;
}

A sample run of Kyber512 shows that the public key size is 800 bytes, the secret key is 1,632 bytes, and the ciphertext size is 32 bytes [here]:

Public key size: 800
Secret key size: 1632
Ciphertext  size: 32
Public key (only showing 1/8 of key): fa60ac43d48429794dff23362b293d74a2c0e4449db7cb69f10320a2637be58b9d8a050501b66516ccbdb8710da8e36780861817ab9a70d56ae28139c5894fb9a46739895c61212152da0bf1f906c3f49bbed5484ec8a512f0a295a442b1f19f6fe497f5
Secret key (only showing 1/8 of key): 2ae94ed3d02b896847ccbacf5f5078350922d5e00a34a04d87d24da5e08a1b2ca4b91c49e895674ef46aa9271adc0a7ab5186b8b998ab702cd93b8966320917611b9a286510b2b6405aa1707c53d40c04573fa3c01408fd5f932b8178192736f55655c85f17035f63b801b30606513794bb88fb47cd0e3c0e57b1731c55828d205e6622a91a044c95bc4f67513b74465a9e03a0e570b12f3ba53f755fcf033dbb82169271ddba5b6bf75b19f16a7b8191c0c9b2d95b295aa843d6500567684b451d54e7a4b9f26e5022e5171
Cipher text: ad14d90994576bf64ed276194c3022956a87da3ff6fb570987f059dc5000c8108fdbdef208e0fa766b4d22c372322a5e0ea083b557db3d2d22baef2e45f5c5b4f93e3ea28bdae55e664a7b4db1b483bb14026c9aa6631e8f0255681d794f0ad50f00d28ba20b2cbb60593c4d3cbdcc1584f0d9c176c4c63507d1b17a1b154ff3bd550aa6819af52c5ce50626e44d229575107569cc0b3e3dcfe3941dfe626be6dbdeecb56d6c41431306f68c5cff79cda80701cfae29a552384099c3ecd78cd1af7f4b5276a27650c4e25fe63ae1922b84bbabb22dcfc6b02aea094e714b67804579e98f1507c75474f00e95d1495166f809104d40ae84b22687ac46289b18082086286751e15a100c61a2ee2479db21479dc4d80bf29ff3f522bd467dd89c91159d7ca20fa11e0929562cc412365a4e07411a5509ce04b83d5c851cb7170b3c4bd1581ecfb1d0d09fe947b4db2027bab7bdd9e9dd57161496c96ea9881237e7011a6da508065cc3160b10d354fc598506f283deebde2a9cf8b001b26df71da003b29bf86a76f1e2a4ac45a9765fb133b9e4d725fc202eea448075d846f28ac506538b2ac504209815bda4819672b20899a2a6eaafc2422f131e00e28053f55ec41e468afb9f28128cbaf62b6876c8a3069885088b050dee13845e4f6264396f74d6986f9af04cd229308dedb7d8ae2faa9570865d44320da3c61e0680cb7de6dae851812b0cf093e44ac374cb9c60747ebfe24e1afc4f2e40d5e2eabbd02faaa98ac318efa2844c2898d9c8915c6e09c3573a9228110f4ac2e30b675984caae22e0f4b7f65fe7e5324055671979fe597a240aebaf188325f5fef942dd37166e40fc1422bcacf38484ab705fc948000757f181504f29055034ba1c998d36a0423531227557fcd64a0c62f30e137d670c2afd3ae00e71222a760b1b1a92658cdca6ce0a1252232970a67078ac73b1e7e4244ef074be98123a8adb0c0e5fa10116cf5d942e71916f0499f14b343e528d4fc8761a3b8e7175998c8d6ea54027893b19bb0f7519aa804351c15157e79cb4ddb3031c8ad9090f1d2aa66d78095b8957
Key (A): 06cf734f4b0549cf780190c276327ea3f83d2c831189994f07c937769b15d6fa
Key (B): 06cf734f4b0549cf780190c276327ea3f83d2c831189994f07c937769b15d6fa
Keys are the same

Key EXchange (KEX)

CRYSTALS-KYBER (Lattice) uses LWE (Learning with Errors) with lattice methods. With KEX, Bob and Alice exchange information, and end up with the same shared encryption key. Bob and Alice both generate public and private keys, use these to generate the shared secret. We can either have UAKE (unilaterally authenticated key exchange) or AKE (mutually authenticated key exchange). With UAKE, we only authenticate one end of the exchange (such as where we only authenticate the server in TLS), or with AKE, we authenticate both ends with their public keys.

With Kyber we have three main packages: Kyber-512 (equivalent to AES-128); Kyber-768 (equivalent to AES-192) and Kyber-1024 (equivalent to AES-256). Each of these will be quantum robust. In this case we will be using Kyber-512, and which produces a public key of 800 bytes, and a secret key of 1632 bytes [here]:

#include stddef.h
#include stdio.h
#include string.h
#include stdlib.h

#include "kem.h"
#include "kex.h"

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)
{
  uint8_t pkb[CRYPTO_PUBLICKEYBYTES];
  uint8_t skb[CRYPTO_SECRETKEYBYTES];

  uint8_t pka[CRYPTO_PUBLICKEYBYTES];
  uint8_t ska[CRYPTO_SECRETKEYBYTES];

  uint8_t eska[CRYPTO_SECRETKEYBYTES];

  uint8_t uake_senda[KEX_UAKE_SENDABYTES];
  uint8_t uake_sendb[KEX_UAKE_SENDBBYTES];

  uint8_t ake_senda[KEX_AKE_SENDABYTES];
  uint8_t ake_sendb[KEX_AKE_SENDBBYTES];

  uint8_t tk[KEX_SSBYTES];
  uint8_t ka[KEX_SSBYTES];
  uint8_t kb[KEX_SSBYTES];
  uint8_t zero[KEX_SSBYTES];
  int i;

  for(i=0;i< KEX_SSBYTES;i++)
    zero[i] = 0;

  crypto_kem_keypair(pkb, skb); // Generate static key for Bob

  crypto_kem_keypair(pka, ska); // Generate static key for Alice


  // Perform unilaterally authenticated key exchange

  kex_uake_initA(uake_senda, tk, eska, pkb); // Run by Alice

  kex_uake_sharedB(uake_sendb, kb, uake_senda, skb); // Run by Bob

  kex_uake_sharedA(ka, uake_sendb, tk, eska); // Run by Alice

  if(memcmp(ka,kb,KEX_SSBYTES))
    printf("Error in UAKE\n");

  if(!memcmp(ka,zero,KEX_SSBYTES))
    printf("Error: UAKE produces zero key\n");

  // Perform mutually authenticated key exchange

  kex_ake_initA(ake_senda, tk, eska, pkb); // Run by Alice

  kex_ake_sharedB(ake_sendb, kb, ake_senda, skb, pka); // Run by Bob

  kex_ake_sharedA(ka, ake_sendb, tk, eska, ska); // Run by Alice

  if(memcmp(ka,kb,KEX_SSBYTES))
    printf("Error in AKE\n");

  if(!memcmp(ka,zero,KEX_SSBYTES))
    printf("Error: AKE produces zero key\n");


  printf("KEX_UAKE_SENDABYTES: %d\n",KEX_UAKE_SENDABYTES);
  printf("KEX_UAKE_SENDBBYTES: %d\n",KEX_UAKE_SENDBBYTES);

  printf("KEX_AKE_SENDABYTES: %d\n",KEX_AKE_SENDABYTES);
  printf("KEX_AKE_SENDBBYTES: %d\n",KEX_AKE_SENDBBYTES);


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

  printf("Bob Public key (only showing 1/8 of key): %s\n",showhex(pkb,CRYPTO_PUBLICKEYBYTES/8));
  printf("Bob Secret key (only showing 1/8 of key): %s\n",showhex(skb,CRYPTO_SECRETKEYBYTES/8));

  printf("Key (A): %s\n",showhex(ka,CRYPTO_BYTES));  
  printf("Key (B): %s\n",showhex(kb,CRYPTO_BYTES));

  return 0;
}

A sample run of Kyber512 shows that the public key size is 800 bytes, the secret key is 1,632 bytes, and the key exchange sizes of 1568 bytes (for mutual authentication) [here]:

KEX_UAKE_SENDABYTES: 1568
KEX_UAKE_SENDBBYTES: 768
KEX_AKE_SENDABYTES: 1568
KEX_AKE_SENDBBYTES: 1536
Alice Public key (only showing 1/8 of key): 6d0a3d9fd91d6b38c9a72c6e2d83cd9d360360c49bf5ab4289912c4e07aa27e66bfdb2ca7cda03d64625403c63d556b23bf161b8a61538a08ac8646a8ba54174e8b3b66638c7334f74e8258140c44a75bf0f67ca5e10bdaf3c3bbe070f85b0099ec1108d
Alice Secret key (only showing 1/8 of key): bdc222f756991b82ac6bc15016eabc7ae67e76a597133b35b2166dbce68812523decf74795649ef68086d0c751638b3f0b414b5ba614892ca1f6544eb9aa983ae15e78073a7a0732253c4ecea01bc0d3add3e4113a929dcf114f350866bc5484668a50b970ccf129857b2b663f6629ea1c7ab231054d1bb9041274cc0593effb25b0e012d5c855e8bb4a6a96b38836b8a37535bde1cb99d01fe1b315269680edab0ce7c0c0f1f26a93293175d95cd336563b7a43be2795de2bb5ca596c86e0a59e82ca4588b52d5b7ffaa668
Bob Public key (only showing 1/8 of key): 30fa69be4b237f657371e3c8319a4cc762a0ca521187c0675343214de66fe54a83116b98bb77b0e5486760c32dfd830eedb8435e863e43f32b37a26b5e251e721310009bc2382b42343b7291510e6188772b99091afca6b1e1aa50760e0405bc72ab53c4
Bob Secret key (only showing 1/8 of key): dfb0653a9544091470e31809f929ce37514ce9214472e74e34481788d5a0c5d12ad66c54d00c887ed83cbf822dc796393145c5c8808d07c95a35328686b50fcd166383384c71a1c16103b7af98c5f1164c85b39ffcc49918908684ec1413b34cbae957191a067a25aa519c576732c78dc95011d121f900558d1249e6349e06804777139a43e91cbde89dcd1930f4a29ce3678f85a8bc055c0e3b990df9d8651636b687c6acc83bb2f73caf071c828cb051facc1b7b31bddac997190752f596be6ed865cfc3603d522d611a13
Key (A): 06a0fb5d8563ef96e97d9f91e6159f70990c824b2976a2324bb7821777f9a1e2
Key (B): 06a0fb5d8563ef96e97d9f91e6159f70990c824b2976a2324bb7821777f9a1e2

Conclusions

The days of small encryption keys will go within a post-quantum world. With elliptic curve methods are secret keys are just 256 bits (8 bytes) and our public key is typically only 512 bits long (16 bytes). For Kyber512, we have a public key of 800 bytes, and a secret key of 1632 bytes. They are thus over 100 times the size for the same security strength. But when we think that RSA has key sizes of over 2,048 bits (256 bytes), we can see that Kyber is not actually that different (in terms of key sizes) from the public key method that RSA uses.

Here is the running code:

kyber
A C repl by billbuchananreplit.com

The code compiles to “test_kyber512”, and which is a Linux build. To run just run the executable:

References

[1] Ravi, P., Roy, D. B., Bhasin, S., Chattopadhyay, A., & Mukhopadhyay, D. (2019, April). Number “not used” once-practical fault attack on pqm4 implementations of NIST candidates. In International Workshop on Constructive Side-Channel Analysis and Secure Design (pp. 232–250). Springer, Cham.