Subject: [CFRG] : Assumptions regarding our I-D and RFC reader groups // Was: eddsa (un)suited for mandatory to implement ciphersuite?

From: Björn Haase <[email-masked]>
Date: Mon, 31 Jan 2022 09:10:48 +0000

Hello Rene,

>DLP-based signature schemes, such as ECDSA, the Schnorr signature scheme (original, full), ECGDSA, EC-KCDSA, or SM2, all share this "securely >generate randomness" component. Frankly, it should be known by now (it is 2022, after all) how to generate random integers in a specified >interval, at least to people who have not been hiding under a rock.

I’d really not under-estimate the amount of things that can go wrong with RNG use in the real-world and unfortunately as you know history prior to 2022 has shown that there were indeed attempts that tried to nudge people using weird and likely backdoored RNG designs. Given that background, I think that is obvious to all of us *why* Ed25519 has been designed this way and why it is superior in important application contextes and why it should really be tweaked in a non-deterministic way for other application scenarios.

Actually, the topic raises a side-aspect that is highly relevant IMO for authors of I-D and RFC regarding the assumptions that we have regarding the audience that we write I-D and RFC for at CFRG and regarding the host systems our designs run on.

E.g. should we expect expert knowledge regarding secure RNG design and should we also consider embedded systems?

This is an important question that comes up also for people like me that try to find the best wording and structure for documents such as the CPace RFC. I doubt that we currently all have a common picture regarding the audience that we expect to read our working group results.

In my perception we should assume that we are writing for 1) a general application software designer (“architect”)  and 2) application software engineer (“implementer”) and 3) a software verification engineer (“tester”), all without a security background and we probably should not assume expert knowledge.

Secondly, the application context that was assumed when writing any RFC or I-D should probably be sketched, I.e. it should be made explicit for which use-case the document’s recommendations were conceived and possibly which additional aspects need to be considered when, e.g., hardware-based attacks such as DPA or fault injection become relevant.

Unfortunately, when trying to cover several distinct application scenarios and reader groups, we most surely will have to live with significantly more complex documents in order to cover all of the tweaks that are to be considered. In the example of EdDSA this means for instance that one would have to add the complexity regarding when and how to add randomness in addition to the deterministic approach.

Currently my perception is that CFRG authors in the past did have a general “office environment” in mind when writing their documents.

In my opinion the fact that hardware-related attacks will become also relevant for internet-based devices such as IoT nodes probably should motivate a slight shift in the structure of the RFC documents issued by CFRG also to consider some attention to resource-constraints and hardware-side-channels.

For this reason, @CRFG and @CFRG-Chairs, I’d appreciate your feedback:

What’s your opinion here regarding the target audience and scope of application scenarios to cover?

Yours,

Björn

P.S.:

We are just in the process of re-structuring the write-up for best readability of the CPace draft and a common ground on the reader groups to write for would be very valuable for us!

For instance, we are currently seriously considering to remove the Ristretto255 and Decaf448 subsections in order to reduce complexity and avoid generating confusion in the group of application-oriented readers which might not want a theoretical background but a clear distinct and simple recommendation “do it that way in your application context”.

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: Mon, 31 Jan 2022 13:42:03 +0200

On Mon, Jan 31, 2022 at 09:10:48AM +0000, Björn Haase wrote:
> 
> Secondly, the application context that was assumed when writing any
> RFC or I-D should probably be sketched, I.e. it should be made
> explicit for which use-case the document’s recommendations were
> conceived and possibly which additional aspects need to be considered
> when, e.g., hardware-based attacks such as DPA or fault injection
> become relevant.
> 
> Unfortunately, when trying to cover several distinct application
> scenarios and reader groups, we most surely will have to live with
> significantly more complex documents in order to cover all of the
> tweaks that are to be considered. In the example of EdDSA this means
> for instance that one would have to add the complexity regarding when
> and how to add randomness in addition to the deterministic approach.
> 
> Currently my perception is that CFRG authors in the past did have a
> general “office environment” in mind when writing their documents.

I think the environment EdDSA (including the RFC) considers is that
the algorithm is executing in physically secure environment on modern
system, that is:

Attacker can:

- Observe all instructions executed (but not the data).
- Observe all memory addresses accessed (but not the values).

Attacker can not:

- Inject faults
- Observe system power usage or physical emissions.

Second factor is that it is much harder to deal with attackers that
can observe system power usage or physical emissions and not just
obtain insturction / memory access traces: It is no longer enough to
just never branch or index on secret data. Working out protections
against such attackers is highly nontrivial, and AFAIK is subject of
continued research.

And attacker capable of high-precision fault injection is not a good
scenario either: There can be individual operations with really bad
failure modes. E.g., what if the (normally infallable) call to RNG
fails? Or the outer hash in EdDSA has guessable fault? Both seem
like they could totally destroy security.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Mon, 31 Jan 2022 15:47:07 -0500

[resending my original message of Mon January 31, 2022, 12:00pm EST 
(which was not posted due to violating imposed msg-size thresholds)]
[I stripped the html-blurb at the end of Bjorn's original message and 
hope posting succeeds now]

Hi Bjorn:

As to "Given that background, I think that is obvious to all of us 
**why** Ed25519 has been designed this way and why it is superior in 
important application contextes and why it should really be tweaked in a 
non-deterministic way for other application scenarios.", to me it is 
*not obvious* why Ed25519 has been designed as is, unless to serve as an 
academic paper generator in the SCA-space (and beyond). {For my own 
perspective, see the feedback I provided during the FIPS 186-4 public 
review (see pages 75-85 of [1]).}

What *is* obvious to me is that not that many people who subscribe to 
the CFRG mailing list seem to do their own due diligence, since 
elementary fault attacks had been known well before RFC 8032 came to be 
(see also [2], written during the adoption call for 
draft-mattsson-cfrg-det-sigs-with-noise/). The CFRG is supposedly a 
research forum, where - certainly in the field of cryptography - "trust 
but verify" rather than "blind trust" should be one of the guiding 
principles.

Let us explore the fault attack topic a little bit more and ask 
ourselves whether, e.g, a specification of RSA signing with mandatory 
use of RSA-CRT would have met the bar for endorsement by the community 
(with post-1997 reference year) and then explore parallels with EdDSA, 
as specified in RFC 8032 (where we take as reference year 2016).

Let us recall the Boneh et al fault attack on RSA-CRT (Eurocrypt 1997; 
see, e.g., J of Cryptology, 2001 [3]):
1) Signing of the message m with RSA-CRT with public parameters (n:=p*q, 
e), private key d, and hash function h) takes place as follows:
Compute s1:=h(m)^d (mod p), s2:=h(m)^d (mod q), and compute 
S:=CRT((s1,p),(s2,q)), where CRT is the Chinese Remainder Theorem 
mapping from Zp x Zq to Zn.
2) Verification of the signature S with RSA-CRT with the same system 
parameters as above takes place as follows:
Compute z:=S^e (mod n) and verify that h(m)=z (mod n).
3) Single-fault attack on RSA-CRT: Cause a computational error during 
the signing operation by the legitimate signer, resulting in, w.l.o.g., 
s1 and s2'<>s2 (mod q), and thereby, S'=CRT(s1,s2'), where S'=S(mod p) 
and S'<>S (mod q). As a result, z':=(S')^e (mod n) satisfies z'=h(m) 
(mod p) and z'<> h(m) (mod q) and, thereby, gcd(z'-h(m), 
n)=gcd(z'-h(m),p*q)=p (unless h(m)=0 (mod p), but that directly gives 
the factorization of n).

Please note that this fault attack requires the signer to use RSA-CRT 
and requires the adversary to get access to the faulty signature S'. The 
attack, as described, does not work against ordinary RSA signing, where 
S:=h(m) (mod n) is computed using the public modulus n. The attack, as 
described, can be prevented if the signer verifies the computed 
signature S' itself and only releases S' if (S')^e=h(m) (mod n).

This attack does not make the specification of ordinary RSA signing 
flawed per se, since an implementor can opt to either implement ordinary 
RSA signing or use the relatively inexpensive remedy of including 
verification checks as part of the signing operation. The verdict might 
have been different if implementors would be forced to use RSA-CRT and 
if, e.g., verification checks would be so expensive that people (read: 
product managers) would try and cut corners and simply not implement those.

With EdDSA, as specified in RFC 8032, a single fault-attack works 
similarly as the classical Boneh et al attack of 1997, where (i) the 
adversary causes a computation error during signing that gives rise to a 
faulty signing equation s'=k-e'*d (mod n); (ii) the adversary has access 
to another non-faulty deterministic signature of the same message, 
thereby giving rise to another signing equation s=k-e*d(mod n), where 
e'<>e (mod n), whereby d:=(s-s')/(e'-e) (mod n).

Contrary to the case with RSA-CRT, with EdDSA the signer has no choice 
but to succumb to this potential attack, since the specification 
mandates deterministic generation of the ephemeral private key k 
(whereby re-signing with the same message m implies reuse of the same k 
value). Moreover, contrary to the case with RSA-CRT, the remedy of 
verifying the computed signature prior to releasing this in public does 
not work: the fault attack can be organized so that, in practice, faulty 
signatures often escape detection. As a side note, the verification 
comes at roughly 3x the cost of signing, so this check may be disabled 
(since considered too expensive a seat belt measure to adhere to).

The single-fault attack on EdDSA alluded to above could have been easily 
prevented, if only the specification would have afforded implementors 
the choice to pick the ephemeral private key k at random and fresh at 
each instantiation of the signature scheme. The specification, however, 
does not allow this, since it mandates determinism, and - moreover - a 
very specific way of realizing this determinism, via a hash function 
with prepended immutable secret string d0, where k:=h(do,m).

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

Another lesson to be learned here is that the work products of the CFRG 
should be critically examined. Unfortunately, garnering the interest of 
such critical thinkers to devote time to this group seems to be a 
challenge. Here, lack of discussion should not be taken to mean 
agreement or endorsement. Moreover, people remembering the (mostly 
unsanctioned) extremely poisonous and political climate on CFRG mailing 
lists at the time of RFC 8032 too well may hesitate to get involved 
again or may have abandoned ship for good, to CFRG's detriment.

A final word (on audience): if one would like to entice people from 
academia, who may be rewarded in terms of the "currency" of conference 
papers, to give things a look, clarity of writing would be a must. 
(Here, having an unreadable document does not help, since it forces, 
e.g., a researcher to rewrite this completely to jump across program 
committee hoops later on and poses "lost in translation" questions with 
the latter.) Of course, this is also required to entice people in 
industry to not simply ignore documents or put these on the bottom of 
stacks of material on to-do lists: also there time is valuable.

Rene

Ref:
[1] 
https://csrc.nist.gov/CSRC/media/Publications/fips/186/4/final/documents/comments-received-fips186-4-december-2015.pdf[
[2] https://mailarchive.ietf.org/arch/msg/cfrg/MOSFCwf5djn7FzjBjEbak1LwCiY/
[3] https://link.springer.com/content/pdf/10.1007/s001450010016.pdf

On 2022-01-31 4:10 a.m., BjÃ¶rn Haase wrote:
 >
 > Hello Rene,
 >
 > >DLP-based signature schemes, such as ECDSA, the Schnorr signature 
scheme (original,
 > full), ECGDSA, EC-KCDSA, or SM2, all share this "securely >generate
 > randomness" component. Frankly, it should be known by now (it is 2022,
 > after all) how to generate random integers in a specified >interval,
 > at least to people who have not been hiding under a rock.
 >
 > Iâ€™d really not under-estimate the amount of things that can go wrong
 > with RNG use in the real-world and unfortunately as you know history
 > prior to 2022 has shown that there were indeed attempts that tried to
 > nudge people using weird and likely backdoored RNG designs. Given that
 > background, I think that is obvious to all of us **why** Ed25519 has
 > been designed this way and why it is superior in important application
 > contextes and why it should really be tweaked in a non-deterministic
 > way for other application scenarios.
 >
 > Actually, the topic raises a side-aspect that is highly relevant IMO
 > for authors of I-D and RFC regarding the assumptions that we have
 > regarding the audience that we write I-D and RFC for at CFRG and
 > regarding the host systems our designs run on.
 >
 > E.g. should we expect expert knowledge regarding secure RNG design and
 > should we also consider embedded systems?
 >
 > This is an important question that comes up also for people like me
 > that try to find the best wording and structure for documents such as
 > the CPace RFC. I doubt that we currently all have a common picture
 > regarding the audience that we expect to read our working group results.
 >
 > In my perception we should assume that we are writing for 1) a general
 > application software designer (â€œarchitectâ€) Â and 2) application
 > software engineer (â€œimplementerâ€) and 3) a software verification
 > engineer (â€œtesterâ€), all without a security background and we 
probably
 > should not assume expert knowledge.
 >
 >
 > explicit for which use-case the documentâ€™s recommendations were
 > general â€œoffice environmentâ€ in mind when writing their documents.
 >
 > In my opinion the fact that hardware-related attacks will become also
 > relevant for internet-based devices such as IoT nodes probably should
 > motivate a slight shift in the structure of the RFC documents issued
 > by CFRG also to consider some attention to resource-constraints and
 > hardware-side-channels.
 >
 > For this reason, @CRFG and @CFRG-Chairs, Iâ€™d appreciate your feedback:
 >
 > Whatâ€™s your opinion here regarding the target audience and scope of
 > application scenarios to cover?
 >
 > Yours,
 >
 > BjÃ¶rn
 >
 > P.S.:
 >
 > We are just in the process of re-structuring the write-up for best
 > readability of the CPace draft and a common ground on the reader
 > groups to write for would be very valuable for us!
 >
 > For instance, we are currently seriously considering to remove the
 > Ristretto255 and Decaf448 subsections in order to reduce complexity
 > and avoid generating confusion in the group of application-oriented
 > readers which might not want a theoretical background but a clear
 > distinct and simple recommendation â€œdo it that way in your application
 > contextâ€.
 >
 > Mit freundlichen GrÃ¼ÃŸen I Best Regards
 >
 > Dr. BjÃ¶rn Haase

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

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 31 Jan 2022 21:14:04 +0000

To argue with Bjorn's point:

Yes, secure RNG design (and implementation) is not trivial. Not unlike designing (and implementing) secure ciphers or secure cryptographic protocols.

However, by now we both know how to design all of the above - and, which is more important - have already-available secure RNG, ciphers, etc. 

In view of that, I think it's more important to defend against practical Side Channel Attacks, than to avoid relying on good RNG because "people can screw up design or implementation of it".
--
Regards,
Uri
 
There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

On 1/31/22, 15:48, "CFRG on behalf of Rene Struik" <[email-masked] on behalf of [email-masked]> wrote:

    Hi Bjorn:

    Rene

    Ref:
    [1] 

    scheme (original,
    probably

    _______________________________________________
    CFRG mailing list
    [email-masked]
    https://www.irtf.org/mailman/listinfo/cfrg

---

From: Björn Haase <[email-masked]>
Date: Tue, 1 Feb 2022 07:58:58 +0000

Hello Rene,

Thank you for your feedback. Specifically I appreciate your suggestions and views regarding future document structures.

I think that this discussion here might still be poisoned by the lack of trust (in RNG) that is at the core of the RFC 8032 design. Most probably we will not be reaching a consensus whether or not we should trust a RNG provided by some operating system or closed-source chipset that we are not able to review.

More importantly this lack of trust seems also to have transferred to the communities – and the people -- that were actively involved in writing other standards (e.g. by NIST). I think that we should try to avoid any such connotation in any discussion.

Actually that’s what I meant to say with “we know why Ed25519 has been designed as is”: The deterministic signature design breathes the spirit “we should distrust the RNG provided to us by other possibly malicious players” and written in this spirit it now lacks the flexibility that we need in hostile environments regarding hardware-assisted attacks.

Actually I am convinced that apart of the “trust” aspect we have a quite similar perception of all the technical aspects of the topic.?

In order to avoid that the discussion gets too emotional I suggest to split this discussion in two parts.

  1.  What could we learn for future I-D and RFC?
How should we write it, for which audience and with which target platforms in mind?
Here, Rene, you seem to stress the point that we also should broaden the scope and consider what happens if the procedures of an RFC have to be carried out in hardware in hostile environments.

  2.  How to improve the existing RFC 8032 (might best be done discussing Mattson’s  “deterministic signatures with noise”) to cover not only the setting “I still don’t trust my external RNG but also want to get the flexibility add some mitigations regarding hardware-side-channels and faults”.

Yours,

Björn.

P.S::
Regarding fault attacks. I think that we should be very careful claiming superiority of any design with respect to the fault-injection setting. Any ECDSA design where you can just make a fault skip RNG is as broken as any EdDSA design where you can inject a fault at a bad place.

Dr. Björn Haase 

Disclaimer: