On Wed, Dec 12, 2012 at 03:13:59AM +0200, George Kadianakis wrote:

Ian Goldberg <iang@cs.uwaterloo.ca> writes:

...

[Should we not be copying tor-dev on this thread?]

We definitely should.

Is it OK if I forward the whole thread to tor-dev (including this mail and your reply)? Feel free to do it yourself too if you want.

I'll copy tor-dev on this email, and not snip things in order that context is mostly preserved. If you think some past snippage should be restored, feel free to forward that as well.

BTW, in my first email, I had tor-assistants CCed, but you stripped it off when you replied, so I didn't add it again :)

Oops; that was unintentional. My bad. But tor-dev is better, anyway.

...

On Fri, Dec 07, 2012 at 02:09:21AM +0200, George Kadianakis wrote: <snip>

...

...

You'll also need to be careful about the exact protocol to select whether to use the curve or the twist; I remember we discussed this at PETS, sitting outside the wine tasting.

Ugh. I admit that even though I remember our discussion at PETS, I don't recall that part of our discussion. What do you mean by "the exact protocol to select whether to use the curve or the twist"?

My plan would be to choose randomly between the base point of the curve and the base point of its twist, make a public key using the randomly chosen base point, and finally send the public key to the other party. Looking at the Telex paper, this is similar to the creation of a_0/a_1 in the 'Setup' phase of appendix 'Tagging Details'.

IIUC the other party shouldn't care whether the public key was created using the curve or its twist, and can just do another point multiplication to derive the shared secret.

Is this the protocol you are talking about, or am I getting my stuff wrong?

That works if clients know a pair of public keys for the bridge in advance. It was unclear to me whether this would be the case. Is it? Can we put public keys in with the bridge descriptors? In this case, you'd need 42 octets for the public key. The spec I see in gitweb doesn't assume that. Rather, it has all operations being performed on a common curve.

Correct. Let's assume that clients _don't_ have any shared-secrets beforehand. It makes our transport more deployable and usable, and it doesn't rely on non-implemented pluggable transport features.

(FWIW, adding public keys (or other info) to bridge descriptors is supported by the pluggable transport spec (DECLARE option), but it's not implemented. Support for passing public keys (or other info) to pluggable transport proxies is implemented in ticket #3594 but it's not ready for merge yet.)

...

The trick is that both sides need to use the *same* curve: either the main curve or the twist. So if I watch a host I suspect is an obfs3proxy responder and find that the first 21 bytes it outputs is always on the same curve as the first 21 bytes it received, that's good evidence for my suspicion.

I see.

Let me formalize the protocol I tried to describe in my previous mail.

Alice randomly selects a bit 'b' \in {0,1}. Similar to Telex, the bit 'b' selects whether Alice will use the normal curve E or its twist E'). Depending on the bit 'b', Alice generates a public key on E or E'.

Now, Alice sends to Bob her public key along with padding, as described in the obfs3 spec.

Bob receives Alice's message and parses the first 21 bytes, which he considers her public key. Bob checks whether the public key fits E or E'. Depending on the curve, Bob loads up the correct domain parameters, does a point multiplication with Alice's public key and his private key, and derives the shared secret.

Now, Bob does the same dance with Alice, so that Alice can also derive the shared secret.

What's the problem with this protocol?

When Bob "does a point multiplication with Alice's public key", you mean "Bob picks a private key y, and multiplies Alice's public key by y to yield the shared secret". Note that the resulting shared secret (y times Alice's public key) will be in the same group (E or E') that Alice's public key is in. Now what does Bob send to Alice? Bob should be sending y times the generator of the group. Which group? If Bob and Alice are to agree on the shared secret, it has to be the same group Alice used. Otherwise, Alice's computation will necessarily end up different from Bob's (since they'd be in different groups) and the two secrets won't match. So in order for this protocol to work, Bob has to always choose the same group he received as a public key from Alice. But that's now a distinguisher for the protocol: if I'm watching someone I think is running an obfsproxy3 bridge, and I notice that the first 21 bytes he receives on any TCP connection always lies in the same group as the first 21 bytes he sends in response, then I can be pretty confident in my suspicion.

I think it's similar to how Telex generates and inspects tags: Looking at the algorithm of the "Telex tag inspection" section of the Telex paper, it seems to me that the Telex station doesn't know whether the tag is on the curve or its twist either.

The big difference is that Telex uses *static* DH (and gains forward secrecy by rotating keys): the client comes pre-loaded with (rP, rP') where P and P' are generators of E and E'. The Telex client then randomly picks Q to be either P or P', and randomly picks s, and sends sQ. The Telex station then can tell which group sQ is in, and multiply sQ by r. Conversely, the client uses whichever of rP and rP' corresponds to its choice of Q, and multiplies that by s. Then the secrets match. The important distinction is that in Telex, the client *already knows one public key in each group*. In the above obfsproxy3 proposal, it does not.

I tried to find how the Telex station code does it, but I didn't manage to find the telex-relay code on the Internet :(

Indeed, I don't believe the UMich people have (yet?) published it.

...

Are we married to using elliptic curves? Is performance a serious concern at the moment? If not, it may be easier to use Z_p, while still using a trick similar to the "twist":

No, we are not married to elliptic curves. It was just that the only trick I knew on hiding DH public keys was the Telex trick, which uses ECC.

...

Let p = 3 mod 4 be prime, with q=(p-1)/2 also prime, and p is at least 1536 bits. (2048 if there's room.) [Use group 5 or group 14 from RFC 3526.] Let g be a generator of the order-q subgroup of Z_p^* (g=2 for the two above groups from the RFC.)

To pick a private key, pick a random 1536-bit (or 2048-bit) number, and force the low bit to 0. So there are 1535 (2047) bits of randomness, which is the size of q. Let x be that private key. Let X = g^x mod p.

Here's the trick: When you send the public key, randomly decide to send either X or p-X. That will make the public key part a uniform 1536-bit (2048-bit) string (well, negligibly different from uniform).

The other side constructs y and Y=g^y mod p in the same way, and sends either Y or p-Y.

Note that both (p-Y)^x = Y^x mod p since x is even, and similarly (p-X)^y = X^y mod p, so key derivation goes through unchanged.

The downside of the larger public keys is that it puts a lower bound on the size of the data sent by the initiator before the responder answers.

Ha. The Z_p stunt you describe is nifty! I will seriously consider it, if the telex-curve protocol doesn't work out without a pre-shared public key.

Note that the above protocol assumes that p is very close to a power of 256, but that's true of the RFC 3526 groups 5 and 14 I pointed to.

...

On a side note, in Philipp Winter's "put the hash there" trick, I think it would be better to use HMAC(SHARED_SECRET, "obfsproxy3 delimiter string") rather than h(SHARED_SECRET).

True.

As a matter of fact, we should probably have two HMACs, one for the initiator and another for the responder. Otherwise, hashing the SHARED_SECRET with a common key, will result in HASH_LEN bytes that appear both in the initiator's and in the responder's traffic stream.

Yes indeed. - Ian