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

[Ian Goldberg]

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