[CFRG] Re: [EXTERNAL] Re: ML-KEM side channels and NoIC / OQUAKE

["Samuel Lee (ENS/Crypto)" <[e-mail]>]

I have no context on PAKE or NoIC / OQUAKE before reading this message, but encrypting a public key material with a low entropy secret (password) seems to be a bad idea independently of the specifics of ML-KEM.
There should not be specific handling of parts of public key material in a protocol to make provisions for what may be variable time or not - public keys should be considered public.

It is entirely natural to treat public keys as public data when implementing a cryptographic library, and to introduce variable timing w.r.t. the public key as a result.
Public key import / Encaps should not be considered to be constant time w.r.t. the value of the public key in KEMs.

Similarly, keypair generation should be expected to be variable time w.r.t. the public key.
This kind of trivially falls out of variable time encapsulation if the context where a library might be forced to check that a generated keypair is consistent (see pairwise consistency tests).


Specifically for ML-KEM, I don't see why Tempo is a full fix for the issue, as I don't see why you should expect Encaps to be constant time w.r.t. t.
FIPS 203 requires that there is a Modulus check on t before operational encapsulation, which would naturally be constant time for valid t (all coefficients are mod Q) and variable time for invalid inputs (at least one coefficient is not in the correct range).


What is the value of encrypting the public key with a key derived from the password in the protocol?
Is there a reason why OQUAKE/etc. cannot be defined s.t. the KEM's public key transmitted in the clear, and the shared secret produced by encapsulation is mixed with the password with an appropriate KDF for both password and public key confirmation?

Best,
Sam


________________________________
From: Christopher Wood <[e-mail]>
Sent: 31 October 2025 10:41
To: Watson Ladd <[e-mail]>
Cc: CFRG <[e-mail]>
Subject: [EXTERNAL] [CFRG] Re: ML-KEM side channels and NoIC / OQUAKE



On Oct 31, 2025, at 11:56 AM, Watson Ladd <[e-mail]> wrote:




On Fri, Oct 31, 2025, 8:10 AM Christopher Wood <[e-mail]<mailto:[e-mail]>> wrote:
Hi folks,

TL;DR: NoIC / OQUAKE [1,2] admit timing-based dictionary attacks on the password due to how ML-KEM is specified and implemented in practice. There exists a proposal which slightly alters NoIC / OQUAKE to hedge against known-bad timing side channels [3], but it slightly modifies the KEM abstraction. Nevertheless, it seems like the best option to address the problem.

To elaborate, NoIC / OQUAKE are subject to a timing attack due to how the ML-KEM expands the key-generation seed (rho) to a matrix (A). An internal function — SampleNTT — uses rejection sampling based on the seed and therefore is variable time. In NoIC / OQUAKE, after a sender password-encrypts a public key, an attacker can perform an offline dictionary attack based on this key in the following way:

1. Password-decrypt the authenticated public key using a candidate password.
2. Time the seed-to-matrix expansion step using this candidate public key and compare it against the known timing target.

This is shown in [4]. One way to fix this side channel is to make SampleNTT constant-time, but it’s not clear if that’s necessary or sufficient for security against variable-time implementations of ML-KEM.

Taking a step back, the core problem is that variable-time functions inside ML-KEM can be exploited to leak information about the password. For example, consider the key generation function (Algorithm 13, FIPS203) inside ML-KEM. The step to compute tHat (18) depends on the matrix A (5), which depends on the seed rho (1). With a candidate rho, an attacker can compute the seed-to-matrix expansion function and perform a dictionary attack. Even if SampleNTT was constant-time, it might be possible that the Matrix-vector multiplication in computing tHat leaked information.

There are also possible functions that exist in the encapsulation phase (Algorithm 14, FIPS203). Specifically, the inverse NTT function involves modular reduction which could be variable-length time if implemented incorrectly. Thus, even with a constant-time SampleNTT implementation, if an attacker can time encapsulation — including step 21 in encapsulation — it may be possible to learn information about whether the public key is correct.

There are several mitigations to this problem, each with different tradeoffs. These are discussed below.

1. Acknowledge and live with the timing side channels. In this approach, NoIC / OQUAKE would simply acknowledges that these timing side channels and the dictionary attack exist, rendering NoIC / OQUAKE insecure in situations where key generation or encapsulation timing information is available to the attacker. This is minimally invasize to the protocol and specification, but seems quite fragile. Deployments would need to determine if timing side channels exist in their use case (almost certainly they do) and take steps to address them.

2. Require all functions to be constant-time, including SampleNTT in ML-KEM. In this approach, we simply demand that all functions are implemented in constant-time, regardless of what FIPS203 says. This would "address" all timing side channels, but would require a change to ML-KEM implementations. This could be problematic for some implementations, especially those which are already formally verified. Moreover, it’s infeasible to determine (at the API level) if an implementation is constant-time, so someone implementing NoIC / OQUAKE might not know if their implementation meets this criteria.

3. Induce protocol changes to address the known-bad SampleNTT side channel, and require all other functions to be constant-time. In this approach, we introduce a protocol-level change (that amounts to a different type of public key encoding for ML-KEM) that works around the variable-time SampleNTT function, while also requiring all other functions to be constant time for completeness. This change is described in [3], and has the benefit of addressing all timing side channels without requiring FIPS203 changes. However, it does introduce a non-standard ML-KEM public key encoding that is different from what is specified in FIPS203. This might not be available in all cryptographic libraries, but where it is present we know that the implementation is suitable to address the timing side channel in SampleNTT.

The paper also describes an option 4 of transmitting the seed in the clear and only encrypting the other parts of the public key. I think that's worth consideration also, since it's a simpler code change than modifying ML-KEM.

To be clear, this is option (3), i.e., Tempo with a splittable KEM.

Best,
Chris




Option (3) seems like the best here, all things considered. We'll talk about this next week, but are keen to know if folks have strong opinions on the desired outcome before then as well.

Best,
Chris

[1] https://eprint.iacr.org/2025/231
[2] https://datatracker.ietf.org/doc/html/draft-vos-cfrg-pqpake-00
[3] https://eprint.iacr.org/2025/1399
[4] https://gist.github.com/chris-wood/95474276035cfbb4b4c43895d114223f
_______________________________________________
CFRG mailing list -- [e-mail]<mailto:[e-mail]>
To unsubscribe send an email to [e-mail]<mailto:[e-mail]>