Subject: [Cfrg] Whether the performance advantage of small d needs to affect specifications.

From: Adam Langley <[email-masked]>
Date: Wed, 31 Dec 2014 13:27:35 +0000

As I understand it, we have significant agreement at the ~128-bit
level: Microsoft accepts curve25519 with a different base point and
sending Montgomery-X for ECDH. Everyone else accepts curve25519 with
Montgomery-X for ECDH. (I'm not considering those who want random
primes as the chairs have said that's out of scope for now.)

Since any base point (in the correct subgroup) is as good as any
other, I'm going to make the assumption that significant existing
practice will mean that we can we can all end up accepting x=9 as the
base point.

Where Microsoft still differ at ~128-bits is that they specify an
isogenous twisted Edwards curve with small d, while existing practice
uses an isomorphic twisted Edwards curve with d=-121665/121666.

There is no security difference between these, but there is an
argument that the small d brings a performance advantage—possibly
leading to a tension between existing practice and performance.

However, I think that tension can be resolved by considering a small d
as an implementation strategy. That requires that implementations who
wish to use the isogenous curve be able to convert inputs and outputs
to/from the isomorphic curve very cheaply.

1) A "small d" implementation wishes to perform a scalarmult:

This case is fairly easy I think. At the point that the implementation
is doing the transformation to affine form, it holds extended
coordinates (X, Y, Z, T) where x'=X/Z, y'=Y/Z and x'y' = T/Z. (I'll
write (x', y') for the isogenous curve and (x, y) for the isomorphic
one.)

Rather than calculate 1/Z and then multiply that by X and Y, it can
use different formulas to merge the transform to the isomorphic curve:
x = TZ/(2Z^2 - X^2 - Y^2), y = (Y^2-X^2)/(Y^2+X^2). (I don't have
Sage, Python or even enough paper with me, so I *probably* have the
equations wrong, but the strategy should hold.)

Since the inversions can be merged, the cost is essentially the same
as outputting affine coordinates on the isogenous curve.

For a modified ECDSA with Edward's curves (which Microsoft have
suggested that they want to do), this is sufficient since the
signature contains only scalars. For EdDSA, the paper[1] says that
they skip the decompression of 'R' and check that the encoding of the
other side of the verification equation matches 'R', thus this should
be sufficient there too.

However, let's assume that some protocol needs to decompress points:

2) A "small d" implementations wishes to use a compressed point on the
isomorphic curve.

The inverse transformation for the isogeny is more complex and results
in 4 times the point. It also needs the decompressed point as an input
to the map.

As the Ed25519 paper shows, it's possible to merge an inversion and
square root when decompressing Edwards points such that only a single
field exponentiation is needed. I certainly won't get the equations
for the inverse map correct here, but it appears that they'll end up
needing an inversion and calculation of 'x', which needs a square
root. (The value to invert needs to be independent of 'x', but that
appears to be easy to arrange.)

Call the value to be inverted 'a', and let b=uv^7, which is the value
that we need to raise to (q-5)/8 in order to calculate 'x'. (I'm using
the variable names 'u' and 'v' to match [1].)

Calculate (a^8×b)^((q-5)/8) = c = a^(q-5)b^((q-5)/8). Multiplying by
a^4 will eliminate the 'a' term leaving b^((q-5)/8), as needed for the
'x' calculation.

Now c^8 = a^(7(q-1) + q - 33)b^q-5. Thus c^8×a^31×b^4 = a^(q-2), as
needed for the inversion.

So I think (albeit with the distinct possibility that I've missed
something by not being able to confirm that it works) that a "small d"
implementation can use compressed points from the isomorphic curve
with only a single field exponentiation, which is the same cost as
decompressing points is for implementations of the isomorphic curve
anyway. It does result in 4R, but often that's not a problem, and
could even be an advantage. (Consider ECDH with compressed points on
the wire: since the private scalar is a multiple of 8, the two
low-order bits can just be skipped.)

So, hopefully, a performance advantage of small d, if any, can be
realised even if the isomorphic curve is specified on the wire. Thus
there need not be tension between performance and existing practice
here.

(Time to catch my flight.)

[1] http://ed25519.cr.yp.to/ed25519-20110926.pdf, section 5.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Wed, 31 Dec 2014 14:50:07 +0100

Hi.

On Wed, 2014-12-31 at 13:27 +0000, Adam Langley wrote: 
> Microsoft accepts 

vs.

> Everyone else accepts

When following the list recently, a recurring issue that seemed to
dominate the discussions is "Microsoft vs. everyone else" and the urge
to reach consensus.

In principle consensus is of course a good thing, since a new standard
or recommendations would be accepted by everyone, but it's also kinda
disturbing when one big player can apparently basically block what
nearly all others would already agree upon.

But in the light of the NSA&friends scandal which basically gave the
CFRG it's purpose (since it became all too obvious that NIST is
untrustworthy per se)

... and in the light of governments being able to easily control&command
companies from at least their own country with secret court orders, gag
orders etc.
... and in the light that we've already seen government agencies
disturbing crypto/security standards indirectly via straw men

I think it's really a bad idea for the CFRG to strive so much for
consensus.

It basically leads us back to the original problem of simply taking
standards from NIST, in that we don't know whether changes wich seem
harmless and not affecting security actually do for someone who may
posses some more knowledge already.
And even if not, one fraction shouldn't be able to block things for so
long, which in a higher level way also undermines security.

Microsoft (and others) may surely be big players, but what should really
count for the CFRG and for a good standard/recommendation is now how
revenues a player has, but rather how many crypto-experts actually voice
and prove their arguments/objections/etc..
And from that POV Microsoft doesn't look like *that big* player anymore.

The main task of CFRG should be to give as good as possible
recommendations/standards.
Whether these standards are actually taken up in the end by the big
players in their products is completely up to them and not even
guaranteed when consensus would have been reached.
Which is just another reason, not to make (possibly bad) compromises.

Cheers,
Chris.

---

From: Adam Langley <[email-masked]>
Date: Wed, 31 Dec 2014 14:44:46 +0000

> I think it's really a bad idea for the CFRG to strive so much for

If you believe in the security of curve25519 then you also believe in the
security of Microsoft's current position at ~128 bits. They have the same
structure and thus strictly the same strength.

There's /no/ possibility of weakening anything, mathematically, with a
different base point (in the correct subgroup) or by using an isogeny.

IRTF groups do not, technically, have to reach consensus. However, everyone
does have to function on the same Internet at the end of the day.

Cheers

AGL

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Wed, 31 Dec 2014 17:19:34 +0100

On Wed, 2014-12-31 at 14:44 +0000, Adam Langley wrote:
> If you believe in the security of curve25519 then you also believe in
> the security of Microsoft's current position at ~128 bits. They have
> the same structure and thus strictly the same strength.
My point wasn't specifically about that discrepancy between curve25519
and MS' position... as you pointed out already in your previous email,
they have the same security, by all means of current knowledge....

> IRTF groups do not, technically, have to reach consensus. However,
> everyone does have to function on the same Internet at the end of the
> day.
... my point was rather about the general political problem that still
hides behind the "now open and no longer NIST controlled"
standardisation process of crypto stuff:
Even though the current example of MS vs. "everyone else" may not be a
security problem, it still shows that the whole process would be kinda
"vulnerable" to manipulations - namely if a big player puts pressure on
the CFRG on behalf of his own ideas (which may - or may not - have some
evil hidden within).

Cheers,
Chris.

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 31 Dec 2014 11:29:00 -0500

> IRTF groups do not, technically, have to reach consensus. However, everyone does have to function on the same Internet at the end of the day.

Neither does the IETF.  As I recall, the phrase is rough consensus.  At least as regards X25519, I think it's pretty obvious that Microsoft is in the rough.

As a security person, not a cryptographer by any stretch of anyone's imagination, this is starting to look like we are trying to find a way to "give them something" so that they can save face.

I think the proper way to phrase the question is this:  are there any security objections to the currently deployed X25519?  Either I haven't seen any, or I haven't understood them.  The only objections have been that they don't fit into a framework.

	/r$

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

---

From: Christoph Anton Mitterer <[email-masked]>
Date: Wed, 31 Dec 2014 17:55:32 +0100

On Wed, 2014-12-31 at 11:29 -0500, Salz, Rich wrote: 
> look like we are trying to find a way to "give them something" so that they can save face.
I really wouldn't think that this is or should be necessary for them.
They have some known experts in the field and saying "we agree with they
majority if there are no security concerns and drop our own proposal" is
no shame at all - actually I think that's an important part of the
research and the process of finding the best solution.

Actually, *if* MS was trying to push something through in order to save
their face (and this is just hypothetical and I don't want to say that
this might be the case)... then *this* would be what would actually
embarrass them.

Cheers,
Chris.

---

From: Yoav Nir <[email-masked]>
Date: Wed, 31 Dec 2014 19:15:15 +0200

> On Dec 31, 2014, at 6:29 PM, Salz, Rich <[email-masked]> wrote:
> 

The consensus process is pretty terrible at choosing between two or more non-horrible alternatives. It’s fairly easy for relatively small groups to block consensus.

When it works, the consensus process produces the best solution that won’t get a group of participants to say, “This sucks, we’re taking out ball and going home.” In our terms that would be Microsoft declaring that the product of this process is not going into Explorer and IIS. 

Compare the process for the ChaCha20+Poly1305 draft. We submitted it, there were several suggestions for improving the text, one suggestion to improve the construction, which was accepted, and a couple of suggestions to modify the base algorithms that were not accepted and no big arguments came out of it. Contributions included better text, pseudo-code, links to research papers about the algorithms, and a more thorough set of test vectors. The group made the document better until there was consensus that it was done.

If the only proposal before CFRG was Curve25519, the process would be the same. I think the extra proposals caught the chairs by surprise. But regardless, it exposed how bad the consensus process is at choosing. For extra fun, see two similar cases at the IETF in the IPsecME working group. 

And now I should  add a sentence that starts with, “And the key to fixing this is…”, but I can’t. As long as we all want to interoperate on the same Internet, and as long as we don’t have any format authority (the way NIST does), we are forced to do our best to avoid people “taking their ball and going home”.  I don’t know how to fix this.

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Wed, 31 Dec 2014 16:26:22 -0500

> the CFRG on behalf of his own ideas (which may - or may not - have some

Yeah, but we would be done now if that was what was going on. Might
even be worth it ;)

What people might not be aware of, particularly if they joined the
list late, is that we've been discussing all of these proposals
(except for 2^389-21) since April. Nothing new has been discovered.
Yet we've missed two self-imposed deadlines, and have no visible plan
to actually meet hard external deadlines, coming close to a year since
we decided to start.

Why? Unclear. We've had requests since 2010 to add X25519 to TLS. In
the meantime, Brainpool and ANSSI curves got added without this mess.
Why are we treating Curve25519 differently from these national
standards? And why did it take so long for the initial request to get
sent to CFRG? Irrelevant the problem we face now, but interesting in
considering how avoid it in the future, or, punt it to someone else.

The CFRG is potentially very good at answering questions about
security. But we shouldn't be surprised that it is bad at having to
make choices, particularly when one group remains determined to stay
in the running by consistently modifying its proposal as issues are
raised. The net effect is that people will go out of their way to not
involve CFRG, new cryptography will not get proposed, and attempts to
ensure that protocols are reviewed by people who know what they are
doing in cryptography will meet resistance due to the long delay that
will be feared.

The IRTF and IETF leadership bear a substantial amount of blame for
this situation, as does the leadership of the TLS WG. By kicking over
to the CFRG a question that wasn't "is X25519 secure? What are the
issues with adoption?", they managed to ensnare us. Meanwhile, SSH
continues to adopt Ed25519, and X25519 without a problem.

The proposed longer curve over 2^384-317 or whatever, is inferior in
security to the equally fast Ed448, and equal in security to the 8%
faster 2^389-21. This is a substantial difference between the
proposals, and is not going away, even with the lower-security curve
being a bikeshed color away from X25519. It's the same difference
between Curve25519 and the original NUMS proposal in terms of prime.

The NUMS group has repeatedly explained that they will not take their
ball and go home, and I doubt that IE and IIS will make the decision
to support or not based on whether or not we pick the NUMS proposal,
which has been repeatedly modified to try to stay in the game. The
concern that we need an actual consensus, or Microsoft won't add these
curves, is one I think is overblown, judging from public statements
from many of the proponents of the NUMS draft.

The fewer differences between the two rival proposals there are, the
more pointless this debate gets. In April the differences were in
point format on the wire, choice of prime (with DJB et al favoring
faster primes, and NUMS slower primes) and signature method. Now we've
eliminated the point format difference, leaving the prime choice
difference, except that the 2^255-19 prime is now being used by both,
and NUMS is open to adding a different signature scheme in addition to
their FrankenECDSA proposal, of which several implementors have been
skeptical of the utility.

The choice is between the extra security of Ed448, extra speed of
2^389-21, or a prime with few redeeming features. Far from being "not
horrible", the NUMS proposal is pure bikeshedding at the 255 bit
length, and retains some of the original disadvantages at the 384
length. We don't know how well it performs in as much detail as I
would like, because there has not been an eBATS submission. Almost all
of the bad original features of the NUMS proposal have been fixed:
they are now proposing the point format for ECDH that was originally
suggested for Curve25519, have corrected the use of incomplete
coordinates, and I think any remaining questions about signatures are
uncontroversial enough to be easily resolved. (If one sentence will
get thrown back at me, this one is it)

TL,DR: I think there are technical factors in favor of either Ed448 or
2^389-21 over the proposed prime at the 384 bit level, either extra
security or extra speed. If the chairs think it necessary to pick the
2^384-317 prime for political reasons they should do, ruling that at
the 384 level the extra performance or security are less important.
They shouldn't rely on the variance between differing benchmarking
systems as an excuse, or try to claim a political choice as due to
spurious technical reasons: I doubt anyone is going to be fooled and
it will only further undermine the reputation of CFRG.

Sincerely,
Watson Ladd

>
>
> Cheers,
> Chris.
>
> _______________________________________________
> 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: Nico Williams <[email-masked]>
Date: Wed, 31 Dec 2014 16:14:23 -0600

On Wed, Dec 31, 2014 at 04:26:22PM -0500, Watson Ladd wrote:
> raised. [...]

The IETF will allow the use of many modern cryptographic algorithms, but
wants to have a limited number of REQUIRED to implement ones.  This is a
good thing: it limits the amount of work needed to produce interoperable
implementations of Internet protocols while still giving us usable
algorithm agility (if there are more than one RTI algorithms; IMO there
should be at least two for each class).

If the IRTF in general, or CFRG in particular are bad at making
recommendations about REQUIRED to implement algorithms, then CFRG should
limit itself to reporting what it has learned -- let the IETF make the
engineering decisions.

That's what I'd expected anyways.  Why are we making this harder than it
needs to be?

Let the IRTF publish one or more documents describing various curves
suitable for use in Internet protocols.  The IETF can pick from among
those.

Nico
--