Subject: Re: [Cfrg] Call for adoption draft-mattsson-cfrg-det-sigs-with-noise

From: Russ Housley <[email-masked]>
Date: Wed, 6 May 2020 11:26:00 -0400

I think that CFRG should move forward with this document.

Russ

> Dear CFRG participants,
> This email commences a 2-week call for adoption for draft-mattsson-cfrg-det-sigs-with-noise-02 that will end on May 12th 2020:
> 
> https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/ <https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/>  
> 
> Please give your views on whether this document should be adopted as a CFRG draft, and if so, whether you'd be willing to help work on it/review it. Please reply to this email (or in exceptional circumstances you can email CFRG chairs directly at [email-masked] <mailto:[email-masked]>).
> 
> Thank you,
> Stanislav (for the chairs)

---

From: Dan Brown <[email-masked]>
Date: Wed, 6 May 2020 17:49:35 +0000

It seems fine to adopt this, but a few things should be checked.

Procedurally, randomizing signatures is a *reversal* of CFRG consensus towards determinism, so maybe past discussions on CFRG are worth reviewing (I have forgotten the arguments). Maybe determinism proponents are too busy to check here, and should be briefly queried.

https://mailarchive.ietf.org/arch/msg/cfrg/NKiP_VOxTNI6lhukz7BP1Dh5kkk/

https://mailarchive.ietf.org/arch/msg/cfrg/QI6-EXVWtcAwBc6WakKl5YmZZlA/

https://mailarchive.ietf.org/arch/msg/cfrg/76HvHx_wXgIZJDr2COO8xQM8tZA/

How much side-channel resistance is gained from randomization? A mild gain sounds plausible to me, but I would to defer to side channel experts, e.g., if they think they think it a loss.  Perhaps determinism + side channel exposes the same bits over and over again (e.g. if the signed message is the constant), but randomization + side channel exposes new bits (for a constant message), making randomized more vulnerable?

I wonder if some applications of signatures now rely on non-standard, off-label properties of signatures, e.g. determinism (or non-determinism for older applications).  (Non-standard here means something 

different from Goldwasser-Micali-Rivest unforgeability against adaptive chosen message attacks.)  For example, maybe EdDSA is somewhere being used like a verifiable hash?  (Ok, any verifier reliance on determinism is probably insecure, because the signer switch over to non-determinism.)

Should we continue to name these “deterministic” signatures, if the plan is to make them non-deterministic?  

How about message-dependent signatures, since both components of the signature (R,S) will depend on the message? Or message-keyed, to emphase that R must depend on M, not just S.  (Multi-word phrases have precedents, I am reminded of nonce-misuse resistance, thought does not fit here.)

I am partly repeating here my past suggestions to CFRG, where I argued that it would be “deterministic” (but insecure!) to always re-use the same ephemeral key (aka nonce, per-message secret).  Hence “deterministic signature” is like naming an armored car, a “heavy car”. 

Dan

From: Cfrg <[email-masked]> On Behalf Of Stanislav V. Smyshlyaev
Sent: Tuesday, April 28, 2020 7:23 AM
To: CFRG <[email-masked]>
Cc: [email-masked]
Subject: [Cfrg] Call for adoption draft-mattsson-cfrg-det-sigs-with-noise

Dear CFRG participants,

https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/ <https://urldefense.proofpoint.com/v2/url?u=https-3A__datatracker.ietf.org_doc_draft-2Dmattsson-2Dcfrg-2Ddet-2Dsigs-2Dwith-2Dnoise_&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=ydtZz5PC4Sux3jOiCX58oVZerBsDmsFrMLrXoTd40sc&s=2Hv35e8ePak-1MtzQnsFFQG5R1VOOCG1zZHav675APw&e=>   

Please give your views on whether this document should be adopted as a CFRG draft, and if so, whether you'd be willing to help work on it/review it. Please reply to this email (or in exceptional circumstances you can email CFRG chairs directly at [email-masked] <mailto:[email-masked]> ).

Thank you,

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Natanael <[email-masked]>
Date: Thu, 7 May 2020 11:57:56 +0200

Den ons 6 maj 2020 19:49Dan Brown <[email-masked]> skrev:

> Procedurally, randomizing signatures is a **reversal** of CFRG consensus
> towards determinism, so maybe past discussions on CFRG are worth reviewing
> (I have forgotten the arguments). Maybe determinism proponents are too busy
> to check here, and should be briefly queried.
>
>From my reading & in my layman's opinion, the primary goal of deterministic
designs is to reduce the risk of bad entropy sources breaking the system.
So it wouldn't be too much of a change of course when the goal is to
increase robustness of the use of entropy, IMHO. But acknowledging the
change makes sense.

I wonder if some applications of signatures now rely on non-standard,
> off-label properties of signatures, e.g. determinism (or non-determinism
> for older applications).  (Non-standard here means something
>
> different from Goldwasser-Micali-Rivest unforgeability against adaptive
> chosen message attacks.)  For example, maybe EdDSA is somewhere being used
> like a verifiable hash?  (Ok, any verifier reliance on determinism is
> probably insecure, because the signer switch over to non-determinism.)
>

There's a separate class of functions called VRF (verifiable random
functions) that should be used if what you need specifically is something
that is equivalent to reliably deterministic signatures.

I've seen cryptocurrency projects rely on assumptions of deterministic
signatures and getting attacked because of it, but these designs were
flawed from the start and probably shouldn't be catered to. People making
assumptions like this needs to verify if the algorithm / implementation
actually provides those properties before using them. It would be much
better in cases like this to explicitly explain which properties are
provided and which aren't, so that flawed choices like this aren't made by
implementors in the first place.

Should we continue to name these “deterministic” signatures, if the plan is
> to make them non-deterministic?
>
> How about message-dependent signatures, since both components of the
> signature (R,S) will depend on the message? Or message-keyed, to emphase
> that R must depend on M, not just S.  (Multi-word phrases have precedents,
> I am reminded of nonce-misuse resistance, thought does not fit here.)
>

I'm reminded of the term "ciphertext stealing" from the XTS cipher mode.
The signature (it parts of it) always was message dependent, but maybe
"entropy stealing" or similar phrasing could be used since we take secret
randomness from additional sources to make the signature algorithm more
robust.

Maybe a more neutral term like "entropy combining" would work better.
"Entropy combining signatures".

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 7 May 2020 17:29:39 +0000

The way I see it (and I confess that I didn’t dive into this at all ;):

Security of randomized signatures depends on availability of a good RNG on the platform.
To mitigate the absence of a good reliable RNG, people defined deterministic signatures. 
Deterministic signatures appear vulnerable to side-channel attacks.
To mitigate these side-channel risks without re-introducing the need for a good RNG, “some” randomness is added.

So, to the Dan’s point – it’s  not a “reversal”, because it doesn’t expect a great RNG to be present. It merely hopes to get “some” randomness sufficient to mitigate side-channel attacks. While the “mostly” deterministic algorithm foils cryptographic attacks that exploit poor randomness.

Did I get it right? ;-)

From: Cfrg <[email-masked]> on behalf of Natanael <[email-masked]>
Date: Thursday, May 7, 2020 at 05:59
To: Dan Brown <[email-masked]>
Cc: CFRG <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] Call for adoption draft-mattsson-cfrg-det-sigs-with-noise

>From my reading & in my layman's opinion, the primary goal of deterministic designs is to reduce the risk of bad entropy sources breaking the system. So it wouldn't be too much of a change of course when the goal is to increase robustness of the use of entropy, IMHO. But acknowledging the change makes sense. 

There's a separate class of functions called VRF (verifiable random functions) that should be used if what you need specifically is something that is equivalent to reliably deterministic signatures. 

I've seen cryptocurrency projects rely on assumptions of deterministic signatures and getting attacked because of it, but these designs were flawed from the start and probably shouldn't be catered to. People making assumptions like this needs to verify if the algorithm / implementation actually provides those properties before using them. It would be much better in cases like this to explicitly explain which properties are provided and which aren't, so that flawed choices like this aren't made by implementors in the first place. 

I'm reminded of the term "ciphertext stealing" from the XTS cipher mode. The signature (it parts of it) always was message dependent, but maybe "entropy stealing" or similar phrasing could be used since we take secret randomness from additional sources to make the signature algorithm more robust. 

Maybe a more neutral term like "entropy combining" would work better. "Entropy combining signatures".

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 12 May 2020 16:48:43 -0700

I didn't study the algorithms in detail, but this seems generally sensible
and worth adopting. I agree with others that we probably should change the
title to avoid confusion.

-Ekr

On Tue, Apr 28, 2020 at 4:23 AM Stanislav V. Smyshlyaev <[email-masked]>
wrote:

> https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/
>
>
> Please give your views on whether this document should be adopted as a
> CFRG draft, and if so, whether you'd be willing to help work on it/review
> it. Please reply to this email (or in exceptional circumstances you can
> email CFRG chairs directly at [email-masked]).
>
> Thank you,
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Hannes Tschofenig <[email-masked]>
Date: Wed, 13 May 2020 13:14:59 +0000

I have asked my co-workers to review the draft and Janos Follath responded. He thinks that this idea to add randomness makes perfect sense.

Here is his response on the discussion points listed in the draft:

  *   One of the goals of the document is to provide the same security level against side channel attacks as a randomised scheme. Using 16 bytes of randomness with Ed25519 fails to achieve this: Ed25519 has 128 bit security, using 128 bits of random data results in collisions after 2^64 signatures (the attack we are defending against already assumes that the attacker can trick the device into signing the same message repeatedly) and every collision reduces the noise in the attacker’s measurements. The overhead is minimal, this is a standard that should recommend good practices, I don’t think this is the right place trying to gain performance improvements.
  *   This question seems to be rather off-topic for this RFC. Nevertheless my thoughts: Whether we use HMAC or KMAC, the schemes are secure, the difference is a minor performance gain. Both variants generate valid signatures, the verifier does not need to know which was used to generate the signature, thus there is no compatibility issue between the two variants. Including both in the IETF standard would allow implementors to choose between NIST compliance and a slight performance gain. (Of course if NIST can be convinced to approve a KMAC-DRBG in SP 800-90-A or diverge from that construction in FIPS 186-5, then everybody can just use KMAC.) That being said, if I had to decide, I would stick with HMAC: the performance gain of KMAC is minimal and SHA2 is still around, I wouldn’t want to risk implementors accidentally trying to use SHA2 with KMAC under any circumstances.

Here are my personal thoughts on this entire topic:

Classical ECDSA required a random value for signature creation.

Then, RFC 6979 was written because there was a concern about environments that do not have access to a source of high-quality randomness. This concern has often been stated in context of Internet of Things devices. You can read about these concerns even in recent IETF documents, such as https://tools.ietf.org/html/draft-ietf-ace-coap-est-18. In that document the authors added a technique to have server-generated keys that are then sent to IoT devices to deal with the lack of a good source of high-quality randomness.

Now, with draft-mattsson-cfrg-det-sigs-with-noise we are adding randomness back into RFC 6979.

Are we now back to where we started?

Ciao
Hannes

From: Cfrg <[email-masked]> On Behalf Of Eric Rescorla
Sent: Wednesday, May 13, 2020 1:49 AM
To: Stanislav V. Smyshlyaev <[email-masked]>
Cc: CFRG <[email-masked]>; [email-masked]
Subject: Re: [Cfrg] Call for adoption draft-mattsson-cfrg-det-sigs-with-noise

I didn't study the algorithms in detail, but this seems generally sensible and worth adopting. I agree with others that we probably should change the title to avoid confusion.

-Ekr

On Tue, Apr 28, 2020 at 4:23 AM Stanislav V. Smyshlyaev <[email-masked]<mailto:[email-masked]>> wrote:
Dear CFRG participants,
This email commences a 2-week call for adoption for draft-mattsson-cfrg-det-sigs-with-noise-02 that will end on May 12th 2020:

Please give your views on whether this document should be adopted as a CFRG draft, and if so, whether you'd be willing to help work on it/review it. Please reply to this email (or in exceptional circumstances you can email CFRG chairs directly at [email-masked]<mailto:[email-masked]>).

Thank you,
Stanislav (for the chairs)
_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Rene Struik <[email-masked]>
Date: Wed, 13 May 2020 09:23:10 -0400

Dear colleagues:

It is by now obvious that the current deterministic signature schemes EdDSA (RFC 8032) and
det-ECDSA (RFC 6979) can be trivially attacked in practice. So, clearly something must be done
about this.

I would suggest another approach than John Mattson's, though, which is more fundamental and
avoids hard-coding a specific mandated way of generating ephemeral private key altogether (after
all, random number generators can be implemented in more than one way).

I do not think labeling the fix as only "RECOMMENDED" is sufficient: the original schemes are
fundamentally flawed for wide-scale adoption and the fix should be surrounded by stronger "MUST"
language.

On a non-technical note, I am curious how RFC 8032 came to be, even though the fault attacks were
well-known prior to issuing the standard. I have not checked all email threads at the time, but
remember that, e.g., Manfred Lochter from BSI has repeatedly made this point inside and outside
the CFRG.

More details on suggested alternative approach below.

==

My understanding of the issues:

a) deterministic EdDSA and ECDSA impose side-channel and fault attack risk, due to way
ephemeral private keys are generated;
b) {from comments John Mattson to draft FIPS 186-5 (these comments have now finally
been posted, I saw this week)}: EdDSA with SHA-256 would be good with IoT applications

CFRG proposal John Mattson addresses an aspect of a), but not b).

Would one be open to a slightly enlarged proposal towards addressing a), but that also makes
it easier to realize b)?

In my mind, we could do the following:

1) define Schnorr signature generation and verification more generally, with random
generation ephemeral private keys;
2) specify instantiation with Ed25519/SHA512/LSB-lsb encoding and Edwards448/SHAKE/LSB-lsb
encoding, which would be fully compatible for verifiers with RFC 8032;
-- this includes informative section on how to generate ephemeral private key k as
k:=H(d0,rnd,m) (mod n).

Result:
i) This would allow cleaning up RFC 8032 (as John's draft does), but with following differences:
-- generation of ephemeral private keys k could also be in different way (e.g., for HW vendors
that already have good RNG on board), so as to allow only one pass of message to be signed,
rather than two with current Pure EdDSA specification.
-- more separation of specification and implementation details, so that RFC does not have to
be rewritten once more implementation vulnerabilities are discovered (since
not impacting specification).
ii) This would easily allow specification of EdDSA, but now randomized and with SHA256 instead
of SHA512 {addressing your point b)}.

Tangential effects:
iii) This would making all kinds of other CFRG drafts easy to describe (e.g., vrf drafts);
iv) This would allow Schnorr to be used with P-256 and SHA-256 as well;
v) This would help in describing Opaque password proposal, which (if one uses HMQV) requires a
Schnorr scheme under the hood (HMQV is, loosely speaking, based on Schnorr).

One of the side benefits of this is that we stop the recent practice of CFRG to produce drafts
that are a curious mix of specification and implementation details (which makes all of this
academic paper generator in the SCA-space).

Best regards, Rene

On 4/28/2020 7:23 AM, Stanislav V. Smyshlyaev wrote:
> Dear CFRG participants,
> This email commences a 2-week call for adoption for 
> draft-mattsson-cfrg-det-sigs-with-noise-02 that will end on May 12th 2020:
>
> CFRG draft, and if so, whether you'd be willing to help work on 
> it/review it. Please reply to this email (or in exceptional 
> circumstances you can email CFRG chairs directly at 
> [email-masked] <mailto:[email-masked]>).
>
> Thank you,

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

---

From: "Dang, Quynh H. (Fed)" <[email-masked]>
Date: Wed, 13 May 2020 13:33:02 +0000

Hi the CFRG chairs,

I personally support adoption of the draft as a starting point because I think in some situations a randomization method may help to improve security.

Sorry for this late response.

Regards,
Quynh.

________________________________
From: Cfrg <[email-masked]> on behalf of Stanislav V. Smyshlyaev <[email-masked]>
Sent: Tuesday, April 28, 2020 7:23 AM
To: CFRG <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: [Cfrg] Call for adoption draft-mattsson-cfrg-det-sigs-with-noise

Dear CFRG participants,

https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/<https://gcc02.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-mattsson-cfrg-det-sigs-with-noise%2F&data=02%7C01%7Cquynh.dang%40nist.gov%7C1ca218621f2f47b6f32c08d7eb66acbb%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C0%7C637236698539882118&sdata=qzHiPhuo8ND1aizWWCeWdjXbYng9%2BhNZ79W1tYeL%2FQE%3D&reserved=0>

Thank you,

---

From: "Riad S. Wahby" <[email-masked]>
Date: Wed, 13 May 2020 10:45:14 -0700

> all, random number generators can be implemented in more than one way).

Said perhaps too glibly (apologies): random number generators can
be implemented in more than one way, and most of those ways are
bad. We've been running the "everyone do your own RNGs" experiment
for a few decades now and it seems like it's still failing.

CFRG should thoroughly vet an approach and mandate it. Folks who
really really want to do something else can still do so in a way
that preserves interoperability.

I'm in favor of adopting the draft, but concur with those calling
for a name change.

Just my 2μ¢,

-=rsw

---

From: Billy Brumley <[email-masked]>
Date: Fri, 15 May 2020 06:45:59 +0300

It's neat to see all the interest in augmenting deterministic
signature schemes with opportunistic randomness!

I had a similar idea long ago:

https://patents.google.com/patent/US9621525B2/en

I'm not the patent holder, but those interested in supporting this
draft or implementing it should be aware of the IPR risks -- the
patent explicitly calls out RFC 6979.

On a side note, my team has volunteered a lot of our time to
supplement unit tests for OpenSSL over the years. What's nice about
pure determinism is the ability to check KATs without hijacking RNG
paths. As soon as any randomness comes in, the tests become extremely
fragile. My 2c.

BBB

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 15 May 2020 00:48:15 -0400

I support this work and I am willing to review.

There are advantages to a deterministic approach but also some drawbacks
beyond the side channel attack mitigation.

The big downside to a non deterministic scheme is that once the sig scheme
is non deterministic, it becomes impossible to audit a sealed HSM. But I
still think it is useful to describe a process for determining k from a set
of inputs that include a random nonce value, a secret value and some value
that depends on the public key pair that is used.

This is about closing the unintended side channel from the HSM and that is
important. But there is also the intentional side channel attack in which
the HSM vendor intends to leak the key. If the attacker knows the messages
that are signed and their signatures, they can leak the key one bit at a
time by generating multiple values for k and picking an R value that has
particular properties.

So if you want belt and braces, you also want a threshold signature scheme.
But not (alas) the single pass version I am currently using. You need to
get a commitment on R before the HSM sees the message digest to be signed.

---

From: Dan Brown <[email-masked]>
Date: Fri, 15 May 2020 15:49:13 +0000

A Eurocrypt 2020 paper says this kind of de-randomization is also more fault-tolerant:

https://iacr.org/submit/files/slides/2020/eurocrypt/ec2020/231/slides.pdf

Fault-tolerance is not my area, perhaps some details are relevant if CFRG adopts this work.

Dan

Dear CFRG participants,

Thank you,

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 15 May 2020 16:07:39 +0000

This presentation seems very relevant, and  pretty clear. 

BTW, I support adoption of the proposed draft. 

Regards,
Uri

Sent from my iPhone

> On May 15, 2020, at 11:50, Dan Brown <[email-masked]> wrote:
> 
> 
> Please give your views on whether this document should be adopted as a CFRG draft, and if so, whether you'd be willing to help work on it/review it. Please reply to this email (or in exceptional circumstances you can email CFRG chairs directly at [email-masked]).
> 
> Thank you,

---

From: Natanael <[email-masked]>
Date: Tue, 19 May 2020 13:52:17 +0200

> "Entropy combining signatures".

Adding one more terminology suggestion - terminology like "whitening" seems
like a good fit, taken from papers on RNG:s and entropy extractors. Those
functions are designed to take potentially biased inputs and produce
uniform outputs.

So perhaps "keyed entropy whitening" would be a suitable name?

So then you'd call it a signature with entropy whitening (I think you can
leave it implied that the whitening function is keyed and deterministic).