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@torproject.org wrote:
Thus spake George Kadianakis (desnacked@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...
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)