Ian Goldberg iang@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