IND-CCA2 issue in HQC (latest version)

[Markku-Juhani O. Saarinen]

Hi,

I was looking at the latest specification of HQC from February 2025 [HQC]. The specification claims IND-CCA2 security by instantiating a [HHK17] - style implicit-rejection Fujisaki-Okamoto transform -- see  Section 1.4. and 5.2 of [HQC].

I have some notes about this.

1. Firstly, on the implementation level, the code does not try to do implicit rejection but offers an explicit true/fail return code on decryption failure. Application code could of course choose to ignore this "oracle" --- but it's not in the spec and the behavior differs from, say, most ML-KEM code that implements same type of FO transform. Here's the relevant line in the PQClean codebase -- same can be found in the latest reference implementation:
https://github.com/PQClean/PQClean/blob/448c71a8f590343e681d0d0cec94f29947b0ff18/crypto_kem/hqc-128/clean/kem.c#L137


2. The FO transform itself appears to have been instantiated a bit badly in HQC.KEM:

There is one crucial difference in how the same [HHK17] transform is implemented in HQC compared to ML-KEM -- the use of "salt," which appears to be a late-stage addition to the scheme (Sect 1.5 [HQC]).

Turning the "salt" ciphertext component into a two-query decryption failure oracle is trivial, and I've tested this against the reference code:

Figure 3 in the [HQC] serves as the main description of HQC.KEM in the spec. Confusingly, "salt" in that pseudocode is a separate value, but it is a part of the ciphertext as noted elsewhere in the spec.

Here's my high-level description of HQC.KEM Encapsulation and Decapsulation. I've split it into discrete steps and abstracted out the "PKE" functions. Below G and K are hash functions (built from SHAKE256 with a domain separator byte.)

HQC KEM Encaps(pk) function:
e1. Pick a random {16,24,32}-byte random message "m"
e2. Pick a random 16-byte "salt"
e3. Compute encryption seed: theta <- G( m | pk[:32] | salt )
e4. "PKE" Encrypt: c = (u,v) <- Encrypt(m, theta, pk)
e5. Ciphertext is:  ct = c | salt
e6. Shared secret is:  ss <- K( m | c )

HQC KEM Decaps(ct, sk):
d1. Unpack ciphertext: (u, v, salt) <- ct. We write c = (u,v)
d2. Unpack secret key: (sk_seed, sigma, pk) <- sk
d3. "PKE" Decrypt: m' <- Decrypt( c, sk_seed )
d4. Compute theta' <- G( m' | pk[:32] | salt )
d5. FO Re-encryption: c' = (u',v') <- Encrypt(m', theta', pk)
d6. If c != c' then return ss <- K( sigma | c )
d7. else return ss <- K( m | c )

Observations:
- Full ciphertext ct is not used to compute shared secret ss in steps e6 and d7, just the c = (u | v) component.
- In step d6, the comparison does not include the full ciphertext. It is not ct == ct'  but just c == c', missing salt from ct = c | salt

So, here's the two-query decryption failure oracle:

In the CCA "game," the adversary can do two decapsulation queries, one with ct and a second with ct', where only the "salt" value has been changed. You can, for example, flip the last bit of ciphertext ct and use that as ct' as the salt is in the end.

Now, if Decaps(ct) = Decaps(ct') i.e. ss == ss', then the adversary learns that decryption failed for ct for sure: The PKE decryption step (d3) will yield the same result m' for both ct and ct'. The re-encryption will surely fail for ct' as a different theta value is computed. If the shared secret computations match ss==ss', then re-encryption failed for ct too.

Conversely, if Decaps(ct) != Decaps(ct') i.e. ss != ss', then ct was a valid ciphertext.

One of the implications is that the "sigma" part (equivalent to "z" in ML-KEM) of the current HQC secret key serves no meaningful purpose as far as I can see.

This is easy to fix just by treating "salt" as a part of the ciphertext -- since it is a part of the ciphertext.

As noted, I've tested this against the reference code as well. In code, the u and v components of PKE ciphertext are compared here:
https://github.com/PQClean/PQClean/blob/448c71a8f590343e681d0d0cec94f29947b0ff18/crypto_kem/hqc-128/clean/kem.c#L121

References:

[HQC] (HQC Team.) "Hamming Quasi-Cyclic (HQC)."
Fourth round version. Updated version 19/02/2025
https://pqc-hqc.org/doc/hqc-specification_2025-02-19.pdf

[HHK17] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz.
"A modular analysis of the Fujisaki-Okamoto transformation." TCC 2017
https://eprint.iacr.org/2017/604
https://doi.org/10.1007/978-3-319-70500-2_12

Cheers,

-markku

[Sophie Schmieg]

Nice find! Shouldn't the salt be derived from the message as well, to get a proper FO transform? I don't quite see a vulnerability if that isn't the case (as long as the salt is included in the ciphertext check, as you point out), but it seems strange that the adversary would be able to pick any salt with the message, given the idea behind the FO transform being that the encapsulator is unable to make any meaningful choice.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/aad21773-df97-4d86-a28b-522bbfadf521n%40list.nist.gov.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[Kathrin Hövelmanns]

Hi Sophie,

the salt doesn't necessarily have to be tied to the message (see eprint 2025/343, Fig. 8/9). I view it as a tool to artificially scale up the message space to prevent multi-challenge attacks (by increasing a random oracle search space).

Best,

Kathrin

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAEEbLAZSkM_uD%3DbA3iTa8M%3DBU5GhPDQxcwVObSW4TtOzq89Zxw%40mail.gmail.com.

[Sophie Schmieg]

Ah, neat, thanks for the reply and the reference. I guess you could consider it as part of the message, encrypted with the null cipher, right?

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/34e1939b-879e-47c6-9ed1-8e756a764d7a%40tue.nl.

[Markku-Juhani O. Saarinen]

Hi Sophie (and Kathrin),

Yes both the message and salt are picked at random in encapsulation (steps e1 and e2 below), but salt is tacked at the end of ciphertext as-is (step e5). 

So I guess one could say "null cipher".. sounds more sensible than "plaintext part of ciphertext" !  I can see that without the salt, and with the message being exactly at the security level there would be some minor shortcut attacks. I guess transmitting the salt like that is more economical than increasing the message size due to the massive expansion / redundancy required by the heavy-duty error correction codes.

Anyway to recap what I was suggesting: The salt does not affect decryption of m (d3), but affects its re-encryption outcome (d5) via theta, (d4).

So the re-encryption ciphertext check (d6) should be ct == ct'  rather than just  c == c'  which lacks the salt..

Also one probably should include full ct (including salt) in shared secret computation (e6, d6, d7) in all cases; ss = K( m | ct ) in encapsulation (e6) and successful decapsulation (d7 should have m'), or  ss= K( sigma | ct ) in case of decapsulation failure (d6).

Since the salt is is only 16 bytes, with any luck lengthening the hashes won't cause an extra Keccak permutation call and the performance impact is negligible.

ps. Table 7 ciphertext sizes in [HQC] are seemingly 64 bytes "too big", and don't match with the reference implementation. The secret key encoding used in that table doesn't match with the reference implementation either, but yes everything can be expanded from a seed.

Cheers,

-markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAEEbLAbO0j%3DC9ncHBiPBG7Cx3NcG4nUh59ykg5s9Wg_okUVk4A%40mail.gmail.com.

[Philippe Gaborit]

Hi Markku,

thank you for your remarks, we were already looking at this type of modification

and will propose a modification shortly,

thanks,

best,

philippe for the HQC team

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_q%3DmJE3XsT-bXGc2nE4iSxQJfVTmv0B9WCh035ujfAwuyQ%40mail.gmail.com.