Bill Buchanan - PQC Gets A Tombstone Notice ASecuritySite Podcast

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 fo