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

From: Stephen Farrell <[email-masked]>
Date: Fri, 28 Jan 2022 21:14:18 +0000

Hiya,

The IETF LAKE wg [1] are developing the edhoc protocol [2]
which aims to be a TLS-like protocol usable in highly
constrained device scenarios. As part of that the wg are
trying to decide which (if any) ciphersuite(s) to recommend
be mandatory to implement. Part of that is comparing suites
using eddsa with suites using ecdsa.

An argument [3,4] has been made that eddsa has significant
issues in this context as fault injection may be relatively
simple to attempt. As this argument isn't really specific to
edhoc I wanted to forward it here in case there's any useful
further information to be had about that.

Specifically, I wondered how one might compare the risks of
this kind of attack against eddsa versus issues with ecdsa
implementations in the constrained device context. Even more
specifically, I'd love to know if an entity capable of
mounting this attack could or could not as easily mount an
equivalently bad attack against ecdsa as commonly implemented
in such devices.

Lastly, if this weakness is as serious as claimed then it'd
be a fine thing if CFRG wanted to address that.

Thanks,
Stephen.

PS: Responses to this will be most useful in the next couple
of weeks as the LAKE wg try figure out what to do about this.

[1] https://datatracker.ietf.org/wg/lake/
[2] https://datatracker.ietf.org/doc/draft-ietf-lake-edhoc/
[3] https://mailarchive.ietf.org/arch/msg/lake/0-9X6McGoQCoqZ0q2v97eH9i4iY/
[4] 
https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 30 Jan 2022 09:36:25 +0000

Stephen Farrell <[email-masked]> writes:

>Responses to this will be most useful in the next couple of weeks as the LAKE
>wg try figure out what to do about this.

This is more a general question than one specifically about eddsa vs. ecdsa,
but if the intent is to create a TLS-like protocol then why not just do an RFC
around WireGuard, which is already widely deployed, formally verified, and
proven in the field?

Conversely, why would someone choose edhoc when WireGuard already does more or
less the same thing?

Peter.

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 30 Jan 2022 10:39:05 +0100

Hi Stephen,

Yes, deterministic nonces in ECDSA / EdDSA are an increased risk for fault attacks, and they also increase the attack surface for other side-channels such as SPA and DPA.  ECDSA is not usually implemented with deterministic nonces, so this particular risk is usually higher with EdDSA.

Trevor Perrin suggests [1] adding a random input to EdDSA to mitigate fault attacks.  His method hashes the key, the message and the random input in order to mitigate both fault attacks (because the nonce should be almost uniformly random) and problems with the random source (because if the RNG fails, the nonce is still a PRF of the message).  The resulting signature scheme would be fully compatible with RFC8032-compliant verifiers, though of course the signer is not compliant.

Note that [1] also uses a different key format, but this is for unrelated reasons.  The same strategy would work with ordinary EdDSA.

Cheers,
— Mike

[1] https://signal.org/docs/specifications/xeddsa/#security-considerations

> On Jan 28, 2022, at 10:14 PM, Stephen Farrell <[email-masked]> wrote:
> 
> 
> Hiya,
> 
> [4] https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise
> <OpenPGP_0x5AB2FAF17B172BEA.asc>_______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: John Mattsson <[email-masked]>
Date: Sun, 30 Jan 2022 11:48:38 +0000

Hi,

Purely deterministic per-message nonces are highly problematic both in IoT devices and in multi-signer settings. The question is if ECDSA with purely random per-message nonces are better? The reason behind purely deterministic per-message nonces was the problems with purely random per-message nonces. There is currently no standard for ECDSA or EdDSA on how to combine randomness with the deterministic mechanisms.

It would be good if CFRG or NIST could standardize something. My draft is is in "Candidate RG Document"-limbo after I told the chairs that I would not analyse other companies IPR.
https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise-02

One plan was to instead specify purely randomized EdDSA or EdDSA where the per-message nonce generation is more unspecified. But neither of these solutions are optimal, and one of my co-authors was against both.

A standard on how to add random noise to the deterministic signature mechanisms are one of the most features that NIST received in the comments on FIPS 186-5 (Draft).
https://csrc.nist.gov/publications/detail/fips/186/5/draft

Cheers,
John

From: CFRG <[email-masked]> on behalf of Mike Hamburg <[email-masked]>
Date: Sunday, 30 January 2022 at 10:39
To: Stephen Farrell <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [CFRG] eddsa (un)suited for mandatory to implement ciphersuite?
Hi Stephen,

Cheers,
— Mike

On Jan 28, 2022, at 10:14 PM, Stephen Farrell <[email-masked]<mailto:[email-masked]>> wrote:

Hiya,

Thanks,
Stephen.

[1] https://datatracker.ietf.org/wg/lake/
[2] https://datatracker.ietf.org/doc/draft-ietf-lake-edhoc/
[3] https://mailarchive.ietf.org/arch/msg/lake/0-9X6McGoQCoqZ0q2v97eH9i4iY/
[4] https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise
<OpenPGP_0x5AB2FAF17B172BEA.asc>_______________________________________________
CFRG mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg<https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-40f7d10cf9eb7c69&q=1&e=61ff2276-5fa1-48ea-8b24-bca20a2cf9df&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>

---

From: John Mattsson <[email-masked]>
Date: Sun, 30 Jan 2022 12:25:22 +0000

>I wondered how one might compare the risks of
>implementations in the constrained device context.

My understanding is that purely deterministic ECDSA offers worse protection than purely deterministic EdDSA when it comes to some kinds of side-channel attacks. EdDSA is more secure than ECDSA when it comes to other kinds of side-channel attacks (that was one of the reasons behind EdDSA). Purely randomized ECDSA mitigates some kinds side-channel attacks but has other problems. If you ignore the per-message nonce generation and the lack of hash algorithm agility, EdDSA is in general superior to ECDSA. I don’t think the way forward is to embrace ECDSA, I think it is to fix the problems with EdDSA.

I think the main question is deterministic per-message nonces vs. random per-message nonces. Not EdDSA vs ECDSA.

John

From: CFRG <[email-masked]> on behalf of John Mattsson <john.mattsson=[email-masked]>
Date: Sunday, 30 January 2022 at 12:49
To: Mike Hamburg <[email-masked]>, Stephen Farrell <[email-masked]>
Cc: [email-masked] <[email-masked]>
Subject: Re: [CFRG] eddsa (un)suited for mandatory to implement ciphersuite?
Hi,

Cheers,
John

Cheers,
— Mike

Hiya,

Thanks,
Stephen.

---

From: Rene Struik <[email-masked]>
Date: Sun, 30 Jan 2022 12:06:09 -0500

Hi Mike:

Your remark that "The resulting signature scheme would be fully 
compatible with RFC8032-compliant verifiers, though of course the signer 
is not compliant." also applies to a version where the ephemeral signing 
key k is fixed (e.g., set to k:=1).

Question is to whether it matters what is in a spec or whether only 
processing behavior counts. I think it does matter *greatly* and should 
to people who do not just care about "compliant with RFC xyz" or other 
standards stickers. This matters even more with RFCs that advertise 
claimed superior security and with work products originating from the 
"Cryptography Forum Research Group", since most people are likely to 
take claims of RFCs originating from CFRG at face value, without much 
further own due diligence.

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.

Rene

On 2022-01-30 4:39 a.m., Mike Hamburg wrote:
> Hi Stephen,
>
> Yes, deterministic nonces in ECDSA / EdDSA are an increased risk for 
> fault attacks, and they also increase the attack surface for other 
> side-channels such as SPA and DPA.  ECDSA is not usually implemented 
> with deterministic nonces, so this particular risk is usually higher 
> with EdDSA.
>
> Trevor Perrin suggests [1] adding a random input to EdDSA to mitigate 
> fault attacks.  His method hashes the key, the message and the random 
> input in order to mitigate both fault attacks (because the nonce 
> should be almost uniformly random) and problems with the random source 
> (because if the RNG fails, the nonce is still a PRF of the message). 
>  The resulting signature scheme would be fully compatible with 
> RFC8032-compliant verifiers, though of course the signer is not compliant.
>
> Note that [1] also uses a different key format, but this is for 
> unrelated reasons.  The same strategy would work with ordinary EdDSA.
>
> Cheers,
> — Mike
>
>> [3] 
>> https://mailarchive.ietf.org/arch/msg/lake/0-9X6McGoQCoqZ0q2v97eH9i4iY/
>> [4] 
> _______________________________________________
> CFRG mailing list
> [email-masked]

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 30 Jan 2022 19:30:11 +0200

On Sun, Jan 30, 2022 at 11:48:38AM +0000, John Mattsson wrote:
> Hi,
> 
> Purely deterministic per-message nonces are highly problematic both in
> IoT devices and in multi-signer settings. The question is if ECDSA
> with purely random per-message nonces are better? The reason behind
> purely deterministic per-message nonces was the problems with purely
> random per-message nonces. There is currently no standard for ECDSA
> or EdDSA on how to combine randomness with the deterministic
> mechanisms.
>
> It would be good if CFRG or NIST could standardize something. My
> draft is is in "Candidate RG Document"-limbo after I told the chairs
> that I would not analyse other companies IPR.
> One plan was to instead specify purely randomized EdDSA or EdDSA where
> the per-message nonce generation is more unspecified. But neither of
> these solutions are optimal, and one of my co-authors was against
> both.
> 
> A standard on how to add random noise to the deterministic signature
> mechanisms are one of the most features that NIST received in the
> comments on FIPS 186-5 (Draft).

AFAIK, the dominant problem with purely random nonces is that it is
akin to flathatting: There is almost no margin for error with the RNG:
It has to be essentially perfect, or the private key leaks.

A bit less risky (but still risky) construction would be to collect some
extra entropy (perhaps with some extra counters) and hash it down to
nonce.

(A pathological crypto flathatter would code "Ed25519" with 32 octet
random nonce (56 octets for "Ed448") straight from RNG.)

Maybe a stupid idea on how to make noisy EdDSA: Overwrite the IV of
the first hash with random value. If coding in C or C++, that seems
like it might be easy thing to do (memory safety, how do you spell
that? :-) ).

Another problem with EdDSA I have heard about in context of IoT is
the hash functions: SHA-512 is not very convinient for constrained
devices. On signing side, replacing SHA-512 with SHA-256 in Edwards25519
would only break key expansion (the 32 byte output is barely enough for
the nonce). And of course the nonce has to vary with the hash.

Not that ECDSA is free of problems with hash functions: I have seen
NIST get ECDSA with SHA-3 wrong (and the code in GnuTLS does not look
right to me).

-Ilari

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 30 Jan 2022 18:44:07 +0100

Hi Rene,

I don’t think I completely understand your meaning here.

My point about being compatible with verifiers is that if CFRG wants to change or extend the RFC, then it will not require software changes from verifiers — only signers that need this countermeasure would have to change, or perhaps some niche software that takes advantage of the determinism (compliance testing, eg).

The security of the change is orthogonal to the interoperability concern.  But an appropriate combination of hashing and randomness is more secure, at least in a typical threat model, than either of those steps alone.  So it makes sense to consider allowing it in the spec.  We would want to say exactly how to do it though.

Cheers,
— Mike

> On Jan 30, 2022, at 6:06 PM, Rene Struik <[email-masked]> wrote:
> 
> Hi Mike:
> 
> Your remark that "The resulting signature scheme would be fully compatible with RFC8032-compliant verifiers, though of course the signer is not compliant." also applies to a version where the ephemeral signing key k is fixed (e.g., set to k:=1). 
> 
> Question is to whether it matters what is in a spec or whether only processing behavior counts. I think it does matter *greatly* and should to people who do not just care about "compliant with RFC xyz" or other standards stickers. This matters even more with RFCs that advertise claimed superior security and with work products originating from the "Cryptography Forum Research Group", since most people are likely to take claims of RFCs originating from CFRG at face value, without much further own due diligence.
> 
> 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. 
> 
> Rene
> 
>> [1] https://signal.org/docs/specifications/xeddsa/#security-considerations <https://signal.org/docs/specifications/xeddsa/#security-considerations>
>> 
>>> On Jan 28, 2022, at 10:14 PM, Stephen Farrell <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>> 
>>> Hiya,
>>> 
>>> [1] https://datatracker.ietf.org/wg/lake/ <https://datatracker.ietf.org/wg/lake/>
>>> [2] https://datatracker.ietf.org/doc/draft-ietf-lake-edhoc/ <https://datatracker.ietf.org/doc/draft-ietf-lake-edhoc/>
>>> [3] https://mailarchive.ietf.org/arch/msg/lake/0-9X6McGoQCoqZ0q2v97eH9i4iY/ <https://mailarchive.ietf.org/arch/msg/lake/0-9X6McGoQCoqZ0q2v97eH9i4iY/>
>>> [4] https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise <https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise>
>>> [email-masked] <mailto:[email-masked]>
>>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
>> 
>> 
>> 
>> [email-masked] <mailto:[email-masked]>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> 
> -- 
> email: [email-masked] <mailto:[email-masked]> | Skype: rstruik

---

From: Benjamin Kaduk <[email-masked]>
Date: Sun, 30 Jan 2022 23:06:49 -0800

> Conversely, why would someone choose edhoc when WireGuard already does more or

The output of the LAKE WG is guided by
https://www.ietf.org/archive/id/draft-ietf-lake-reqs-04.html, most notably
https://www.ietf.org/archive/id/draft-ietf-lake-reqs-04.html#name-lightweight

On a quick skim of https://www.wireguard.com/protocol/ it does not seem to
care about conserving bytes (and understandably so, given its target use
cases).

-Ben

---

From: Jack Grigg <[email-masked]>
Date: Mon, 31 Jan 2022 12:57:10 +0000

> https://www.ietf.org/archive/id/draft-ietf-lake-reqs-04.html#name-lightweight

Quoting this definition:

'lightweight' refers to:

>    - resource consumption, measured by bytes on the wire, wall-clock time
>    and number of round trips to complete, or power consumption
>    - the amount of new code required on end systems which already have an
>    OSCORE stack
>
> The design constraints under which Wireguard was developed, resulted in a
protocol that satisfies most (if not all) of the given definition of
"lightweight". Jason is on the record [0] as saying that as part of his
focus of "this is suitable for going into the kernel":

   - The protocol needed to be as close to one round trip as possible
   (Wireguard is precisely 1RT).
   - The protocol needed minimal state.
   - The implementation needed to be small (both for "as little new code as
   possible" reasons, and "the codebase can fit in my head" secure impl
   understanding reasons).

Another part of the design (I don't know if this was driven by kernel
considerations) is that the state machine is silent: if it isn't receiving
messages, it isn't doing anything. This greatly reduces the "resource
consumption" focus: the only resources consumed by the protocol are the
stored state (the protocol needs 80 bytes per connection for the keys and
counters), and the CPU/memory required to process a received message.

The most CPU-heavy aspect of Wireguard is the ECDH operations: it requires
four DH() calls at each end (plus generation of an ephemeral keypair on
each side, which requires one DH_PUBKEY() that could be prepared ahead of
time if needed). So that is the relevant operation to consider in terms of
power consumption.

[0] SCW Podcast Episode 9. Transcript:
https://securitycryptographywhatever.buzzsprout.com/1822302/9667632-wireguard-feat-jason-donenfeld

> care about conserving bytes (and understandably so, given its target use

I don't know if byte conservation was an explicit goal going in, but
stealth was a focus (the silent state machine being one aspect of that),
and having fewer bytes on the wire is relevant to that focus. Concretely,
the initiator's handshake message is 148 bytes, and the responder's
handshake message is 92 bytes, while all data messages have a fixed
overhead of 16 bytes. These are noticeably lower than the protocols it was
designed as an alternative to (OpenVPN, IPSec).

There are a few places where the protocol could have been trimmed further,
but Wireguard is built around the Noise protocol framework (specifically
using the Noise IK pattern), which helps to simplify security analysis, but
placed some constraints on e.g. how ciphertexts are constructed (the
initiator's handshake packet contains two separate AEAD ciphertexts for the
static key and the payload, instead of one containing both, due to how
HandshakeState.WriteMessage is defined [1]).

[1] http://www.noiseprotocol.org/noise.html#the-handshakestate-object

Jack

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 31 Jan 2022 15:30:51 +0000

Hiya,

> that I would not analyse other companies IPR.
I'm told that the IPR reference above relates to an earlier
mail to this list [1] that does indeed refer to possible IPR.
That mail refers to [2]. When I look at [2] I see it says
"Status Expired - Fee Related." Personally, I don't know how
to interpret that, but were it the case that the relevant
filing had been abandoned, I guess that could be helpful
in term of progressing the relevant draft. [3]

Does anyone know enough to interpret that status information?
If so, and you tell me, I'd be fine with doing a 3rd party
IPR disclosure on [3]. (I'm fine if someone wanted to send
me off-list mail to help me understand that status, if
sending to the list isn't desirable.)

Of course, it would be way better if someone familiar
with [2] (e.g. someone related to the assignee which
seems to be qualcomm) were in a position to do a normal
IPR disclosure. (The form for those is at [4] in case
that helps.)

Thanks,
S.

[1] https://mailarchive.ietf.org/arch/msg/cfrg/AHM9cQlezMv-RGKxmxg7tcI2ceQ/
[2] https://patents.google.com/patent/US9621525B2/en
[3] 
https://datatracker.ietf.org/doc/html/draft-mattsson-cfrg-det-sigs-with-noise-02
[4] https://datatracker.ietf.org/ipr/about/