[tor-dev] RFC on obfs3 pluggable transport

[George Kadianakis]

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

> On Wed, Dec 12, 2012 at 03:13:59AM +0200, George Kadianakis wrote:
>> Ian Goldberg <iang at 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.
>

Sounds good.

Hey tor-dev, if anyone is interested in the snipped parts of the
discussion, send me an email and I will forward them.

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

Oh you are right. Got it now. Thanks!

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

Right.

The only issue with your trick, is that I'm not looking forward
implementing a custom DH key exchange in Python (especially the DH
parameter generation and public key validation parts).

My current plan is to do some reading and thinking on other
key-exchange schemes that might look uniformly random on the wire, and
if I can't come up with anything I will start thinking of an
implementation plan for your DH over Z_p idea.

Thanks!