[tor-dev] Notes from the prop224 proposal reading group

[David Goulet]

On 24 Mar (16:55:57), George Kadianakis wrote:
> George Kadianakis <desnacked at riseup.net> writes:
> 
> > [ text/plain ]
> > Hello,
> >
> > so we had a meeting about the future of "Next Generation Hidden Services" aka prop224.
> > It was a good meeting.
> >
> > We spent most of the time discussing the topics brought up here:
> >   https://lists.torproject.org/pipermail/tor-dev/2016-March/010534.html
> > Please read the above mail to get up to speed with the topics of discussion.
> >
> > <snip>
> >
> > b) In prop224, why do intro points need to know the "intro point encryption key"
> >    and also what's the point of UPDATE-KEYS-SUBCMD?
> >
> >    Nick told us that the main point of UPDATE-KEYS-SUBCMD is that so hidden
> >    services can rotate their intro point encryption key periodically, so that
> >    they can reset their replay caches. 
> >
> >    That's a fair point. The big question here is, is this worth the complexity
> >    that MAINT_INTRO and UPDATE-KEYS-SUBCMD add to the protocol logic?
> >
> >    Unfortunately we don't know the answer to this yet, because we actually
> >    don't have stats on how our replay caches are doing currently. Here are some
> >    things we need to look into:
> >
> >    i) Speak with facebook or some other big onion hoster, and try to get some
> >       information about their replay cache. Is it ready to bust? How much space
> >       is it occupying?
> >
> >    ii) The above will help us gauge replay caches in terms of normal activity,
> >        but we also need to think of how replay caches should act in cases of a DoS.
> >
> >    iii) Also think about INTRODUCE1 replay attacks in general, and understand
> >         how dangerous they can be, so that we know how robust our replay caches
> >         should be. Is it _that_ dangerous if an attacker manages to sneak in a
> >         replay attack every once in a while? 
> >
> >         For example, imagine an attacker who fills up our replay cache on
> >         purpose, so that she can sneak in one replay attack when we reset
> >         it. If an attacker can send legit INTRODUCE2 cells to fill up our
> >         replay cache, what does she need the replays for? What other types of
> >         attacker are there?
> >
> >    After we learn more about the above, we will understand *how much we care*
> >    about onion services being able to rotate intro pint encryption keys on the
> >    fly using UPDATE-KEYS-SUBCMD. Here are some possible scenarios here:
> >
> >    - We end up deciding that INTRODUCE1 replay attacks are *dangerous* and we
> >      need to seriously defend ourselves against them. In this case, having some
> >      sort of UPDATE-KEYS-SUBCMD mechanism sort of makes sense, since onion
> >      services should be able to rotate keys at will and let their clients know,
> >      without them having to fetch a new HS descriptor.
> >
> >    - We end up deciding that INTRODUCE1 are a concern but not something we
> >      should complicate our design considerably for. In this case, we might want
> >      to consider improving the quality of our replay caches, by using more
> >      compact designs (= more space for entries), or by using bloom filters or a
> >      similar tech. A proposal will need to be made if so. Yawning posted the
> >      following relevant paper: https://home.kookmin.ac.kr/~mkyoon/publications/2010TKDE.pdf
> >
> >    - We end up deciding it's no big deal if the attacker sneaks in a replay
> >      attack every once in a while. In this case, we can just go with the most
> >      minimal approach and ditch the UPDATE-KEYS-SUBCMD mechanism for now, and
> >      have intro points be oblivious about encryption keys (which further
> >      simplifies our cell formats, etc.). If we take this approach, and in the
> >      future future we change our minds about the importance of replay attacks,
> >      we can still add some sort of UPDATE-KEYS-SUBCMD mechanism using the
> >      extensions mechanism of ESTABLISH_INTRO cells.
> >    
> 
> Hm. Unfortunately I didn't receive any feedback on this matter, and we need to
> move forward here, so I thought about this some more on my own. I'm still not
> sure what's the right thing to do here, but here are my current thoughts:
> 
> First of all, the UPDATE-KEYS-SUBCMD mechanism does not actually prevent replay
> attacks at all. It's a performance feature. It's there so that if the HS
> rotates its replay cache and encryption key, the intro point can inform clients
> about the new encryption key. The win here is performance, since that clients
> don't need to fetch a new descriptor to learn the new encryption key.
> 
> Howevr, the performance gain from UPDATE-KEYS-SUBCMD does not seem substantial
> since it only occurs in the case where a client has already fetched an HS
> descriptor, and then the HS rotates its keys, and then the client wants to
> revisit that HS.

IMO, as I stated in #tor-dev discussions, I don't think this is a lost in
performance. Fetching a new descriptor is cheap and by cheap I mean it's
something that the client does once all IPs in there don't work which is (if
all goes well) once every ~18-24h.

Furthermore, the client connection to an IP is _short_ live so when a service
needs to rotate the replay cache, we can create a new one for the new keys and
the old one can be kept for "on going" introduction with clients and then once
they are all done, we can drop that replay cache along with encryption keys.

In other words, there are ways that we can address this issue without an
update keys subcmd. I don't see the performance benefit.

> 
> If UPDATE-KEYS-SUBCMD is implemented, then the intro point will pass the new
> keys to the client, and the client will be able to connect to the HS by issuing
> a new INTRODUCE1 cell.
> 
> On the other hand, if we don't implement the UPDATE-KEYS-SUBCMD mechanism, then
> the client will need to send an INTRODUCE1 cell to another intro point.

I think, we could be able to keep the old enc keys for current client
introducing themselves as we are rotating our replay cache. This is just a
timing issue here between changing keys and serving current clients no?

> This is not terrible performance-wise. However, in the worst case, where the
> HS has rotated the encryption keys of *all* its intro points, then the
> client will need to try all of them, fail all of them, and fetch a new
> descriptor. This worst case scenario should never really happen, except if
> the HS is under INTRODUCE1 DoS and rotates its keys more frequently than
> usual. But why would an attacker do that?  To delay the clients?

I'm also OK with a client re-fetching the descriptor tbh....

> 
> So basically, UPDATE-KEYS-SUBCMD does not offer much, except in the case of
> a targetted DoS. This DoS attack does not seem very plausible to me, since
> its only purpose is to delay clients. I don't see how it can completely
> block access to an HS, except if the attacker is able to *instantly* exhaust
> the replay cache of an HS which should not be the case.
> 
> Hence, my current intuition is to kill the UPDATE-KEYS-SUBCMD feature for
> the sake of simplicity. It seems like a dirty and not trivial to implement
> feature that so far only helps in the case of a hypothetical DoS attack
> which is not very profitable (fwiw it's also possible with the current
> hidden services subsystem)
> 
> Now, if I'm wrong and this hypothetical DoS attack ever becomes a real
> problem, we can then implement a feature like UPDATE-KEYS-SUBCMD by using
> the extension fields of ESTABLISH_INTRO and INTRODUCE_ACK. I feel that using
> extension fields is cleaner than the way UPDATE-KEYS-SUBCMD is currently
> specified (as a weird subtype of ESTABLISH_INTRO).
> 
> What do you people think? Do you feel this suggestion is too sloppy? I'm
> really not sure myself.

My take on that is we don't need this extra complexity for something we can
cope with imo farily easily. And as you say, we can extend at some point the
establish intro cell if we discover we _really_ need this.

Cheers!
David

> 
> PS: FWIW, if we are actually serious about INTRODUCE1 replay attacks and we
> want to block them no matter what, we need to either change our detection
> method from replay caches to something else, or at least make replay caches
> more compact so that they fit more elements.
> 
> _______________________________________________ tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 603 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160328/53b210c4/attachment.sig>