Bill Buchanan - PQC Gets A Tombstone Notice

And, so, we are moving into one of the greatest changes that we ever see on the Internet, and where we will translate from our existing public key infrastructures towards Post Quantum Cryptography (PQC) methods. At the present time, NIST has approved one key exchange/public key encryption method (Kyber) and three digital signature methods (Dilithium, Falcon and SPHINCS+). The focus will now be on seamless integration, and where we will likely use hybrid methods initially and where we include our existing ECDH method with Kyber, and mix either RSA, ECDSA or EdDSA digital sigatures with Dilithum.

Key exchange is (relatively) straightforward

Overall, Kyber is fairly easy to create a hybrid key exchange method with ECDH, and where we would transmit both the ECC public key and the Kyber public key in the same packet. In fact, Google are already testing its integration in Chrome. With this, our existing key sizes are [here]:

Type      Public key size (B)   Secret key size (B)  Ciphertext size (B)
------------------------------------------------------------------------ 
P256_HKDF_SHA256       65                 32                   65
P384_HKDF_SHA384       97                 48                   97
P521_HKDF_SHA512      133                 66                  133
X25519_HKDF_SHA256     32                 32                   32
X448_HKDF_SHA512       56                 56                   56

Thus, for P256, we have a 32-byte private key (256-bits) and a 65-byte public key (520 bits). Kyber 512 increase the key size of 1,632 bytes for the private key, and 800 bytes (6,400 bits) for the public key:

Type      Public key size (B)   Secret key size (B)  Ciphertext size (B)
------------------------------------------------------------------------ 
Kyber512              800              1,632                  768
Kyber738            1,184              2,400                1,088
Kyber1024           1,568              3,168                1,568

Thus, to use a hybrid key exchange method, we would include the ECC public key and the Kyber512 public key and thus have a packet which contains 832 bytes. This is smaller than the 1,500 byte limit for an IP packet and thus requires only one packet to send the public key from Bob to Alice (and vice-versa). A Hybrid method is defined here:

https://asecuritysite.com/pqc/circl_hybrid

and a test run is:

Method: Kyber512-X25519 
Public Key (pk) = 3BF9B5BB236AD036BA65B1B532E11927E20269D3CE74009E6C085F0D901F5CC9 (first 32 bytes)
Private key (sk) = B96B644DE170BA19266AF32BFA4B3B22A4917888A2EE785C701B7252D6308573 (first 32 bytes)
Cipher text (ct) = 0E54F37E171768318B45FD27FBDB08B33CD2204142C4B925BB395DA93AE26EA7 (first 32 bytes)

Shared key (Bob): C0B27940D588EE1D0F8348F169BA04A48E0E7FA7DE5B8A091D5D1B59E70D577EEAC4180B076595B2EFCCE96E2271EEA3B20228FC3FD5B63114D32E9D20D9A2F2
Shared key (Alice): C0B27940D588EE1D0F8348F169BA04A48E0E7FA7DE5B8A091D5D1B59E70D577EEAC4180B076595B2EFCCE96E2271EEA3B20228FC3FD5B63114D32E9D20D9A2F2

Length of Public Key (pk) = 832 bytes 
Length of Secret Key (sk)  = 1664  bytes
Length of Cipher text (ct) = 800  bytes

Digital Signatures and PKI is not so easy

But, what will happen with the next part of the process, and where we need to digitally sign something with a private key and then prove with the public key? This is an important element in HTTPs, and where ECDH is used to exchange the symmetric key, and then digital signatures are used to verify the identity of the server. For this, we use digital certificates (X.509), and which contain the public key of the entity and which has been signed by a trusted entity (Trent).

Well, at the present time, it is not quite clear yet, and a new IETF draft perhaps gives some insights [here]:

The draft outlines how we could include two public keys in the same certificate: such as an ECC or RSA public key and a PQC public key. Unfortunately, it has been given a “Tombstone notice”, which means it will not progress. The reason for this is that it adds a PQC key — no matter if the host actually wants (or uses) it. Along with this, it does not give a mechanism for coping with two signatures on a method (with a traditional one and a PQC one), and where it is not possible to detect where one of the signatures has been removed — a stripping attack.

Public key sizes for Dilithum

Like it or not, the days of small public key sizes are coming to an end. In ECC, for NIST P256, we have a 32-byte (256 bit) private key, and a 64-byte (512-bit) public key. For Ed25519, we use Curve 25519, and which reduces the public key to ust 32 bytes (256 bits).

For RSA 2K, we have a 256-byte private key (2,048 bits), and a 256-byte public key (2,048 bits). The equivalent security for Dililithum is Dililithum2, and which gives a much larger private key of 2,528 bytes (20,224 bits) and a public key of 1,312 bytes (10,496 bits). The Dilithium public key is thus over 20 times larger than the ECC key. This could be a major overhead in communication systems, and where more than one data packet would have to be sent in order to transmit the public key.

Method                           Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium 2 (Lattice)        1,312              2,528              2,420         1 (128-bit) Lattice
Crystals Dilithium 3                  1,952              4,000              3,293         3 (192-bit) Lattice
Crystals Dilithium 5                  2,592              4,864              4,595         5 (256-bit) Lattice
Falcon 512 (Lattice)                    897              1,281                690         1 (128-bit) Lattice
Falcon 1024                           1,793              2,305              1,330         5 (256-bit) Lattice
Sphincs SHA256-128f Simple               32                 64             17,088         1 (128-bit) Hash-based
Sphincs SHA256-192f Simple               48                 96             35,664         3 (192-bit) Hash-based
Sphincs SHA256-256f Simple               64                128             49,856         5 (256-bit) Hash-based
RSA-2048                                256                256                256
ECC 256-bit                              64                 32                256

A hybrid scheme is defined here:

https://asecuritysite.com/pqc/circl_dil2

For our existing signatures, we have:

Method        Public key size (B) Private key size (B)  Signature size (B)  Security level
------------------------------------------------------------------------------------------------------
Ed25519       32                  32                    64                  1 (128-bit) EdDSA
Ed448         57                  57                   112                  3 (192-bit) EdDSA
ECDSA         64                  32                    48                  1 (128-bit) ECDSA
RSA-2048     256                 256                   256                  1 (128-bit) RSA

And in using a hybrid approach, we increase the signature size of 64 bytes or Ed25519 to 2,484 bytes — a 38-fold increase in size:

Method                           Public key size    Private key size   Signature size  Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium2-X25519           2,560              1,344              2,484         1 (128-bit) Lattice
Crystals Dilithium3-X25519           4,057              2,009              3,407         3 (192-bit) Lattice
Crystals Dilithium 2 (Lattice)        1,312              2,528              2,420         1 (128-bit) Lattice
Crystals Dilithium 3                  1,952              4,000              3,293         3 (192-bit) Lattice
Crystals Dilithium 5                  2,592              4,864              4,595         5 (256-bit) Lattice
Falcon 512 (Lattice)                    897              1,281                690         1 (128-bit) Lattice
Falcon 1024                           1,793              2,305              1,330         5 (256-bit) Lattice
Sphincs SHA256-128f Simple               32                 64             17,088         1 (128-bit) Hash-based
Sphincs SHA256-192f Simple               48                 96             35,664         3 (192-bit) Hash-based
Sphincs SHA256-256f Simple               64                128             49,856         5 (256-bit) Hash-based

And, so, what about using SPHINCS+? That has a 32-byte public key. The downside is that Sphincs SHA256–128f requires a 17,088-byte signature. This would also overload the communication channel and require over 11 packets to send a single signature to prove the identity of a Web site. It is highly unlikely that SPHINCS+ will be used to replace RSA and ECC signatures in ECDH, but where it would be used in applications that did not have a communications channel.

Conclusions

And, so, the double public key draft has been sent back, and we are awaiting the next iteration.

Learn more about PQC here:

https://asecuritysite.com/pqc