[tor-dev] A concrete proposal for crypto (at least part of it)

[Nick Mathewson]

On Wed, Nov 2, 2011 at 2:19 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
> On Wed, Nov 2, 2011 at 11:45 AM, Robert Ransom <rransom.8774 at gmail.com> wrote:
>> On 2011-11-02, Watson Ladd <watsonbladd at gmail.com> wrote:
>>> Dear All,
>>[...omitted..]
>>
>>> Right now Tor encrypts the streams of data from a client to a OR with
>>> AES-CTR and no integrity checks.
>>
>> Bullshit.  We have a 32-bit-per-cell integrity check at the ends of a circuit.
> So let's say that I am a malicious 1st hop and a malicious 3rd hop,
> and I want to find out. If I have known plaintext I can modify it, say
> the packet type headers.  Then the third router will see nonsense and
> know that it this circuit is compromised. The second router can detect
> this with my proposal, it
> cannot right now.

See https://blog.torproject.org/blog/one-cell-enough ; see also the
part in the original Tor design paper where we discuss integrity
checking and tagging attacks.  See also the three paragraphs near the
beginning of section 6.4 in the document under discussion, which say:

"""
   It's not such an obvious improvement.  Including more MACs is more
   expensive in per-cell overhead.  The attacks that we would foil this
   way but not with Option 3 are not so much better than the the passive or
   timing-based-active end-to-end attacks that would still remain.

   Consider that if option 3 is in place, an end-to-end attacker who
   wants to do a tagging attack at one node can garble the rest of the
   circuit and see if the output is garbled at the exit node.  But such
   an attacker could just as easily close the circuit at one of those
   nodes and watch for a corresponding close event, or even better --
   simply pause traffic on that circuit for a while and watch for a
   corresponding gap at the exit.  The only advantage of the garbling
   attack would be that garbled cells are presumably rarer than circuit
   closes or traffic pauses, and thus easier to use to distinguish
   target circuits.  But that's still questionable: the other attacks
   win fine, and the pause attack doesn't risk detection as much.

   So why might we want to do this?  First, the overhead doesn't need to
   be as bad as you might first expect (see below).  Second, it would be
   nice to increase the security margin as much as possible: "attacks
   only get better".
"""

In summary:

 - If you control first and last hops in any currently known
deployable low-latency anonymity design, you win already through
active and passive timing attacks.  (As Paul notes in his mail.)
 - Xor tagging attacks are strictly easier to detect than timing
attacks, since the attacker risks breaking the circuits that they
don't in fact control.
 - Therefore it isn't completely obvious that any attacker actually
gets weaker if Tor does hop-by-hop integrity-checking.  (Before
anybody says "but..." here, please actually go read that blog post :)
)
 - Moreover, doing whole-cell crypto (as in option 3) lowers the
number of bits that you can get out of a tagging attack.  So the
incremental advantage of option 4 (hop-by-hop integrity checking) over
option 3 may be even less than its advantage over current Tor.

 - But maybe we should do hop-by-hop integrity checking anyway, since:
   - Less sophisticated attackers probably would have an easier time
implementing tagging attacks than they would implementing timing
correlation attacks.
   - "Attacks get better, not worse."  Right now, I can't think of a
way to make cell tagging better than active or passive timing attacks.
 But who knows, maybe we'll be glad later that we added it for some
reason if somebody finds a novel attack on some other part of our
protocol stack or something.
  - It's doesn't have to be all that expensive in space to help a lot,
and it doesn't seem to be any more expensive in time than the
whole-cell-crypto designs of option 3.  (It might in fact be cheaper
in time, depending.)

This is one of the parts of the document that I wish people would
discuss, btw.  The conclusions here are not obvious to me, and
although I prefer hop-by-hop checking based on the reasons above, I
don't think that they're absolutely compelling.

> Ends of circuit alone are not enough.

That's certainly worth discussing, but it's not what Robert was
disagreeing with.  What you said was "Tor encrypts the data ... with
no integrity checks."  I think that's what he was reacting to.

cheers,
--
Nick