[tor-dev] RFC on obfs3 pluggable transport

[George Kadianakis]

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

> On Wed, Dec 12, 2012 at 04:52:11AM +0200, George Kadianakis wrote:
>> >> > 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).
>
> You're in luck!  You don't get to implement any of those parts!  ;-)
>

You are very right!

RFC 3526 did the parameter generation for me, and since we are doing
anonymous DH and our threat model doesn't include active attacks there
is no point in doing public key validation (Initially, I was worried
about attacks like Tor's CVE-2005-2643).

This makes things much easier.

> Write a class UniformDH that has hard-coded constants p (the 1536-bit
> prime in group 5 of RFC 3526) and g = 2.  Compute len = the number of
> bytes of p = 192.  Its init method will pick a uniformly random len-byte
> string, and convert it to a long called priv.  Let flip = (priv % 2) and
> priv -= flip (so flip is the old low bit of priv, and priv is now even
> for sure).  Compute pub = pow(g,priv,p) and if flip == 1: pub = p - pub.
> Convert pub to a len-byte string and store it as pubstr.
>
> Add a method getpub() which returns pubstr.
>
> Add a method getsecret(theirpub) which converts theirpub (a len-byte
> string) into a long called theirpublong.  Compute secret =
> pow(theirpublog,priv,p) and convert secret into a len-byte string and
> return that string.
>
> That should be it.
>
> [You can use Crypto.Util.Number.{long_to_bytes,bytes_to_long} to
> accomplish the conversions above, if you're allowed to use PyCrypto.
> For the randomness, os.urandom() is fine.]
>

Many thanks for the help with the implementation! :)

>    - Ian