Subject: [Cfrg] Requirements for curve candidate evaluation update

From: Benjamin Black <[email-masked]>
Date: Tue, 12 Aug 2014 14:58:50 -0700

The CFRG, while part of IRTF, cannot separate itself from the practical
demands of IETF. The CFRG brings a different set of skills to bear, but the
outcome of its work must be pragmatic. The original list of requirements in
the request forwarded by Kenny reflected the required pragmatism in asking
only for new curves based on the 15 years of research and deployment
experience with the NIST curves. Every other aspect of the problem was and
is constrained by the existing RFCs, existing installed base, and existing
customer expectations.

Returning to the engineering requirements for new curves, the curves must
take into consideration the well-established fact that many implementations
will not be authored by professional cryptographers and almost no users of
systems relying on them will be professional cryptographers. If we require,
rather than allow, multiple curve models be implemented to support
different algorithms or for different security levels, we are increasing
complexity and hence opportunities for security and interoperability
errors. If we require new security levels, we are again working against the
existing protocols, implementation and deployment experience, customer
expectations, even user interfaces. None of these can simply be dismissed
because they are inconvenient. They are the facts on the ground.

1. Curves must be generated using a rigid process, and the more rigid the
better.

2.  The curves we recommend should only require implementation of a single
curve model, which implies:

  a) ECDHE and ECDSA must be supported with a single curve model.

  b) The same curve model must be used for all security levels.

3. For the purposes of evaluating candidates, ephemeral in ECDHE means used
exactly once per key exchange.

4. The security levels are 128, 192, and 256 bits and each curve will only
be evaluated at one of those levels.

5. No changes to coordinate wire formats.

The outcome of these is that we need 3 rigidly generated  curves in either
short Weierstrass or twisted Edwards form. Anything beyond that should be
addressed at a later point, and should not block progress on this specific
request for new curves.

b

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 12 Aug 2014 18:05:46 -0400

I have asked before, perhaps you missed it.

I take exception to your claims that “single curve model” and “no change to wire formats” are facts on the ground.  Can you justify that?

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

---

From: Watson Ladd <[email-masked]>
Date: Tue, 12 Aug 2014 18:14:18 -0700

On Tue, Aug 12, 2014 at 2:58 PM, Benjamin Black <[email-masked]> wrote:
> rather than allow, multiple curve models be implemented to support different
> algorithms or for different security levels, we are increasing complexity
> and hence opportunities for security and interoperability errors. If we
> require new security levels, we are again working against the existing
> protocols, implementation and deployment experience, customer expectations,
> even user interfaces. None of these can simply be dismissed because they are
> inconvenient. They are the facts on the ground.
>

This doesn't distinguish among curves. Read DJB's email "curves,
coordinates and computations" email. It's a question about what
protocols should do: why should we prohibit x-coordinate only
exchanges, if protocols see a security or bandwidth benefit to them?

> exactly once per key exchange.

How does this help distinguish between curves?

> be evaluated at one of those levels.

Well, this is not what the NIST curves are (P521, not P512). Nor does
Curve25519 fit this model, and yet it continues to be adopted, despite
being against "existing  protocols, implementation and deployment
experience, customer expectations, and even user interfaces". Of
course, what does evaluation at a level mean? Will people get upset if
we give them more security for the same speed? What about the
cofactors? Should we complain about those also?

> 5. No changes to coordinate wire formats.

Does this mean just Weierstrass? Or is a change to Edwards somehow not
a change in the wire format? (Of course this doesn't constrain the
curves either)
> addressed at a later point, and should not block progress on this specific

Except the Microsoft curves send points on a twisted Edwards curve
with a=-1, and q=3 (4), so aren't complete without using an isogeny
and a slower formula. This is a much more serious problem, as it makes
implementation quite a bit more complicated. If we assume implementors
don't know crypto, then complete formulas are very necessary.

Lastly, the requests on the table for TLS and SSH do change the point
format and use new algorithms: clearly these facts aren't actually
facts.

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

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: William Whyte <[email-masked]>
Date: Tue, 12 Aug 2014 21:49:03 -0400

[Benjamin Black]
> 5. No changes to coordinate wire formats.

[Watson Ladd]

Requirement 5 strikes me as entirely unnecessary. Why is it important that
two different curves have the same wire format? The wire format can be one
of the things identified by the curve identifier, and each curve will have a
certain amount of custom code anyway; why does it matter if this custom code
includes code to interpret the wire format? I'd like to see this requirement
more thoroughly justified.

William

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 12 Aug 2014 19:11:59 -0700

> don't know crypto, then complete formulas are very necessary.
Presumably this is not an exhaustive list of desiderata.

If these requirements become final, then surely the complete curves mod 
the Microsoft primes with a=1 and no restriction on the sign of d 
(choose the one with q<p) should be in the running.

Cheers,
-- Mike

---

From: Benjamin Black <[email-masked]>
Date: Wed, 13 Aug 2014 16:22:16 -0700

On Tue, Aug 12, 2014 at 3:05 PM, Salz, Rich <[email-masked]> wrote:
> I take exception to your claims that “single curve model” and “no change
to wire formats” are facts on the ground.  Can you justify that?
> IM: [email-masked] Twitter: RichSalz

Rich,

The facts on the ground, as described in my post, are that people
implementing these systems may not be professional cryptographers, and even
if they are, they make mistakes, so requiring implementation of two
different models or transforms between models is a significant burden. If
an implementer wishes to use a different model internally, they can do so.
The difference is not requiring everyone do so.

As illustrated in the NaCl and TweetNaCl libraries having multiple required
models makes implementation more challenging, even for some of the best
cryptographers in the world. From
http://tweetnacl.cr.yp.to/tweetnacl-20131229.pdf :

"However, NaCl’s performance comes at a price. A single NaCl function
usually consists of several different implementations, often including
multiple assembly-language implementations optimized for different CPUs.
NaCl’s compilation system is correspondingly complicated. Auditing the NaCl
source is a time-consuming job. For example, four implementations of the
ed25519 signature system have been publicly available and waiting for
integration into NaCl since 2011, but in total they consist of 5521 lines
of C code and 16184 lines of qhasm code. Partial audits have revealed a bug
in this software (r1 += 0 + carry should be r2 += 0 + carry in
amd64-64-24k) that would not be caught by random tests; this illustrates
the importance of audits."

"In principle we could use the same scalar-multiplication code for both
Curve25519 and Ed25519. This would require conversion of points on M to
points on E and back. If we used the x-coordinate-based differential
addition ladder of Curve25519 also for Ed25519, we would additionally need
code to recover the y-coordinate as described by Okeya and Sakurai in [20].
Conversion code is not substantially shorter than the code required for the
Curve25519 Montgomery ladder, so we decided to not use the same code for
scalar multiplication in Curve25519 and Ed25519."

That requiring multiple models makes implementation more difficult and
implies more code is both intuitively obvious and supported by available
evidence. Again, implementers are allowed, even encouraged, to write
whatever optimizations they like. Requiring them to implement specific
optimizations for small performance gains at a cost of more, and more
difficult, code would be unusual in any IETF proposal, but is especially
out of place when the proposal is for core cryptography primitives.

You, like many of us, have had up close and personal experience with bugs
in crypto code. You know that even the best make mistakes. Requiring a
single model for everything significantly reduces opportunities for
mistakes and the small performance gain of multiple models does not justify
requiring the additional exposure.

b

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 13 Aug 2014 19:48:44 -0400

I really could care less about wire formats. They are completely
mutable at this point.

The only place where I have real legacy problems is in HSM support.
Long term signature keys have to be generated and stored in HSMs. And
no, that is not a 'nice to have feature', it is a 'be prepared to be
laughed at and told that you completely wasted your time' if it isn't
met type of feature.

I don't need to be able to use my existing HSMs but if the curves
chosen are not supported by any existing hardware and it takes 3 years
for it to become available then its going to delay everything (apart
from EDH).

On Tue, Aug 12, 2014 at 6:05 PM, Salz, Rich <[email-masked]> wrote:
> I take exception to your claims that “single curve model” and “no change to
> wire formats” are facts on the ground.  Can you justify that?
>
>
>
> --
>

---

From: David Jacobson <[email-masked]>
Date: Wed, 13 Aug 2014 18:42:05 -0700

I certainly don't agree that we need to be hamstrung by compatibility 
with existing HSM.  Clearly, the existing HSMs will work with NIST P-256.

Let's look at the risks of P-256 on an existing HSM.  The only real 
concern is that the NSA might know a vulnerability. For many users, this 
is not the end of the world.

I would not be surprised if many of the organizations with HSMs are 
financial institutions or government agencies.  These organizations are 
likely also constrained to FIPS 140-2 validated devices.  This means 
they can't escape  FIPS-approved curves, i.e. NIST P-256, etc.  And that 
means that even if we restricted ourselves to short Weierstrass curves, 
these HSM users still wouldn't be able to use their HSMs.

Finally, there is the assumption that the manufacturer of the HSM can't 
or won't upgrade the firmware.  That could be a business decision by the 
HSM manufacturer, but I doubt it is a technical one.  In a past life I 
worked for a company that built HSMs, and those could have their 
firmware updated.  Admittedly there is some possibility that the 
upgraded HSM will be slower, depending on how much of any special silcon 
can be harnessed for the new curve.

    --David Jacobson

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 13 Aug 2014 22:27:03 -0400

> Long term signature keys have to be generated and stored in HSMs

So EDH keys do not, and therefore do not need HSM requirements, right?

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 13 Aug 2014 22:34:42 -0400

> Requiring a single model for everything significantly reduces opportunities for mistakes and the small performance gain of multiple models does not justify requiring the additional exposure.
 
That's a value judgement, and different people will come to different conclusions. It's certainly not an axiomatic principle. And when I see it put forth like that, I instantly get suspicious of the people doing that.  FWIW.

To me, it's trading off "this is hard, and some people will get it wrong" -- when the community of people doing it is maybe a few hundred, certainly under 1K -- compared to zillions of devices in the web of things for the next couple of decades.

	/r$

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 13 Aug 2014 22:39:35 -0400

> So EDH keys do not, and therefore do not need HSM requirements, right?

I don't see a large field of established use that would make
availability of HSMs a gating factor for EDH. But obviously someone
could come up with one.

What I am trying to do here is to pare down the set of requirements
WITHOUT throwing out any that could be show stoppers or gating
deployment.

The use of ECC to date in open standards based systems is so
insignificant that we really should not think twice about blowing it
all up and starting from scratch. But if we do that then someone has
to tell the HSM vendors where we are going and some of them have to
sign on.

Not wanting to make a big fuss on the HSM requirement but it is
definitely a potential gating factor. Using the same curve model for
encryption and signature does not interest me in the slightest. I
cannot see that as being a necessary requirement, it is just someone
wanting things to be tidy.

The only good reason to go to ECC right now is to get a bigger safety
margin on your crypto. And it really makes no sense to want to do that
and be shooting yourself in both feet by using signature keys for
encryption or vice versa.

The keys are plenty small enough to have separate encryption and
signature keys. It would be no bad thing if we made it algorithmically
impossible to attempt that type of abuse.

I do want to junk the NIST curves though but not for the reason folk
think. The big problem with ECC is the sheer length of time we have
been waiting. Deployment is going to continue to be slow unless we get
some sort of starting gun. One possibility is that the starting gun is
breaking RSA1024 but having a new set of NSA-free curves agreed by
IETF is good as well.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 13 Aug 2014 22:42:43 -0400

+1

To be clear, I am arguing that we put HSM support way ahead of a
single model. HSM support is essential, a single model is someone's
idea of tidiness.

You might think you are going to share the sign and decrypt code but I
bet you won't.

---

From: Benjamin Black <[email-masked]>
Date: Wed, 13 Aug 2014 20:00:59 -0700

"The use of ECC to date in open standards based systems is so
insignificant that we really should not think twice about blowing it
all up and starting from scratch."

ECDHE is the default kx for Google, Microsoft, Facebook, Twitter, and many
other large service providers. Perhaps you mean ECDSA.

"And it really makes no sense to want to do that
and be shooting yourself in both feet by using signature keys for
encryption or vice versa."

Which encryption do you mean here?

b

On Wed, Aug 13, 2014 at 7:39 PM, Phillip Hallam-Baker <[email-masked]
> wrote:

---

From: Benjamin Black <[email-masked]>
Date: Wed, 13 Aug 2014 20:48:57 -0700

"You might think you are going to share the sign and decrypt code but I
bet you won't."

Using the same scalar multiplication code for kx and signatures is the
norm.

On Wed, Aug 13, 2014 at 7:42 PM, Phillip Hallam-Baker <[email-masked]

> >> Requiring a single model for everything significantly reduces
> opportunities for mistakes and the small performance gain of multiple
> models does not justify requiring the additional exposure.
> >
> > That's a value judgement, and different people will come to different
> conclusions. It's certainly not an axiomatic principle. And when I see it
> put forth like that, I instantly get suspicious of the people doing that.
>  FWIW.
> >
> > To me, it's trading off "this is hard, and some people will get it
> wrong" -- when the community of people doing it is maybe a few hundred,
> certainly under 1K -- compared to zillions of devices in the web of things
> for the next couple of decades.
> >
> >         /r$
> >
> > --

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 14 Aug 2014 06:49:17 +0100

On 14/08/2014 03:42, Phillip Hallam-Baker wrote:

> single model. HSM support is essential, a single model is
> someone's idea of tidiness.

That is a null property. Anything we can specify can be implemented in
software or hardware. As I said before, there will _eventually_ be new
HSMs, and new HSM firmware. People have already begun work on that.

The commercial world of this are however glacially slow-moving, partly
due to onerous and ineffective governmental certification requirements
(one of the things that has been - rightly - criticised). Several do
not support ECDSA (or ECDHE, where applicable) properly or at all, and
this is why RSA is still far more common in the wild and ECDSA is
quite honestly barely used by anyone publicly (there are _very few_
ECDSA PKIX roots...) - those that are using it are running it in
software and are therefore not relevant to your 'essential' requirement.

That's about the same as Kevin's problem with military procurement
cycles (in fact, more identical than you think - we are actually
talking about the same vendors/fabs in some cases!).

Inertia mustn't hold us back from recommending anything new and
better, because otherwise we'd _never_ consider anything new.

The TLS WG asked for this because they have new requirements for trust
and performance reasons. Anyone using a commercially-available HSM
obviously doesn't, and are not the intended targets of this proposal
within the timeframe ECC will be useful at all.

Most TLS stakeholders are much, much more agile than that. You can
usually spot the ones that aren't: still using 3DES. :-)

- -- 
/akr

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 14 Aug 2014 08:16:22 -0400

> other large service providers. Perhaps you mean ECDSA.

No, I see no reason to consider that use as relevant at all to the
decision of what the preferred curves should be for the industry for
the future.

ECDHE does not create legacy issues because it is by definition always
a direct negotiation between two parties who both know what they are
doing. So transition is simply specifying a new cipher suite.

Transition in the PKIX part of TLS is really hard because a curve is
only useful if everything under the sun supports it.

The issue is not who uses is but what the switching costs are. I am
looking at the parts of the problem with the highest switching costs.

> Which encryption do you mean here?

Encryption of static data and key exchange really should be separate
from signing.

One protocol design aspect that bleeds in here is how the key exchange
works. There are two mechanisms that can be used for doing ephemeral
keys (leaving out mutual auth for the moment)

A) Encrypt the ephemeral key under the server's public key.

B) Server returns an ephemeral key and client nonce signed by its
private key. [Or alternatively authenticated under a MAC derived from
a master session key]

>From a proof point of view, both seem equally secure but A is actually
a lot better than B because it allows for depth in security.

I want the security of the connection to be protected by both the
master keys and the ephemerals. So breaking an ephemeral only allows
an attack if the master key is also compromised. Sending an
authenticated key across en-clair is a lot weaker than using
encryption. What we should do is this:

A1) As for A but derive the session key from a hash of both the master
session secret and the result of the ephemeral agreement.

So if we have a WF-256 key we can still use a WF-128 ephemeral for
forward secrecy without reducing the security overall.

As a practical matter, we don't need to worry about the WF-192 key at
all, nobody will ever use it. And nobody is going to use less than
WF-256 with PKIX. It is however possible that DNSSEC would use WF-128
keys because of the different mode of use. Curve 25519 might well be
the right match there.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 14 Aug 2014 08:26:01 -0400

On Thu, Aug 14, 2014 at 1:49 AM, Alyssa Rowan <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>

What the constraint means is that if we come down to two curves and
little to choose between them and there is a significant difference in
the HSM situation then the curve that allows re-use of existing HSMs
wins, if neither does that then the curve that has support from HSM
manufacturers wins.

So folk peddling a curve would do well to line up HSM vendor support.

It isn't quite true to say that you can do everything in hardware or
software. There are very specific constraints here to do with side
channels and IPR that could have a huge bearing on what curve families
are viable and which are not.

> software and are therefore not relevant to your 'essential' requirement.

There are very few serious CAs. So its not surprising there are few
ECC roots. We have ECC roots, so do the other leading CAs. But the
reason for the lag has been IPR FUD.

---

From: Alyssa Rowan <[email-masked]>
Date: Thu, 14 Aug 2014 14:10:38 +0100

On 14 August 2014 13:26:01 BST, Phillip Hallam-Baker <[email-masked]> wrote:

>It isn't quite true to say that you can do everything in hardware or software. There are very specific constraints here to do with side channels and IPR that could have a huge bearing on what curve families are viable and which are not.

Well, as per IPR policy: please identify any (still-extant) relevant patents you're aware of?

>There are very few serious CAs. So its not surprising there are few ECC roots. We have ECC roots, so do the other leading CAs. But the reason for the lag has been IPR FUD.

>From who: Certicom? (Who are on this list.) All the more reason to bring this to the fore, then: if "IPR FUD" is constraining wide PKIX adoption of ECDSA with NIST P256, then there is actually far _less_ legacy for us to be scared of deprecating, and more reason for us to consider carefully the IPR status of every algorithm, technique and curve family considered.

We need to recommend things everyone can actually use, royalty-free.

- --
/akr

---

From: Watson Ladd <[email-masked]>
Date: Thu, 14 Aug 2014 07:39:50 -0700

> So folk peddling a curve would do well to line up HSM vendor support.

Let's back up a bit: every curve can be expressed in Weierstrass form
over the same field, so will work with todays ECDSA implementations.
Good? No.

1: Some implementations may have dedicated hardware to do reduction on
the NIST primes
2: Some implementations may assume prime order for correctness
3: Some implementations may not permit the use of arbitrary parameters

So to the extent that we are changing curves, it's not clear that
there is any way, even if we use prime order Weierstrass over the same
primes, to get complete support on HSMs. It's also not clear that
different curves materially differ in this respect.

> are viable and which are not.

All the proposals look about the same: if you were to quiz me on which
was which, just showing me the primes and the coefficients, I would
have to do some arithmetic to see if they were complete or not, and so
if they were the NUMS curves or not.

Sincerely,
Watson Ladd

---

From: "D. J. Bernstein" <[email-masked]>
Date: 14 Aug 2014 19:38:59 -0000

The current topic is the simplicity of secure implementations: in
particular, how this is affected by choosing Montgomery coordinates
rather than Edwards coordinates for DH, assuming that one has already
chosen Edwards coordinates for signatures (in violation of standards
such as ECDSA, contrary to MSR's claims, but that's a separate issue).
Everyone seems to agree that simplicity of secure implementations is
desirable, so I presume that it will end up on the list of desiderata.

> Using the same scalar multiplication code for kx and signatures is the

Really? Then how do you explain MSR ECCLib? I peeked briefly at the code
and found a rather long function

   ECCRYPTO_STATUS ECC_DBLMUL_INTERNAL_TE(POINT_PRECOMP_EXTAFF_TE
   *P_table, dig *k, POINT_TE Q, dig *l, POINT_TE R, unsigned int w_P,
   PCurveStruct TedCurve)
   { // Double-base scalar multiplication R = k.P + l.Q using wNAF with Interleaving

which doesn't seem to be used in your DH performance numbers, along with
another rather long function

   ECCRYPTO_STATUS ECC_MUL_TE(POINT_TE P, dig *k, POINT_TE Q, PCurveStruct TedCurve)
   { // Variable-base scalar multiplication Q = k.P using fixed-window method 

which doesn't seem to be used in your signature (mislabeled "ECDSA")
performance numbers. I don't immediately find functions for signing and
verification (is this actually a complete library?), and I suppose that
with some extra work you could implement signature verification using
ECC_MUL_TE rather than ECC_DBLMUL_INTERNAL_TE, but this doesn't seem
consistent with the performance claims. Am I misunderstanding something?

> As illustrated in the NaCl and TweetNaCl libraries having multiple
> required models makes implementation more challenging

Have you actually looked at the code? It doesn't support your claims.

Let's start with TweetNaCl, which prioritizes simplicity (but is still
fast enough for many applications). Here's the complete high-security
constant-time TweetNaCl code for DH shared-secret computation using the
Montgomery x-coordinate for Curve25519---excluding the subroutines that
are already used in TweetNaCl's implementation of Ed25519 signatures:

  int crypto_scalarmult(u8*q,const u8*n,const u8*p){u8 z[32];i64 x[80],r,i;
  gf a,b,c,d,e,f;FOR(i,31)z[i]=n[i];z[31]=(n[31]&127)|64;z[0]&=248;
  unpack25519(x,p);FOR(i,16){b[i]=x[i];d[i]=a[i]=c[i]=0;}a[0]=d[0]=1;
  for(i=254;i>=0;--i){r=(z[i>>3]>>(i&7))&1;sel25519(a,b,r);sel25519(c,d,r);
  A(e,a,c);Z(a,a,c);A(c,b,d);Z(b,b,d);S(d,e);S(f,a);M(a,c,a);M(c,b,e);
  A(e,a,c);Z(a,a,c);S(b,a);Z(c,d,f);M(a,c,_121665);A(a,a,d);M(c,c,a);
  M(a,d,f);M(d,b,x);S(b,e);sel25519(a,b,r);sel25519(c,d,r);}
  FOR(i,16){x[i+16]=a[i];x[i+32]=c[i];x[i+48]=b[i];x[i+64]=d[i];}
  inv25519(x+32,x+32);M(x+16,x+16,x+32);pack25519(q,x+16);return 0;}

For DH keygen you also have to include the following lines:

  static const u8 _0[16], _9[32] = {9};
  int crypto_scalarmult_base(u8 *q,const u8 *n)
  { return crypto_scalarmult(q,n,_9); }

That's it.

The total complexity of the combined DH+signature implementation in
TweetNaCl is much higher: it includes the top-level signature code and
verification code, a hash function, and (shared between signatures and
DH) the underlying code for arithmetic mod 2^255-19, serialization, etc.
An implementation focused on DH---exactly what many applications need---
can skip many lines of signature-specific code, although obviously it
still needs the arithmetic mod 2^255-19. An implementation focused on
signatures---exactly what many other applications need---would only be
able to skip the above lines.

The arithmetic mod 2^255-19 is also the part that requires much more
work for a high-speed implementation. There's no reason to deviate from
the simple high-level Montgomery structure, but top performance requires
careful attention to the lower-level details of arithmetic.

The arithmetic mod 2^255-19 is _also_ the part that requires by far the
most work for auditors. Our auditing standards for NaCl are far beyond
normal industry practice, and the bug you mentioned was in code that was
never accepted into NaCl---a bug not in something high-level such as the
Montgomery ladder, but rather in the lower-level details of highly
optimized arithmetic. Note that the subsequent paper

   http://cryptojedi.org/papers/#verify25519

(ACM CCS 2014) formally verifies the Montgomery-ladder steps in two
highly optimized assembly-language implementations of Curve25519---
including all the details of arithmetic mod 2^255-19.

You correctly observe that the signature portion of TweetNaCl is simpler
than the DH+signature portion: it saves the lines of code shown above. 
But what you're claiming is something completely different (and
incorrect), namely that Montgomery+Edwards on the wire for DH+signatures
"makes implementation more challenging" compared to Edwards+Edwards.

In fact, switching from Montgomery coordinates to Edwards coordinates
for DH would make the simplest DH-specific implementations noticeably
more complex, and certainly wouldn't allow a DH+signature implementation
to be less "challenging." For higher-speed implementations, whether pure
DH or DH+signature, much more code is required for fast arithmetic mod
the prime, further reducing any possible value in these speculative
high-level DH+signature simplifications.

---Dan

---

From: Tanja Lange <[email-masked]>
Date: Fri, 15 Aug 2014 04:31:50 +0200

>    be evaluated at one of those levels.
You Keep Using That Word, I Do Not Think It Means What You Think It Means.

Seriously, define for me n-bit security level.

	Tanja

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 15 Aug 2014 01:27:24 -0400

> Seriously, define for me n-bit security level.

Well its easy enough to define work factor according to best known attack.

Only we need some security margin and we probably need to round up so
that we can defend the choice to folk who are not experts without
getting into citing specific papers.

So if the work factor isn't a 1:1 exponent of the key size or very
close, one way is we round up to the next integer.

AES-128 has a work factor of 2^128
AES-256 has a work factor of 2^256

A 128 bit modulus curve does not have a 128 bit work factor, its less.
but it is greater than 64 bits which is 128/2.

Now obviously the case can be made that a 448 bit modulus gives a work
factor greater than 2^256. But it requires a PhD to understand it. And
that is not a case I want to have to make to lay-people who think
everyone secretly works for the NSA.