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

[Phillip Hallam-Baker <[e-mail]>]

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=
[e-mail]> wrote:

> 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" <[e-mail]>
> *Date: *Monday, 9 March 2020 at 22:43
> *To: *John Mattsson <[e-mail]>, "Dang, Quynh H. (Fed)" <
> [e-mail]>, Tony Arcieri <[e-mail]>
> *Cc: *"[e-mail]" <[e-mail]>
> *Subject: *Re: [Cfrg] FW: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>
> I too prefer
>
>
>
> ( Z || prefix || 000... || PH(M) )
>
>
>
> over
>
>
>
> ( (prefix XOR Z) || PH(M) )
>
>
>
> Yes there is a reason for those zeroes.
>
>
>
> *From: *Cfrg <[e-mail]> on behalf of John Mattsson
> <john.mattsson=[e-mail]>
> *Date: *Monday, March 9, 2020 at 5:37 PM
> *To: *"Dang, Quynh H. (Fed)" <quynh.dang=[e-mail]>, Tony
> Arcieri <[e-mail]>
> *Cc: *CFRG <[e-mail]>
> *Subject: *Re: [Cfrg] FW: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>
> 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=[e-mail]>
> *Date: *Tuesday, 3 March 2020 at 20:36
> *To: *Tony Arcieri <[e-mail]>, John Mattsson <
> [e-mail]>
> *Cc: *"[e-mail]" <[e-mail]>
> *Subject: *Re: [Cfrg] FW: New Version Notification for
> draft-mattsson-cfrg-det-sigs-with-noise-00.txt
>
>
>
> 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 <[e-mail]> on behalf of Tony Arcieri <
> [e-mail]>
> *Sent:* Tuesday, December 17, 2019 12:30 PM
> *To:* John Mattsson <john.mattsson=[e-mail]>
> *Cc:* [e-mail] <[e-mail]>
> *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://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>
>
>
>
>
>
> Perhaps "with Added/Additional Entropy" instead?
>
>
>
> On Tue, Dec 17, 2019 at 8:53 AM John Mattsson <john.mattsson=
> [e-mail]> 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: "[e-mail]" <[e-mail]>
> Date: Tuesday, 17 December 2019 at 16:33
> To: John Mattsson <[e-mail]>, John Mattsson <
> [e-mail]>, Sini Ruohomaa <[e-mail]>,
> Erik Thormarker <[e-mail]>
> 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://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:
>        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
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
> <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
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>