Subject: [Cfrg] [Errata Verified] RFC8391 (6024)

From: RFC Errata System <[email-masked]>
Date: Tue, 23 Jun 2020 01:16:30 -0700 (PDT)

The following errata report has been verified for RFC8391,
"XMSS: eXtended Merkle Signature Scheme". 

--------------------------------------
You may review the report below and at:
https://www.rfc-editor.org/errata/eid6024

--------------------------------------
Status: Verified
Type: Technical

Reported by: Andreas Hülsing <[email-masked]>
Date Reported: 2020-03-18
Verified by: Colin Perkins (IRSG)

Section: 5

Original Text
-------------
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.

Corrected Text
--------------
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)

--------------------------------------
RFC8391 (draft-irtf-cfrg-xmss-hash-based-signatures-12)
--------------------------------------
Title               : XMSS: eXtended Merkle Signature Scheme
Publication Date    : May 2018
Author(s)           : A. Huelsing, D. Butin, S. Gazdag, J. Rijneveld, A. Mohaisen
Category            : INFORMATIONAL
Source              : Crypto Forum Research Group
Area                : N/A
Stream              : IRTF
Verifying Party     : IRSG