Subject: [Crypto-panel] Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 11 Jun 2020 20:57:01 +0300

Dear Crypto Review Panel members,

There is a need to validate the following errata:
https://www.rfc-editor.org/errata/eid6024

Any volunteers?

Regards,
CFRG chairs

---------- Пересылаемое сообщение ---------
От: Colin Perkins <[email-masked]>
Дата: сб, 6 июня 2020 г. в 16:03
Тема: Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)
Кому: <[email-masked]>

Hi CFRG chairs,

Can you discuss, and review with the RG if necessary, and let me know  if
the following errata should be marked as verified.

Thanks,
Colin

Begin forwarded message:

*From: *RFC Errata System <[email-masked]>
*Subject: **[irsg] [Technical Errata Reported] RFC8391 (6024)*
*Date: *18 March 2020 at 13:01:52 GMT
*To: [email-masked], [email-masked],
[email-masked], [email-masked], [email-masked], [email-masked]
*Cc: [email-masked], [email-masked]

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

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

--------------------------------------
Type: Technical
Reported by: Andreas Hülsing <[email-masked]>

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. The same applies for SHA3 but for SHA3 a
bigger internal state is used.

In consequence, SHAKE-128 cannot provide more security than NIST
post-quantum security level II (Any attack that breaks the relevant
security definition must require computational resources comparable to or
greater than those required for collision search on a 256-bit hash function
(e.g. SHA256 / SHA3-256)).

Instructions:
-------------
This erratum is currently posted as "Reported". If necessary, please
use "Reply All" to discuss whether it should be verified or
rejected. When a decision is reached, the verifying party
can log in to change the status and edit the report, if necessary.

--------------------------------------
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

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 11 Jun 2020 19:12:28 +0000

I volunteer; however I can’t read the link.  Did you send it correctly?

Actually, the corrected text you include below looks decent (although the discussion of SHA3 may be a bit misleading – SHA-3 has more than n/2 bits of security, which someone might assume from a quick reading of “The same applies for SHA3…”).

I’d want to see the full errata before I place my seal of approval, of course.

From: Crypto-panel <[email-masked]> On Behalf Of Stanislav V. Smyshlyaev
Sent: Thursday, June 11, 2020 1:57 PM
To: [email-masked]
Cc: [email-masked]
Subject: [Crypto-panel] Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)

There is a need to validate the following errata:
https://www.rfc-editor.org/errata/eid6024<https://www.rfc-editor..org/errata/eid6024>

Any volunteers?

Regards,
CFRG chairs

---------- Пересылаемое сообщение ---------
От: Colin Perkins <[email-masked]<mailto:[email-masked]>>
Дата: сб, 6 июня 2020 г. в 16:03
Тема: Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)
Кому: <[email-masked]<mailto:[email-masked]>>

Hi CFRG chairs,

Can you discuss, and review with the RG if necessary, and let me know  if the following errata should be marked as verified.

Thanks,
Colin

Begin forwarded message:

From: RFC Errata System <[email-masked]<mailto:[email-masked]>>
Subject: [irsg] [Technical Errata Reported] RFC8391 (6024)
Date: 18 March 2020 at 13:01:52 GMT
To: [email-masked]<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>, [email-masked]<mailto:[email-masked]>

--------------------------------------
Type: Technical
Reported by: Andreas Hülsing <[email-masked]<mailto:[email-masked]>>

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. The same applies for SHA3 but for SHA3 a bigger internal state is used.

In consequence, SHAKE-128 cannot provide more security than NIST post-quantum security level II (Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g. SHA256 / SHA3-256)).

Instructions:
-------------

Author(s)           : A. Huelsing, D. Butin, S. Gazdag, J. Rijneveld, A.. Mohaisen

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 11 Jun 2020 19:47:45 +0000

The text looks correct, however I do have a few nits about the notes.  One is the reference to SHA3, which on a quick read might be misleading; here is some alterative text:

The reason is that SHAKE allows for meet-in-the-middle preimage attacks that reduce to a collision search on the internal state. These internal collision attacks do not affect the security of SHA3, because of the larger capacity used.

Alternatively, just drop the reference to SHA3, which isn’t relevent to XMSS.

The other nit is with the sentence that starts:

Any attack that breaks the relevant security definition must require computational resources…

That sort of statement always has an implicit assumption of the form “unless someone has a cryptographical result against the SHA-3 permutation”; while we are used to that sort of assumption, a causal reader might not be.  I don’t see what that sentence brings to the table; I’d suggest dropping it.

Any volunteers?

Regards,
CFRG chairs

---------- Пересылаемое сообщение ---------
От: Colin Perkins <[email-masked]<mailto:[email-masked]>>
Дата: сб, 6 июня 2020 г. в 16:03
Тема: Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)
Кому: <[email-masked]<mailto:[email-masked]>>

Hi CFRG chairs,

Thanks,
Colin

Begin forwarded message:

Section: 5

Original Text
-------------

Corrected Text
--------------

Notes
-----

Instructions:
-------------

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 11 Jun 2020 22:51:28 +0300

Thank you, Scott!

Here is the correct link: https://www.rfc-editor.org/errata/eid6024

Regards,
Stanislav

On Thu, 11 Jun 2020 at 22:12, Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> Actually, the corrected text you include below looks decent (although the
> discussion of SHA3 may be a bit misleading – SHA-3 has more than n/2 bits
> of security, which someone might assume from a quick reading of “The same
> applies for SHA3…”).
>
>
>
> *From:* Crypto-panel <[email-masked]> * On Behalf Of *Stanislav
> V. Smyshlyaev
> *Sent:* Thursday, June 11, 2020 1:57 PM
> *To:* [email-masked]
> *Cc:* [email-masked]
> *Subject:* [Crypto-panel] Fwd: [irsg] [Technical Errata Reported] RFC8391
> (6024)
>
>
>
> <https://www.rfc-editor..org/errata/eid6024>
>
>
>
> Any volunteers?
>
>
>
> Regards,
>
> CFRG chairs
>
>
>
>
>
>
>
> От: *Colin Perkins* <[email-masked]>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Mon, 15 Jun 2020 11:01:22 +0300

Many thanks, Scott!

Therefore, you will be happy if the proposed change is applied, with the
revised version of notes, dropping the sentences "The same applies for SHA3
... " and "(Any attack that breaks...", – right?

Regards,
Stanislav

On Thu, 11 Jun 2020 at 22:48, Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> The text looks correct, however I do have a few nits about the notes.  One
> is the reference to SHA3, which on a quick read might be misleading; here
> is some alterative text:
>
>
>
> The reason is that SHAKE allows for meet-in-the-middle preimage attacks
> that reduce to a collision search on the internal state. *These internal
> collision attacks do not affect the security of SHA3, because of the larger
> capacity used.*
>
>
>
> That sort of statement always has an implicit assumption of the form
> “unless someone has a cryptographical result against the SHA-3
> permutation”; while we are used to that sort of assumption, a causal reader
> might not be.  I don’t see what that sentence brings to the table; I’d
> suggest dropping it.
>
>
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 15 Jun 2020 11:58:32 +0000

Actually, I’d be happy either way (as these are ‘nits’, not real problems).  Those changes would be my suggestion.

From: Stanislav V. Smyshlyaev <[email-masked]>
Sent: Monday, June 15, 2020 4:01 AM
To: Scott Fluhrer (sfluhrer) <[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: [Crypto-panel] Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)

Many thanks, Scott!

Therefore, you will be happy if the proposed change is applied, with the revised version of notes, dropping the sentences "The same applies for SHA3 ... " and "(Any attack that breaks...", – right?

Regards,
Stanislav

On Thu, 11 Jun 2020 at 22:48, Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>> wrote:
The text looks correct, however I do have a few nits about the notes.  One is the reference to SHA3, which on a quick read might be misleading; here is some alterative text:

From: Crypto-panel <[email-masked]<mailto:[email-masked]>> On Behalf Of Stanislav V. Smyshlyaev
Sent: Thursday, June 11, 2020 1:57 PM
To: [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>
Subject: [Crypto-panel] Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)

Any volunteers?

Regards,
CFRG chairs

---------- Пересылаемое сообщение ---------
От: Colin Perkins <[email-masked]<mailto:[email-masked]>>
Дата: сб, 6 июня 2020 г. в 16:03
Тема: Fwd: [irsg] [Technical Errata Reported] RFC8391 (6024)
Кому: <[email-masked]<mailto:[email-masked]>>

Hi CFRG chairs,

Thanks,
Colin

Begin forwarded message:

Section: 5

Original Text
-------------

Corrected Text
--------------

Notes
-----

Instructions:
-------------

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Mon, 15 Jun 2020 14:59:06 +0300

Agreed, thanks!

Regards,
Stanislav

On Mon, 15 Jun 2020 at 14:58, Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> Actually, I’d be happy either way (as these are ‘nits’, not real
> problems).  Those changes would be my suggestion.
>
>
>
> *From:* Stanislav V. Smyshlyaev <[email-masked]>
> *Sent:* Monday, June 15, 2020 4:01 AM
> *To:* Scott Fluhrer (sfluhrer) <[email-masked]>
> *Cc:* [email-masked]; [email-masked]
> *Subject:* Re: [Crypto-panel] Fwd: [irsg] [Technical Errata Reported]
> RFC8391 (6024)
>
>
>
> Many thanks, Scott!
>
>
>
> *From:* Crypto-panel <[email-masked]> *On Behalf Of *Stanislav
> V. Smyshlyaev