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 65P384_HKDF_SHA384 97 48 97P521_HKDF_SHA512 133 66 133X25519_HKDF_SHA256 32 32 32X448_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 768Kyber738 1,184 2,400 1,088Kyber1024 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): C0B27940D588EE1D0F8348F169BA04A48E0E7FA7DE5B8A091D5D1B59E70D577EEAC4180B076595B2EFCCE96E2271EEA3B20228FC3FD5B63114D32E9D20D9A2F2Shared key (Alice): C0B27940D588EE1D0F8348F169BA04A48E0E7FA7DE5B8A091D5D1B59E70D577EEAC4180B076595B2EFCCE96E2271EEA3B20228FC3FD5B63114D32E9D20D9A2F2Length of Public Key (pk) = 832 bytes Length of Secret Key (sk) = 1664 bytesLength 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) LatticeCrystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) LatticeCrystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) LatticeFalcon 512 (Lattice) 897 1,281 690 1 (128-bit) LatticeFalcon 1024 1,793 2,305 1,330 5 (256-bit) LatticeSphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-basedSphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-basedSphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-basedRSA-2048 256 256 256ECC 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) EdDSAEd448 57 57 112 3 (192-bit) EdDSAECDSA 64 32 48 1 (128-bit) ECDSARSA-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) LatticeCrystals Dilithium3-X25519 4,057 2,009 3,407 3 (192-bit) LatticeCrystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) LatticeCrystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) LatticeCrystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) LatticeFalcon 512 (Lattice) 897 1,281 690 1 (128-bit) LatticeFalcon 1024 1,793 2,305 1,330 5 (256-bit) LatticeSphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-basedSphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-basedSphincs 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