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

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

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 <[e-mail]> on behalf of Rene Struik <[e-mail]>
Date: Tuesday, February 15, 2022 at 09:21
To: John Mattsson <john.mattsson=[e-mail]>, Ilari Liusvaara <[e-mail]>, CFRG <[e-mail]>
Subject: [CFRG] (Re: EdDSA square roots (RFC 8032))

 

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:

>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.

 

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 <[e-mail]> on behalf of Ilari Liusvaara <[e-mail]>
Date: Monday, 14 February 2022 at 09:20
To: [e-mail] <[e-mail]>
Subject: Re: [CFRG] EdDSA square roots (RFC 8032)

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 

_______________________________________________
CFRG mailing list
[e-mail]
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
[e-mail]
https://www.irtf.org/mailman/listinfo/cfrg
 
-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]