On Wed, May 11, 2011 at 02:55:43PM -0500, Watson Ladd wrote:
Careful! The arguments to curve25519 are (output, exponent, base). (Note the order; that confused me when we were coding up Sphinx.) Presumably you meant for EXP(a,b) to mean a^b, though.
Note that 9 does not have prime order in curve25519; it has order 8 times a prime. But if the client always ensures private keys are 0 mod 8 (as djb requires; see below), this problem is mostly elided.
I just checked again, and 9 *is* a generator of the prime-order subgroup, it turns out. That doesn't affect anything we've said before, though.
More technically we have H=the curve25519 group, which is Z/pZxZ/8Z.
Actually, the curve25519 group is isomorphic to Z/pZxZ/4ZxZ/2Z, I'm pretty sure. (Oddly, djb's page claims that 325606250916557431795983626356110631294008115727848805560023387167927233504 has order 8, but when I try it, it looks to have order 4 to me.)
But even more correctly, curve25519 is the union of two groups, one Z/pZxZ/4ZxZ/2Z and the other Z/qZxZ/2ZxZ/2Z, for large primes p and q. (And even more more correctly, it's the x-coordinates of the elements of the above groups, which technically doesn't form a group at all, but does allow for unambiguous exponentiation.)
Since private keys are 0 mod 8 they always annihilate the Z/8Z part. So the curve25519 group is in fact one that is cyclic with prime order when we generate private keys the right way. The problem is completely elided
I said "mostly" because you still have to check that you don't end up with the identity element, since you might start out in the small subgroup.
What is "checks X" here? Since the server doesn't really care whether or not the crypto is good, this check can probably be elided.
In the GSO paper it is required that X be a non identity element. This is nontrivial given the curve25519 wire format, but is either squaring four times or checking that EXP(X,y) is not zero. when we calculate it.
The paper does indeed say that, but I'm questioning whether we actually needed that restriction. All it's checking is that the client isn't stupidly picking x=0. But the server doesn't really care, as it doesn't know who it's speaking with, anyway. The client could just as easily broadcast whatever x it chose. But yes, for symmetry, we could abort if EXP(X,y) is the identity element. (Which I just verified is indeed represented by all-0s.)
The GSO paper uses HMAC for only some of the operations that we are doing them on and use hash functions of double the length of the HMAC. Is this an important detail or an unimportant one?
Nick implemented the "double the length" hashes by simply hashing twice with different tweaks.
- Ian