RFC 8391, "XMSS: eXtended Merkle Signature Scheme", May 2018

Errata ID: 6024
Status: Verified
Type: Technical
Publication Format(s) : TEXT
Reported By: Andreas Hülsing
Date Reported: 2020-03-18
Verifier Name: Colin Perkins
Date Verified: 2020-06-23

Section 5 says:

This section provides basic parameter sets that are assumed to cover most relevant applications.  Parameter sets for two classical security levels are defined.  Parameters with n = 32 provide a classical security level of 256 bits.  Parameters with n = 64 provide a classical security level of 512 bits.  Considering quantum-computer-aided attacks, these output sizes yield post-quantum security of 128 and 256 bits, respectively.

It should say:

This section provides basic parameter sets that are assumed to cover most relevant applications. Parameter sets for two classical security levels are defined using the cryptographic functions SHA2 and SHAKE.  Parameters with SHA2 and n = 32 provide a classical security level of 256 bits. Parameters with SHA2 and n = 64 provide a classical security level of 512 bits.  Considering quantum-computer-aided attacks, these parameters yield post-quantum security of 128 and 256 bits, respectively. Parameters with SHAKE and n = 32 provide a classical security level of 128 bits.  Parameters with SHAKE and n = 64 provide a classical security level of 256 bits.  Considering quantum-computer-aided attacks, these parameters yield post-quantum security of 86 and 170 bits, respectively. 

Notes:

Traditionally, a hash function with n-bit outputs is assumed to have n-bit security against classical preimage and second-preimage attacks, and n/2-bit security against classical collision attacks. For adversaries with access to a quantum computer, these bounds change to n/2 and n/3 bits when only counting queries to the hash function. This also applies to SHA2 and SHA3. In contrast, SHAKE follows a different reasoning. SHAKE with an internal state of n bits and an output length of n bits achieves n/2 bit security against classical preimage, second-preimage and collision attacks. For quantum attacks security changes to n/3 bits. The reason is that SHAKE allows for meet-in-the-middle preimage attacks that reduce to a collision search on the internal state.

In consequence, SHAKE-128 cannot provide more security than NIST post-quantum security level II.

(Errata submitted by Andreas Hülsing; notes slightly revised after Crypto Forum review by Scott Fluhrer; verified by CFRG Chairs and IRTF Chair)

Report New Errata