Round 3 (Additional Signatures) OFFICIAL COMMENT: SDitH, MQOM

[Demi Marie Obenour]

The security proofs of SDitH and MQOM assume the ideal cipher model.
However, this model is questionable for the cipher chosen.

Specifically, AES-192 and AES-256 are vulnerable to related-key attacks.
While I'm not aware of attacks on Rijndael-256, I think assuming that
it is safe against such attacks is not a conservative assumption.
Therefore, I recommend adjusting the proof (and possibly design)
to make more conservative assumptions about the cipher used, or to
specify the exact construction in which AES/Rijndael is used.

Additionally, instead of using Rijndael-256 with a padded key and
truncated output, Rijndael-192 might be a better choice.

These recommendations are precautionary, not a response to a
particular attack. Another option would be to adopt a different
symmetric algorithm that is a better fit for the purpose.
--
Sincerely,
Demi Marie Obenour (she/her/hers)

[John Mattsson]

Hi,

I agree with this comment. Beyond the related-key attacks on AES-192 and AES-256, Biryukov, Khovratovich, and Nikolić presented an efficient chosen-key distinguisher for AES-256 (CRYPTO 2009), concluding that “AES-256 can not model an ideal cipher in theoretical constructions.” Gilbert later presented a known-key distinguisher for the full AES-128 (ASIACRYPT 2014).

Thus, all three AES variants can be distinguished from an ideal block cipher, and assuming that Rijndael-256-256 behaves like an ideal cipher does seem conservative or even likely. That said, SDitH and MQOM do not seem to require Rijndael-256-256 to fully behave as an ideal cipher. The design teams should therefore state the concrete cryptographic properties they actually require, rather than relying on an all-encompassing ideal-cipher assumption. Cryptanalysts could then target those properties directly.

More cryptanalytic work on Rijndael-256-256 in general would also be welcome since 3GPP has standardized it for use in MILENAGE-256 and NIST is planning to standardize it for general-purpose use.

Cheers,

John Preuß Mattsson

--

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/3510d6df-db09-42c3-a782-a62cf7f982a6%40gmail.com.

[Matthieu Rivain]

Dear Demi and John,

Thank you for your comments, which raise a pertinent point regarding the reliance of MQOM and SDitH on the Ideal Cipher Model (ICM). 

Note that this response also applies to the following thread, which raises essentially the same points: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/tUr40RgE32w/m/rYoHnHHeFQAJ

I will first discuss this reliance in general terms in the context of the EUF-CMA security of MQOM and SDitH, before turning to the specific points raised in your e-mails.

AES and Rijndael are not ideal ciphers, just as SHA-2 and SHA-3 are not random oracles, and yet proofs in the random oracle model with SHA-2 or SHA-3 instantiations are standard practice. What a proof in the ICM establishes is security against attacks that treat the cipher as a black box. Any attack must therefore exploit structural properties of AES or Rijndael specifically. That is a meaningful guarantee, and it also tells us where to look: the question becomes whether any known structural property of these ciphers yields the preimages, collisions or biases that our assumptions rule out.

More importantly, in several parts of the EUF-CMA security analysis of MQOM and SDitH, reliance on the ICM can be relaxed to non-idealized assumptions on AES-128 and Rijndael-256-256. Let me elaborate on what those assumptions are.

In both schemes (as in FAEST), the block cipher essentially serves three functionalities:

  (1) deriving the seeds of the GGM tree;

  (2) expanding the leaf seeds into randomness;

  (3) committing to the leaf seeds.

1. SEED DERIVATION AND EXPANSION IN SDitH

For SDitH, a fairly standard pseudorandomness assumption suffices. At category 1 (as for FAEST), that assumption is pseudorandomness of AES-128 keyed by the secret seed and evaluated on public, domain-separated inputs, which is about as standard as one can ask for. At categories 3 and 5, SDitH uses Rijndael-256-256 (with zero-padding for category 3) rather than AES with its 128-bit block. So the same standard assumption, with (zero-padded) Rijndael-256-256 instead of AES-128.

2. SEED DERIVATION AND EXPANSION IN MQOM

MQOM uses the block cipher differently and derives sibling seeds through a correlation, so its replacement assumptions are less standard. Concretely, MQOM places the secret seed not in the key field but in the plaintext field, with a Davies-Meyer-style feed-forward through an F2-linear orthomorphism ψ.

The correlated-tree variant introduces a correlation in the GGM tree that makes the analysis more involved. It is treated in

  https://eprint.iacr.org/2026/615.pdf   (to appear at ASIACRYPT 2026)

Dispensing with the ICM in this analysis essentially amounts to assuming the hardness of distinguishing the output of the "correlated tree oracle" (Figure 4) from uniform, with the functions H^tree, H^com and H^rnd instantiated by the "enhanced Davies-Meyer construction" of Section 4.6, adopted in MQOM v3. 

A non-idealized formulation would reduce to a tweakable circular correlation robustness (TCCR) assumption on E_t(·) ⊕ ψ(·), in the sense of Guo, Katz, Wang and Yu (IEEE S&P 2020, https://eprint.iacr.org/2019/074), for which the secret offset corresponds to the first λ bits of the MQ solution (this is called "TCCR with one-wayness" in https://eprint.iacr.org/2026/629.pdf). This is where we need the PGOW-MQ assumption, a partial-recovery problem associated with MQ, which we believe to be essentially as hard as MQ (see analysis in the MQOM v3 specification). 

Disregarding the hint on the secret offset provided by the underlying MQ instance, TCCR is then the only assumption concerning the cipher. A concrete attack on it would have to exploit a structural weakness of AES-128 or Rijndael-256-256 in the function

    seed -> E_{t_i}(seed) ⊕ ψ(seed)

(for t_i a tweaked salt of the form t_i = salt || i), such as a joint relation among outputs under different tweaked salts or correlated inputs, or some way to invert the function. To the best of our knowledge, no such structural weakness is known for AES-128 or Rijndael-256-256.

MQOM v3 also provides a variant based on the one-tree technique (Baum et al., ASIACRYPT 2024, https://eprint.iacr.org/2024/490) used by SDitH and FAEST, which avoids both PGOW-MQ and the correlated tree oracle analysis. It still builds the tree as a half-tree, so the TCCR assumption above is the only one that remains, with the same concrete attack paths. A plain GGM construction would remove the half-tree correlation-robustness requirement, leaving a conventional PRG requirement for the underlying seed-expansion function.

3. LEAF SEED COMMITMENTS

The seed commitment function is defined as

    seed -> E_seed(t_i) || E_seed(t_j)

in SDitH, and

    seed -> (E_{t_i}(seed) ⊕ ψ(seed)) || (E_{t_j}(seed) ⊕ ψ(seed))

in MQOM, where t_i = salt || i and t_j = salt || j, for i != j.

The EUF-KO to EUF-CMA reduction (using the ZK simulator to simulate signatures) requires a joint pseudorandomness assumption covering the commitment and the other values derived from the same hidden seed. For MQOM this is already captured by the correlated tree oracle analysis.

Binding, required in the EUF-KO reduction, is where the ICM is most convenient: it gives straight-line extraction of the witness, which keeps the reduction simple. 

In a classical ROM analysis, rewinding offers a possible alternative to straight-line extraction, allowing a simple collision-resistant assumption on the commitment function, at the cost of lossiness in the reduction (the standard loss due to the forking lemma).

In the quantum setting, one possible way would be to assume an appropriate straight-line extractability property for the commitment scheme, which would provide the extractor with the committed seeds without rewinding. Alternatively, one may seek to rely on a non-idealized computational assumption on the concrete commitment function, such as the almost-injective PRG assumption used in the analysis of FAEST-EM. This assumption states that it is hard to produce a commitment value admitting two distinct seed openings, even without exhibiting those openings. Adapting such an approach to MQOM or SDitH may require some modifications to the proof, or to the scheme itself.

4. GRINDING

For completeness, there is one use of the ICM in MQOM and SDitH that is not of this kind: the cipher-based grinding in the Fiat-Shamir challenge derivation (as a variant for SDitH), where the model is used to lower-bound the work per forgery attempt. To beat this lower bound, an attacker would typically need either to compute a certain number of output bits of the function

  nonce -> E_{k0}(pref0 || nonce) ⊕ E_{k1}(pref1 || nonce)

more cheaply than by evaluating it, or to exhibit a bias in those bits over the nonce space, which would yield a zero in fewer trials than exhaustive search. Here, k0, k1, pref0, pref1 are fixed (derived from the hashed transcript), and nonce lies in {0,1}^32. Again, we are not aware of any structural weakness in AES-128 or Rijndael-256-256 that would make either of these possible.

5. RESPONSE TO SPECIFIC POINTS

Here are some responses to specific points raised in your e-mails:

    "SDitH at level III uses a Rijndael-256 key with 64 zero bits"

In both MQOM and SDitH, the 192-bit secret seed is zero-padded to 256 bits when input to Rijndael-256-256 (in the key field in SDitH and the plaintext field in MQOM). Zero padding does not reduce the seed's 192 bits of entropy but the concrete security assumption concerns Rijndael-256-256 restricted to precisely this key/input space.

    "both SDitH and MQOM use keys that are not indistinguishable from random"

The ICM does not assume uniform keys: it gives an independent random permutation for every key, and the adversary may query any key it likes, related ones included. Nonuniformity of the key distribution is hence not a violation of the ICM. The proof accounts for the actual distributions, correlations, and repeated uses of keys and inputs.

    "Would a cipher designed to protect against related key attacks be a more conservative choice?"

While resistance to related-key attacks is relevant, it is neither sufficient nor directly equivalent to the properties we require. A more conservative replacement would need to be evaluated against these actual security assumptions. Analysis targeting the specific assumptions we make about AES-128 and Rijndael-256-256 in our schemes would be very welcome.

    "Additionally, instead of using Rijndael-256 with a padded key and truncated output, Rijndael-192 might be a better choice."

We deliberately chose to rely only on Rijndael-256-256, rather than introducing Rijndael-192 as an additional primitive. The goal was to limit the attack surface and the number of AES/Rijndael variants on which the security of the schemes depends. This choice is also consistent with NIST's announced interest in standardizing a wider-block variant of AES based on Rijndael-256: https://csrc.nist.gov/news/2024/nist-proposes-to-standardize-wider-variant-of-aes

    "Another option would be to adopt a different symmetric algorithm that is a better fit for the purpose."

An important consideration is implementation. AES has the broadest hardware support of any symmetric primitive at industrial scale, through the AES instructions of x86 (AES-NI) and ARMv8, and Rijndael-256-256 can be built from those same instructions. Since the symmetric primitive dominates signing and verification time in these schemes, that support is much of what makes them competitive. 

All the best,

Matthieu, on behalf of the SDitH and MQOM teams

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/AS4PR07MB8825C6DC050C651086F9A9EC89962%40AS4PR07MB8825.eurprd07.prod.outlook.com.

[John Mattsson]

Hi Matthieu,

Thanks for your detailed answers.

Matthieu Rivain wrote:

>AES and Rijndael are not ideal ciphers, just as SHA-2 and SHA-3 are not random oracles, and yet proofs in the random oracle model with SHA-2 or SHA-3 instantiations are standard practice

I think the situation with SHA-2, SHA-3, and AES/Rijndael is quite different:

SHA-3: There are no known attacks distinguishing SHA-3 from a random oracle. I therefore think it is perfectly reasonable to model SHA-3 as a random oracle.

SHA-2: There are trivial distinguishing attacks. Moreover, assuming that SHA-2 behaves like a random oracle has led to vulnerabilities in SPHINCS+ [1]. I therefore do not think it is appropriate to model SHA-2 as a random oracle, and I think SHA-2 should be phased out.

AES/Rijndael: There are known attacks distinguishing AES/Rijndael from an ideal cipher, but these attacks have considerably higher complexity than the corresponding attacks on SHA-2. I think it can be reasonable to model AES/Rijndael as ideal ciphers, provided that the limitations of this assumption are understood. Which seems to be the case in SDitH and MQOM.

Cheers,

John Preuß Matttson

[1] https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=935143

[Sydney Antonov]

> SHA-2: There are trivial distinguishing attacks. Moreover, assuming that SHA-2 behaves like a random oracle has led to vulnerabilities in SPHINCS+ [1]. I therefore do not think it is appropriate to model SHA-2 as a random oracle, and I think SHA-2 should be phased out.

What lead to vulnerabilities in SPHINCS+ was the gap between modelling SHA-2 as a random oracle and more realistically modelling it as a a Merkle-Damgård hash with a Davies-Meyer compression function built from an ideal cipher.

> AES/Rijndael: There are known attacks distinguishing AES/Rijndael from an ideal cipher, but these attacks have considerably higher complexity than the corresponding attacks on SHA-2. I think it can be reasonable to model AES/Rijndael as ideal ciphers, provided that the limitations of this assumption are understood. Which seems to be the case in SDitH and MQOM.

If we compare known attacks on AES/Rijndael to the block cipher underlying SHA-2's compression function, I don't think convinced AES wins. In general I also think the limitations of SHA-2 as a random oracle are better understood, as we actually have a model (Merkle-Damgård hash with a Davies-Meyer compression function built from an ideal cipher) that to my knowledge encompasses all known vulnerabilities.

I don't know about the specifics of SDitH or MQOM, but I would be suspicious of AES/Rijndael in applications involving structured or adversarially chosen keys where its key schedule could be exploited.

Sydney

[Blumenthal, Uri - 0553 - MITLL]

I wonder - how practical is related-key attack in the real world? If the adversary controls your RNG, aren’t there worse things she can do…?
—
Regards,
Uri

Secure Resilient Systems and Technologies
MIT Lincoln Laboratory

> On Oct 7, 2026, at 17:55, 'Sydney Antonov' via pqc-forum <pqc-...@list.nist.gov> wrote:
>
> !-------------------------------------------------------------------|
> This Message Is From an External Sender
> This message came from outside the Laboratory.
> |-------------------------------------------------------------------!

> --
> 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/VDPB6a3NSwpUiEps_g5AsnPNdQmI5Ja64QxPiBZGUjKrlBeKGYaaYPeLdXp7rCx_zf3Exm3rlx2npoSOfXgZKqDTo1I-CYl9oN_Sze5V9u8%3D%40protonmail.com.

[Demi Marie Obenour]

I generally agree.

That said, it is also true that using a hash function for very short, fixed-length inputs comes at a huge (and almost certainly unnecessary) performance cost. Would it make sense to use the TurboKeccak permutation instead, discarding some of its output, as a PRF? If there is sufficient parallelism (which there hopefully is here!), it's very fast in SIMD mode (less than 0.55 cycles per byte). If software performance is the primary concern, Blake2b's compression function might be an option too.

We *really really really* need symmetric algorithms that are designed with PQC in mind. Using Keccak instead of KangarooTwelve in ML-KEM and ML-DSA was a mistake. For hash-based. MPC-in-the-head, and VOLE-in-the-head signatures, different primitives are needed.

[Sydney Antonov]

On Wednesday, October 7th, 2026 at 10:03 PM, Blumenthal, Uri - 0553 - MITLL <u...@ll.mit.edu> wrote:

> I wonder - how practical is related-key attack in the real world? If the adversary controls your RNG, aren’t there worse things she can do…?

That isn't really the relevant threat model. For AES encryption, related-key attacks would only be a concern for poorly-designed protocols (well-designed protocols would use proper key derivation so that it is only necessary to assume that AES is a PRP). The relevant threat model for my "adversarially chosen keys" comment is when AES takes the role of an ideal cipher in a construction of something like a collision-resistant compression function or a Fiat-Shamir hash, where the "key" is really the adversarially-chosen hash/compression function input.

Sydney

[John Mattsson]

I agree with Sydney that related-key security is not a relevant model. I think that too much of the Rijndael-256 standardization discussion has focused on related-key attacks [1].

However, the ICM is substantially stronger, including resistance to known-key and chosen-key distinguishers, which are relevant attack models. My understanding is that NIST plans to standardize Rijndael-256 without changing the key schedule [2], which I think is the right decision.

I think two areas deserve further research:

- Design of new block ciphers with strong resistance to chosen-key distinguishers.

- Systematic analysis of Rijndael-256 against known-key and chosen-key distinguishers, including how closely it approximates an ideal cipher under these models.

Cheers,

John Preuß Mattsson

[1] https://csrc.nist.gov/files/pubs/sp/800/197/iprd/docs/sp800-197-pre-draft-public-comments.pdf

[2] https://csrc.nist.gov/csrc/media/presentations/2026/mpts2026-3a1/images-media/mpts2026-3a1-slides-nist-symm-meltem.pdf

--
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://eur02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgroups.google.com%2Fa%2Flist.nist.gov%2Fd%2Fmsgid%2Fpqc-forum%2FPj1xSjq3vLbDBKG5e4gRElxMlUf5etKndgi1pnnpbocUgoGCqpZn1OpR5TfnG5jkVOelXVkMZFE5z3EEZdds8MUjsl93W1rz5NvONrDEChA%253D%2540protonmail.com&data=05%7C02%7Cjohn.mattsson%40ericsson.com%7Cb78c64a62d8e4e24442308df253caeaf%7C92e84cebfbfd47abbe52080c6b87953f%7C0%7C0%7C639270614690763805%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=LA94k6WdscsLs1Lz0SoXqEvVK%2FHtx4KtERXjSocRafI%3D&reserved=0.

[Demi Obenour]

I definitely think that the ideal cipher model should be replaced by specific assumptions about the specific modes of operation in which AES/Rijndael is used.  The ideal cipher model is not considered conservative, but assumptions about specific modes are much safer.

Also, could MQOM use SDitH’s tree expansion and commitments?

[Kang Wan]

Dear all,

Thank you all for this thread — reading it in full, I think the debate
has converged more than it might appear.

On the threat model: I agree with Sydney and John that related-key
attacks were the wrong frame from the start. The live questions are
the ones John and Sydney identified: known-key/chosen-key
distinguishers (Biryukov et al., Gilbert), and Sydney's "adversarially
chosen keys" setting — where AES plays the ideal cipher's role and the
"key" is really adversarial input. Dismissing the concern because
related-key attacks are impractical misses where the actual risk sits.

On Demi's latest question — whether MQOM could adopt SDitH's tree
expansion and commitments: Matthieu already noted that MQOM v3
includes a one-tree variant (Baum et al.) that sidesteps PGOW-MQ, so
part of this convergence has happened. The remaining gap, as I read
it, is on the commitment side, where the ICM is still load-bearing for
straight-line extraction. John's proposal seems like the right
framing: state the concrete properties needed (TCCR-style correlation
robustness, almost-injective PRG, or whatever the de-idealized proof
requires) so cryptanalysts can target them directly, instead of
debating the ICM in the abstract.

One concrete question this leaves open: Sydney's
adversarially-chosen-keys setting maps directly onto MQOM's
E_{t_i}(seed) ⊕ ψ(seed) usage, where the tweaks are adversarially
influenced. The known-key/chosen-key distinguisher literature tells us
AES-128 is distinguishable in those models — but a distinguisher is
not an attack on this specific usage. Has anyone analyzed AES-128 or
Rijndael-256-256 specifically in this adversarially-chosen-tweak
Davies–Meyer setting? That gap — between "a distinguisher exists
somewhere" and "this usage is concretely threatened" — is exactly
where John's call for systematic analysis of Rijndael-256-256 should
land, in my view.

Best regards,
kang