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

[Nick Mathewson]

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.)

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.

Corrections on the above are welcome!

DJB's curve25519 paper is pretty easy to read and understand; I'd
suggest reading it and following up on its references.

-- 
Nick