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

[Douglas Stebila]

On 2011/05/12, at 10:33, Ian Goldberg wrote:

>>> Remember also that if you have non-black-box access to the
>>> exponentiation routine, the server can compute X^y and X^b
>>> simultaneously.  That will make a bigger difference in time, but is not
>>> really relevant from a spec-level standpoint.
>> 
>> Can you expand on how this would work?  I didn't ask the first time
>> you told me this, on the theory that I could figure it out if I
>> thought about it for long enough, but several days later I still don't
>> have it.  All the ways I can think of are inefficient,
>> non-constant-time, or both.
> 
> Use right-to-left exponentiation.  This is totally off the top of my
> head.
...
> Then exp2(base, expon1, expon2) will be:
...

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.

On 2011/05/12, at 04:19, Ian Goldberg wrote:

>>    CLIENT_PK:  X              -- G_LENGTH bytes
>> 
>>  The server checks X,
> 
> 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.
> 
>>  The server sends a CREATED cell containing:
>> 
>>    SERVER_PK:  Y                     -- G_LENGTH bytes
>>    AUTH:       H(auth_input, t_mac)  -- H_LENGTH byets
>> 
>>  The client then checks Y, and computes
> 
> Here, the check is more important.  Ideally, one would check that Y \in
> G^* (which should have prime order, but doesn't here).  But in
> curve25519, I think you can get away with something a bit cheaper.  If Y
> isn't in G at all, but is on the twist curve, the AUTH verification
> below is certain to fail, so that's OK.  If it's in G, but has low order
> (i.e. order dividing 8), then EXP(Y,x) will end up being the point at
> infinity, which would be bad.  (Indeed, it would be pretty much the same
> problem that Tor had lo those many years ago.) So I think it's probably
> OK to check that EXP(Y,x), which you're computing anyway, is not the
> point at infinity.  I don't remember offhand how curve25519 represents
> that point; it may be as simple as all-0s, but you should check.


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.

Douglas