Post-Quantum Session Key Management

With the impending arrival of quantum computers expected within the next 5 to 8 years, the way cryptographic key management is to be designed today needs rethinking. 

Problem

Any new project being developed today (assuming a 2 year rollout), and then running in production for at least 7-8 years will certainly face the threat of quantum computers during the lifetime of the project. If classical public key management techniques, say using RSA to distribute session keys, are used, then such projects are likely to see a major upgrade during the useful life of the project or worse still, be forced to be decommissioned earlier than expected. On the other hand, waiting for the new NIST PQC FIPS-203 ML-KEM (Kyber) algorithm to be standardized and be widely available for use in most applications may require projects to postpone their rollouts by another 1 to 2 more years.

A more straight-forward quantum-safe session key management using symmetric cryptographic techniques already exists and has been used for decades (for example in  deterministic generation in RFC4226, session key derivation in EMV). It is a combination of AES and SHA algorithms, both of which are quantum-safe when keys of sufficient sizes are used. The recommended minimum values for NIST Quantum Security Level 1 are AES-256 and SHA256.

Solution

To understand symmetric session key management, let's envision a hub-and-spoke model where the central "hub" is responsible to generating and injecting keys to the "spoke" devices. All secured communications between "spokes" are required to go through the "hub" which is responsible for processing and translating the messages accordingly.

The key preparation/provisioning process is as follows:

• Hub generates a master key MK which needs to be kept secret, preferably in a Hardware Security Module (HSM).
• Each spoke has a unique identifier, id, which can be publicly know. This ID should be of sufficient length, e.g. 16-20 digits.
• Hub computes each spoke's device key as follows DK_id = SHA256(id,salt). where id represents the spoke's unique identifier, salt represents a stored random generated by the hub, and SHA256() represents the SHA256 hash function. Once generated, the DK_id is injected into the spoke device and never stored in the Hub.
• Note that the process of injecting DK_id into the spoke devices needs to be secured (e.g. via physical means), and hence is suitable if the Hub operates as a central issuance body.

When Hub requires to communicate with Spoke A, the following happens

• Hub generates a random session key SK, and uses the session key to encrypt the message, e.g. EncMsg = AES256_enc(Msg,SK) where AES256_enc() represents the AES256 encrypt function. 
• Hub computes Spoke A's device key using DK_A = SHA256(A,salt), and uses the device key to encrypt the session key, i.e. EncSK = AES256_enc(SK,DK_A).
• Hub transmits EncSK and EncMsg to Spoke A which can decrypt the message by first computing SK = AES256_dec(EncSK,DK_A), and then Msg = AES256_dec(EncMsg,SK). AES256_dec() represents the AES256 decrypt function.
• The communication from spoke to hub works similarly in reverse.

To extend the system to support spoke-to-spoke communications (e.g. between Spoke A and Spoke B), the hub requires to include a translate operation which will has modify EncSK as follows, EncSK_toB = AES256_enc(AES256_dec(EncSK_fromA,DK_A),DK_B)

Security extensions

What I've described above is a basic architecture for a symmetric key hierarchy which should be extended to enhance security. These include 

• Scope-limiting the master key. Instead of 1 master key, multiple master keys can be generated and used under different situations to achieve key rotations, key expiry, etc.
• Scope-limiting the device key. Use of different salts for different situations will achieve similar outcomes for multiple device keys.
• Changing the hash function to SHA512 instead of SHA256 to increase the key-space complexity
•  As the security of the overall system is highly dependent on the protection of the master key during storage and processing, the use of HSMs at the hub is crucial.

Conclusion

While quantum computers can threaten cryptographic security, there are already well-tested and well-used techniques that will not cost huge amounts of resources to still remain secure over the long term. The smart use of symmetric key and hashing techniques is one such example.

Do contact us at pQCee if you want to know more.