Subject: Re: [CFRG] : Was: eddsa (un)suited for mandatory to implement ciphersuite?

From: "D. J. Bernstein" <[email-masked]>
Date: 1 Feb 2022 17:00:49 -0000

The Ed25519 paper says that randomness in signing is "directly relevant
to the recent collapse of the Sony PlayStation 3 security system". Sony
had simply copied one random number into their code to be used for every
signature, in effect plugging a stuck RNG into ECDSA:

   https://fahrplan.events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf

The following paper breaks keys generated by an RNG that appears to have
become stuck because of physical failures---this isn't a signing-RNG
example but presumably there are many cases of stuck RNGs beyond the
ones that we know about:

   https://cr.yp.to/papers.html#smartfacts

The Ed25519 paper also describes the more traditional failure mode of
signing randomness being exposed to the adversary. Here's an example of
software-engineering problems creating a predictable RNG:

   https://www.schneier.com/blog/archives/2008/05/random_number_b.html

Here's an example of a malicious RNG, predictable by the adversary:

   https://cr.yp.to/papers.html#dual-ec

See PDF pages 20ff of

   https://csrc.nist.gov/CSRC/media/Publications/fips/186/5/draft/documents/fips-186-5-draft-comments-received.pdf

for further references and security analysis of various signature
options. Obviously a signer hashing more inputs is compatible with EdDSA
verifiers, but this has to be carefully specified in a way that's easy
to test; it would be very bad if an effort to raise the cost of local
side-channel attacks ends up exposing the signer to fast remote attacks!

---Dan

---

From: Rene Struik <[email-masked]>
Date: Tue, 1 Feb 2022 13:25:59 -0500

Hi Dan:

Aside from self-citations, could you also point to technical work by 
others that could be relevant to and sheds an unbiased and impartial 
light on EdDSA security issues?

Rene

On 2022-02-01 12:00 p.m., D. J. Bernstein wrote:
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Feb 2022 10:59:05 -0000

Rene Struik writes:
> Aside from self-citations

Hmmm. Since a moment ago there were questions and comments regarding the
rationale for the design (e.g., your comment "to me it is *not obvious*
why Ed25519 has been designed as is"), it seems appropriate to (1)
review what the Ed25519 paper says on exactly this topic, and (2) point
to a variety of motivating examples of real-world RNG failures before
and after that paper.

Furthermore, since the main question on the table is whether to specify
alternative methods to generate the secret nonce for each signature---
and, if so, what exactly those methods should be---it seems important to
look at what's known about the many ways that nonce generation can go
wrong. There's extensive material on this in Section 2 ("Nonce attacks")
of the last document that I mentioned.

Since I've been working on these topics for some time, it shouldn't be
surprising that I'm a coauthor on some of the relevant literature.
Readers looking at the cited documents can immediately see which ones I
coauthored and which ones I didn't. If you disagree with the content of
something, let me suggest that you quote what you disagree with and
explain why.

---D. J. Bernstein

---

From: Rene Struik <[email-masked]>
Date: Wed, 2 Feb 2022 09:55:04 -0500

Hi Dan:

The topic on the table (and what triggered Stephen Farrell to bring this 
topic from the Lake WG to the CFRG mailing list) is the assertion that 
Ed25519 is subject to trivial single-fault attacks (and which would 
preclude its use with IoT-style devices highly problematic).

Simple question: if you believe this assertion is false, please indicate 
so on technical grounds (this is CFRG after all). Otherwise, please 
simply acknowledge this.

Others have already concluded there is a problem, but given your 
experience in the matter your technical assessment is of interest.

Once there is general (or at least rough) consensus that something is 
astray, the next step would be how to best address the identified 
problems (where, rng-design minutiae may be relevant). First, however, 
one should have a proper problem statement: after all, one would not 
wish to embark on a solution direction that turns out not to solve the 
problem(s) well. This problem solving approach is sound engineering 
practice.

BTW - For clarity, with trivial single-fault attacks, we do not refer to 
"simply disable the RNG call, so that everything turns into a Sony 
Playstation example" (since it would be a diversion of the main topic). 
We do refer to attacks that take advantage of the mandated determinism, 
as known in the technical literature and sketched on the CFRG mailing 
list this Monday.

"Comment is free, but facts are sacred."

Rene

-- 
email:[email-masked]  | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Feb 2022 16:54:48 -0000

Rene Struik writes:
> Ed25519 is subject to trivial single-fault attacks (and which would preclude
> its use with IoT-style devices highly problematic).

Hmmm. All evidence that I've seen is compatible with the hypothesis that
standard IoT implementations of _every_ signature system are breakable
at low cost by an attacker with physical access to the device.

I can't endorse selectively stating examples of low-cost attacks, nor
can I endorse picking certain types of low-cost attacks and declaring
those to be "trivial"; this would lead readers to misunderstand what's
required for security against this type of attacker.

I'll again point to PDF pages 20ff of

as a reference for security considerations regarding nonce-generation
options; this seems directly relevant to the discussions at hand.

---D. J. Bernstein

---

From: Yolan Romailler <[email-masked]>
Date: Wed, 2 Feb 2022 18:32:59 +0100

Hi,

I agree here with Dan's sentiments regarding the resistance of signature
schemes against fault attacks in off-the-shelf IoT devices in front of a
motivated adversary with full physical access.

Having worked on attacking both ECDSA and EdDSA using fault attacks, I just
wanted to confirm that they are both are equally easy to attack when used
with a deterministic nonce generation à la RFC6979 or like the Ed25519
paper does, without any additional randomness. But _not only_ because of
fault attacks on their nonces generation processes at all, for instance the
base point or the scalar multiplication can be targeted too, causing
invalid R values which also allow recovery of the secret key.

I've seen repeated demand for references, so a good summary of what has
been done publicly on the fault attack front is this paper:
https://eprint.iacr.org/2020/803

The currently preferred "design" countermeasure, as far as I can tell, is
to "inject extra randomness" in the hash function like XEdDSA does and like
Mike mentioned earlier in this thread, because it appears to deter all
known fault attacks against the schemes.

Overall, cases where fault attacks are important are typically: smart
cards, which are increasingly concerned about implementing EdDSA, and IoT
devices, but it's not the case that these are relevant for all IoT devices,
it's really a matter of threat model. That being said, there would
definitely be value in adding some wording to make sure people reading the
EdDSA RFC are aware that there are extra considerations in the case where
fault attacks are relevant to their threat model, in order to raise
awareness.

Fault attacks are notoriously difficult to prevent in general, and are
often implementation dependent. For instance an implementation using a loop
to populate a buffer with random data could _very_ easily be forced into
skipping the rest of the loop after very few iterations, leaving almost no
random data in that buffer, like Björn mentioned... So "just using ECDSA or
EdDSA with a fully random nonce" isn't even necessarily a good
countermeasure.

Note that resorting to random nonce or even a RNG is not necessarily
required, as already noted in https://eprint.iacr.org/2017/975, adding
noise to the hash computation, even if it is just a counter, can already
defeat fault attacks as far as we know / have tested.

Finally, in the smart card world, one would typically rely on _hardware_
countermeasures to _detect_ attempted fault attacks and erase private key
material / stop the current signature process if triggered, thus rendering
fault attacks way more difficult to achieve. It's not doing so by tweaking
the algorithms themselves if these are properly side-channel resistant,
instead it will add voltage glitch detection, add depackaging detection,
and so on. I would recommend giving a read to
DOI:10.1109/TVLSI.2012.2231707 (
https://www.esat.kuleuven.be/cosic/publications/article-2204.pdf) for a
better idea of how faults are "prevented" at the hardware level.

Best regards,
Yolan

Le mer. 2 févr. 2022 à 17:56, D. J. Bernstein <[email-masked]> a écrit :

> preclude

---

From: Rene Struik <[email-masked]>
Date: Wed, 2 Feb 2022 13:14:37 -0500

Hi Yolan:

I agree that fault attacks are difficult to prevent. However, this does 
not mean one should make this super-easy by design, where your email 
actually provides further evidence for this:

Your confirmation of easy fault attacks on deterministic ECC-based 
signature schemes (EdDSA, det-ECDSA) actually prove the assertion: both 
RFC6979 and EdDSA do a bad job there, due to hardcoded requirements for 
determinism. Actually, if you look at the original Lake WG message I 
sent on this topic [1], you will find that I made a statement on both 
det-ECDSA and det-EdDSA).

    [excerpt of your email]
    "Having worked on attacking both ECDSA and EdDSA using fault
    attacks, I just wanted to confirm that they are both are equally
    easy to attack when used with a deterministic nonce generation à la
    RFC6979 or like the Ed25519 paper does, without any additional
    randomness. But _not only_ because of fault attacks on their nonces
    generation processes at all, for instance the base point or the
    scalar multiplication can be targeted too, causing invalid R values
    which also allow recovery of the secret key."

I do think that not all fault attacks are created equal, though, since 
some require targeting a specific instruction, whereas others allow an 
adversary much more flexibility. As an example, in the paper IACR ePrint 
2020-803 that you reference, attacks described in Section 4 depend on 
targeted faults (e.g., on ephemeral key k when loading from memory). 
Moreover, ironically, all of these attacks only work by using lattice 
techniques in an N-dimensional space, where one repeats an attack N 
times and exploits non-determinism (the very point that is on our radar 
in CFRG now!). If one looks at Tables 2 and 3 of that paper, one finds 
N>1 in all cases and the countermeasures (Section 6) emphasize this at 
the first para, which reads:

    In this section, we discuss the effectiveness of some possible
    countermeasures. -Randomization. As introduced above, _the proposed
    attacks take advantage of the fact that k is determined by the input
    message and the private key, and remains unchanged during the
    process of signature queries__. _Intuitively the condition can be
    removed by reintroducing randomness to the derivation of k. This is
    the exact idea of hedged signature schemes, where the input message,
    secret key and a nonce are input to generate the per-signature
    randomness k.

So, your quoted paper is actually another one in the SCA-paper generator 
sequence triggered by designing-in determinism.

         [excerpt of your email]
         I've seen repeated demand for references, so a good summary of 
what has been done publicly on the fault attack front is this paper: 
https://eprint.iacr.org/2020/803

Your reference to ePrint 2017-975 illustrates the point that designing 
determinism into the mandatory feature set of a specification is too 
rigid of a measure. As you noted, there are easy countermeasures (adding 
some noise), but the point is that the current specification does not 
allow this (since deterministic). This, therefore, provides further 
evidence that something is amiss.

    [excerpt of your email]
    "Note that resorting to random nonce or even a RNG is not
    necessarily required, as already noted in
    https://eprint.iacr.org/2017/975, adding noise to the hash
    computation, even if it is just a counter, can already defeat fault
    attacks as far as we know / have tested."

The point of raising this topic is not to kill-off EdDSA; it is to make 
it more resilient in the face of realistic attacks in, e.g., IoT-settings.

We all know that some good engineering thinking went into the design of 
EdDSA, but unfortunately also a few (very few) bad ideas. It is the 
latter one should root out.

Ref: [1] 
https://mailarchive.ietf.org/arch/msg/lake/0-9X6McGoQCoqZ0q2v97eH9i4iY/

On 2022-02-02 12:32 p.m., Yolan Romailler wrote:
> Hi,
>
> I agree here with Dan's sentiments regarding the resistance of 
> signature schemes against fault attacks in off-the-shelf IoT devices 
> in front of a motivated adversary with full physical access.
>
> Having worked on attacking both ECDSA and EdDSA using fault attacks, I 
> just wanted to confirm that they are both are equally easy to attack 
> when used with a deterministic nonce generation à la RFC6979 or 
> like the Ed25519 paper does, without any additional randomness. But 
> _not only_ because of fault attacks on their nonces generation 
> processes at all, for instance the base point or the scalar 
> multiplication can be targeted too, causing invalid R values which 
> also allow recovery of the secret key.
>
> I've seen repeated demand for references, so a good summary of what 
> has been done publicly on the fault attack front is this paper: 
> The currently preferred "design" countermeasure, as far as I can tell, 
> is to "inject extra randomness" in the hash function like XEdDSA does 
> and like Mike mentioned earlier in this thread, because it appears to 
> deter all known fault attacks against the schemes.
>
> cards, which are increasingly concerned about implementing EdDSA, and 
> IoT devices, but it's not the case that these are relevant for all IoT 
> devices, it's really a matter of threat model. That being said, there 
> would definitely be value in adding some wording to make sure people 
> reading the EdDSA RFC are aware that there are extra considerations in 
> the case where fault attacks are relevant to their threat model, in 
> order to raise awareness.
>
> often implementation dependent. For instance an implementation using a 
> loop to populate a buffer with random data could _very_ easily be 
> forced into skipping the rest of the loop after very few iterations, 
> leaving almost no random data in that buffer, like Björn mentioned... 
> So "just using ECDSA or EdDSA with a fully random nonce" isn't even 
> necessarily a good countermeasure.
>
> noise to the hash computation, even if it is just a counter, can 
> already defeat fault attacks as far as we know / have tested.
>
> Finally, in the smart card world, one would typically rely on 
> _hardware_ countermeasures to _detect_ attempted fault attacks and 
> erase private key material / stop the current signature process if 
> triggered, thus rendering fault attacks way more difficult to achieve. 
> It's not doing so by tweaking the algorithms themselves if these are 
> properly side-channel resistant, instead it will add voltage glitch 
> detection, add depackaging detection, and so on. I would recommend 
> giving a read to DOI:10.1109/TVLSI.2012.2231707 
> (https://www.esat.kuleuven.be/cosic/publications/article-2204.pdf) for 
> a better idea of how faults are "prevented" at the hardware level.
>
> Best regards,
> Yolan
>

---

From: John Mattsson <[email-masked]>
Date: Fri, 4 Feb 2022 09:34:04 +0000

Hi Dan,

As you say, you have published a lot on methods to generate the secret nonce for ECC signatures. You are also the creator of EdDSA. Do you have any opinions regarding the alternative nonce generation that CFRG came up with in 2020? It is similar to XEdDSA but with the improvements suggested by Samwel et al. in "Breaking Ed25519 in WolfSSL".

https://eprint.iacr.org/2017/985.pdf

https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/

Cheers,
John

----------------------------------------------------------------

2.  Updates to RFC 8032 (EdDSA)

   For Ed25519ph, Ed25519ctx, and Ed25519: In deployments where side-
   channel and fault injection attacks are a concern, the following step
   is RECOMMENDED instead of step (2) in Section 5.1.6 of [RFC8032]:

      2.  Compute SHA-512(dom2(F, C) || Z || prefix || 000... || PH(M)),
          where M is the message to be signed, Z is 32 octets of random
          data, the number of zeroes 000... is chosen so that the length
          of (dom2(F, C) || Z || prefix || 000...)  is 1024 bytes.
          Interpret the 64-octet digest as a little-endian integer r.

   For Ed448ph and Ed448: In deployments where side-channel and fault
   injection attacks are a concern, the following step is RECOMMENDED
   instead of step (2) in Section 5.3.6 of [RFC8032]:

      2.  Compute SHAKE256(dom4(F, C) || Z || prefix || 000... || PH(M),
          114), where M is the message to be signed, and Z is 57 octets
          of random data, the number of zeroes 000... is chosen so that
          the length of (dom4(F, C) || Z || prefix || 000...) is 1088
          bytes. F is 1 for Ed448ph, 0 for Ed448, and C is the context
          to use. Interpret the 114-octet digest as a little-endian
          integer r.

----------------------------------------------------------------

From: CFRG <[email-masked]> on behalf of D. J. Bernstein <[email-masked]>
Date: Wednesday, 2 February 2022 at 12:00
To: [email-masked] <[email-masked]>
Subject: Re: [CFRG] : Was: eddsa (un)suited for mandatory to implement ciphersuite?

---D. J. Bernstein

_______________________________________________
CFRG mailing list
[email-masked]
https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-40f7d10cf9eb7c69&q=1&e=1073fbcb-d711-4ee3-bb60-ab5c3b83f338&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 4 Feb 2022 13:08:50 +0200

On Fri, Feb 04, 2022 at 09:34:04AM +0000, John Mattsson wrote:
> Hi Dan,
> 
> As you say, you have published a lot on methods to generate the secret
> nonce for ECC signatures. You are also the creator of EdDSA. Do you
> have any opinions regarding the alternative nonce generation that
> CFRG came up with in 2020? It is similar to XEdDSA but with the
> improvements suggested by Samwel et al. in "Breaking Ed25519 in
> WolfSSL".
> 

This seems to be mixing bytes and bits? The blocksize of SHA-512 is 128
bytes, and dom2(F, C) || Z || prefix can not be longer than
32+1+1+255+32+32=353 bytes, so last possible block boundary is 384
bytes.

And reading the WolfSSL attack paper, the most straightforward
adaptation of the construction they recommend is:

SHA-512(dom2(F, C) || 000... || prefix || Z || PH(M)),

Where 000... are to align to 128 byte block, and Z is 96 bytes. In
fact, in case of Ed25519, this would exactly correspond to the proposed
construction, as the first part is empty, and thus alignment is also
empty.

Number of extra blocks beyond message:
- 1 for Ed25519
- 2 for contexts (yuck) up to 94 bytes.
- 3 for contexts from 95 up to 222 bytes.
- 4 for contexts from 223 bytes up to the maximum.

Similar things apply to Ed448 case. In that case, the blocksize is 136
bytes, and longest possible value of dom4(F, C) || Z || prefix is is
8+1+1+255+57+57=379, so last possible block boundary is 408 bytes.

In that case, the straightforward adapatation is:

SHAKE256(dom4(F, C) || 000... || prefix || Z || PH(M), 114),

Where 000... are to align to 136 byte block, and Z is 79 bytes.

Number of extra blocks beyond message:

- 2 for Ed448, and contexts up to 126 bytes.
- 3 for contexts from 127 bytes up to the maximum.

-Ilari

---

From: John Mattsson <[email-masked]>
Date: Fri, 4 Feb 2022 11:57:25 +0000

Thanks Ilari,

>This seems to be mixing bytes and bits?

Yes, obliously :) The 1024 bytes was intended to be "1024 bits" or "128 bytes".

> prefix can not be longer than 32+1+1+255+32+32=353 bytes, so last possible block boundary is 384 bytes.

Then 128 bytes would also be wrong. It should then be "where 000... are to align to 128 byte block" as you suggest.

> And reading the WolfSSL attack paper, the most straightforward adaptation

There was some discussion of this on the list.

https://mailarchive.ietf.org/arch/msg/cfrg/UFCY6JNkYZAIUL0JQJ6scZ05zTw/
https://mailarchive.ietf.org/arch/msg/cfrg/bZ_KPW5ajiEwxrrmQ9o2lNRoy9c/

I think it is very good to dicsuss the order of the three parameters “Z”, “prefix”, and “000...” and the length of Z again.

Not sure that a straightforward adaptation of the WolfSSL attack paper is a goal in it self. Do you think a straightforward adaptation of the WolfSSL paper is better than the current proposal in draft-mattsson-cfrg-det-sigs-with-noise?

Cheers,
John

From: Ilari Liusvaara <[email-masked]>
Date: Friday, 4 February 2022 at 12:09
To: John Mattsson <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [CFRG] : Was: eddsa (un)suited for mandatory to implement ciphersuite?

-Ilari

---

From: Björn Haase <[email-masked]>
Date: Fri, 4 Feb 2022 12:06:30 +0000

As a suggestion regarding notation regarding the input block size of the hash.:

I think that it would be good if we could align the notations used in the hash-to-curve, CPace and EdDSA drafts and use "s_in_bytes".

In the hash-to-curve draft they used the definition

"   - s_in_bytes, the input block size of H, measured in bytes (see
     discussion above). For example, for SHA-256, s_in_bytes = 64."

and for CPace I-D I re-used it as 

   *  H.s_in_bytes denotes the _input block size_ used by H.  For
      instance, for SHA-512 the input block size s_in_bytes is 128,
      while for SHAKE-256 the input block size amounts to 136 bytes.

After discussion with Leila and Nils I indeed think that the mitigation of padding the secret inputs with zeros for the first block before starting with hashing public inputs is indeed a good idea. At least for the similar case in CPace that's what we have suggested.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware

Endress+Hauser Liquid Analysis

Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 10377
[email-masked] |  www.ehla.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 4 Feb 2022 14:42:26 +0200

On Fri, Feb 04, 2022 at 11:57:25AM +0000, John Mattsson wrote:
> I think it is very good to dicsuss the order of the three parameters “Z”,
> “prefix”, and “000...” and the length of Z again.
> 
> Not sure that a straightforward adaptation of the WolfSSL attack paper
> is a goal in it self. Do you think a straightforward adaptation of the
> WolfSSL paper is better than the current proposal in
> draft-mattsson-cfrg-det-sigs-with-noise?

If contexts in Ed25519ctx can be manipulated, then in construction
specified by det-signs-with-noise, it is possible to cause seed to be
in its own block (by specifying 62 byte context) with zero padding and
random IV. I do not know if this is an issue or not.

Similar thing is possible with Ed448, this time with 69 byte context.
However, the WolfSSL attack paper alleges SHAKE256 is much easier to
protect against sidechannel attacks than SHA-512.

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 4 Feb 2022 16:16:38 +0200

> protect against sidechannel attacks than SHA-512.

Hmm...

Turns out the construction of r in Ed25519ctx is such that attacker
capable of collision attacks (satisfying some additional constraints)
against SHA-512 can mount key-recovery attack by manipulating contexts.
This is far beyond state of the art (actual collision attacks against
SHA-2), but far below what it should be (needs preimage attacks against
SHA-2).

Fortunately, construction of r is not interop-critical. So it is
possible to counter the attack without breaking compatibility. Any of
the discussed "noisy" constructs break the attack. Or it can be broken
in deterministic construction by padding dom2 to full block.

Specifically:

- For each byte x (so 256 total), attacker computes pair of 93 or 221
  byte contexts (c1, c2) such that dom2(F,c1)||x and dom2(F,c2)||x
  collide in SHA-512. These collisions are universal for all keys.
- Attacker picks a message M, and gets signatures for it under all
  512 contexts. If signer follows standard, two of the signatures
  will have identical first 32 bytes.
- If the two signatures have identical last 32 bytes (p~1/256), try
  those two contexts again with different message, until the last 32
  bytes differ.
- Now the private key can be recovered from those two signautres.

Similar attack against Ed448 seems to be much harder. The obstacle
is that any context length seems either too small for reliable
collisions, or gives too many pairs.

-Ilari

---

From: "D. J. Bernstein" <[email-masked]>
Date: 7 Feb 2022 08:02:58 -0000

> Compute SHA-512(dom2(F, C) || Z || prefix || 000... || PH(M)),

What stops implementors from forgetting to include PH(M) in the hash
input? I'd recommend building this on top of a deterministic interface
where Z is an explicit input, and making sure to test that interface.

Also, two useful rules of thumb regarding input concatenations (for
motivating attacks see, e.g., Crypto 1995 Preneel--van Oorschot): 1.
Never put a variable-length input anywhere but last. Previous positions
can have fixed-length _hashes_ of other variable-length inputs. 2. Put
whatever is least likely to be attacker-predictable first. Both Z and
"prefix" are less likely to be attacker-predictable than C; scenarios
where RNG failures are the top threat should put "prefix" first, while
scenarios where side channels are the top threat (which seems to be the
scenario under discussion) should put Z first.

---D. J. Bernstein

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 7 Feb 2022 12:39:03 +0000

On 2/7/22, 03:04, "CFRG on behalf of D. J. Bernstein" <[email-masked] on behalf of [email-masked]> wrote:

> input? 

Short answer is - interoperability testing.

But seriously, I don't buy this kind of logic. What stops implementers from "forgetting" to include "dom2(F, C)"? Or to "forget" replacing their 3-decades-old MD5 with SHA-512 in the running code? Or...?

> I'd recommend building this on top of a deterministic interface

It does not seem necessary.

---

From: Rene Struik <[email-masked]>
Date: Mon, 7 Feb 2022 09:21:48 -0500

Hi Dan:

What if implementors "forget" to update "Z" in a deterministic 
interface, thereby reintroducing deterministic signatures that give rise 
to disastrous single-fault attacks against Ed25519 as currently 
specified in RFC 8032 (and that the recent thread on trivial 
implementation attack failures of Ed25519 initiated a week ago)?

I think the time has long past for arguments of convenience of the type 
"what if implementors forget that 2+2=4 ?" (in decimal). If implementors 
do not read specification carefully or do have proper review and Q&A 
processes in place, this is a project management and, ultimately, an HR 
issue.

Just to reiterate what I wrote last Monday (Jan 31, 2021, 3.47pm EST):

    In my mind, one of the lessons to be learned here is that it would
    be highly recommended to stop the recent practice of CFRG to produce
    drafts that are a curious mix of specification and implementation
    details (which makes of this academic paper generators in the SCA
    space and, moreover, monolithic documents that are hard to maintain
    of, e.g., adapt to an instantiation with another hash function, say
    SHA-256).

It *would* help implementors a lot, though, if CFRG work products (and 
other IETF documents) are written in a clear and unambiguous way, where 
my sobering observation is that there is still a long way to go here. 
 From my same email at the time:

     if one would like to entice people [...] to give things a look, 
clarity of writing would be a must.

So, not all "forgetting" implementors of an IETF specification are 
entirely at fault themselves, if they can only rely on poorly written or 
poorly motivated specifications.

Regards, Rene

---

From: Watson Ladd <[email-masked]>
Date: Mon, 7 Feb 2022 06:44:11 -0800

On Mon, Feb 7, 2022 at 6:22 AM Rene Struik <[email-masked]> wrote:
>
> Hi Dan:
>
> What if implementors "forget" to update "Z" in a deterministic interface, thereby reintroducing deterministic signatures that give rise to disastrous single-fault attacks against Ed25519 as currently specified in RFC 8032 (and that the recent thread on trivial implementation attack failures of Ed25519 initiated a week ago)?

This can be detected by signing the same message twice and seeing the
answer is the same.
>
> I think the time has long past for arguments of convenience of the type "what if implementors forget that 2+2=4 ?" (in decimal). If implementors do not read specification carefully or do have proper review and Q&A processes in place, this is a project management and, ultimately, an HR issue.

Actual real world vulnerabilities exist and were exploited because of
failing to use a randomly generated nonce. Of course why can't these
people with proper expertise design a signature generation algorithm
that meets their needs?

You cannot handwave away real exploitation as needing proper review,
where proper review is of course defined as that that avoids real
exploitation. Does Juniper have proper code review of their products?

-- 
Astra mortemque praestare gradatim

---

From: Taylor R Campbell <[email-masked]>
Date: Mon, 7 Feb 2022 15:14:17 +0000

> Date: Mon, 7 Feb 2022 12:39:03 +0000
> From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
> 
> [...]

How does interoperability testing help when

1. the signing procedure is nondeterministic, and

2. the verification procedure is independent of whether PH(M) is
   included in the hash input?

If you make the signing procedure a deterministic function of

(signing key, additional randomization, message),

then you can use KATs written down in the spec to rule out a class of
implementation mistakes that led to actual catastrophic offline
cryptanalysis.

_And_ you can wire it up to an entropy source to mitigate a limited
class of fault attacks, without losing offline cryptanalytic security
if the entropy source goes bad.

But if the signing procedure is nondeterministic, no automatic testing
will detect the mistakes of (a) omitting the message from the hash
used in signing, and (b) wiring it up to a bad RNG.  Both of these
have happened repeatedly in the real world, by independent designers
and implementors -- mistake (a) by design in original (EC)DSA and most
implementations of it until RFC 6979, and mistake (b) by accident in
implementations like Debian OpenSSL or Sony PS3 firmware.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 7 Feb 2022 15:39:12 +0000

>    included in the hash input?

You're saying that verification of the signature does not depend on the input to the hash...???

> (signing key, additional randomization, message),

Isn't it already...?

> if the entropy source goes bad.

That's what NIST did for PQC. Some say that it would've been better if there was an explicit parameter for randomness input, otherwise - quite similar.

> used in signing, and (b) wiring it up to a bad RNG. 

You cannot detect bad RNG with such testing, that's true.

But please explain how to differentiate "deterministic" signing procedure that is a function of RANDOMIZATION, from "nondeterministic" signing procedure? An example of an existing/deployed NON-DETERMINISTIC signing procedure WITH ITS CORRESPONDING VERIFICATION procedure would illustrate your point nicely.

> Both of these have happened repeatedly in the real world, by independent designers

Please explain how in the above (a) won't be caught with interop testing - unless you assume ALL the developers "omitted the message from the hash used in signing"?

---

From: Taylor R Campbell <[email-masked]>
Date: Mon, 7 Feb 2022 16:01:15 +0000

> Date: Mon, 7 Feb 2022 15:39:12 +0000

There are two hashes involved (or three, with `prehashing', PH(M)).
In the notation of RFC 8032:

- r := SHA512(dom2(F, C) || [Z ||] prefix || PH(M)), the per-signature
  secret nonce (proposed modification in square brackets), where
  `prefix' is part of the secret signing key

- k := SHA512(dom2(F, C) || R || A || PH(M)), the Fiat-Shamir public
  `challenge'

r is secret and known only to the verifier, but k is public and
recomputed by the verifier.  (The signer then reveals R := r*B and S
:= r + k s, where B is the standard base point and s is the secret
signing scalar; and the verifier checks S*B ?= R + k*A, where A = s*B
is the public key.)

Obviously the verifier won't work if the signer computes k wrong, e.g.
by omitting PH(M), and I think that's what you had in mind with the
`???'.

But the verifier is independent of how the signer chooses r.  For
traditional Schnorr/(EC)DSA, r is chosen at random -- or not, on
Debian in 2007.  Ed25519 broke from the tradition by choosing it
deterministically as a PRF, under the secret signing key, of the
message.

Either way, the verifier is none the wiser.  The signer could use r =
SHA512(dom2(F, C) || prefix || "hello") instead of r = SHA512(dom2(F,
C) || Z || prefix || PH(M)) and all interoperability tests would still
pass.

> > (signing key, additional randomization, message),

No.  The string Z in draft-mattsson-cfrg-det-sigs-with-noise-03 is
chosen at random _inside the signing procedure_.  It is not a
parameter that can be specified in KATs feedable to any correct
implementation treated as a black box, because there is no additional
randomization parameter to that black box.  Correct implementations of
the proposed change to RFC 8032 still have only two parameters (other
than the fixed public application context) when treated as a black
box: signing key and message.

---

From: Taylor R Campbell <[email-masked]>
Date: Mon, 7 Feb 2022 16:11:24 +0000

With apologies for the self-reply and for not noticing the error while
proof-reading before I hit send:

> Date: Mon, 7 Feb 2022 16:01:15 +0000
> From: Taylor R Campbell <[email-masked]>
> 
> r is secret and known only to the verifier, but k is public and...
                                    ^^^^^^^^
Should have read:

r is secret and known only to the _signer_, but k is public and...

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 8 Feb 2022 22:17:44 +0000

>   `prefix' is part of the secret signing key

Yes, of course. Silly me - I never cared much for RFC 8032, so completely forgot how exactly it specified the signature. :-(

> r is secret and known only to the signer, but k is public and

Yes, precisely.

> message

Yes. But, whatever my personal opinion of RFC 8032 may be, it comes with test vectors - wouldn't a non-compliant implementation fail those?

> randomization parameter to that black box. 

Ah... NIST API design rears its ugly head again. :-)

But, like NIST PQC candidates did, it is possible to specify KAT to include the PRNG seed, and rig "a-la NIST RNG" that would take seed, for the testing. That's ugly as a mule - but at least it would do the job and weed out non-compliant "forgetful" implementations (and implementers ;). 

Remaining question would be ensuring that production version does not ship with the "NIST RNG". :-) :-)

Abd there got to be a BCP saying that randomness must be passed explicitly. ;-)