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

[Sophie Schmieg <[e-mail]>]

I think this points to a flaw within OQUAKE more than anything: the draft
RFC currently only requires that the public key is uniformly random, but
not that it is impossible to reconstruct a public key from a known valid
ciphertext. None of the definitions of a KEM implies that the public key is
secret, and not, well, public (in fact, for signature schemes, it is often
possible to compute the public key from valid signatures, see [1]). It
seems to me that this construction fundamentally requires properties beyond
the ones listed in the draft, and this problem is just one manifestation of
this problem.

Note that ML-KEM is already not a BUKEM, so you already cannot use standard
ML-KEM implementations with OQUAKE as is, so I don't think this has a lot
of consequences for timing side channels in ML-KEM implementations not
specifically written for OQUAKE. But importantly, the spec needs to give a
proper security model that BUKEMs require, or for the very least state that
the public key is indistinguishable for uniform random *in the presence of
ciphertext*.

[1]
https://keymaterial.net/2024/06/15/reconstructing-public-keys-from-signatures/

On Fri, Oct 31, 2025 at 2:18 PM Samuel Lee (ENS/Crypto) <Samuel.Lee=
[e-mail]> wrote:

> 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]>
> 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]
> To unsubscribe send an email to [e-mail]
>
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>


-- 

Sophie Schmieg | Information Security Engineer | ISE Crypto |
[e-mail]