[tor-dev] RFC on obfs3 pluggable transport

[Ian Goldberg]

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!  ;-)

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

   - Ian