NIST requests public comments on Rijndael-256

[Morris Dworkin]

FYI, on Monday NIST requested public comments by June 25 on a plan to develop a draft standard for Rijndael-256 over the next year.

[John Preuß Mattsson]

Thanks Morris,

 Very good news. In addition to supporting large volumes there are many strong security reasons for larger block sizes even when processing modest volumes of data.

-        The complexity of distinguishing attacks against current AES-256 modes is only ≈ 128 - log₂(σ) bits. It can be discussed how dangerous distinguishing attacks are, but TLS 1.3, DTLS 1.3 and QUIC mandates rekeying to limit the complexity of distinguishing attacks to 93.5 bits. 64-bit security against distinguishing attacks as allowed by 800-38D does not feel optimal.

-        The complexity of IV collision attacks against AES-256-GCM with random nonces is ≈ |IV| – log₂(q). Compared to distinguishing attacks (lack of collisions) this is definitely a serious attack directly affecting practical security.

-        The authenticity advantage of AES-GCM has as a factor the Bernstein bound δ ≈ 1 + (q + v)² ⋅ ℓ² / 2¹²⁹, which is tight. Keeping δ ≈ 1 puts a lot of constraints on the usage. Not keeping δ ≈ 1 leads to bad security. NIST should enforce that δ ≈ 1 when updating 800-38D.

-        The expected number of forgeries for AES-CMAC and AES-CCM with 128-bit tags is cubic in the number of queries.

The above issues are all directly linked to the narrow 128-bit block size of AES. The impact is low security, complex constraints, or both. Rijndael-256 solves all of the issues.

Two very good questions that NIST asked during the Accordion workshop [1–2] were:

-        Should the key schedule be revised to mitigate related-key attacks? As discussed during the workshop, very small changes to the key schedule mitigates related-key attacks, and the performance on x86-64 platforms equipped with AES-NI and VAES is independent of the key schedule. I think NIST has two options. Revise the key schedule or clearly state that NIST does not think related-key attacks needs to be considered in general. I don’t have a preference here.

-        New or adapted modes? I don’t think CBC, CFB, OFB, or CTR, XTS, KW, or KWP should be allowed. They should be replaced by better modes. I think CMAC and CCM could be adopted. A CBC-MAC with Rijndael-256 truncated to 96- or 128-bit behaves like an ideal MAC and offers good integrity comparable to HMAC-SHA-256/128 and KMAC128. GCM and GMAC should be improved to behave like an ideal MAC in unicast protocols with replay protection, including reforgeability resistance.

Cheers,
John

[1] https://csrc.nist.gov/csrc/media/Presentations/2024/options-for-encryption-algorithms-and-modes/images-media/sess-3-regenscheid-acm-workshop-2024.p

[2] https://csrc.nist.gov/csrc/media/Presentations/2024/toward-a-new-block-cipher-mode-standard/images-media/sess-2-mouha-acm-workshop-2024.pdf

[John Preuß Mattsson]

Hi,

On Wednesday, January 8, 2025 at 7:56:13 AM UTC+1 John Preuß Mattsson wrote:

The complexity of distinguishing attacks against current AES-256 modes is only ≈ 128 - log₂(σ) bits. It can be discussed how dangerous distinguishing attacks are, but TLS 1.3, DTLS 1.3 and QUIC mandates rekeying to limit the complexity of distinguishing attacks to 93.5 bits. 64-bit security against distinguishing attacks as allowed by 800-38D does not feel optimal.

Upon further reading, it seems there is no need to discuss the risks of distinguishing attacks on block ciphers in counter mode. McGrew, Leurent, and Sibleyras [1-2] showed that for block ciphers in counter mode, an attacker with partial knowledge of the plaintext can execute plaintext-recovery attacks against counter mode with roughly the same complexity (up to logaritmic factors) as distinguishing attacks. This is not the case for other stream ciphers, where many distinguishing attacks do not seem to facilitate plaintext recovery [3]. AES-256-GCM with the usage limits specified in 800-38D (P_MAX = 2^36 and Q_MAX = 2^32) only offers 64-bit security against plaintext-recovery attacks.

I don't know exactly what complexity [1-2] gives for attacks with lower probability than 1, but unless someone proves otherwise, it does not seem to be any reason to assume that the complexity of distinguishing attacks (128 - log₂(σ)) and plaintext-recovery attacks are not the same for all probabilities. Even under the strict usage limits defined by QUIC in RFC 9001 (P_MAX = 2^16 and Q_MAX = 2^23 AES-256-GCM-SST provides only 94 bits of security against distinguishing attacks and therefore likely plaintext-recovery attacks.

The brief comment in NIST IR 8459, stating that "the key must be changed well before encrypting 2^(n/2) blocks of data", appears to underestimate the findings in [1-2]. These findings demonstrate that the earlier assumption, that distinguishing attacks on block ciphers in counter mode do not lead to plaintext-recovery attacks, is incorrect.

[1] Leurent and Sibleyras, "The Missing Difference Problem, and Its Applications to Counter Mode Encryption"
https://link.springer.com/chapter/10.1007/978-3-319-78375-8_24

[2] McGrew, "Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes"
https://eprint.iacr.org/2012/623.pdf

[3] Rose, Hawkes, "On the Applicability of Distinguishing Attacks Against Stream Ciphers"
https://eprint.iacr.org/2002/142.pdf

[Markku-Juhani O. Saarinen]

Thanks Morris and Hi All,

RISC-V Crypto SIG discussed Rijndael-256 in our meeting on Thursday, January 16. We will be submitting an official comment by the June 25 deadline. Here are some preliminary findings.

For that meeting, I implemented Rijndael-256 with the standard RISC-V Vector AES cryptography extensions (Zvkned). See its README for further discussion: https://github.com/mjosaarinen/rij256-rv/

Recall that as an open-source ISA, RISC-V has custom (DIY) and standard (ratified by RISC-V International) extensions. The Zvkned "vector AES" instructions (used here) are ratified and already supported by compiler toolchains, etc. They are also a part of e.g. prominent RISC-V Architecture profiles and Google's requirements for Android on RISC-V.

Summary:
- One can process a single round of Rijndael-256 by combining a 256-bit byte shuffle instruction (in the case of RISC-V, vrgather.vv) with an instruction that computes two parallel AES rounds (vaesz, vaesef, vaesem, vaesdf, vaesdm), in a similar way to other major ISA architectures (in case of x86-64, the Drucker-Gueron paper referenced in our implementation README.)
- However, there is a hitch compared to "plain" SIMD (non-vector) architectures; since the element width is different in the required byte shuffle operation (SEW=8) and the AES instructions (SEW=32), additional instructions for changing the element width and vector length are required, nearly doubling the instruction count. 
- The good news is that this type of Rijndael-256 implementation is constant time -- as the vrgather instruction is DIEL (Data Independent Execution Latency / Zvkt ) in relation to data being permuted (but not the permutation.)

The actual speed of the implementation is highly dependent on the microarchitecture. Instructions such as vrgather (as a crossbar permutation) can be implemented in several ways, depending on the gate budget. It *can* indeed be a 1-cycle instruction, but some existing silicon implements it as a 4-cycle instruction (VLEN=256). Another issue is that AES pipelining is likely to be broken by the vector element size switch, causing additional delays.

Outcome:

Some options considered can be found at the end of the presentation https://mjos.fi/doc/20250116-cryptosig-rij256.pdf

We didn't take any action in the meeting (such as starting a new TG for additional instructions) as the NIST SP 800-197 / Rijndael-256 standardization is just starting and details such as the key schedule may still change. However, the SIG will track (and perhaps even participate in) the development of SP 800-197 and remind RISC-V chip architects to take Rijndael-256 into account in their plans (as well as the full-round Keccak f1600 instructions.)

Best Regards,
- Markku, (RISC-V PQC TG Chair) on behalf of the RV Crypto SIG

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

On Thu, Dec 26, 2024 at 5:31 PM 'Morris Dworkin' via ciphermodes-forum <ciphermo...@list.nist.gov> wrote:

FYI, on Monday NIST requested public comments by June 25 on a plan to develop a draft standard for Rijndael-256 over the next year.

--
To unsubscribe from this group, send email to ciphermodes-fo...@list.nist.gov
 
View this message at https://list.nist.gov/ciphermodes-forum
To unsubscribe from this group and stop receiving emails from it, send an email to ciphermodes-fo...@list.nist.gov.