Re: [TLS] Curve25519 in TLS

[Watson Ladd <[e-mail]>]

Minor nitpicks about language below.

On Tue, Oct 15, 2013 at 11:36 PM, Manuel Pégourié-Gonnard
<[e-mail]> wrote:
> Hi,
>
> On 24/09/2013 17:32, Simon Josefsson wrote:
>> http://tools.ietf.org/html/draft-josefsson-tls-curve25519-01
>>
> I think a few points should be clarified in the draft. As the
> introduction correctly states, Curve25519 is a new ECDH function, not
> just a new curve for use with the usual ECDH construction. Let me sum up
> the constructions of ECDH in TLS and in Curve25519.
>
> TLS ECDH:
> 1. Private keys: random integer in the range [1, q-1] with q the order of G.
> 2. Public keys: a point on the curve (defined over F_p).
> 3. Public key encoding: either
>     (a) the x and y coordinates of the point, or
>     (b) the x coordinate and a bit for determination of the y coordinate,
> with integers represented as big-endian bytes strings, preceded by a
> first byte indicating which format was chosen (and holding the possible
> additional bit).
I don't believe this is correct: RFC4492 permits curves with cofactor
greater than one.
I don't have a copy of the IEEE standard in front of me, but I believe
in this case one has to
do a group membership check. So it depends on what the meaning of G is.
>
> Curve25519 ECDH:
> 1. Private keys: random 254-bit positive integer with the high-order bit
> set and the three lowest-order bits cleared.
> 2. Public keys: any number in the range [0, 2^{256}-1].
> 3. Public key encoding: a byte string in little-endian convention.
>
> Now I'll discuss the differences and possible issues in more detail.
>
> 1. Concerning the private key, I think keeping the paper's definition
> does not raise any issue. Implementors should just be careful to use a
> special procedure for this curve.
What is actually happening is that exponentiation by the private key
is annihilating the small order
torsion subgroup on both the curve and the twist because the private
key is divisible by 8, and the curve and twist
have large prime-order subgroups with cofactor 8 and 4 respectively.
This is a big difference from the usual method,
in which one only sends members.
>
> 2. Concerning the public key, the 256-bit integer in the paper
> represents (modulo p) the x coordinate of a point on the curve E, but
> this point may not be defined over F_p, but over F_{p^2}. An alternative
> way of seeing things is that the public key may be either the x
> coordinate of a point in E(F_p) or of a point in E'(F_p) where E' is the
> twist curve y^2 = x^3 + 2Ax^2 + 4x.
>
> By construction of E, this is not a security issue at all, and rather a
> fact that simplifies implementations of the Curve25519-ECDH protocol,
> since there is no need to check the validity of public keys and they are
> shorter, but it introduces a real difference (in the type of objects,
> not just their representation) with the usual TLS ECDH function.
>
> 3. So, if we want to preserve the nice property than any 32-byte string
> (ie, any 256-bit integer x) is a valid key (and I think we do), we don't
> have a y coordinate at our disposal for the normal encoding procedure.
> Some ideas around this issue:
>
> A. Just use the convention y = 0 and one of the existing formats.
> Pros: simple, just works.
> Cons: with the basic "uncompressed" format, wastes 32 bytes of bandwidth.
Also, a dirty hack.
>
> B. Always use the "ansiX962_compressed_prime" format.
> Pros: doesn't waste bandwidth.
> Cons: forces applications to advertise support this format, which is a
> problem if they can't support it for other prime curves, unless we
> introduce an exception to the effect that support for this format with
> this particular curve is implied as soon as support for the curve is
> advertised. Does not seem very clean to me.
The other issue is that this isn't the ansiX962 format for deep
technical reasons. You would need to use
a birational morphism to Weirstrauß form, which is a pointless PITA,
or just tell pleasing lies, which annoys those of
us trying to analyze things, and is a potential source of bugs.
>
> C. Introduce a new point format "compressed_prime_montgomery".
> Pros: doesn't waste bandwidth, doesn't look hacky.
> Cons: a new point format only for one curve? OTOH, it is indeed a
> particular class of curve, since the recommended formulas work only with
> the x coordinate, and other curves in this class may be added later.
>
> Note that A and C may be combined.
Probably the best idea, especially given that definition of addition
is completely different.
>
> Any other idea?
>
> Manuel.
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls



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