Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-eddsa-02.txt

From: Simon Josefsson <[email-masked]>
Date: Mon, 01 Feb 2016 13:53:00 +0100

Ilari Liusvaara <[email-masked]> writes:

> On Mon, Jan 25, 2016 at 06:36:47PM +0000, Alexey Melnikov wrote:
>> Dear CFRG participants,
>> 
>> This message starts 2 weeks RGLC on draft-irtf-cfrg-eddsa-02 ("Edwards-curve
>> Digital Signature Algorithm (EdDSA)"), which will end on February 8th.
>
> On Curdle list, somebody was apparently confused about algorithm
> choices and requested some guidance to be included.
>
> Here is initial (quite biased) attempt (probably also full of
> bad editing):
>
>
> Choice of signature primitive
> =============================
>
> The Ed25519 and Ed25519ph have nominal strength of 128 bits,
> whereas Ed448 and Ed448ph have strength of 224.

I think "around" and possibly "believed" should be added here.  Compare
other text in the document on security levels.  Ed25519 doesn't provide
exactly 128 bits of security, and suggesting so makes it harder to
understand how ECC security levels work.  Otherwise fine.

> While the lower strength is sufficient for the forseeable future, the
> higher level brings some defense against possible future cryptographic
> advances.  Both are demolished by quantum computers just about the
> same.
>
> The Ed25519ph and Ed448ph variants are prehashed. This is mainly
> useful for interoperation with legacy APIs, since in most of the
> cases, either the amount of data signed is not large, or the protocol
> is in position to do digesting in ways better than just prehashing (e.g.
> tree hashing or splitting the data). The prehashing also makes the
> functions greatly more vulernable to weaknesses in hash functions
> used. These variants SHOULD NOT be used.
>
> On implementation front, Ed25519 is widely implemented, and has
> many high-quality implementations. The others have much worse
> support.

I agree up until here.  The language could be tightened up a bit.

> As summary, if high 128-bit security level is enough, use of
> Ed25519 is RECOMMENDED, otherwise Ed448 is RECOMMENDED.

I believe this is too strong.  I believe the basic recommendation is to
use Ed25519 since that is what is deployed and in serious use and
provides sufficient security.  Ed448 is there to hedge against
analytical attacks.

/Simon

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 1 Feb 2016 16:44:34 +0000

On 2/1/16, 7:53 , "Cfrg on behalf of Simon Josefsson"
<[email-masked] on behalf of [email-masked]> wrote:

>>...Here is initial (quite biased) attempt (probably also full of
>> bad editing):
>>...

I disagree. 

Some people and organizations (myself included) believe (and/or are under
the policy guidance) that P256 and Ed25519 are coupled with 128-bit
ciphers to provide *128 bits of crypto strength*. That guidance states
that for higher strength (estimated as 256 bits) other curves are needed.

So it is not a “hedge”. It is an option for those who require 256 (or more
generically speaking, “more than 128) bits of presumed strength.

I recommend keeping that text as is.

P.S. At this time all the assumptions about strength are just that -
educated assumptions.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 1 Feb 2016 08:50:57 -0800

> that for higher strength (estimated as 256 bits) other curves are needed.

These policies ignore differences between authentication and
encryption, and between block cipher strength and ECC strength. They
aren't serious efforts at thinking through what is actually required,
but numerology.
> P.S. At this time all the assumptions about strength are just that -

Or they are careful analysis of what attackers using a given amount of
computation can achieve with the best publically known algorithm

>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 1 Feb 2016 18:05:56 +0000

>computation can achieve with the best publically known algorithm
                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Yes.

---

From: John Mattsson <[email-masked]>
Date: Fri, 12 Feb 2016 17:25:22 +0000

Hi,

Seems well written. I have not checked any formulas or code.

Cheers,
John

Some comments on draft-irtf-cfrg-eddsa-02:

General:

- The document talks about both “private key” and “secret key”, you should
chose one. Preferably “private key” as that is what RFC4949 recommends and
as “secret key cryptography” is sometimes used as a synonym to symmetric
key cryptography.

- “Curve25519” -> “curve25519” and “Curve448” -> “curve448” if you want to
align with RFC7748, but I think it would be even better to talk about
“edwards25519” and “edwards448” as RFC7748 calls the curves in (twisted)
Edwards form.

- The draft talks about “strongly unified” as valid for all points on the
curve, with no exceptions. But to my understanding the term “strongly
unified” means “work without change for doublings”, while the term
“complete” is used for “work without change for all inputs”. See e.g.
https://cr.yp.to/newelliptic/inverted-20071009.pdf

- The document talks about “key” or “secret” in several places. I think
you should you should always write out “key” and also specify which key,
i.e. “private key” or “public key"

Section 1:

- “possibly Twisted” -> “possibly twisted” (I think...)

- The specific key and signature sizes are for Ed25519 and Ed448, not for
EdDSA in general.

- Good if already the introduction describes that the document specifies
to different variants of EdDSA called PureEdDSA and HashEdDSA and that
these are instantiated with edwards25519 and edwards448 resulting in the
four instances Ed25519, Ed25519ph, Ed448 and Ed448ph. Now the reader has
to wait until section 4 to find out.

- “a large quantum computer”
It is really “large”? Isn’t it just larger that the extremely tiny QC that
currently exist? Maybe “sufficiently large”?

Section 2:

- You define “<=” but not “>=”

- I think you should define the element notation “(x,y)”

- “[n]B” I don’t think the operation should be defined with the generator.

- As you define [n]X, I think it is good to define X[n] to make clear that
it does not mean multiplication from the right.

- You define sum and multiplication but not subtraction and division.

- RFC7748 calls the generator point ‘P’

- “tab” instead of “ --- ” as in RFC7748 makes the notation section easier
to read.

Section 3:

- You should explain what a “conservative hash function” is.

- Elements are written both with and without space, i.e. “(0,1)” and “(0,
1)”

- To state “EdDSA has eleven parameters” and then listing 10 seem strange.
Looking at [EDDSA2], I see that “d” is missing

- The symbol “l” is very hard to distinguish from the number “1” (at least
in the font used on tools.ietf.org).

- “#E is part of the standard data provided for an elliptic curve E.”
Not in RFC7748 even if it can easily be calculated as order * cofactor.

- Would be good for the reader to understand which parameters are given by
RFC7748 and which are introduced by this document.

Section 5:

- “FIXME: Add reference”

- “x y = T/Z”
Something missing between x and y?

- “X(P)” and “X(Y)” is not defined.

Section 10:

- “The context should” -> “The context SHOULD”?

- Does the security consideration have to be negative? I think it would be
good with a little bit more analysis of the positive advantages 2,3,5,6
mentioned in the introduction.

Appendix A:

- Section 6 has good warning text “Note that this code is not ..."
I think such warning text would be good in Appendix A as well.

- The following 5 methods are never used:

def sha3_224(msg): return sha3_raw(msg,18,6,28)
def sha3_256(msg): return sha3_raw(msg,17,6,32)
def sha3_384(msg): return sha3_raw(msg,13,6,48)
def sha3_512(msg): return sha3_raw(msg,9,6,64)
def shake128(msg,olen): return sha3_raw(msg,21,31,olen)

(As the code uses hashlib.sha512() instead of sha3_512())

Purely Editorial:

- Section headings use different heading capitalization.

- “significant”

- “Chosing”

- “practicular”

- “percolates”

- “protocol”

- “X(p)”

- “Y(p)”

- “for readability Ed25519” -> “for readability. Ed25519”

- “private and public keys 32 octets” -> “private and public keys are 32
octets”

- “for the Curve25519 and Ed448 curves,” -> “for curve25519 and curve448,”

- “Ed448ph is the same but with P” -> “Ed448ph is the same but with PH”

- “a^ (p+1)/4” -> “a^(p+1)/4”

On 25/01/16 19:36, "Cfrg on behalf of Alexey Melnikov"
<[email-masked] on behalf of [email-masked]> wrote:

>Dear CFRG participants,
>
>This message starts 2 weeks RGLC on draft-irtf-cfrg-eddsa-02
>("Edwards-curve Digital Signature Algorithm (EdDSA)"), which will end on
>February 8th. Please respond with your reviews to the mailing list or
>directly to chairs and editors. If you reviewed the document and found
>it to be ready for publication, please let the chairs know as well.
>
>Best Regards,
>Kenny and Alexey
>

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 12 Feb 2016 12:30:37 -0500

On 02/12/2016 12:25 PM, John Mattsson wrote:
> - Curve25519� -> curve25519 and Curve448� -> curve448� if you want to
> edwards25519 and edwards448 as RFC7748 calls the curves in (twisted)
> Edwards form.

I always thought the style guide is proper nouns are capitalized and if 
so the the RFC is wrong, not this draft.

That is something we would hope the RFC Editor would catch in time. My 
work in IEEE, we expect to get dinged by the editorial staff on items 
like this.