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

Berkant Ustaoglu bustaoglu at cryptolounge.net
Fri May 13 06:58:10 UTC 2011

Quoting Ian Goldberg <iang at cs.uwaterloo.ca>:

> On Thu, May 12, 2011 at 10:10:11AM -0400, Nick Mathewson wrote:
>> On Thu, May 12, 2011 at 8:12 AM, Ian Goldberg <iang at cs.uwaterloo.ca> wrote:
>> > On Thu, May 12, 2011 at 07:13:58AM -0400, Ian Goldberg wrote:
>> >> The directory authorities should probably checks the B's anyway, just to
>> >> be sane.  They should all have order exactly p_1, so check that
>> >> EXP(B,8) is not O, and check that EXP(B,p_1) is O.
>> >
>> > While we're talking about this, note that our paper says that the CA
>> > (the directory authority here) should check that the node submitting B
>> > actually does know b (the private key).  This could be as simple as the
>> > standard Fiat-Shamir NIZKPK.
>> Hm.  What goes wrong in the protocol as I've written it if the
>> authorities *don't* check this?  As "simple" as you say Fiat-Shamir
>> is, it would seem to add a few round trips to the server publication
>> protocol.
> No, Fiat-Shamir is the non-interactive (the NI in NIZKPK) version, so
> the node would just attach the proof to B when it submits it.
> Node knows b and B = g^b
> Node picks random t \in Z/p_Z where p is the order of g
> Node computes c = H(g^t | B | ID | D)
>     where ID is the node ID, D is any other data already sent or
>     received in the server publication protocol
> Node computes r = t - c*b mod p
> Node sends (c,r) along with B to be registered.  (256+256 bits)
> The DA checks that c =?= H(g^r * B^c | B | ID | D) before accepting the
> registration.
> You're right that it seems unlikely anything will go wrong in this
> particular protocol if B is unattested.  But then you're getting back to
> lots of moving parts relying on the properties of other moving parts.
>    - Ian

Proof of possession of private key is indeed the more sound  
cryptographic thing to do, but for security it suffices to verify B  
lies on the correct group. Hijacking someone else's public key is not  
going to help the adversary to break ntor's security. That is what  
ntor's argument suggests. Given that is it really worth creating and  
maintaining the extra code to run a NIZKPK, when validation - a  
routine already required for the protocol, suffices?

This does not mean foolproof security, for example using B also as a  
signature key is likely to be problematic. However, such problems feel  
independent from whether you know or don't know "b". The only case  
where this would be issue is if two server use their respective Bs not  
only to establish connection with clients but between each other *and*  
the protocol used to establish server-to-server channel relies  
non-trivially on the assumption that your peer knows its own private  
key. Well in that case it's better to simply use a protocol that  
doesn't rely on proof of possession.

Last remark: I think in Ian's algorithm the DA must also check that B  
lies in the correct group. Otherwise, it's still possible to register  
invalid keys: for example with finite fields set B = 0 and it's easy  
to fool the verification step; a similar idea can be applied to  
elliptic curves (if validation is free then not on curve25519). I'm  
not familiar with how exactly Tor handles registration, but can come  
up with a few "reasonable" scenarios where an adversary can  
successfully impersonate servers by posting invalid static keys.


Berkant Ustaoglu

More information about the tor-dev mailing list