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?
At the very least, it sounds like it hints at reduced strength of the curve: non-uniformity over a 256bit keyspace means it takes less than 256 bits to describe the keypair mapping, which should mean a technique exists with less than 2^128 operations for solving the ECDLP (as compared to using Shanks or rho collisions, etc).
Did you write this up anywhere? I see the XXX for the "FAQ" entry in your spec...
Also, to help reduce my ignorance: Does anyone know if ECC curves are usually tested for key distribution uniformity?
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.)
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.
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)
-
Ian Goldberg -
Mike Perry -
Nick Mathewson