Subject: [TLS] draft-ietf-tls-curve25519-01 and the X25519 significant bit.

From: Adam Langley <[email-masked]>
Date: Tue, 22 Dec 2015 10:52:28 -0800

Curve25519, as the name suggests, operates on 255-bit numbers. When
encoded as bytes, there's obviously a 256th bit that needs to be
specified.

Curve25519 implementations didn't set the bit but did used to vary on
how they parsed it. Some would take a 256-bit number and reduce it
while others would ignore the bit completely.

However, I believe that implementations have converged on ignoring it.
That behaviour is specified in draft-irtf-cfrg-curves and tested via
the test vectors.

Currently https://tools.ietf.org/html/draft-ietf-tls-curve25519-01#section-2.3
says that implementations SHOULD reject inputs with the high-bit set.
I think that should be dropped. The X25519 function is specified in
terms of bytes in draft-irtf-cfrg-curves and I think the TLS spec
should just use that draft.

Cheers

AGL

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

---

From: Brian Smith <[email-masked]>
Date: Tue, 22 Dec 2015 11:36:32 -1000

Adam Langley <[email-masked]> wrote:

> Currently
> https://tools.ietf.org/html/draft-ietf-tls-curve25519-01#section-2.3

First, maybe I'm overlooking something obvious, but I'm not seeing it: Why
are we concerned only with whether the high bit has been set, instead of
whether the public value has been reduced mod q (q == 2^255-19)? Aren't
there ~19 interesting values that don't have the high bit set but which are
also relevant to this issue?

The draft notes that if the sender calculated the result correctly, then
the result will never have the high bit set. So, then, we should have a
requirement on the sender that the sender MUST NOT send a representation of
its public value that has the high bit set? And, more generally, the sender
MUST NOT send a representation of its public value that isn't reduced mod
q. Would this be problematic to add this requirement?

If we added the above requirement on senders, then it would matter less
whether receivers reject values that aren't reduced mod q, as a conforming
implementation would never send them, right?

It seems like a good idea to reject non-reduced public values because:

1. By the argument in section 2.3, a conforming sender would never send
them, so if the sender did send one, it means there's a problem with the
sender of unknown severity, or an unknown attack on the wire. Either way,
it's safest to bail out early.

2. Rejecting non-reduced values allows us to compare keys (after
validation) by bytewise comparison and/or comparison of secure hashes of
the bytes. AFAICT, this seems to matter less for x25519 and ECDH in general
than it matters for signatures, but I bet that is just because I'm not
creative enough to discover why it might matter for ECDH. I did give an
example of why it can matter for signature public keys in [1]. It seems
better to me to be cautious on the topic.

[1] https://code.google.com/p/chromium/issues/detail?id=522228#c9

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Adam Langley <[email-masked]>
Date: Tue, 22 Dec 2015 13:59:00 -0800

> also relevant to this issue?

You're correct, but I'm trying to say that the CFRG document defines a
function that operates on bytestrings so that higher-level protocols
don't have to worry about things like this. I think TLS should handle
the byte strings opaquely so that we have uniform behaviour for
X25519/X448 and only a single place where it needs to be tested. The
behaviour of X25519/X448 for non-reduced values is also specified in
the CFRG document.

Cheers

AGL

---

From: Brian Smith <[email-masked]>
Date: Tue, 22 Dec 2015 13:15:38 -1000

> behaviour of X25519/X448 for non-reduced values is also specified in

I agree with all of that in principle. In fact, I think that most
of section 2.3 should be removed in deference to the CFRG document, and
only TLS-specific concerns should be given.

I still think there is value in requiring senders to send their public
value in the "normalized" form and for allowing (if not requiring)
receivers to reject, at least, public values >= q, for the reasons I gave
in my previous email. Ideally that would happen in the CFRG document. But,
what is the status of the CFRG document? I've heard that it's past the
point where changes will be accepted.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Adam Langley <[email-masked]>
Date: Mon, 28 Dec 2015 07:39:05 -0800

On Tue, Dec 22, 2015 at 3:15 PM, Brian Smith <[email-masked]> wrote:
> I agree with all of that in principle. In fact, I think that most of section
> 2.3 should be removed in deference to the CFRG document, and only
> TLS-specific concerns should be given.
>
> I still think there is value in requiring senders to send their public value
> in the "normalized" form and for allowing (if not requiring) receivers to
> reject, at least, public values >= q, for the reasons I gave in my previous
> email. Ideally that would happen in the CFRG document. But, what is the
> status of the CFRG document? I've heard that it's past the point where
> changes will be accepted.

The CFRG document is in AUTH48 right now so, indeed, it's probably too
late for that sort of change.

To give some background about why the CFRG document ended up the way it did:

The curve25519 paper only mentions the extra bit to say: "Note that
Curve25519 is not surjective: in particular, its final output bit is
always 0 and need not be transmitted." [1]. It didn't specify whether
it should be ignored or not and implementations started to differ on
that point. Also, in order to keep the code simple, it didn't check
for values >= 2^255-19. Both because that could be more code in the
primitive itself, and because it would mean that the function would
change from being total to partial.

Some years ago, there was a small effort to align the different
implementations around the same behaviour and ignoring the bit was
chosen. I think that decision probably arose from changing the fewest
things and also the thought that people might want to use the extra
bit as a sign bit in the future.

No implementations rejected values >= 2^255-19 from what I recall.

Since the CFRG has standardised Curve25519, in practice the existing
implementations will seed the implementation ecosystem. Changing
something really subtle like the extra bit behaviour, or rejecting
oversized values, without a clear need, doesn't seem to me to be
worthwhile (or, perhaps, even achievable for a spec).

So at this point I'd like to nail down the existing behaviour with
tests, try to make it uniform across most implementations, and try to
avoid other specs interpreting the byte strings.

[1] http://cr.yp.to/ecdh/curve25519-20060209.pdf

Cheers

AGL

---

From: Brian Smith <[email-masked]>
Date: Tue, 29 Dec 2015 09:02:25 -1000

Adam Langley <[email-masked]> wrote:

> value
> that point.

Does that matter, though? The CFRG document doesn't allow the sender to set
the high bit to 1, right? In particular, it says "All calculations are
performed in GF(p), i.e., they are performed modulo p." and "For X25519,
the unused, most-significant bit MUST be zero."

If the receiver can detect that the sender is non-conforming, then it
should be able to stop talking to it on that basis alone.

> Also, in order to keep the code simple, it didn't check

I think there is value in it being a total function. But, I think there is
value in checking the conformance of the sender in the receiver. Note that
such a check can be layered on top of the X25519 primitive.

I do have a private implementation that does this check, not just for
X25519 but for basically all ECC calculations. I don't want to have to make
Curve25519 special in allowing non-canonical/non-reduced values when all
the rest of my code doesn't allow such cases, especially when the CFRG spec
already forbids implementations from sending the non-canonical/non-reduced
values.

> worthwhile (or, perhaps, even achievable for a spec).

As long as senders conform to the spec, they will not notice what the
receiver does regarding this.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Kurt Roeckx <[email-masked]>
Date: Wed, 30 Dec 2015 11:30:40 +0100

> should be able to stop talking to it on that basis alone.

I don't know enough about all the various draft to know if this
might be a problem or not, but I'm concerned about providing an
error oracle.

Kurt

---

From: Brian Smith <[email-masked]>
Date: Wed, 30 Dec 2015 13:04:09 -1000

> might be a problem or not, but I'm concerned about providing an

It's a public value sent by the other side, so that's not an issue.

Cheers,
Brian
-- 
https://briansmith.org/