Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

From: "Dang, Quynh H. (Fed)" <[email-masked]>
Date: Tue, 3 Mar 2020 19:36:12 +0000

Hi John,

I think there are people who would like some noisy deterministic ECDSA/EdDSA options.

I would prefer (Z ||int2octets(x) ) over (int2octets(x) XOR Z) , and   (Z || prefix) over (prefix XOR Z)  for the following reasons.

1) For randomized hashing, the random value should get hashed first before the message for a SHA2 hash function ( even thought it is not the same thing here since a secret value is a part of the message).

2) Z1 and Z2 both are Z bits long and have Z bits of entropy.  (Z1 Xor Z2) have only Z bits of entropy, but Z1||Z2 have 2Z bits of entropy (if Z1 and Z2 are generated from 2 different seeds/entropy sources).

An extra Z bits long would cost at most 1 compression function for SHA-512 and it would likely not cost anything for SHAKE256.  So, the cost is minimal.

Regards,
Quynh.
________________________________
From: Cfrg <[email-masked]> on behalf of Tony Arcieri <[email-masked]>
Sent: Tuesday, December 17, 2019 12:30 PM
To: John Mattsson <john.mattsson=[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

This looks like a good document (so far you've managed to cover every nit I had to pick with it), however I think it might be a bad idea to describe your construction as "with Noise", in order to prevent confusion with the Noise Protocol, which among other things supports an Ed25519 signatures extension (which can, if one so desires, be used with XEdDSA):

https://noiseprotocol.org/<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fnoiseprotocol.org%2F&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648727502&sdata=yrPQ7K0144eU1d9x0IG%2F66Xjnr4BkZs%2FNzbXDELfrSU%3D&reserved=0>

Perhaps "with Added/Additional Entropy" instead?

On Tue, Dec 17, 2019 at 8:53 AM John Mattsson <john.mattsson=[email-masked]<mailto:[email-masked]>> wrote:
Hi,

I read up a lot more on recent research on side-channel and fault injection attacks on deterministic ECC signatures. This has increased my understanding that deterministic ECC signatures should not be recommended in environments where side-channel and fault injection attacks are a concern. One such environment is IoT deployments where the adversary can be assumed to have access to devices to induce faults and measure side-channels.

As many such embedded devices also lacks a good RNG, none of the currently standardized fully-randomized or fully-deterministic ECC signature algorithms seems like a good choice. I therefore think there is a need to specify deterministic ECC signatures with noise.

My colleagues and I started to write a draft specifying how a random noise can be added to the otherwise deterministic calculation of the per-message secret number. We ended up not proposing the solution chosen in XEdDSA as at least one research paper claims that XEdDSA does prevent their attack due to insufficient mixing of the hashed private key with the random noise.

The current document aims to give a quite broad overview with many references, suggests one possible construction for deterministic ECDSA and EdDSA, and lists several issues and TODOs. It should be discussed what the best construction is for achieving protection against fault and side-channel attacks, simplicity and ease of implementation, as well as efficiency. Comments are very welcome!

Cheers,
John

-----Original Message-----
From: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Date: Tuesday, 17 December 2019 at 16:33
To: John Mattsson <[email-masked]<mailto:[email-masked]>>, John Mattsson <[email-masked]<mailto:[email-masked]>>, Sini Ruohomaa <[email-masked]<mailto:[email-masked]>>, Erik Thormarker <[email-masked]<mailto:[email-masked]>>
Subject: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

    A new version of I-D, draft-mattsson-cfrg-det-sigs-with-noise-00.txt
    has been successfully submitted by John Preuß Mattsson and posted to the
    IETF repository.

    Name:               draft-mattsson-cfrg-det-sigs-with-noise
    Revision:   00
    Title:              Deterministic ECDSA and EdDSA Signatures with Noise
    Document date:      2019-12-17
    Group:              Individual Submission
    Pages:              14
    URL:            https://www.ietf.org/internet-drafts/draft-mattsson-cfrg-det-sigs-with-noise-00.txt<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Finternet-drafts%2Fdraft-mattsson-cfrg-det-sigs-with-noise-00..txt&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648737458&sdata=vk3J7iuIr1R0K0clMK4zE1j0Y72usGW21l3WWQ%2BpNEw%3D&reserved=0>
    Status:         https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/<https://gcc01.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%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648737458&sdata=Ztk7IuH0rNpiiJzz%2FzAscqior31KGMX0PNCOQD0vaa8%3D&reserved=0>
    Htmlized:       https://tools.ietf.org/html/draft-mattsson-cfrg-det-sigs-with-noise-00<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Ftools.ietf.org%2Fhtml%2Fdraft-mattsson-cfrg-det-sigs-with-noise-00&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648747401&sdata=GIW%2BfSFKyMR3cuxyJ9g5vWpN0gwBFXhkZlWLvfC%2Fqn8%3D&reserved=0>
    Htmlized:       https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Fdraft-mattsson-cfrg-det-sigs-with-noise&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648747401&sdata=RuBFhWEGgpGQlQLekhUd0%2FV9%2BGVMOg680fgERm1YWx8%3D&reserved=0>

    Abstract:
       Deterministic elliptic-curve signatures such as deterministic ECDSA
       and EdDSA have gained popularity over randomized ECDSA as their
       security do not depend on a source of high-quality randomness.
       Recent research has however found that implementations of these
       signature algorithms may be vulnerable to certain side-channel and
       fault injection attacks due to their determinism..  One countermeasure
       to such attacks is to add noise to the otherwise deterministic
       calculation of the per-message secret number.  This document updates
       RFC 6979 and RFC 8032 to recommend constructions with noise for
       deployments where side-channel attacks and fault injection attacks
       are a concern.

    Please note that it may take a couple of minutes from the time of submission
    until the htmlized version and diff are available at tools.ietf.org<https://gcc01.safelinks.protection.outlook.com/?url=http%3A%2F%2Ftools.ietf.org&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648757373&sdata=8wRNbI4K0fp%2FToU1LYrlDZJjYZUChULvw1sN1ynd4fA%3D&reserved=0>.

    The IETF Secretariat

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg<https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648757373&sdata=g%2FnCiXGEXtfaRGvv9tRVaz9CAcsVq0gbqmy32xNZE1o%3D&reserved=0>

--
Tony Arcieri

---

From: John Mattsson <[email-masked]>
Date: Mon, 9 Mar 2020 21:03:59 +0000

Thanks Tony,

Good suggestion, the name is also confusing for another reason, the side-channel descriptions of the draft use noise when talking to signal-to-noise. I’ll update the document to “Additional randomness” as entropy has precise but different meanings in various fields.

Cheers,
John

From: Cfrg <[email-masked]> on behalf of Tony Arcieri <[email-masked]>
Date: Tuesday, 17 December 2019 at 18:30
To: John Mattsson <john.mattsson=[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

https://noiseprotocol.org/<https://protect2.fireeye.com/v1/url?k=33cd4452-6f4766bb-33cd04c9-0cc47ad93e2e-a6467ecaa96f7be5&q=1&e=5b52830d-ee57-4f08-9055-29945f9eaa50&u=https%3A%2F%2Fnoiseprotocol.org%2F>

Cheers,
John

-----Original Message-----
From: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Date: Tuesday, 17 December 2019 at 16:33
To: John Mattsson <[email-masked]<mailto:[email-masked]>>, John Mattsson <[email-masked]<mailto:[email-masked]>>, Sini Ruohomaa <[email-masked]<mailto:[email-masked]>>, Erik Thormarker <[email-masked]<mailto:[email-masked]>>
Subject: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

    Name:               draft-mattsson-cfrg-det-sigs-with-noise
    Revision:   00
    Title:              Deterministic ECDSA and EdDSA Signatures with Noise
    Document date:      2019-12-17
    Group:              Individual Submission
    Pages:              14
    URL:            https://www.ietf.org/internet-drafts/draft-mattsson-cfrg-det-sigs-with-noise-00.txt<https://www.ietf.org/internet-drafts/draft-mattsson-cfrg-det-sigs-with-noise-00..txt>
    Status:         https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/
    Htmlized:       https://tools.ietf.org/html/draft-mattsson-cfrg-det-sigs-with-noise-00
    Htmlized:       https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise

    Abstract:

    Please note that it may take a couple of minutes from the time of submission
    until the htmlized version and diff are available at tools.ietf.org<http://tools.ietf.org>.

    The IETF Secretariat

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg<https://protect2.fireeye.com/v1/url?k=54f3cc81-0879ee68-54f38c1a-0cc47ad93e2e-4e1e45c3b2b270c4&q=1&e=5b52830d-ee57-4f08-9055-29945f9eaa50&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>

--
Tony Arcieri

---

From: John Mattsson <[email-masked]>
Date: Mon, 9 Mar 2020 21:34:32 +0000

Thanks for the review Quynh!

I agree that there are compelling reasons to do as you suggests. We never considered

( Z || prefix || PH(M) ).

We chose

( (prefix XOR Z) || PH(M) ) over the XEdDSA construction ( prefix || PH(M) || Z )

as https://eprint.iacr.org/2017/985.pdf states the the XEdDSA construction did not protect against all of their attacks due to insufficient mixing of the hashed private key with the additional randomness. Do you see any need to insert zeroes like

( Z || prefix || 000... || PH(M) )

as suggested by https://eprint.iacr.org/2017/985.pdf so that the first 1024-bit block of SHA-512 is composed only of the hashed private key and the random value, but not the message?

I agree with you that the cost of hashing operations are not really worth optimizing as their cost is negligible compared to the cost of the Elliptic curve point multiplications. We have not looked into how much additional security the zeroes gives in practice.

PS. We would also be very happy if NIST just went ahead and standardized some variant of  deterministic signatures with additional randomness in FIPS 186-5 :)

Cheers,
John

From: "Dang, Quynh H. (Fed)" <quynh.dang=[email-masked]>
Date: Tuesday, 3 March 2020 at 20:36
To: Tony Arcieri <[email-masked]>, John Mattsson <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

Hi John,

Regards,
Quynh.

Cheers,
John

-----Original Message-----
From: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Date: Tuesday, 17 December 2019 at 16:33
To: John Mattsson <[email-masked]<mailto:[email-masked]>>, John Mattsson <[email-masked]<mailto:[email-masked]>>, Sini Ruohomaa <[email-masked]<mailto:[email-masked]>>, Erik Thormarker <[email-masked]<mailto:[email-masked]>>
Subject: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

    Abstract:

    The IETF Secretariat

--
Tony Arcieri

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 9 Mar 2020 21:42:51 +0000

I too prefer

over

( (prefix XOR Z) || PH(M) ) 

Yes there is a reason for those zeroes.

From: Cfrg <[email-masked]> on behalf of John Mattsson <john.mattsson=[email-masked]>
Date: Monday, March 9, 2020 at 5:37 PM
To: "Dang, Quynh H. (Fed)" <quynh.dang=[email-masked]>, Tony Arcieri <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

We chose

Cheers,

John

Hi John,

Regards,

Quynh. 

https://noiseprotocol.org/

On Tue, Dec 17, 2019 at 8:53 AM John Mattsson <john.mattsson=[email-masked]> wrote:

Hi,

Cheers,
John

-----Original Message-----
From: "[email-masked]" <[email-masked]>
Date: Tuesday, 17 December 2019 at 16:33
To: John Mattsson <[email-masked]>, John Mattsson <[email-masked]>, Sini Ruohomaa <[email-masked]>, Erik Thormarker <[email-masked]>
Subject: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

    URL:            https://www.ietf.org/internet-drafts/draft-mattsson-cfrg-det-sigs-with-noise-00.txt

    Abstract:

    Please note that it may take a couple of minutes from the time of submission
    until the htmlized version and diff are available at tools.ietf.org.

    The IETF Secretariat

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

-- 

Tony Arcieri

---

From: John Mattsson <[email-masked]>
Date: Tue, 10 Mar 2020 05:44:58 +0000

Thanks Uri,

I’ll change the constructions in the next version to:

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

V || 0x00 || Z || int2octets(x) ||  000... || bits2octets(h1)

where

Z is chosen to be the same length as prefix / int2octets(x)

and

the number of zeroes 000... is chosen so that the length of 

dom2(F, C) || Z || prefix || 000...

V || 0x00 || Z || int2octets(x) ||  000...

is equal to the block length of the hash function.

Other choices for the length of Z would also be possible, like a fixed length of 32 or 64 bytes.

Cheers,

John

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Monday, 9 March 2020 at 22:43
To: John Mattsson <[email-masked]>, "Dang, Quynh H. (Fed)" <[email-masked]>, Tony Arcieri <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

I too prefer

over

We chose

Cheers,

John

Hi John,

Regards,

Quynh. 

 

Hi,

Cheers,
John

-----Original Message-----
From: "[email-masked]" <[email-masked]>
Date: Tuesday, 17 December 2019 at 16:33
To: John Mattsson <[email-masked]>, John Mattsson <[email-masked]>, Sini Ruohomaa <[email-masked]>, Erik Thormarker <[email-masked]>
Subject: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

    Abstract:
       fault injection attacks due to their determinism...  One countermeasure

    The IETF Secretariat

 

-- 

Tony Arcieri

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 10 Mar 2020 07:18:57 -0400

This should probably be aligned with the Threshold signature proposal if
accepted. Threshold signatures require either an additional commitment
round or random construction of all but the last the signature contribution
r_i values:

https://www.ietf.org/id/draft-hallambaker-threshold-sigs-02.html

Another related technique is Kocher side channel resistance through random
blinding now that Paul's original patent has expired (there may be others
of course).

On Tue, Mar 10, 2020 at 1:45 AM John Mattsson <john.mattsson=
[email-masked]> wrote:

> *From: *"Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
> *Date: *Monday, 9 March 2020 at 22:43
> *To: *John Mattsson <[email-masked]>, "Dang, Quynh H. (Fed)" <
> [email-masked]>, Tony Arcieri <[email-masked]>
> *Cc: *"[email-masked]" <[email-masked]>
> *Subject: *Re: [Cfrg] FW: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>
> I too prefer
>
>
>
> *From: *Cfrg <[email-masked]> on behalf of John Mattsson
> <john.mattsson=[email-masked]>
> *Date: *Monday, March 9, 2020 at 5:37 PM
> *To: *"Dang, Quynh H. (Fed)" <quynh.dang=[email-masked]>, Tony
> Arcieri <[email-masked]>
> *Cc: *CFRG <[email-masked]>
> *Subject: *Re: [Cfrg] FW: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>
> as https://eprint.iacr.org/2017/985.pdf states the the XEdDSA
> construction did not protect against all of their attacks due to insufficient
> mixing of the hashed private key with the additional randomness. Do you see
> any need to insert zeroes like
>
>
>
> as suggested by https://eprint.iacr.org/2017/985.pdf so that the first
> 1024-bit block of SHA-512 is composed only of the hashed private key and
> the random value, but not the message?
>
>
>
> I agree with you that the cost of hashing operations are not really worth
> optimizing as their cost is negligible compared to the cost of the Elliptic
> curve point multiplications. We have not looked into how much additional
> security the zeroes gives in practice.
>
>
>
> PS. We would also be very happy if NIST just went ahead and standardized
> some variant of  deterministic signatures with additional randomness in
> FIPS 186-5 :)
>
>
>
> Cheers,
>
> John
>
>
>
> *From: *"Dang, Quynh H. (Fed)" <quynh.dang=[email-masked]>
> *Date: *Tuesday, 3 March 2020 at 20:36
> *To: *Tony Arcieri <[email-masked]>, John Mattsson <
> [email-masked]>
> *Cc: *"[email-masked]" <[email-masked]>
> *Subject: *Re: [Cfrg] FW: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>
> Hi John,
>
>
>
> I would prefer (Z ||int2octets(x) ) over (int2octets(x) XOR Z) , and   (Z
> || prefix) over (prefix XOR Z)  for the following reasons.
>
>
>
> 1) For randomized hashing, the random value should get hashed first before
> the message for a SHA2 hash function ( even thought it is not the same
> thing here since a secret value is a part of the message).
>
>
>
> 2) Z1 and Z2 both are Z bits long and have Z bits of entropy.  (Z1 Xor Z2)
> have only Z bits of entropy, but Z1||Z2 have 2Z bits of entropy (if Z1 and
> Z2 are generated from 2 different seeds/entropy sources).
>
>
>
> An extra Z bits long would cost at most 1 compression function for SHA-512
> and it would likely not cost anything for SHAKE256.  So, the cost is
> minimal.
>
>
>
> Regards,
>
> Quynh.
> ------------------------------
>
> *From:* Cfrg <[email-masked]> on behalf of Tony Arcieri <
> [email-masked]>
> *Sent:* Tuesday, December 17, 2019 12:30 PM
> *To:* John Mattsson <john.mattsson=[email-masked]>
> *Cc:* [email-masked] <[email-masked]>
> *Subject:* Re: [Cfrg] FW: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>
> This looks like a good document (so far you've managed to cover every nit
> I had to pick with it), however I think it might be a bad idea to describe
> your construction as "with Noise", in order to prevent confusion with the
> Noise Protocol, which among other things supports an Ed25519 signatures
> extension (which can, if one so desires, be used with XEdDSA):
>
>
>
>
>
> <https://protect2.fireeye.com/v1/url?k=beccca08-e24600cb-becc8a93-86e1ed4002b1-b100179dffe9824e&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https%3A%2F%2Fgcc01.safelinks.protection.outlook.com%2F%3Furl%3Dhttps%253A%252F%252Fnoiseprotocol.org%252F%26data%3D02%257C01%257Cquynh.dang%2540nist.gov%257Ccf04b3b1a4264ee89f7108d78316e3dd%257C2ab5d82fd8fa4797a93e054655c61dec%257C1%257C1%257C637122006648727502%26sdata%3DyrPQ7K0144eU1d9x0IG%252F66Xjnr4BkZs%252FNzbXDELfrSU%253D%26reserved%3D0>
>
>
>
>
>
> I read up a lot more on recent research on side-channel and fault
> injection attacks on deterministic ECC signatures. This has increased my
> understanding that deterministic ECC signatures should not be recommended
> in environments where side-channel and fault injection attacks are a
> concern. One such environment is IoT deployments where the adversary can be
> assumed to have access to devices to induce faults and measure
> side-channels.
>
> As many such embedded devices also lacks a good RNG, none of the currently
> standardized fully-randomized or fully-deterministic ECC signature
> algorithms seems like a good choice. I therefore think there is a need to
> specify deterministic ECC signatures with noise.
>
> My colleagues and I started to write a draft specifying how a random noise
> can be added to the otherwise deterministic calculation of the per-message
> secret number. We ended up not proposing the solution chosen in XEdDSA as
> at least one research paper claims that XEdDSA does prevent their attack
> due to insufficient mixing of the hashed private key with the random noise.
>
> The current document aims to give a quite broad overview with many
> references, suggests one possible construction for deterministic ECDSA and
> EdDSA, and lists several issues and TODOs. It should be discussed what the
> best construction is for achieving protection against fault and
> side-channel attacks, simplicity and ease of implementation, as well as
> efficiency. Comments are very welcome!
>
> Cheers,
> John
>
> To: John Mattsson <[email-masked]>, John Mattsson <
> [email-masked]>, Sini Ruohomaa <[email-masked]>,
> Erik Thormarker <[email-masked]>
> Subject: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>     URL:
> https://www.ietf.org/internet-drafts/draft-mattsson-cfrg-det-sigs-with-noise-00.txt
> <https://protect2.fireeye.com/v1/url?k=117c199e-4df6d35d-117c5905-86e1ed4002b1-9fbf838aa5b9f48f&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https%3A%2F%2Fgcc01.safelinks.protection.outlook.com%2F%3Furl%3Dhttps%253A%252F%252Fwww.ietf.org%252Finternet-drafts%252Fdraft-mattsson-cfrg-det-sigs-with-noise-00..txt%26data%3D02%257C01%257Cquynh.dang%2540nist.gov%257Ccf04b3b1a4264ee89f7108d78316e3dd%257C2ab5d82fd8fa4797a93e054655c61dec%257C1%257C1%257C637122006648737458%26sdata%3Dvk3J7iuIr1R0K0clMK4zE1j0Y72usGW21l3WWQ%252BpNEw%253D%26reserved%3D0>
>     Status:
> https://datatracker.ietf.org/doc/draft-mattsson-cfrg-det-sigs-with-noise/
> <https://protect2.fireeye.com/v1/url?k=ddee9146-81645b85-ddeed1dd-86e1ed4002b1-204a929da59f550b&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https%3A%2F%2Fgcc01.safelinks.protection.outlook.com%2F%3Furl%3Dhttps%253A%252F%252Fdatatracker.ietf.org%252Fdoc%252Fdraft-mattsson-cfrg-det-sigs-with-noise%252F%26data%3D02%257C01%257Cquynh.dang%2540nist.gov%257Ccf04b3b1a4264ee89f7108d78316e3dd%257C2ab5d82fd8fa4797a93e054655c61dec%257C1%257C1%257C637122006648737458%26sdata%3DZtk7IuH0rNpiiJzz%252FzAscqior31KGMX0PNCOQD0vaa8%253D%26reserved%3D0>
>     Htmlized:
> https://tools.ietf.org/html/draft-mattsson-cfrg-det-sigs-with-noise-00
> <https://protect2.fireeye.com/v1/url?k=090d6bef-5587a12c-090d2b74-86e1ed4002b1-65823b9a478f65ed&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https%3A%2F%2Fgcc01.safelinks.protection.outlook.com%2F%3Furl%3Dhttps%253A%252F%252Ftools.ietf.org%252Fhtml%252Fdraft-mattsson-cfrg-det-sigs-with-noise-00%26data%3D02%257C01%257Cquynh.dang%2540nist.gov%257Ccf04b3b1a4264ee89f7108d78316e3dd%257C2ab5d82fd8fa4797a93e054655c61dec%257C1%257C1%257C637122006648747401%26sdata%3DGIW%252BfSFKyMR3cuxyJ9g5vWpN0gwBFXhkZlWLvfC%252Fqn8%253D%26reserved%3D0>
>     Htmlized:
> https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise
> <https://protect2.fireeye.com/v1/url?k=f37e8530-aff44ff3-f37ec5ab-86e1ed4002b1-6deb93e44c241ca2&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https%3A%2F%2Fgcc01.safelinks.protection.outlook.com%2F%3Furl%3Dhttps%253A%252F%252Fdatatracker.ietf.org%252Fdoc%252Fhtml%252Fdraft-mattsson-cfrg-det-sigs-with-noise%26data%3D02%257C01%257Cquynh.dang%2540nist.gov%257Ccf04b3b1a4264ee89f7108d78316e3dd%257C2ab5d82fd8fa4797a93e054655c61dec%257C1%257C1%257C637122006648747401%26sdata%3DRuBFhWEGgpGQlQLekhUd0%252FV9%252BGVMOg680fgERm1YWx8%253D%26reserved%3D0>
>
>
>     Abstract:
>     until the htmlized version and diff are available at tools.ietf.org
> <https://gcc01.safelinks.protection..outlook.com/?url=http%3A%2F%2Ftools.ietf.org&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648757373&sdata=8wRNbI4K0fp%2FToU1LYrlDZJjYZUChULvw1sN1ynd4fA%3D&reserved=0>
> .
>
>     The IETF Secretariat
>
>
>
> <https://protect2.fireeye.com/v1/url?k=f768d7b6-abe21d75-f768972d-86e1ed4002b1-bfbedd89a6a207ca&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https%3A%2F%2Fgcc01.safelinks.protection.outlook.com%2F%3Furl%3Dhttps%253A%252F%252Fwww.irtf.org%252Fmailman%252Flistinfo%252Fcfrg%26data%3D02%257C01%257Cquynh.dang%2540nist.gov%257Ccf04b3b1a4264ee89f7108d78316e3dd%257C2ab5d82fd8fa4797a93e054655c61dec%257C1%257C1%257C637122006648757373%26sdata%3Dg%252FnCiXGEXtfaRGvv9tRVaz9CAcsVq0gbqmy32xNZE1o%253D%26reserved%3D0>
>
>
>
>
> --
>
> Tony Arcieri

---

From: John Mattsson <[email-masked]>
Date: Wed, 11 Mar 2020 15:15:33 +0000

Hi Philip,

I think the current discussions (NISTIR 8214A and your drafts) to standardize different threshold schemes are very interesting and I think they will be practical in a lot situations. 

However, I don't think draft-hallambaker-threshold-sigs-02.html and draft-mattsson-cfrg-det-sigs-with-noise-02 should or need to be aligned. I think they are quite independent. The mechanisms in draft-hallambaker-threshold-sigs-02.html do not seem suitable to deploy today in constrained IoT devices as:

- The schemes are relatively heavy (for constrained IoT) as they increase the number of Elliptic curve point multiplications.
- The schemes require significant modifications to the implementation.
- The schemes are not for ECDSA
- The protection against fault attacks (active side-channel attacks) is to my understanding not well studied while the construction suggested in draft-mattsson-cfrg-det-sigs-with-noise-02 is analyzed and recommended in a lot of recent papers.
- The work to standardize threshold signatures will probably take some time.

Today, we have a situation where a lot of IoT devices have are or planning to implement deterministic ECC signatures. Most IoT deployments today use ECDSA, but EdDSA is getting some footprint in new deployments. IoT devices are often vulnerable to side-channel and fault injection attacks and my current view is that such IoT devices should not use purely deterministic ECC signatures. For this reasons, there is a strong need to as soon as possible standardize a very lightweight solution for both ECDSA and EdDSA that does not require substantial changes to the implementation.

Cheers,
John

From: Phillip Hallam-Baker <[email-masked]>
Date: Tuesday, 10 March 2020 at 12:19
To: John Mattsson <[email-masked]>
Cc: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>, "Dang, Quynh H. (Fed)" <[email-masked]>, Tony Arcieri <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

This should probably be aligned with the Threshold signature proposal if accepted. Threshold signatures require either an additional commitment round or random construction of all but the last the signature contribution r_i values:

Another related technique is Kocher side channel resistance through random blinding now that Paul's original patent has expired (there may be others of course).

On Tue, Mar 10, 2020 at 1:45 AM John Mattsson <john.mattsson=mailto:[email-masked]> wrote:
Thanks Uri,

 
where

and

 

Cheers,
John
 
From: "Blumenthal, Uri - 0553 - MITLL" <mailto:[email-masked]>
Date: Monday, 9 March 2020 at 22:43
To: John Mattsson <mailto:[email-masked]>, "Dang, Quynh H. (Fed)" <mailto:[email-masked]>, Tony Arcieri <mailto:[email-masked]>
Cc: "mailto:cfrg@irtf..org" <mailto:[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt
 
I too prefer

over

 
From: Cfrg <mailto:[email-masked]> on behalf of John Mattsson <john.mattsson=mailto:[email-masked]>
Date: Monday, March 9, 2020 at 5:37 PM
To: "Dang, Quynh H. (Fed)" <quynh.dang=mailto:[email-masked]>, Tony Arcieri <mailto:[email-masked]>
Cc: CFRG <mailto:[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

 
 
We chose

 
 
as suggested by https://eprint.iacr..org/2017/985.pdf so that the first 1024-bit block of SHA-512 is composed only of the hashed private key and the random value, but not the message?

 
Cheers,
John
 
From: "Dang, Quynh H. (Fed)" <quynh.dang=mailto:[email-masked]>
Date: Tuesday, 3 March 2020 at 20:36
To: Tony Arcieri <mailto:[email-masked]>, John Mattsson <mailto:[email-masked]>
Cc: "mailto:[email-masked]" <mailto:[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt
 
Hi John,

 

 
Regards,
Quynh. 

From: Cfrg <mailto:[email-masked]> on behalf of Tony Arcieri <mailto:[email-masked]>
Sent: Tuesday, December 17, 2019 12:30 PM
To: John Mattsson <john.mattsson=mailto:[email-masked]>
Cc: mailto:[email-masked] <mailto:[email-masked]>
Subject: Re: [Cfrg] FW: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt 

https://protect2.fireeye.com/v1/url?k=beccca08-e24600cb-becc8a93-86e1ed4002b1-b100179dffe9824e&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fnoiseprotocol.org%2F&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648727502&sdata=yrPQ7K0144eU1d9x0IG%2F66Xjnr4BkZs%2FNzbXDELfrSU%3D&reserved=0

 
On Tue, Dec 17, 2019 at 8:53 AM John Mattsson <john.mattsson=mailto:[email-masked]> wrote:
Hi,

Cheers,
John

-----Original Message-----
From: "mailto:[email-masked]" <mailto:[email-masked]>
Date: Tuesday, 17 December 2019 at 16:33
To: John Mattsson <mailto:[email-masked]>, John Mattsson <mailto:[email-masked]>, Sini Ruohomaa <mailto:[email-masked]>, Erik Thormarker <mailto:[email-masked]>
Subject: New Version Notification for draft-mattsson-cfrg-det-sigs-with-noise-00.txt

    Name:               draft-mattsson-cfrg-det-sigs-with-noise
    Revision:   00
    Title:              Deterministic ECDSA and EdDSA Signatures with Noise
    Document date:      2019-12-17
    Group:              Individual Submission
    Pages:              14
    URL:            https://protect2.fireeye.com/v1/url?k=117c199e-4df6d35d-117c5905-86e1ed4002b1-9fbf838aa5b9f48f&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Finternet-drafts%2Fdraft-mattsson-cfrg-det-sigs-with-noise-00..txt&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648737458&sdata=vk3J7iuIr1R0K0clMK4zE1j0Y72usGW21l3WWQ%2BpNEw%3D&reserved=0
    Status:         https://protect2.fireeye.com/v1/url?k=ddee9146-81645b85-ddeed1dd-86e1ed4002b1-204a929da59f550b&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https://gcc01.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%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648737458&sdata=Ztk7IuH0rNpiiJzz%2FzAscqior31KGMX0PNCOQD0vaa8%3D&reserved=0
    Htmlized:       https://protect2.fireeye.com/v1/url?k=090d6bef-5587a12c-090d2b74-86e1ed4002b1-65823b9a478f65ed&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Ftools.ietf.org%2Fhtml%2Fdraft-mattsson-cfrg-det-sigs-with-noise-00&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648747401&sdata=GIW%2BfSFKyMR3cuxyJ9g5vWpN0gwBFXhkZlWLvfC%2Fqn8%3D&reserved=0
    Htmlized:       https://protect2.fireeye.com/v1/url?k=f37e8530-aff44ff3-f37ec5ab-86e1ed4002b1-6deb93e44c241ca2&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Fdraft-mattsson-cfrg-det-sigs-with-noise&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648747401&sdata=RuBFhWEGgpGQlQLekhUd0%2FV9%2BGVMOg680fgERm1YWx8%3D&reserved=0

    Abstract:

    Please note that it may take a couple of minutes from the time of submission
    until the htmlized version and diff are available at https://gcc01.safelinks.protection..outlook.com/?url=http://tools.ietf.org&data=[email-masked]|cf04b3b1a4264ee89f7108d78316e3dd|2ab5d82fd8fa4797a93e054655c61dec|1|1|637122006648757373&sdata=8wRNbI4K0fp/ToU1LYrlDZJjYZUChULvw1sN1ynd4fA=&reserved=0.

    The IETF Secretariat

_______________________________________________
Cfrg mailing list
mailto:[email-masked]
https://protect2.fireeye.com/v1/url?k=f768d7b6-abe21d75-f768972d-86e1ed4002b1-bfbedd89a6a207ca&q=1&e=9ab9ccab-2de7-4dee-bbec-0a0da2647812&u=https://gcc01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&data=02%7C01%7Cquynh.dang%40nist.gov%7Ccf04b3b1a4264ee89f7108d78316e3dd%7C2ab5d82fd8fa4797a93e054655c61dec%7C1%7C1%7C637122006648757373&sdata=g%2FnCiXGEXtfaRGvv9tRVaz9CAcsVq0gbqmy32xNZE1o%3D&reserved=0

mailto:[email-masked]

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 11 Mar 2020 12:40:45 -0400

On Wed, Mar 11, 2020 at 11:15 AM John Mattsson <[email-masked]>
wrote:

> Hi Philip,
>
> I think the current discussions (NISTIR 8214A and your drafts) to
> standardize different threshold schemes are very interesting and I think
> they will be practical in a lot situations.
>
> However, I don't think draft-hallambaker-threshold-sigs-02.html and
> draft-mattsson-cfrg-det-sigs-with-noise-02 should or need to be aligned. I
> think they are quite independent. The mechanisms in
> draft-hallambaker-threshold-sigs-02.html do not seem suitable to deploy
> today in constrained IoT devices as:
>
> - The schemes are relatively heavy (for constrained IoT) as they increase
> the number of Elliptic curve point multiplications.
>

If you are doing threshold, the use of Kocher blinding is free because the
blinding can be distributed across the implementations.

> - The schemes require significant modifications to the implementation.

My scheme requires a non-deterministic signature. I can make use of your
scheme to do that. So I cam make my draft dependent on yours. It is
obviously not desirable to do the reverse.

> - The schemes are not for ECDSA

The math works for ECDSA as well. The reason I didn't include it in my
draft is that is a NIST spec, and NIST has announced work in this area. So
I am anticipating they will provide their own spec in due course. If not,
we can do a draft here if there is demand. But for the time being, best to
focus on the CFRG signatures.

The other reason for not doing ECDSA is that nobody is paying me to do this
stuff right now. It is clear that in the short term threshold ECDSA is of
great interest so we can secure code signing. If someone wants to support
my work, I will be more than happy to work out how to apply the schemes to
that algorithm and how to make use of it. My company does not require
ECDSA, we only use the CFRG curves and as Barzini put it, "we are not
communists".

> - The protection against fault attacks (active side-channel attacks) is to
> my understanding not well studied while the construction suggested in
> draft-mattsson-cfrg-det-sigs-with-noise-02 is analyzed and recommended in a
> lot of recent papers.
>

Which looks like an argument to reference your draft in mine.

> - The work to standardize threshold signatures will probably take some

Very much so.

> Today, we have a situation where a lot of IoT devices have are or planning
> to implement deterministic ECC signatures. Most IoT deployments today use
> ECDSA, but EdDSA is getting some footprint in new deployments. IoT devices
> are often vulnerable to side-channel and fault injection attacks and my
> current view is that such IoT devices should not use purely deterministic
> ECC signatures. For this reasons, there is a strong need to as soon as
> possible standardize a very lightweight solution for both ECDSA and EdDSA
> that does not require substantial changes to the implementation.
>

One issue that we both need to address is whether we cut new signature IDs
for the non deterministic variants. I would like us to do that as soon as
possible for the CFRG curves.

There is an application that depends on Sig(A, k) == Sig (A, k) for all
messages A and k. In particular, BitCoin assumes the uniqueness of
signatures to avoid double spending. That is (allegedly) what caused the
collapse of MtGox

We don't need to decide how we do non deterministic to roll out identifiers
for the non deterministic sig values. And threshold sigs can share those
identifiers.