Multiple Directory Authorities' keys compromise: a partial solution for Tor clients protection

[Roger Dingledine]

Ygrek just reminded me that nobody had answered this. Sorry for the delay;
I'll try to provide a brief response here.

On Fri, Dec 28, 2007 at 01:29:37PM +0300, unknown wrote:
> The core problem with Tor is the lack of directory authorities which one
>need to unconditionally trust. Despite the mechanisms of DAs consensus
>voting and client comparing signed data downloaded from different DAs,
>an opponent controlling more than half of DAs' keys is able to conduct
>a multitude of attacks.

Yep.

> Unfortunately, we have a really small set of semi-trusted authorities
>and more than a half of them are in the single jurisdiction (US), so we
>are forced to believe that owners of these servers really protect their
>servers' keys from compromise, and operators themselves are free from
>any third-party malicious influence ;-)

Actually, of the current v3 authorities:

3 are in the US (moria1, lefkada, ides)
3 are in Europe (tor26, gabelmoo, dannenberg)

but yes, it's definitely an issue we need to stay aware of.

> We propose a partial (very limited, but adequate) solution: Tor client with active connection and relatively "fresh" stats cache can resort to "heuristic" analysis for suspicious stats changes.
> 
> At most two criteria can be analyzed:
> 
> 1) An attempt to download stats from all of the mirrors is blocked or gives the stats with invalid signatures. As a result, it could be downloaded only from semi-trusted DAs. (Possibility of a legitimate DA's IP substituted with a malicious one, and data authenticated with compromised keys).
> 
> 2) Tor-nodes' keys signed by a DA are changed significantly (for example, >90% of all keys) during a very short period of time. (This case rises a suspicion about fake stats injection for user cache.)
> 
> Some questions remains: How many keys have to be affected by this attack to rise a suspicion? What the minimum time period threshold should be?
> 
> ...) What's about other criteria of suspicious activity or formal model of other possible attacks detection for Tor clients?

Right. This is really tricky though. If we are too brittle, then we will
throw false warnings to ordinary users, who will get really agitated but
not really know what they're supposed to do. (Every few weeks there's
another big thread on or-talk where a warning message that we thought
would never happen in ordinary circumstances did happen and the users
get all upset about it.) And if we're not brittle enough, then we won't
catch much at all in the way of possible attacks.

Worse, since these attacks rarely (never?) show up in practice, we're
never going to get feedback that the code is still working. The most
likely scenario for any balance that we pick between too brittle and
not brittle enough is that in about a year people will start seeing the
warnings when no actual attack is occurring, and we'll wonder why the
code is there.

Extra worse, there is no single balance that's right for all users. If a
user is on a network with a firewall that he doesn't understand, it will
block some outgoing connections, and then the "you're being attacked!"
warnings are more likely to pop up, confusing the user further. (We also
need to tolerate users who accidentally unplug their ethernet cable,
try to use Tor, and conclude that there's a massive global conspiracy
against Tor.)

Then what if we have a bug where a lot of Tor servers die at once, so
the network looks quite a bit different in a very short period of time.
Should we make that even worse by popping up "Possible attack! Click
ok!" messages?

All of the above scenarios actually do happen periodically. Whereas
we've never seen an attack on a majority of the directory authorities.
So to keep things sane both now and a year from now, I think we would
err on the side of "try to not show the warning" as much as possible --
and then there's less point with the whole feature.

> We propose next log messages for the Tor client as an indication of probable attack-in-progress:
> 
> -> Warning! Warning: a lot of tor-nodes' keys were changed during a short period of time!
> -> If more than a half of Directory Authorities' keys are compromised, stats could be poisoned with a fake data.

An ordinary user would have no idea what this means. Should they stop
using Tor and retry their connection without Tor? Should they ignore it?
Should they get really scared, and then try one of the above choices?

> As a paranoid option listed in config file (client-only section) one may use:
> 
> StopTorIfTooManyKeysChanged 0|1

This would be a fine option for a few people to set, but we couldn't
usefully turn it on by default, for the reasons explained above.

But I agree with you that being able to detect this situation would be
potentially useful. Rather than having Tor itself do it, why not have an
external tool that monitors your cached directory information (or asks
via the control port) and notifies you if it decides something is too
suspicious? You could then tune its level of suspicion however you like,
since you're the one running it and you know what it's looking for and
how to interpret the output. That would also help resolve your other
questions of "what is the right thing for an ordinary user to do when
he sees this", since ordinary users would learn about it when we put
out the emergency security update.

What do you think?

--Roger