[tor-dev] UniformDH question

[Ian Goldberg]

On Thu, Oct 08, 2015 at 05:04:14PM +0200, Jeff Burdges wrote:
> 
> What is the advantage of using X or p-X in UniformDH in obfsproxy?
> 
> https://gitweb.torproject.org/pluggable-transports/obfsproxy.git/tree/d
> oc/obfs3/obfs3-protocol-spec.txt#n65
> 
> Isn't just X itself dense pretty quickly anyways? 

I'm not sure what you mean by "dense pretty quickly".  Only half of the
values between 1 and p-1 are possible values for X (the quadratic
residues).  Someone observing network traffic seeing that the first 192
bytes of traffic in each direction between Alice and anyone else are
always in this specific half, would be clued in that a DH was taking
place.  The p is such that X is a quadratic residue if and only if p-X
is *not*, so by choosing one of those two uniformly at random to send,
you end up sending a uniformly random value in the range [1,p-1].  Since
p is very close to 2^1536, this is negligibly different from a uniform
1536-bit random value.

   - Ian