Planned revision of NIST SP 800-38D
Dworkin, Morris J. (Fed)
FYI, on January 6, NIST posted a pre-draft call for comments on the revision of NIST SP 800-38D, to get public input on two approaches to increasing the usage bounds for GCM. Comments were requested by March 14.
John Preuß Mattsson
Hi Morris,
I did some
further thinking on distinguishing attacks on block ciphers in counter mode and
how they are related to plaintext-recovery attacks.
I could not find any results for how small fraction of a bit an attacker can actually recover from a PRP in counter mode, so I calculated a formula for that and published on IACR ePrint, see Section 4 of [1].
As far as I
can see, the entropy loss of a pseudorandom permutation (PRP) in counter mode,
which corresponds to the amount of information an attacker can theoretically
recover is σ^2 / 2^b / ln 4 where σ is the number of encrypted blocks and b is
the block size.
When σ = 2^(b/2), an attacker can theoretically recover up to ≈ 1 / ln 4 ≈ 0.721 bits of plaintext. When b = 128 and σ ≤ 2^35 as required for AES-GCM in QUIC, an attacker can theoretically recover up to ≈ 1 / 2^58.47 bits of the plaintext.
The limits
in TLS 1.3, DTLS 1.3, and QUIC appear to be far stricter than necessary. There
is no universally agreed-upon threshold for how much information an attacker
must recover for it to constitute a meaningful attack. However, protecting
against the recovery of 1 / 2^58.47 bits, a practically negligible fraction, seems
overly cautious and unlikely to be a realistic threat.
I agree with the conclusion in NIST IR 8459 that the key must be changed well before encrypting 2^(b/2) blocks of data. I recommend that NIST aligns with ANSSI [2] by requiring that the maximum number of encrypted blocks under the same key must not exceed 2^(b/2 - 5). This appears to be a well-thought-out and balanced requirement, effectively limiting the amount of plaintext an attacker could recover to ≈ 1 / 2^10.47 ≈ 0.0007 bits. For global companies it is very important with alignment between NIST, ANSSI, BSI, Swedish NCSA etc. I do not think NIST should align with (D)TLS 1.3 and QUIC.
We are planning
to include the above in in our official comments on SP 800-38D that NIST
has requested by March 14 [3].
Cheers,
John Preuß
Mattsson
Expert, Cryptographic Algorithms and Security Protocols, Ericsson
[1] https://eprint.iacr.org/2024/1111.pdf
[2] https://cyber.gouv.fr/sites/default/files/2021/03/anssi-guide-mecanismes_crypto-2.04.pdf
[3] https://csrc.nist.gov/News/2025/pre-draft-call-for-comments-on-gcm-and-gmac
John Preuß Mattsson
- We recommend that NIST standardizes Galois Counter Mode with Strong Secure Tags (GCM-SST) including Rijndael-GCM-SST. Due to the weaknesses with GCM, we do not think NIST should specify GCM with any additional block ciphers. For a given tag length, GCM-SST has strictly better security properties than GCM (also when used with random nonces and in multicast), and for a fixed security level, GCM-SST has smaller ciphertext expansion.
- We think NIST should specify a function for deriving key-nonce pairs that can be instantiated with different KDFs and AEADs. Such a function would also be useful for Rijndael- and Keccak-based AEADs. The KDF could be one of the current NIST-approved KDFs, or a new AES-based KDF optimized for the purpose.
- We think NIST should mandate stricter confidentiality and integrity constrainsts for AES-GCM. P_MAX ⋅ Q_MAX ⪅ 263 and (P_MAX + A_MAX) ⋅ (Q_MAX + V_MAX) ⪅ 266. The suggested confidentiality constraint aligns with ANSSI.
- We think NIST should forbid random nonces with a fixed key. Instead of allowing random nonces, NIST should define a method for deriving random key-nonce pairs.
- Following a comment from Rogaway, we think NIST should explain how to derive a large number of non-colliding random nonces.
Expert Cryptographic Algorithms and Security Protocols, Ericsson