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

[Rene Struik <[e-mail]>]

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 
> avariable-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 
> <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]