Entity authentication with a KEM

In cryptography, the process of authenticating a user (or app/service) is known as entity authentication or identification (to distinguish it from message authentication or data origin authentication). There are lots of ways to do this. In this post I’m going to talk about authentication schemes based on public key cryptography. It turns out that the notion of Key Encapsulation Mechanism (KEM), originally invented for (unauthenticated) public key encryption, also provides a unifying framework for thinking about public key entity authentication.

As a dedicated reader of this blog, you will of course recall that a KEM is a nice way of describing public key hybrid encryption algorithms: i.e., those involving a combination of public key and secret key cryptography. A KEM provides two operations:

• The encapsulate operation takes the recipient’s public key and returns a fresh symmetric data encryption key (DEK), along with an encapsulation of that key. You use the DEK to encrypt the message body (using something like AES-GCM) and then send the resulting ciphertext along with the encapsulation to the recipient.
• The recipient then takes the encapsulated key and runs the KEM’s decapsulate operation with their private key to recover the original DEK, which they then use to decrypt the rest of the message.

It turns out that we can also use this interface to authenticate a user using a challenge-response protocol. I’m sure this is well-known amongst cryptographers, but it was a real “aha!” moment for me when I first realised it. The process goes like this:

1. Alice wants to log into our website, where she already has an account. She sends her username “alice” to the site.
2. The website looks up Alice in the user database and finds her associated public key (or generates a random one if she doesn’t exist, to prevent account enumeration).
3. The website runs the KEM encapsulate operation with Alice’s public key. It stores the secret key somewhere safe (e.g. encrypted in a cookie) and sends the encapsulation to Alice as a challenge.
4. Alice runs the KEM decapsulate operation with her private key and the challenge to recover the secret key.
5. Alice then sends the secret key to the website as the response. (Or uses it as a HMAC key to sign some response message, but for now we’ll keep it simples).
6. The website compares the secret key sent by Alice to the one it stored in step 3: if they are the same (compared in constant time, naturally) then authentication succeeds.

Let’s see how this pans out when we plug in concrete KEM implementations into this scheme:

RSA-KEM

In RSA-KEM, the encapsulate method generates a random value and encrypts it with the RSA public key (please see my original article for the details). The secret key is then derived by running this random value through a key derivation function (KDF). In the context of our authentication process, this will result in Alice being challenged to decrypt a random value encrypted under her public key. This is a classic way to authenticate using RSA, for example listed as the very first method in section 10.3.3 of the classic Handbook of Applied Cryptography (pdf link).

DH-KEM

When we look at DH-KEM, which is based on Diffie-Hellman (DH) key agreement (or its Elliptic Curve equivalent), the encapsulate method works like the following:

• First a random ephemeral key-pair is generated. The ephemeral public key becomes the encapsulation value.
• The KEM then computes a DH key agreement between the recipient’s public key and the ephemeral private key to generate a shared secret. This shared secret is then passed through a KDF to generate the final secret DEK.

The decapsulate method then decodes the encapsulated value to recover the ephemeral public key and performs a DH between that and the recipient’s private key to recover the same shared secret.

In the context of our authentication scheme, this KEM performs an ephemeral-static DH key agreement which is another well-known method of authentication. This is, for example, used to provide recipient authentication in the Noise protocol framework and in Signal’s X3DH.

Note that in this scheme, nothing actually gets encrypted at all!

Summary

In general, any secure KEM will be a secure entity authentication mechanism when using this generic scheme. This security of these authentication methods both depend on the KEM encryption scheme being secure against chosen ciphertext attacks (IND-CCA), which is the security goal required of a KEM in the first place.

I find it fascinating that an abstraction that was introduced to unify different hybrid encryption schemes also turns out to be a great abstraction for describing challenge-response authentication schemes, some of which involve no encryption at all.

If you want to learn more about KEMs and all the things they are useful for, check out my three-part series:

• Hybrid encryption and the KEM/DEM paradigm
• When a KEM is not enough
• From KEMs to protocols

I’m also available to hire for all your authentication needs.