Subject: Re: [CFRG] EdDSA square roots (RFC 8032)

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 14 Feb 2022 10:19:17 +0200

On Sun, Jan 30, 2022 at 09:45:36PM +0000, John Mattsson wrote:
> I agree with Paul that RFC8032bis would make a lot of sense. In
> addition to the issues discussed in this thread:
> 
> - Purely deterministic per-message nonces are highly problematic both
>   in IoT devices and in multi-signer settings. The issues are so
>   significant that the only choices are to not use EdDSA or to
>   implement the signing in a non-compliant way.
> 
> - Current constrained IoT devices use SHA-256 (in the future maybe
>   SHAKE256, KangarooTwelve, or NIST LWC). Implementing SHA-512 just
>   for EdDSA is not likely to happen. If EdDSA do not support the
>   _hash_ function supported on the device, they will likely use ECDSA
>   instead.

(Have fun with bit order if using ECDSA with SHAKE256 or
KangarooTwelve... I do not think the latter is even defined).

And I do not think it is possible to make EdDSA use SHA-256. What one
could do is define a new signature algorithm that is similar to what
EdDSA would be with arbitrary signature algorithm.

One example construction (closely modelled after Ed25519):

Parameters:

 * A group.
   + Assumed to be dlog-hard.
   + Generator G, of order l.
   + has constant-length octet-string encoding.
 * Hash function H
   + Assumed to be preimage-resistant.
   + Assumed to be from octets to octets.

Keygen:

1) Generate a random number a in range [1,l).
2) Let A=a*G (scalar multiplication)
3) Public key is encode(A), private key is a.

Signing:

1) Let r be random/noisy/deterministic per-message nonce in range
   [0,256^roctets), where roctets is big enough (what is big enough
   depends on l).
2) Let R = r*G (scalar multiplication)
3) Let h = le_decode(H(encode(R)|encode(A)|M))
4) Let s = (r+h*a)%l
5) Signature is encode(R)|le_encode(s). Where s is encoded using minimal
   constant-length encoding.

Note: If G is chosen so that l is the same as in Ed25519, then roctets
is at least 32. For l equal to one in Ed448, roctets is at least 56. One
way of determining roctets is to pick least value that gives entropy
loss of less than 1/sqrt(l).

Note: If G is chosen to be the same group as in Ed25519, and H is chosen
to be SHA-512, then the signatures will with overwhelming probability
pass Ed25519 signature verification. On the other hand, no natural
choice of G and H gives something compatible with Ed448.

Verifying:

1) Decode R, A and s. If decoding fails, reject.
2) Let h = le_decode(H(encode(R)|encode(A)|M))
3) Check s*G =? R + h*A holds  (*'s are scalar multiplications).

Note: For some beyond-standard-signature-security properties, check that
the encodings are canonical, and R and A have high order. Any legimate
signature is extremely unlikely to fail these checks.

For prehashing, I think it is better to do that at higher layer, which
can apply things like salting hashes in order to counter some attacks
against hash function used. 

Then if one really wants to optimize code size, there is qDSA,
which can share vast majority of code with montgomery-ladder key
exchange code, like unclamped curve25519.

-Ilari

---

From: John Mattsson <[email-masked]>
Date: Tue, 15 Feb 2022 06:42:08 +0000

>exchange code, like unclamped curve25519.

Yes, I agree. I strongly think CFRG should look more at all aspects of signatures for IoT. It would then make more sense to look at new designs such as qDSA. I re-read the qDSA paper. It seems very promising with:

- Small memory footprint.
- Small code size.
- Only one type of key (and code) for DH and signatures.
- Fast (lower latency is good. Not sure power consumption is a practical problem).

I think it could make a lot of sense to standardize qDSA with a variable-length hash function like SHAKE128. SHA-256 is the old standard, I don't think we need to drag that into the future.

Cheers,
John

From: CFRG <[email-masked]> on behalf of Ilari Liusvaara <[email-masked]>
Date: Monday, 14 February 2022 at 09:20
To: [email-masked] <[email-masked]>
Subject: Re: [CFRG] EdDSA square roots (RFC 8032)

Parameters:

 * A group.

Keygen:

Signing:

Verifying:

-Ilari

_______________________________________________
CFRG mailing list
[email-masked]
https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-40f7d10cf9eb7c69&q=1&e=bc1044a0-1981-4657-818f-5ae3dd11e71d&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg

---

From: John Mattsson <[email-masked]>
Date: Tue, 15 Feb 2022 08:53:03 +0000

> Not sure power consumption is a practical problem.

Some clarification: Power consumption from signatures and DH might not significant for deployments with infrequent use of AKE and firmware update. But if used often like in protection of multicast requests it can definitely be significant.

From: CFRG <[email-masked]> on behalf of John Mattsson <john.mattsson=[email-masked]>
Date: Tuesday, 15 February 2022 at 07:43
To: Ilari Liusvaara <[email-masked]>, [email-masked] <[email-masked]>
Subject: Re: [CFRG] EdDSA square roots (RFC 8032)

Cheers,
John

Parameters:

 * A group.

Keygen:

Signing:

Verifying:

-Ilari

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 15 Feb 2022 12:08:41 +0100

> Some clarification: Power consumption from signatures and DH might not significant for deployments with infrequent use of AKE and firmware update. But if used often like in protection of multicast…

It can also be significant if an attacker can trigger execution of these algorithms beyond what would normally be needed only infrequently.

(That’s why having a “friend in the network” — cf. https://www.ietf.org/archive/id/draft-bormann-t2trg-sworn-05.html for a way to organize this — can be necessary.)

Grüße, Carsten

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 15 Feb 2022 14:30:50 +0200

On Tue, Feb 15, 2022 at 06:42:08AM +0000, John Mattsson wrote:
> Yes, I agree. I strongly think CFRG should look more at all aspects
> of signatures for IoT. It would then make more sense to look at new
> designs such as qDSA. I re-read the qDSA paper. It seems very
> promising with:
> 
> I think it could make a lot of sense to standardize qDSA with a
> variable-length hash function like SHAKE128. SHA-256 is the old
> standard, I don't think we need to drag that into the future.

IIRC, there was an error in one of the formulas in qDSA paper.

Looking at the paper, it seems that the error is in step 3 of algorithm
2: That step should read:

if B_ZZ*x^2 − B_XZ*x + B_XX = 0 then return True

As that step is supposed to be formula (2) with Z^R=1. The coefficient
of X^R^2 (which corresponds to x^2) is B_ZZ for some reason.

I found my notes about signatures on Curve25519 (based on qDSA),
here is a brief version (playing fast and loose with typing):

Keygen:

1) Generate a in [1,l)
2) Compute A <- a*G
3) Public key is A, private key is a.

Signing:

1) Generate nonce r.
2) Compute R <- r*G
3) Compute h <- H(R||A||M)
4) Compute h <- abs(h) (in Z_l)
5) Compute s <- (r+h*a)%l
6) Signature is R||s.

Verification:

1) Compute h <- H(R||A||M)
2) Compute h <- abs(h) (in Z_l)
3) Compute Px/Pz <- s*G  (may be projective)
4) Compute Qx/Qz <- h*A  (may be projective)
5) Compute u <- (Px*Qx-Pz*Qz)^2+((Px*Qz-Pz*Qx)*R)^2 (mod p)
6) Compute v <- ((Px*Qx+Pz*Qz)*(Px*Qz+Pz*Qx)+2*Ac*Px*Qx*Pz*Qz)*R*2 (mod p)
7) Check u =? v.

Where G is basepoint, H is hsah, Ac is the constant appearing in the
Montgomery curve equation (486662 for Curve25519).

As note, if one assumes standard signature security and the Montgomery
curve is complete (Curve25519 and Curve448 are both complete), then zero
and on curve checks can be omitted, because it turns out that for any
zero or not on curve point, either the check equation always fails, or
impiles R=h*A, which is very difficult to arrange due to the hash.

One weakness of qDSA is that it looks to be nontrivial to extend it to
BSM security, while such extensions are very simple for EdDSA-like
schemes.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Tue, 15 Feb 2022 09:20:39 -0500

Hi John:

You wrote: "Only one type of key (and code) for DH and signatures".

Doesn't co-factor ECDH and ECDSA with NIST's P-256 curve (or with 
short-Weierstrass curve Wei25519 [1]) already do this? Or, doesn't this 
count, since not sexy enough, or not coming from the right stable? BTW - 
it would be trivial to define Schnorr signatures (if that is the only 
thing that counts) with short-Weierstrass curves, without introducing 
yet more zoos of variants, roll-yet-something-new encoding formats, 
confusion, etc.

BTW - qDSA is again deterministic (to fit with the dogma of the day). 
There is nothing to preclude implementation of Ed25519 with Montgomery 
ladders (where only verification speed suffers compared to "Shamir's 
trick"), so I do not see the competitive advantage (but am happy to be 
educated here).

What would the benefit be of taking on yet another shiny object now? 
Shouldn't one first try and fix the current half-baked (pardon le mot) 
mess?

Rene

Ref: [1] 
https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/
(see also 
https://www.ietf.org/archive/id/draft-struik-lwig-curve-representations-00.txt 
of Nov 17, 2017)

On 2022-02-15 1:42 a.m., John Mattsson wrote:
> Yes, I agree. I strongly think CFRG should look more at all aspects of 
> signatures for IoT. It would then make more sense to look at new 
> I think it could make a lot of sense to standardize qDSA with 
> avariable-length hash function like SHAKE128. SHA-256 is the old 
> *From: *CFRG <[email-masked]> on behalf of Ilari Liusvaara 
> <[email-masked]>
> *Date: *Monday, 14 February 2022 at 09:20
> *To: [email-masked] <[email-masked]>
> *Subject: *Re: [CFRG] EdDSA square roots (RFC 8032)
>
> <https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-40f7d10cf9eb7c69&q=1&e=bc1044a0-1981-4657-818f-5ae3dd11e71d&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>
>
>
> https://www.irtf.org/mailman/listinfo/cfrg

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

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 15 Feb 2022 15:08:53 +0000

I second the concern here. What are the advantages of qDSA over ECDSA and EdDSA? 

How many “pre-Quantum” signature algorithms to we want to standardize, and why?

Also, shouldn’t we specify the algorithms in a way conducive to validation testing? E.g., recall the discussion about implementer “forgetting” to add PH(M).

--

Regards,

Uri

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

From: CFRG <[email-masked]> on behalf of Rene Struik <[email-masked]>
Date: Tuesday, February 15, 2022 at 09:21
To: John Mattsson <john.mattsson=[email-masked]>, Ilari Liusvaara <[email-masked]>, CFRG <[email-masked]>
Subject: [CFRG] (Re: EdDSA square roots (RFC 8032))

Hi John:

Doesn't co-factor ECDH and ECDSA with NIST's P-256 curve (or with short-Weierstrass curve Wei25519 [1]) already do this? Or, doesn't this count, since not sexy enough, or not coming from the right stable? BTW - it would be trivial to define Schnorr signatures (if that is the only thing that counts) with short-Weierstrass curves, without introducing yet more zoos of variants, roll-yet-something-new encoding formats, confusion, etc.

BTW - qDSA is again deterministic (to fit with the dogma of the day). There is nothing to preclude implementation of Ed25519 with Montgomery ladders (where only verification speed suffers compared to "Shamir's trick"), so I do not see the competitive advantage (but am happy to be educated here).

What would the benefit be of taking on yet another shiny object now? Shouldn't one first try and fix the current half-baked (pardon le mot) mess? 

Rene

Ref: [1] https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ 

(see also https://www.ietf.org/archive/id/draft-struik-lwig-curve-representations-00.txt of Nov 17, 2017)

- Small code size.

Cheers,

John

Parameters:

 * A group.

Keygen:

Signing:

Verifying:

-Ilari 

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

---

From: John Mattsson <[email-masked]>
Date: Wed, 16 Feb 2022 11:05:08 +0000

> I second the concern here. What are the advantages of qDSA over ECDSA and EdDSA?

If the numbers in the qDSA paper hold up it seems significantly more efficient when it comes to memory footprint, code size, speed, and energy consumption. I think it makes a lot of sense for a research group like CFRG to evaluate new designs like qDSA. IF the numbers hold up and IF there are no big disadvantages, I think a signature scheme with the performance numbers presented in the qDSA paper could be a welcome addition to COSE, HPKE, and other protocols used in constrained IoT.

>How many “pre-Quantum” signature algorithms to we want to standardize, and why?

So far I think CFRG has published one ECC based (EdDSA) and two hash-based (XMSS and LMS) signature schemes. The EdDSA work did not focus on IoT. It was agreed that CFRG might come back to signatures focusing on IoT. I think more CFRG work considering IoT would be very welcome.

Right now we don't know if CRQCs will ever exist or how many decades it could take. In 20 years, we might have CRQCs or we might have a situation where funding to quantum computing development perished (due to lack of use cases or technical difficulties) and we are thankful that we continued work on Elliptic Curve Cryptography.

For profiles like US CNSA used in non-constrained systems to protect TOP SECRET information that need to stay secret for a long, long time (75 years?) it makes a lot of sense to switch to PQC as soon as possible. The situation in constrained IoT is very different. Many constrained IoT systems today do not use any cryptography or rely on symmetric group keys. The current size of PQC signatures and keys are unusable for some use cases in constrained IoT systems (both devices and radio might be constrained). The struggle right now is to get these systems to use ECC instead of “no security” or symmetric group keys. Any system using ECC needs to be aware of the development of quantum computers, but many systems will likely continue to use ECC and switch algorithms if/when the CRQC threat is more tangible. For some constrained use cases, the switch would unfortunately likely be back to symmetric group keys (with very weak security properties) instead of asymmetric PQC. For some use cases like using Non-Interactive Key Exchange (NIKE) in groups, there is not even any PQC standardization ongoing.

Cheers,
John

From: CFRG <[email-masked]> on behalf of Blumenthal, Uri - 0553 - MITLL <[email-masked]>
Date: Tuesday, 15 February 2022 at 16:09
To: [email-masked] <[email-masked]>
Subject: Re: [CFRG] (Re: EdDSA square roots (RFC 8032))
I second the concern here. What are the advantages of qDSA over ECDSA and EdDSA?
How many “pre-Quantum” signature algorithms to we want to standardize, and why?

Hi John:

Rene

Cheers,
John

From: CFRG <[email-masked]><mailto:[email-masked]> on behalf of Ilari Liusvaara <[email-masked]><mailto:[email-masked]>
Date: Monday, 14 February 2022 at 09:20
To: [email-masked]<mailto:[email-masked]> <[email-masked]><mailto:[email-masked]>
Subject: Re: [CFRG] EdDSA square roots (RFC 8032)

Parameters:

 * A group.

Keygen:

Signing:

Verifying:

-Ilari

_______________________________________________
CFRG mailing list
[email-masked]<mailto:[email-masked]>
https://protect2.fireeye.com/v1/url?k=31323334-501d5122-313273af-454445555731-40f7d10cf9eb7c69&q=1&e=bc1044a0-1981-4657-818f-5ae3dd11e71d&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg

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=ef97e2ee-4fe3-4885-bfcc-5729330ffe91&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg>

--

email: [email-masked]<mailto:[email-masked]> | Skype: rstruik

---

From: Rene Struik <[email-masked]>
Date: Wed, 16 Feb 2022 09:59:50 -0500

On 2022-02-16 9:54 a.m., Rene Struik wrote:
> Hi John:
>
> I would appreciate if you could also answer *my* question posed to the 
> mailing list (your email to Uri Blumenthal (which was f/u of my 
> question) below is quite generic and does not provide any concrete 
> technical detail or evidence.
>
> In particular, I would like to have your assessment on my questions re
> (a) whether the other example I provided for only one type of key and 
> code for both ECDH and signatures is correct;
> (b) ability of EdDSA to use Montgomery ladders under the hood.
>
> I think it is important to have technical clarity, also for 
> discussions on the use of ECC-based schemes for IoT devices (and the 
> MTI algorithm discussion in the IETF Lake WG).
>
> As a reminder, I copied my email of yesterday, Tue Feb 15, 2022, 
> 9.16am EST below.
>
> Thanks, Rene
>
> ==
> Ref: 
> https://mailarchive.ietf.org/arch/msg/cfrg/KOMUKUCXS_a9-L-Ceb8F4kH6dqE/
>
> Hi John:
>
> short-Weierstrass curve Wei25519 [1]) already do this? Or, doesn't 
> this count, since not sexy enough, or not coming from the right 
> stable? BTW - it would be trivial to define Schnorr signatures (if 
> that is the only thing that counts) with short-Weierstrass curves, 
> without introducing yet more zoos of variants, roll-yet-something-new 
> encoding formats, confusion, etc.
>
> On 2022-02-16 6:05 a.m., John Mattsson wrote:
>>
>> Uri Blumethal wrote:
>>
>> If the numbers in the qDSA paper hold up it seems significantly more 
>> efficient when it comes to memory footprint, code size, speed, and 
>> energy consumption. I think it makes a lot of sense for a research 
>> group like CFRG to evaluate new designs like qDSA. IF the numbers 
>> hold up and IF there are no big disadvantages, I think a signature 
>> scheme with the performance numbers presented in the qDSA paper could 
>> be a welcome addition to COSE, HPKE, and other protocols used in 
>> constrained IoT.
>>
>> So far I think CFRG has published one ECC based (EdDSA) and two 
>> hash-based (XMSS and LMS) signature schemes. The EdDSA work did not 
>> focus on IoT. It was agreed that CFRG might come back to signatures 
>> focusing on IoT. I think more CFRG work considering IoT would be very 
>> welcome.
>>
>> Right now we don't know if CRQCs will ever exist or how many decades 
>> it could take. In 20 years, we might have CRQCs or we might have a 
>> situation where funding to quantum computing development perished 
>> (due to lack of use cases or technical difficulties) and we are 
>> thankful that we continued work on Elliptic Curve Cryptography.
>>
>> For profiles like US CNSA used in non-constrained systems to protect 
>> TOP SECRET information that need to stay secret for a long, long time 
>> (75 years?) it makes a lot of sense to switch to PQC as soon as 
>> possible. The situation in constrained IoT is very different. Many 
>> constrained IoT systems today do not use any cryptography or rely on 
>> symmetric group keys. The current size of PQC signatures and keys are 
>> unusable for some use cases in constrained IoT systems (both devices 
>> and radio might be constrained). The struggle right now is to get 
>> these systems to use ECC instead of “no security” or symmetric group 
>> keys. Any system using ECC needs to be aware of the development of 
>> quantum computers, but many systems will likely continue to use ECC 
>> and switch algorithms if/when the CRQC threat is more tangible. For 
>> some constrained use cases, the switch would unfortunately likely be 
>> back to symmetric group keys (with very weak security properties) 
>> instead of asymmetric PQC. For some use cases like using 
>> Non-Interactive Key Exchange (NIKE) in groups, there is not even any 
>> PQC standardization ongoing.
>>
>> Cheers,
>>
>> John
>>
>
> --

---

From: Rene Struik <[email-masked]>
Date: Wed, 16 Feb 2022 12:26:03 -0500

(resend - msg cap 40kB again)

On 2022-02-16 12:21 p.m., Rene Struik wrote:
> Hi John:
>
> You claimed to have read the paper, so I would assume you could 
> provide more details to support your claims. Apparently, this would be 
> asking too much.
>
> One does not have to hide behind presumed authority of other people 
> (which seems to be a favorite pass time for some). I do not contest 
> that this forum has some very knowledgeable people, but it would help 
> doing one's own homework *first*, before making claims.
>
> Once again, CFRG is (supposed to be) a research forum, where technical 
> debate is (supposed to be) not uncommon.
>
> There is no need to be antagonistic here: in fact, by throwing out 
> random pieces, without analysis, I think you do not value other 
> people's time (since you force others, like me, to debunk bogus claims).
>
> Just FYI:
>
> - Small memory footprint. EdDSA can be implemented with Montgomery 
> ladders, as qDSA does (with same Curve25519 under the hood);
>
> - Small code size. Both key generation routine, signing operation, and 
> verification can be implemented as qDSA does (with same Curve25519 
> under the hood);
>
> - Only one type of key (and code) for DH and signatures. NIST curve 
> P-256 with ECDH and ECDSA already did this, as did ANSI, BSI, etc. 
> CFRG was only one who wanted to suddenly do things differently
>
> - Fast (lower latency is good. Not sure power consumption is a 
> practical problem). Main operation is ECC arithmetic, so any 
> performing implementation can be used by either.
>
>
> I hope this ends the FUD.
>
> If one thinks something is worth considering, one has to provide 
> convincing arguments.
>
> "Opinions are free; facts are sacred"
>
> Rene
>
> On 2022-02-16 11:57 a.m., John Mattsson wrote:
>>
>> Hi Rene,
>>
>> I don't know why you so strongly want my assesment on these questions.
>>
>> I think you have already provided the relevant information to the list.
>>
>> Yes, you can do that for e.g., P-256. You can also use a Ed25519
>>
>> key and transform it to Montgomery for ECDH.
>>
>> I assume you can. I don't know exactly what the qDSA paper compared 
>> against.
>>
>> The qDSA paper claims that they "significantly outperforms 
>> state-of-the-art
>>
>> signature implementations". If you think that is wrong and that 
>> EdDSA/X25519
>>
>> (or ECDSA/ECDH with some curve) can be implemented with similar memory
>>
>> footprint,code size, and clock cycles it would be very interesting to 
>> hear more
>>
>> detailsabout that. Ilari Liusvaara and Mike Hamburg seem to think that
>>
>> qDSA(or something similar) has benefits.
>>
>> Cheers,
>>
>> John
>>
>> *From: *Rene Struik <[email-masked]>
>> *Date: *Wednesday, 16 February 2022 at 15:55
>> *To: *John Mattsson <[email-masked]>, Blumenthal, Uri - 
>> 0553 - MITLL <[email-masked]>, [email-masked] <[email-masked]>
>> *Subject: *Re: [CFRG] (Re: EdDSA square roots (RFC 8032))
>>
>> Hi John:
>>
>> I would appreciate if you could also answer *my* question posed to 
>> the mailing list (your email to Uri Blumenthal (which was f/u of my 
>> <https://mailarchive.ietf.org/arch/msg/cfrg/KOMUKUCXS_a9-L-Ceb8F4kH6dqE/>
>>
>> Hi John:
>>
>> There is nothing to preclude implementation of Ed25519 with 
>> Montgomery ladders (where only verification speed suffers compared to 
>> "Shamir's trick"), so I do not see the competitive advantage (but am 
>> happy to be educated here).
>>
>> Shouldn't one first try and fix the current half-baked (pardon le 
>> mot) mess?
>>
>> Rene
>>

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 16 Feb 2022 19:31:27 +0200

On Tue, Feb 15, 2022 at 09:20:39AM -0500, Rene Struik wrote:
> count, since not sexy enough, or not coming from the right stable? BTW - it
> would be trivial to define Schnorr signatures (if that is the only thing
> that counts) with short-Weierstrass curves, without introducing yet more
> zoos of variants, roll-yet-something-new encoding formats, confusion, etc.

ECDH+ECDSA is larger in code size than Curve*+qDSA. qDSA seems to be
really good at "scavenging" Curve* code, which in turn is one of the
most compact ways to do key exchange.

As for being trivial to define Schnorr signatures, didn't I do that
already in earlier mail? It says it needs a dlog-hard encodable group,
which are trivial to build from dlog-hard short-Weierstrass curves.

For cofactor-4 Edwards curves, one can quotent the groups with the
small subgroups. For E-521, the result actually can be shoehorned into
520 bits (65 bytes), despite the base field being 521 bits. Similarly, 
for Edwards448, result fits into 56 bytes.

> BTW - qDSA is again deterministic (to fit with the dogma of the day). There
> is nothing to preclude implementation of Ed25519 with Montgomery ladders
> (where only verification speed suffers compared to "Shamir's trick"), so I
> do not see the competitive advantage (but am happy to be educated here).

Random, noisy and deterministic all have advantages and disadvantages.
I think that:

1) If you need one-pass operation, use random and harden against
   fault attacks (as one-pass needs random, and random is vulernable
   to fault attacks).
2) Otherwise, If you have physically secure hardware, use deterministic.
3) Otherwise use noisy.

There is no one pareto-winner (superrior to everything else in every
way).

And Ed25519 with montgomery ladder is larger than qDSA in code. And
for Ed448, Curve448 and Edwards448 are not isomorphic, which could be
quite annoying.

> Shouldn't one first try and fix the current half-baked (pardon le mot)

Well, ECDSA and SHAKE128... Now that is a hot mess, too cursed for me.
:-)

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Wed, 16 Feb 2022 12:36:33 -0500

BTW - You wrote "Yes, you can do that for e.g., P-256. You can also use 
a Ed25519key and transform it to Montgomery for ECDH."

In theory - yes. In practice, mostly no, e.g., with COSE, such 
transforms are not allowed, see 
https://www.iana.org/assignments/cose/cose.xhtml#elliptic-curves

If one wishes to allow this, one has to write a specification, etc., 
that allows this (I know of many trivialities that are delayed because 
even asking something as trivial as a code point is claimed to be 
controversial, where specs do not allow things, are incorrectly written 
or not written in a future-proof way, etc.)

On 2022-02-16 12:26 p.m., Rene Struik wrote:
>> provide more details to support your claims. Apparently, this would 
>> be asking too much.
>>
>> Once again, CFRG is (supposed to be) a research forum, where 
>> technical debate is (supposed to be) not uncommon.
>>
>> - Small code size. Both key generation routine, signing operation, 
>> and verification can be implemented as qDSA does (with same 
>> Curve25519 under the hood);
>>
>>> footprint,code size, and clock cycles it would be very interesting 
>>> to hear more
>>>
>>> (a) whether the other example I provided for only one type of key 
>>> and code for both ECDH and signatures is correct;
>>>
>>> without introducing yet more zoos of variants, 
>>> roll-yet-something-new encoding formats, confusion, etc.
>>>
>>> BTW - qDSA is again deterministic (to fit with the dogma of the 
>>> day). There is nothing to preclude implementation of Ed25519 with 
>>> Montgomery ladders (where only verification speed suffers compared 
>>> to "Shamir's trick"), so I do not see the competitive advantage (but 
>>> am happy to be educated here).
>>>

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 16 Feb 2022 23:14:20 +0000

Hiya,

> There is no one pareto-winner (superrior to everything else in every

With my limited knowledge of the topic, the above seems like
it could well be close to a reasonable quick-summary to me.
A 2-3 page expansion of that could I think be a valuable bit
of CFRG guidance for IETF WGs and others. Wrapped up in I-D
boilerplate and with refs that'd get to 7-8 pages - shouldn't
be that much work for someone with the right expertise:-)

Cheers,
S.

---

From: Yolan Romailler <[email-masked]>
Date: Thu, 17 Feb 2022 17:37:50 +0100

I'd like to put a reminder here that it is important, even when relying on
a hash function to generate the "nonce", (for EdDSA, qDSA and ECDSA alike)
to have an **unbiased** nonce, since otherwise it would leak the private
key through signatures! Not too long ago, LadderLeak was exploiting less
than 1 bit of information about the nonce (which means a probable leak that
did not occur systematically) to perform a full private-key recovery and
public exploitation of a single bit bias goes back to at least 2014.
Deterministic nonces in EdDSA and RFC8032 have sadly "brought back" the
notion that we can _simply_ reduce the nonce modulo the curve order, which
is not necessarily true if we start playing around with other hash
functions (I've seen a mention of SHA256).

EdDSA and qDSA are both relying on a hash function that maps to at least a
2log_2(N)-bit output, which is 512 bits roughly for them.
RFC6979 on the other hand mandates "rejection sampling" on the nonce as per
its step 3.2 h.3.
Reducing a 512-bit value modulo a 256-bit is fine from a bias perspective,
since we would get a negligible modulo bias that is considered fine for the
current state of the art in HNP/Bleichenbacher based attacks.
But going down to a 256-bit nonce, if reduced modulo the curve order, would
become dangerous from a biased nonce perspective. So, shall it be done in
practice, we should really make sure to mandate proper rejection sampling
like RFC6979 to not introduce any exploitable modulo bias.

Best,
Yolan

On Tue, Feb 15, 2022, 07:43 John Mattsson <john.mattsson=
[email-masked]> wrote:

> Yes, I agree. I strongly think CFRG should look more at all aspects of signatures
> for IoT. It would then make more sense to look at new designs such as qDSA.
> I re-read the qDSA paper. It seems very promising with:
>
>
>
> I think it could make a lot of sense to standardize qDSA with a variable-length
> hash function like SHAKE128. SHA-256 is the old standard, I don't think we
> need to drag that into the future.
>
>
>
> Cheers,
>
> John
>
>
>
> *From: *CFRG <[email-masked]> on behalf of Ilari Liusvaara <
> [email-masked]>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 17 Feb 2022 18:52:46 +0000

It looks like both EdDSA and qDSA designs could benefit from security improvements.

Is CFRG going to do anything about it? 

-- 

V/R,

Uri

From: CFRG <[email-masked]> on behalf of Yolan Romailler <[email-masked]>
Date: Thursday, February 17, 2022 at 11:39
To: CFRG <[email-masked]>
Subject: Re: [CFRG] EdDSA square roots (RFC 8032)

I'd like to put a reminder here that it is important, even when relying on a hash function to generate the "nonce", (for EdDSA, qDSA and ECDSA alike) to have an **unbiased** nonce, since otherwise it would leak the private key through signatures! Not too long ago, LadderLeak was exploiting less than 1 bit of information about the nonce (which means a probable leak that did not occur systematically) to perform a full private-key recovery and public exploitation of a single bit bias goes back to at least 2014. 
Deterministic nonces in EdDSA and RFC8032 have sadly "brought back" the notion that we can _simply_ reduce the nonce modulo the curve order, which is not necessarily true if we start playing around with other hash functions (I've seen a mention of SHA256). 

EdDSA and qDSA are both relying on a hash function that maps to at least a 2log_2(N)-bit output, which is 512 bits roughly for them.

RFC6979 on the other hand mandates "rejection sampling" on the nonce as per its step 3.2 h.3. 

Reducing a 512-bit value modulo a 256-bit is fine from a bias perspective, since we would get a negligible modulo bias that is considered fine for the current state of the art in HNP/Bleichenbacher based attacks.

But going down to a 256-bit nonce, if reduced modulo the curve order, would become dangerous from a biased nonce perspective. So, shall it be done in practice, we should really make sure to mandate proper rejection sampling like RFC6979 to not introduce any exploitable modulo bias.

Best,

Yolan

- Small code size.

Cheers,

John

Parameters:

 * A group.

Keygen:

Signing:

Verifying:

-Ilari