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

[John Mattsson <[e-mail]>]

Uri Blumethal wrote:

> 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 <[e-mail]> on behalf of Blumenthal, Uri - 0553 - MITLL <[e-mail]>
Date: Tuesday, 15 February 2022 at 16:09
To: [e-mail] <[e-mail]>
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?

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]><mailto:[e-mail]> on behalf of Ilari Liusvaara <[e-mail]><mailto:[e-mail]>
Date: Monday, 14 February 2022 at 09:20
To: [e-mail]<mailto:[e-mail]> <[e-mail]><mailto:[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]<mailto:[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]<mailto:[e-mail]>

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: [e-mail]<mailto:[e-mail]> | Skype: rstruik

cell: [phone] | US: [phone]