Subject: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Additional Curves in TLS

From: Robert Ransom <[email-masked]>
Date: Thu, 23 Jan 2014 14:18:34 -0800

This is relevant to CFRG discussions as well, and I don't know whether
everyone on the CFRG list is also subscribed to the TLS list.

---------- Forwarded message ----------
From: Robert Ransom <[email-masked]>
Date: Thu, 23 Jan 2014 13:37:18 -0800
Subject: Re: [TLS] Curve25519 in TLS and Additional Curves in TLS
To: Manuel Pégourié-Gonnard <[email-masked]>
Cc: [email-masked]

On 1/23/14, Robert Ransom <[email-masked]> wrote:
> On 1/23/14, Manuel Pégourié-Gonnard <[email-masked]> wrote:
>> On 23/01/2014 02:17, Robert Ransom wrote:

>>> * If you do not add a leading point-format byte, there is no reason to
>>> specify the meaning of the high bit in this document.  If you do add a
>>> leading byte, you will have to choose in this document whether the
>>> sign bit is for the Edwards-form x coordinate or the Montgomery-form y
>>> coordinate.
>>>
>> Or we could add a leading byte now and say that the meaning of the msb is
>> not
>> defined yet an reserved for future use (which is what you suggest anyway,
>> IIUC).
>> Then a future document could update the meaning of this leading byte.
>
> I think that's easiest (provided that current implementations also
> accept 64-byte points and discard the second half; see below).

On further thought, there is a major technical benefit to sending
(either all of or a sign bit for) the Edwards-form x coordinate rather
than the Montgomery-form y coordinate.  Denoting the Montgomery-form
point as (u, v) and the Edwards-form point as (x, y), the isomorphism
from Montgomery form to Edwards form computes x = 2 u/v, which is
undefined for the point of order 2 (Montgomery (0, 0)).

I think that issue, combined with the fact that implementations which
use the sign bit will almost certainly use Edwards form internally,
should rule out any use of a Montgomery-form y coordinate in any
current or future protocol.

Since Curve25519's coordinate field order is congruent to 5 mod 8,
there is no notion of ‘principal square root’, and thus no plausible
alternative to using the least significant bit of a coordinate as its
sign bit.  So there is only one likely choice of sign bit for
Curve25519 group elements, and that is the LSB of the Edwards-form x
coordinate.

Now that I'm not worried about what will eventually be chosen as the
sign bit, the only reason I can see to use a leading magic byte in the
point format is to distinguish ‘the sender did not compute the sign
bit of this point’ from ‘the sender computed the sign bit of this
point, and it is 0’.  I have previously suggested that distinguishing
those cases could be useful, but now I think mitigation of
implementation fingerprinting is more important -- I see no reason to
advertise whether an implementation computes the sign bit of its group
elements or not, even if an attacker could infer that piece of
information after a series of connections.

Robert Ransom

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 23 Jan 2014 16:59:12 -0800

> Curve25519 group elements, and that is the LSB of the Edwards-form x

Wouldn't http://tools.ietf.org/html/draft-jivsov-ecc-compact be another 
method?

Traditionally the problem was solved by carrying 1 bit and then finding 
a place to fit it in and defining what it means, etc. There is another 
way. One can adjust the private key to make the coordinate that we drop, 
x in this case, be the smallest of the two possibilities.

The nice feature of my proposal is that you can still also encode the 
bit if you wish so, as you proposed.

> information after a series of connections.

That's why I think that the party that generates the key needs to be 
nice to everybody and make the key "compliant". If you mandate a very 
fast adjustment Order-private_key (if you have to), there is no ambiguity.

In general, I think that whatever the encoding of the bit is, it needs 
to be fixed in the document.

( BTW, the proposal in the draft is in public domain since it was 
published on December 10, 2012. )

---

From: Michael Hamburg <[email-masked]>
Date: Thu, 23 Jan 2014 18:08:45 -0800

On Jan 23, 2014, at 4:59 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> Wouldn't http://tools.ietf.org/html/draft-jivsov-ecc-compact be another method?
> 
> Traditionally the problem was solved by carrying 1 bit and then finding a place to fit it in and defining what it means, etc. There is another way. One can adjust the private key to make the coordinate that we drop, x in this case, be the smallest of the two possibilities.
> 
> The nice feature of my proposal is that you can still also encode the bit if you wish so, as you proposed.

This is interesting, but I think it works better with the Edwards x-coordinate instead of the Montgomery y-coordinate.  That is, it applies well to Watson’s (Montgomery x, Edwards x) representation.  This is because not every point you might want to transmit is a public key; it might be the product of something which does not support an easy negation, such as PAKE.  In this case, with your proposal, implementers have to send the sign bit, and we have two wire formats again.  But if the Edwards x-coordinate is used, you can also fast-adjust by adding the point of order 2, which maps EdX to -EdX.  (It maps EdY to -EdY and MontX to 1/MontX.)  If the protocol wipes out the cofactor (almost every protocol does for security reasons), then this is more likely to be acceptable than negating the point.

Then again, any discussion like this is fraught with issues about alternative encodings for non-wire formats, implementation compatibility, uniqueness, covert channels, etc.  Might take some hashing out.

Cheers,
— Mike

---

From: Robert Ransom <[email-masked]>
Date: Thu, 23 Jan 2014 18:58:02 -0800

> published on December 10, 2012. )

Are you claiming that the point format that I suggested is patented?

Robert Ransom

---

From: Robert Ransom <[email-masked]>
Date: Thu, 23 Jan 2014 19:17:12 -0800

On 1/23/14, Michael Hamburg <[email-masked]> wrote:
>> Traditionally the problem was solved by carrying 1 bit and then finding a
>> place to fit it in and defining what it means, etc. There is another way.
>> One can adjust the private key to make the coordinate that we drop, x in
>> this case, be the smallest of the two possibilities.
>>
> This is interesting, but I think it works better with the Edwards
> x-coordinate instead of the Montgomery y-coordinate.  That is, it applies
> well to Watson’s (Montgomery x, Edwards x) representation.  This is because
> not every point you might want to transmit is a public key; it might be the
> product of something which does not support an easy negation, such as PAKE.
> In this case, with your proposal, implementers have to send the sign bit,
> and we have two wire formats again.  But if the Edwards x-coordinate is
> used, you can also fast-adjust by adding the point of order 2, which maps
> EdX to -EdX.  (It maps EdY to -EdY and MontX to 1/MontX.)  If the protocol
> wipes out the cofactor (almost every protocol does for security reasons),
> then this is more likely to be acceptable than negating the point.

This makes point encoding to Montgomery-form x slightly less efficient
and more complex -- instead of computing (for the main coordinate)
Zinv=1/Z, then x=X*Zinv, this requires XZinv=1/(X*Z), then either
x=X^2*XZinv or xinv=Z^2*XZinv (conditional on the sign bit of the
Edwards-form x coordinate).  (I'm omitting the part where Zinv or
XZinv must be batched with the inversion to compute the Edwards-form x
coordinate and its sign bit.)

(It may still be worthwhile; I'm just pointing out exactly what effect
this would have on implementations.  I should also point out that the
Montgomery-form x coordinate can't distinguish the identity element
from the point of order 2.)

Robert Ransom

---

From: Mike Hamburg <[email-masked]>
Date: Thu, 23 Jan 2014 22:07:55 -0800

> from the point of order 2.)

You're right.

The part that counts is complexity, though, not speed.  Adding a dozen muls to a 2500-mul computation is less than half a percent.  The bigger the curve, the smaller the fraction.

Furthermore, to be a truly uniform point-encoding format (including for hashes and stuff), you'd have to modify your ladder to figure out which y is correct at the end.  And that's going to be complicated.  Or you could not do that, but then again you'd have to figure out which encoding to use where.  I should probably go work out the formulas and post them at some point...

So yeah.  Upside.  Downside.

-- Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Thu, 23 Jan 2014 22:31:09 -0800

> Then again, any discussion like this is fraught with issues about alternative encodings for non-wire formats, implementation compatibility, uniqueness, covert channels, etc.  Might take some hashin…

It seems to me that it will be possible to find an option to tweak the 
private scalar in more complex protocols, while making this an internal 
adjustment.

For example, in
http://tools.ietf.org/search/draft-irtf-cfrg-dragonfly-02#page-10

the PE is never sent out, so its generation doesn't change.

The Element is a point, which is very similar to a public key for our 
purpose. The Element is sent to the other peer and it needs to be 
"compliant". The element is generated from a random mask and PE; thus 
the mask can be adjusted appropriately so that the Element is 
"compliant" (then the 'scalar' is calculated with the appropriately 
adjusted mask).

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 24 Jan 2014 10:44:57 -0800

On Jan 23, 2014, at 10:31 PM, Andrey Jivsov <[email-masked]> wrote:

> It seems to me that it will be possible to find an option to tweak the private scalar in more complex protocols, while making this an internal adjustment.
> 
> For example, in
> The Element is a point, which is very similar to a public key for our purpose. The Element is sent to the other peer and it needs to be "compliant". The element is generated from a random mask and PE; thus the mask can be adjusted appropriately so that the Element is "compliant" (then the 'scalar' is calculated with the appropriately adjusted mask).

Dragonfly, SPEKE and ECDH don’t use addition, and don’t need y-coordinates at all.  They could use a Montgomery ladder and never compute or transmit those coordinates.

Some systems, such as signatures, use addition but don’t send the results out on the wire.  Your technique works well for those.  You still need a point encoding before hashing, but compression has no value there anyway.

But I can’t think of an obvious way to extend your approach to a protocol like SPAKE2 which requires sending a point out after addition.

— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 24 Jan 2014 12:01:38 -0800

> But I can’t think of an obvious way to extend your approach to a protocol like SPAKE2 which requires sending a point out after addition.
I looked at this description of SPAKE2 
http://www.ietf.org/mail-archive/web/cfrg/current/msg03840.html

I will use the additive notation. Assuming M=m*G, the SPAKE2 client 
sends the point (x+h(pass)m) G

It must be a compliant point. Let's say that the client must adjust (1) 
to (2)

    (x+h(pass)m)  (1)
    Ord - x - h(pass)m   (2)

Doing just that will not work because the server will be subtracting (in 
effect) h(pass)m and the server will not arrive at either x or Ord-x.

Here is what the client does instead.

The client adjusts the randomly generated x as

    x' = Ord - x - 2h(pass)m

and assumes x' and x'*G as the ephemeral keypair (corresponding to the 
g^x in the above email reference)

Now, with that private x' plugged into the equation (1), (1) is exactly 
(2), which we said is a compliant point. Then the value in (2) times G 
is sent out.

Performance-wise, the delta = Ord - 2h(pass)m by which the x may need to 
be adjusted is fixed for the user (provided that the M is fixed).

Hopefully, I can always get away with this technique, as long as a peer 
generates a random private-key-like scalar that I can adjust (by Ord in 
trivial cases, but potentially by other quantities as in SPAKE2).

This should work for your suggestions to use the Elligator map, assuming 
that I get the corresponding scalar.

I will need access to the private m for M=mG. I assumed it is sort of a 
user static public key.

The server side adjustments are similar.

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 24 Jan 2014 12:13:49 -0800

On Jan 24, 2014, at 12:01 PM, Andrey Jivsov <[email-masked]> wrote:
> This should work for your suggestions to use the Elligator map, assuming that I get the corresponding scalar.
> 
> I will need access to the private m for M=mG. I assumed it is sort of a user static public key.
> 

It is critical to the security of SPAKE2 that nobody can know m.  Part of why Elligator is nice is that it removes the possibility that someone could somehow figure out m, thereby breaking the security of the entire system.  It is an essential security feature of Elligator (in this use and others) that it does not give you access to that discrete log.

So, in other words, you can’t do this, and changing the system so that you can do this would break it.

Cheers,
— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 24 Jan 2014 12:19:21 -0800

On 01/24/2014 12:13 PM, Michael Hamburg wrote:
> On Jan 24, 2014, at 12:01 PM, Andrey Jivsov <[email-masked] 
> <mailto:[email-masked]>> wrote:
>> This should work for your suggestions to use the Elligator map, 
>> assuming that I get the corresponding scalar.
>>
> It is critical to the security of SPAKE2 that nobody can know m.  Part 
> of why Elligator is nice is that it removes the possibility that 
> someone could somehow figure out m, thereby breaking the security of 
> the entire system.  It is an essential security feature of Elligator 
> (in this use and others) that it does not give you access to that 
> discrete log.
>

Given that I am trusted to keep my password, why am I not trusted to 
keep my m in M=m*G private?

---

From: Robert Ransom <[email-masked]>
Date: Fri, 24 Jan 2014 13:04:59 -0800

> keep my m in M=m*G private?

M and N are protocol parameters, and must be shared among all users.

Robert Ransom

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 24 Jan 2014 14:37:05 -0800

> M and N are protocol parameters, and must be shared among all users.
I see. So the protocol allows a network of nodes where each one can be a 
server or a client. Given recent discussions on this list, the trusted 
3d party that is generating the M,N and forgetting the m,n is better be 
really trusted ;-).

The solution then is the "black box" one. Generate x randomly until the 
X = xG + h(pass)M is a compliant point. The expected number of tries 
should be 2. (sec 
http://tools.ietf.org/html/draft-jivsov-ecc-compact-03#section-4.2.1 but 
the criterion is for X, not xG )

---

From: Watson Ladd <[email-masked]>
Date: Fri, 24 Jan 2014 15:15:06 -0800

> I see. So the protocol allows a network of nodes where each one can be a
server or a client. Given recent discussions on this list, the trusted 3d
party that is generating the M,N and forgetting the m,n is better be really
trusted ;-).

All of this to save 32 bytes?

>
> The solution then is the "black box" one. Generate x randomly until the X
= xG + h(pass)M is a compliant point. The expected number of tries should
be 2. (sec
http://tools.ietf.org/html/draft-jivsov-ecc-compact-03#section-4.2.1 but
the criterion is for X, not xG )
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Dan Harkins" <[email-masked]>
Date: Sat, 25 Jan 2014 01:34:33 -0800 (PST)

On Fri, January 24, 2014 3:15 pm, Watson Ladd wrote:
>>>>>> I will need access to the private m for M=mG. I assumed it is sort
>>>>>> of
>>>>>> a user static public key.
>>>>>>
>>>>> So, in other words, you can’t do this, and changing the system so
>>>>> that
>>>>> you can do this would break it.
>>>>>
>>>>> Cheers,
>>>>> — Mike
>>>>

  No, it has nothing to do with saving 32 bytes. It has to do with making
SPAKE2 be something other than the DUAL_EC_DRBG of PAKEs (a protocol
with SUTS-- something up their sleeve).

  Dan.

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 28 Jan 2014 00:26:01 -0800

> Are you claiming that the point format that I suggested is patented?

I was making a statement about my contribution, in case this issue comes up.

The IP for the use of 1 bit to compress a point is a common knowledge, 
but I've heard that some of them are expiring.

However, I am concerned about the cofactor issue. These curves have the 
cofactor greater than 1. Unlike "unsafe" NIST curves, this needs to be 
handled. The draft suggest methods that, as I understand them, may run 
into IP issues. Besides, there may be protocols that want to do classic 
DH. One solution to these issues is to enumerate the points in the small 
subgroup, explicitly in the document, or by providing the method to 
identify them.

---

From: Robert Ransom <[email-masked]>
Date: Tue, 28 Jan 2014 06:47:47 -0800

> but I've heard that some of them are expiring.

If you are referring to the patent addressed in
<http://cr.yp.to/patents/us/6141420.html>, claim 29 of the same patent
covers point decompression with your proposal.

> subgroup, explicitly in the document, or by providing the method to

U.S. patent 6,226,383 (Jablon) claims 31 and 32 cover the use of your
suggestion in ECDH.

Dr. Bernstein's paper which specifies Curve25519 for use in ECDH
addresses its groups' cofactors by (a) generating Diffie-Hellman
keypairs such that the secret exponent is divisible by the cofactor
(as is common in multiplicative-group Diffie-Hellman, where the
cofactor is at least 2), and (b) requiring that the shared-secret
group element be used only as input to a hash function or hash-based
KDF (as is required for all Diffie-Hellman systems).

Are you aware of any specific patent claims which cover these
techniques, or are you merely trying to spread patent FUD?

Robert Ransom

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 28 Jan 2014 09:20:29 -0800

I am basing the method on the the CRYPTO '85 paper, which tells:

> Finally, it should be remarked, that even though we have phrased
> everything in terms of points on an elliptic curve, that, for the key
> exchange protocol (and other uses as one-way functions), that only the
> x-coordinate needs to be transmitted. The formulas for multiples of a
> point cited in the first section make it clear that the x-coordinate of
> a multiple depends only on the x-coordinate of the original point.

> U.S. patent 6,226,383 (Jablon) claims 31 and 32 cover the use of your

I try not to read patents, one never knows what can be found there...

Because any modp group will have a cofactor of at least 2, all modp 
operations are effected by these claims. These claims would cover, for 
example, http://tools.ietf.org/html/rfc6989 sec 2.2 that excludes 0 and p-1.

I was assuming that such a general method of comparing one element to 
another, or a concept of a subgroup, were known before 1990s.

> techniques, or are you merely trying to spread patent FUD?

The quick search reveals this one: US6563928. Yes, I did notice that the 
paper specifies that the key generation must clear the lower bits, which 
is equivalent to multiplying by a (power of 2) cofactor. Such a method 
hardwires the cofactor multiplication into the field operation. This was 
not necessarily needed, but I understand that this was important to be 
"safe". I personally would prefer the cofactor not to be a part of the 
raw ECC operations.