[tor-dev] [tor-reports] George's status report: November 2012

[Ian Goldberg]

On Mon, Dec 03, 2012 at 10:36:54PM -0500, Nick Mathewson wrote:
> On Mon, Dec 3, 2012 at 10:19 PM, Mike Perry <mikeperry at torproject.org> wrote:
> > Thus spake George Kadianakis (desnacked at riseup.net):
> >
> >> Hi,
> >>
> >> - Started researching and developing obfs3, an improved version of the
> >>   obfs2 pluggable transport. The proposed protocol currently looks
> >>   like this:
> >>   https://gitweb.torproject.org/user/asn/pyobfsproxy.git/blob/refs/heads/obfs3:/doc/obfs3-protocol-spec.txt
> >>
> >>   The current implementation uses curve25519 to do ECDH, but
> >>   curve25519 public keys don't look random enough on the wire and we
> >>   will probably need to use a curve similar to the one that Telex
> >>   uses.
> >>
> >>   Ian, Philipp and Roger helped a lot with this.
> >
> > Holy crap. In what way are the public keys in curve25519 "not random
> > enough"?
> >
> > I don't really know anything of substance about ECC (especially ECC
> > curve choice), but if the public keys are distributed unevenly over the
> > keyspace, isn't this a hint of something extremely bad?
> 
> It isn't, really.
> 
> The issue is that curve25519's members do not occupy the entirety of
> all 256-bit binary strings.  So when you make a "public key", there
> are some 256-bit binary values it can't be.  (Roughly half of them
> IIUC.)

It's actually less than 1/2.  (1/8 I think it is.)  That's because 1/2
are on the twist, but then curve25519 isn't a prime-order group, so djb
(properly) suggests using the prime-order subgroup, which further cuts
things down.

> IIUC, these 'impossible' values represent points on a related curve,
> called the "twist" of curve25519. There are circumstances under which
> properties of the twist can give you bad security properties, but I'm
> told curve25519 doesn't have them.

That's right, except for the non-primeness, which is slightly
unfortunate, but Edwards curves like curve25519 can't have prime order,
so it's as close as it can be.  Using a curve like Telex's (prime order
with prime twist) saves you from having to worry about that.  The
new EC implementation in openssl should be plenty fast (but as
implemented, only gets the speed improvements on 64-bit architectures).

   - Ian (offline most of today)