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

Berkant Ustaoglu bustaoglu at cryptolounge.net
Thu May 12 09:32:06 UTC 2011

Quoting Ian Goldberg <iang at cs.uwaterloo.ca>:
>> > 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.)
>

In theory, the check X \in G* does a bit more than selecting x=0,
namely prevents invalid curve attacks. A server doesn't really care
for the security of a single connection (the anonymous client may
decide on purpose to reveal it's secrets and only the client would
suffer, server and other clients will remain unaffected). If however,
the server blindly accepts anything, then server would accept X' that
lies on an invalid curve where X' has small prime order. As a result
an adversary could potentially learn server's "b" - for comparison
invalid curve attacks apply to MQV, HMQV with similar result (leaked
static keys); I think it took a day for Alfred to verify the attack
works on HMQV for a curve defined in FIPS 186-2. Having server's Y and
the secret X'^y would complicate the attack a bit, but for
sufficiently motivated adversary I suspect it will not be a barrier.
As a result, if a client does establish a connection with the server,
the adversary cannot compromise the security of that particular
connection, but it would be trivial to fool the client to establish
connection with the adversary thinking the connection is with an
honest server.

In practice, I haven't read D. Bernsteins curve25519-20060209.pdf in
detail. It claims (as pointed out by Doug) that there is "free key
validation", which seems to imply invalid curves are not an issue.
However, I'd still suggest to keep the check X \in G* if at least to
serve as warning should there be a decision to move away from
curve25519.

There may be an alternative form of validation: instead of computing
X^y and X^b, the shared secret can be set as X^8y and X^8b. The
results is verified to not match identity point (assuming X \in G of
course). This will kill any multiples coming from the cofactor 8. If I
recall correctly something along these lines is going on in SP800-56A
for ECMQV.

- BU

--
Berkant Ustaoglu
http://cryptolounge.net