Subject: [Cfrg] Fwd: I-D Action: draft-turner-thecurve25519function-00.txt

From: Sean Turner <[email-masked]>
Date: Tue, 29 Jul 2014 16:05:04 -0400

At the interim CFRG meeting, I agreed to publish a draft of the curve 25519 function with some help from Rich, Watson, and Tanja.  That draft is now up.  Note there’s also a github repo:

https://github.com/seanturner/draft-turner-thecurve25519function

Please review and provide comments if needed.

spt

Begin forwarded message:

> From: [email-masked]
> Subject: I-D Action: draft-turner-thecurve25519function-00.txt
> Date: July 29, 2014 at 15:59:26 EDT
> To: [email-masked]
> Reply-To: [email-masked]
> 
> 
> A New Internet-Draft is available from the on-line Internet-Drafts directories.
> 
> 
>        Title           : The Curve25519 Function
>        Authors         : Watson Ladd
>                          Rich Salz
>                          Sean Turner
> 	Filename        : draft-turner-thecurve25519function-00.txt
> 	Pages           : 7
> 	Date            : 2014-07-29
> 
> Abstract:
>   This document specifies the Curve25519 function, an ECDH (Elliptic-
>   Curve Diffie-Hellman) key-agreement scheme for use in cryptographic
>   applications.  It was designed with performance and security in mind.
>   This document is based on information in the public domain.
> 
> 
> The IETF datatracker status page for this draft is:
> https://datatracker.ietf.org/doc/draft-turner-thecurve25519function/
> 
> There's also a htmlized version available at:
> http://tools.ietf.org/html/draft-turner-thecurve25519function-00
> 
> 
> Please note that it may take a couple of minutes from the time of submission
> until the htmlized version and diff are available at tools.ietf.org.
> 
> Internet-Drafts are also available by anonymous FTP at:
> ftp://ftp.ietf.org/internet-drafts/
> 
> _______________________________________________
> I-D-Announce mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/i-d-announce
> Internet-Draft directories: http://www.ietf.org/shadow.html
> or ftp://ftp.ietf.org/ietf/1shadow-sites.txt

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 29 Jul 2014 23:41:38 +0300

> > 	Filename        : draft-turner-thecurve25519function-00.txt

  To compute the conditional swap in constant time (independent of s_t)
  use dummy = s_t*(x_2-x_3) x_2 = x_2 - dummy x_3 = x_3 + dummy where
  s_t is 1 or 0, or dummy = s_t & (x_2 XOR x_3) x_2 = x_2 XOR x_3 x_3 =
  x_3 XOR x_2 where s_t is regarded as the all-1 word of 255 bits.  The
  latter version is more efficient on most architectures.

The latter formulas: Where is the dummy used? And s_t can also be 0
(no swap)?

Should those formulas be:
dummy = s_t & (x_2 XOR x_3)
x_2 <- x_2 XOR dummy
x_3 <- x_3 XOR dummy

?

And that paragraph could perhaps use some reformatting.

-Ilari

---

From: Sean Turner <[email-masked]>
Date: Wed, 30 Jul 2014 13:30:11 -0400

> And that paragraph could perhaps use some reformatting.

Let me fix up the formatting first and then see if it’s clearer.

spt

---

From: Randy Bush <[email-masked]>
Date: Wed, 30 Jul 2014 20:05:49 +0200

sean, we also need signatures.  would you consider adding ed25519 to
this draft or doing a parallel draft?

randy

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Jul 2014 14:16:16 -0400

> this draft or doing a parallel draft?

We do need signatures, but do we need curve 25519 signatures?

RSA allows one key to be used for encryption and signature easily. But
that is still terrible security practice.

Looking through the sets of requirements we have, a curve optimized
for encryption may not be best for signatures. And writing up how to
do signatures from a curve is non-trivial (unless its 'do DSA with
this curve')

Given that the EC keys are short, we could have a combined 'encryption
and signature' certificate  but with different curves for each one.

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 30 Jul 2014 14:28:06 -0400

I think the DH function of 25519 should be separate from a signature function based on 25519 and, for now at least, we're not going to add Ed25519 signatures.

--  
Principal Security Engineer
Akamai Technologies, Cambridge MA
IM: [email-masked] Twitter: RichSalz

---

From: Benjamin Black <[email-masked]>
Date: Wed, 30 Jul 2014 11:28:18 -0700

> We do need signatures, but do we need curve 25519 signatures?
Using the same curve across kx and signatures simplifies specification,
implementation, and deployment.

> that is still terrible security practice.
I don't see how this is relevant to using the same curves in different
algorithms.

> do signatures from a curve is non-trivial (unless its 'do DSA with
Specific to Randy's request, EdDSA is specified in the same paper as
ed25519.

> and signature' certificate  but with different curves for each one.
The discussion is about using the same curves in different algorithms.
Curves are not keys.

b

---

From: Robert Ransom <[email-masked]>
Date: Wed, 30 Jul 2014 11:49:26 -0700

On 7/29/14, Sean Turner <[email-masked]> wrote:
> At the interim CFRG meeting, I agreed to publish a draft of the curve 25519
> function with some help from Rich, Watson, and Tanja.  That draft is now up.

Some notes (this is not a thorough review):

Section 3:

* The draft correctly specifies that the high bit must be discarded,
but does not mention that that differs from the specification in the
Curve25519 paper, and does not explain the reasons for that difference
(resistance to implementation fingerprinting, and forward
compatibility with point formats which preserve the sign bit for use
in other protocols).  It should do both, so that the RFC won't be
‘corrected’ to match the paper when someone else notices that
difference five or more years from now.

* The draft correctly specifies that implementations must produce
outputs less than the field order p, but does not explicitly state
that implementations must accept inputs which are greater than or
equal to p (and silently reduce them mod p).

Section 4:

* In the second paragraph, “All calculations are done over GF(p)”
should be replaced with “All calculations are performed in GF(p)” --
“performed” is slightly more precise, and “in” is more correct than
“over” when you're operating on field elements rather than e.g.
polynomials with coefficients in the field (i.e. polynomials ‘over’
the field).

Robert Ransom

---

From: Paul Lambert <[email-masked]>
Date: Wed, 30 Jul 2014 11:50:20 -0700

On Wed, Jul 30, 2014 at 11:16 AM, Phillip Hallam-Baker <[email-masked]<mailto:[email-masked]>> wrote:
> this draft or doing a parallel draft?
+1

Using the same curve across kx and signatures simplifies specification, implementation, and deployment.
Yes!

RSA allows one key to be used for encryption and signature easily. But
that is still terrible security practice.
Not always.  First, using the same curve could be with different keys.
Option should also be allowed to have same key support key establishment
and signatures.  There are improvements in protocol design/usability that are possible.

Paul

I don't see how this is relevant to using the same curves in different algorithms.

Specific to Randy's request, EdDSA is specified in the same paper as ed25519.

The discussion is about using the same curves in different algorithms. Curves are not keys.

b

---

From: Randy Bush <[email-masked]>
Date: Wed, 30 Jul 2014 21:15:38 +0200

> implementation, and deployment.

bingo

> Specific to Randy's request, EdDSA is specified in the same paper as

i am hoping to learn a lot from/if sean specs ed25519 in parallel.

randy

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 30 Jul 2014 15:25:55 -0400

> Some notes (this is not a thorough review):

All excellent points, thanks.  Please, continue :)

	/r$

---

From: Tanja Lange <[email-masked]>
Date: Wed, 30 Jul 2014 23:09:46 +0200

Dear Robert,
> difference five or more years from now.
The paper specifies that the x value is an integer between 0 and p-1. 
It does not specify what to do if the sent value does not adhere to 
this format. On the math side, there is no attack from accepting 
DH inputs which do not match this format, but for specifications
I want a defined format.

The text specifies that s[31] is minimal; the representation is
unique.

> equal to p (and silently reduce them mod p).
Why would you do this? If the DH input is >=2^255-19 then it was
not generated according to the specification and should be rejected.

If you want to have the ambiguity of having multiple representations
for inputs (which I would recommend against) there is still no need 
to reduce modulo p. The computation could start from the unreduced
value and give the same result.

Do you see any benefit in having non-unique representations? Any 
problems with rejecting malformed inputs?

All the best
	Tanja

---

From: James Cloos <[email-masked]>
Date: Wed, 30 Jul 2014 17:36:00 -0400

>>>>> "SR" == Salz, Rich <[email-masked]> writes:

SR> I think the DH function of 25519 should be separate from a signature
SR> function based on 25519 and, for now at least, we're not going to add
SR> Ed25519 signatures.

Why not?  They work well for ssh.

But even if ipsec a/o tls don't care, there still should be an rfc
specifying the algorithm.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 31 Jul 2014 01:11:55 +0100

+1

CFRG are being asked to propose such for use in TLS. In order to
allow CFRG the possibility to consider Ed25519 a draft that
describes that is needed.

S.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 30 Jul 2014 19:41:25 -0700

> describes that is needed.

There already is a paper describing the algorithm. I'm happy to spend
time writing an ID describing it, but I think we all know what
the situation with the alternatives is. (There still is no draft
describing the Microsoft alternatives). Furthermore, the chair of the
CFRG said
the issue of which signature algorithm to recommend was not being
taken up: the question of point formats for use with ECDSA-like things
would be. (I actually believe there are questions DJB identified that
need addressing: ECDSA assumes Weierstrass x, and there is good reason
to prefer Schnorr)

Furthermore, we've in this draft assumed Montgomery points,
x-coordinate only. Combining it with a draft describing a signature
scheme with an isomorphic curve doesn't gain much over splitting them.

Sincerely,
Watson Ladd
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Randy Bush <[email-masked]>
Date: Thu, 31 Jul 2014 09:09:53 +0200

> specifying the algorithm.

indeed.  i am trying to understand objecting to this and am not being
very successful.

i realize that a/o is so widely deployed, it will be impossible to
change.  </sarcasm>

randy