[tor-dev] New paper by Goldberg, Stebila, and Ustaoglu with proposed circuit handshake

[Ian Goldberg]

On Thu, May 12, 2011 at 02:07:10PM +1000, Douglas Stebila wrote:
> Implementing simultaneous exponentiation for curve25519 is going to be
> problematic, no matter how simple the algorithm, because Dan
> Bernstein's curve25519 main loop code is an unravelled assembly file.
> Modifying it directly to do simultaneous exponentiation will be a huge
> pain.  I expect he actually wrote the code using his personal
> pseudo-assembly language called qhasm and then generated the .s Athlon
> assembly from that.  We could email him to ask.  Without it, and
> without spending decades decoding the assembly, his curve25519 code,
> even when run twice, will likely be faster than any simultaneous
> exponentiation code I write myself.

Nick, were you planning on using djb's qhasm code, or the C version
(curve25519-donna)?  (A quick look at the latter suggests it's doing
left-to-right, so some changes would still be required, but not evil
assembly ones.

> In curve25519, every 32-byte string is a valid public key.  The
> curve25519 webpage
> 	http://cr.yp.to/ecdh.html
> says that public key validation is not required for Diffie-Hellman key
> agreement.  The webpage also lists several points that do not
> guarantee "contributory" behaviour, which the webpage suggests may be
> important in non-DH protocols.  Contributory, as I know it, refers to
> when it is important that both parties contributed some randomness to
> the protocol.  I would think that being contributory is a desirable
> property of key agreement, as it seems necessary for forward secrecy.
> Perhaps I'm misunderstanding this, however.

Every string is a valid public key, but half of them are on the twist
curve instead of the normal curve.  As discussed in the other part of
the thread, this turns out not to matter because the twist curve has
order 4*p_2.

Now that I think about it, I'm no longer positive that the client
absolutely needs to check that Y has large order, since the adversary
still won't know B^x = X^b.

So *either* the client should check this, *or* the directory authorities
should check that submitted B's are in G^*.  (Or both.  I think both is
best.)

That said, the client check is practically free; it's calculating
EXP(Y,x) anyway, and it just needs to memcmp that with 32 bytes of 0.

The directory authorities should probably checks the B's anyway, just to
be sane.  They should all have order exactly p_1, so check that
EXP(B,8) is not O, and check that EXP(B,p_1) is O.

   - Ian