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