Subject: Re: [lamps] supporting ECDSA25519, i.e., ECDSA/SHA256 with Curve25519 under the hood (was: Re: LAMPS Minutes for IETF 109)

From: "Brockhaus, Hendrik" <[email-masked]>
Date: Thu, 3 Dec 2020 18:14:56 +0000

Thanks to Tomas for his feedback and insight into HW support and PKCS#11.

> Von: Spasm <[email-masked]> Im Auftrag von Rene Struik
> Gesendet: Donnerstag, 26. November 2020 21:58
>
> Dear colleagues:
>
> Do you think supporting ECDSA25519 would make sense as well? 
> 
> This is well-defined and non-deterministic and also can use existing Curve25519 ladders under the hood (see [1]) as well as existing generic hardware supporting short-Weierstrass curves (see [2]).
>
> Due to the PKIX/CMS OID requested during IETF Last-Call on lwig-curve draft [3], it seems this could just be used without further ado.

Does anyone from LAMPS reviewed the draft and has an opinion on the work? 

After discussing the support of curve25519 and curve448 at IETF109 I tend to add EdDSA (referred to as Ed25519 and Ed448) according to RFC8419 and ECDH (referred to as X25519 and X448) according to RFC8419 to CMP Algorithms.
I think I understand what Renes aims at reading the draft. I would like to ask the WG, should I add support of Wei25519 and Wei448 (referred to as signature schemes ECDSA25519 and ECDSA448 and key agreement schemes ECDH25519 and ECDH448).

Hendrik

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 9 Dec 2020 16:17:58 +0200

On Thu, Dec 03, 2020 at 06:14:56PM +0000, Brockhaus, Hendrik wrote:
> > This is well-defined and non-deterministic and also can use existing
> > Curve25519 ladders under the hood (see [1]) as well as existing
> > generic hardware supporting short-Weierstrass curves (see [2]).

1) It is not well defined enough for common sign/verify APIs that take
message hash. This is because it triggers special case inside ECDSA
that makes signature dependent on bit order of the hash function. SHA-2
defines it one way, SHAKE defines it the other, and other hash functions
may not define it at all.

2) Deterministic/noisy/non-deterministic is only about specification and
implementation, it is not about interoperability.

3) It is not trivial to use existing Curve25519 ladders for verification,
because those do not produce indication if the two products are same- or
opposite-sign. The cheap trick used by qDSA to check both at once does
not obviously work because of mod n at output.

> > Due to the PKIX/CMS OID requested during IETF Last-Call on lwig-curve
> > draft [3], it seems this could just be used without further ado.
> 

My opinion is that ECDSA25519, ECDSA448, ECDH25519 and ECDH448 try to
shoehorn Curve25519 and Curve448 to obsolete constructions (nevermind
that those constructions obsolete even more obsolete constructions)
that mostly negate the simplicity advantages. And in case ECDSA, hit
a nasty edge case.

And if one wants complete arithmetic, one needs to transform all the
way to Edwards domain. Not an issue with Curve25519, since mapping
between montgomery and edwards forms is isomorphism, but for Curve448,
it is not, so this needs some extra thought. And then there are the
"-3" variants, which seem to involve mapping that is not isomorphism.

Now, EdDSA does have its problems. Mainly the fixed hash functions
causing issues with constrained environments, where one wants to use
single hash (which is most probably SHA-256) for everything. Since if
one wants to use Curve25519 with SHA-256 one needs a new signature
algorithm, one could define one that is simple.

-Ilari

---

From: Rene Struik <[email-masked]>
Date: Wed, 9 Dec 2020 10:22:28 -0500

Hi Ilari:

I am somewhat puzzled by your claims, since - if true - seem to suggest 
ECDSA (which has been used in practice almost two decades by now and is 
virtually ubiquitous) is not well-defined.

If anything in the specification of ECDSA25519 [1] or ECDSA448 is 
unclear, please indicate how this could be improved and I will take your 
advice at heart.

Curve448, Ed448, and Wei448 are isomorphic (see [3]).

I do agree with you that the security posture of EdDSA schemes can be 
improved, so as to remove trivial single-shot implementation attacks, 
but that is out of scope for discussion of ECDSA as defined in [1] and 
[2]. What about you fix RFC 8032 (you are one of the authors)?

Best regards, Rene

Ref:
[1] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-15#section-4.3
ECDSA25519 =ECDSA with SHA256 and the short-Weierstrass curve Wei25519 
(isomorphic to Curve25519)
[2] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-15#section-4.4
ECDSA448 = ECDSA with SHAKE256 with output-size d=512 bit (as also 
specified in RFC 8692) and the short-Weierstrass curve Wei448 
(isomorphic to Curve448)
[3] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-15#appendix-M
This section provides full details of isomorphic mappings between 
Curve448 (Montgomery curve), Ed448 (twisted Edwards curve with complete 
addition laws), and Wei448 (short-Weierstrass version)

On 2020-12-09 9:17 a.m., Ilari Liusvaara wrote:
> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm

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

---

From: Rene Struik <[email-masked]>
Date: Wed, 9 Dec 2020 10:46:49 -0500

Implementation of Curve25519 ladder, with y-coordinate recovery:

Inputs: point Q:=(u,v) with u nonzero field element of GF(p); 
non-negative integer k;
Output ladder: x-coordinate xR of R, where R:=(xR,yR):=k*Q; {note that 
y-coordinate is missing};
Output fixed ladder, with minimal changes: x-coordinate k*Q and 
x-coordinate (k+1)*Q
-- This allows computation of y-coordinate of k*Q (or of (k+1)*Q, as 
spelled out in [1] with formula in [2] (also displayed below). 
Incremental cost: few field multiplies (<1%).

 From the group laws above it follows that if P=(u, v), P1=(u1, v1),
    and P2=(u2, v2) are distinct affine points of the Montgomery curve
    M_{A,B} with P2:=P+P1 and if v is nonzero, then the v-coordinate of
    P1 can be expressed in terms of the u-coordinates of P, P1, and P2,
    and the v-coordinate of P, since

        2*B*v*v1=(u*u1+1)*(u+u1+2*A)-2*A-u2*(u-u1)^2.

Ref: [1] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-15#section-4.2
[2] 
https://datatracker.ietf.org/doc/html/draft-ietf-lwig-curve-representations-15#appendix-C.2

I hope this helps, Rene

==

On 2020-12-09 10:22 a.m., Rene Struik wrote:
> Hi Ilari:
>
> I am somewhat puzzled by your claims, since - if true - seem to 
> suggest ECDSA (which has been used in practice almost two decades by 
> now and is virtually ubiquitous) is not well-defined.
>
> unclear, please indicate how this could be improved and I will take 
> your advice at heart.
>
> Curve448 (Montgomery curve), Ed448 (twisted Edwards curve with 
> complete addition laws), and Wei448 (short-Weierstrass version)
>
>