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

[George Kadianakis]

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.

So these are basically two topics:

a) Should we try to maintain backwards compatibility with old intro/rend points?

   We ended up deciding that it's actually worthwhile keeping backwards
   compatibility if we can help it: Our rationale was that coding the logic for
   the extra cells that are required to maintain backwards compatibility is
   probably less painful than coordinating a perfect bug-free incremental
   deployment of prop224 in such a way that the whole network has upgraded
   before we enable client support.

   So our current plan is to bake backwards compat in the code, and also
   introduce a consensus parameter of "Should we connect to prop224 onion
   services using legacy IPs/RPs?" which we will switch off when a good
   percentage of the network has upgraded to support prop224. At that point, we
   will be able to rip out the backwards compat code as well.  As an added
   point to that, we should implement the backwards compat code in a way that
   it's not spagghetied with the normal code, so that it's easy to analyze and
   remove when needed. Furthermore, we should look back in prop224 and see if
   we can simplify the backwards compat logic even more.

   FWIW, prop224 does not have backwards compatibility for HSDirs, so we will
   still have to do careful deployment there, and make sure that a good
   percentage of HSDirs have upgraded to prop224 before we start using them
   (maybe a new consensus parameter is needed here).

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.
   
   Furthermore on this topic, we discussed some alternate approaches for doing
   replay detection that would require less heavy replay caches:

   i) Maybe we can have an increasing counter in the HS descriptor, that
      clients need to also include in their INTRODUCE1 cell. If an onion
      service receives an INTRODUCE1 cell with a counter value different than
      the one in the descriptor, it ignores it. Onion services update the
      counter and publish a new descriptor when their replay cache is close to
      getting filled.

      I believe various subtle engineering details are hidden in this scheme,
      along with edge cases and race conditions like "What happens if the
      client fetches a descriptor with counter value N, right before the onion
      service updates the descriptor with a new counter value?".

   ii) When an intro point replay cache is almost full, the onion service will
       make new encryption keys, tear down the old intro circuit and make a new
       one, and also pass a signed "HS moved to another circuit" message to the
       intro point. The intro point will forward that message to any clients
       that ask for the onion service using its old keys, so that clients know
       the right place to ask. Lots of engineering details hidden in this
       proposal as well.

   In the end we decided that Roger might have some useful feedback for us here :]

More research is required!

Cheers!