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

[Berkant Ustaoglu]

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