[tor-dev] RFC on obfs3 pluggable transport

[Ian Goldberg]

On Wed, Dec 12, 2012 at 11:14:08AM -0500, vmonmoonshine at gmail.com wrote:
> >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).
> 
> From the conversation of Zack with Steven at the breakfast table at
> Hotel Cellai, I'm pretty sure that Stegotorus is using DH based on 
> elliptic curve and its twist protocol. So you can find an implementation
> of it there. Though I haven't looked at the crypto part of the code myself.
> 
> Also could you please refer me to the reference that proves that X or
> p-X is uniformly random. It seems to me that you are taking a quadratic
> residue to an even power, so you always get a bi-quadratic residue for
> X. Then if I'm the distinguisher who knows the public group, and I see that the
> bi-quadratic residues appears 1/2 times instead of 1/4 of the times then
> I can smell that something going on.

Z_p^* has order 2q, where q=(p-1)/2 is prime.  Since 2 is a quadratic
residue, both 2 and 4 generate all of the order-q subgroup of quadratic
residues (call the group Q), so X will be a uniform (up to
negligibility) element of Q.  Since -1 is a quadratic non-residue, X is
a quadratic residue if and only if p-X is not.  (For all 0 < X < p.)  So
the output (randomly X or p-X) will be a uniform element of Z_p^*, which
is negligibly different from a uniform 1536-bit string.

[There's no such thing as a "bi-quadratic residue" in this setting; all
quadratic residues in this group have one square root which is itself a
quadratic residue and one which is not.]

   - Ian