Versions affected: stable versions up through 0.1.0.13 and experimental
versions up through 0.1.1.4-alpha.

Impact: Tor clients can completely lose anonymity, confidentiality,
and data integrity if the first Tor server in their path is malicious.
Specifically, if the Tor client chooses a malicious Tor server for
her first hop in the circuit, that server can learn all the keys she
negotiates for the rest of the circuit (or just spoof the whole circuit),
and then read and/or modify all her traffic over that circuit.

Solution: upgrade to at least Tor 0.1.0.14 or 0.1.1.5-alpha.


The details:

In Tor, clients negotiate a separate ephemeral DH handshake with each
server in the circuit, such that no single server (Bob) in the circuit
can know both the client (Alice) and her destinations. The DH handshake
is as follows. (See [1,2] for full details.)

Alice -> Bob: E_{Bob}(g^x)
Bob -> Alice: g^y, H(K)

Encrypting g^x to Bob's public key ensures that only Bob can learn g^x,
so only Bob can generate a K=g^{xy} that Alice will accept. (Alice, of
course, has no need to authenticate herself.)

The problem is that certain weak keys are unsafe for DH handshakes:

Alice -> Mallory: E_{Bob}(g^x)
Mallory -> Bob:   E_{Bob}(g^0)
Bob -> Mallory:   g^y, H(1^y)
Mallory -> Alice: g^0, H(1^y)

Now Alice and Bob have agreed on K=1 and they're both happy. In fact,
we can simplify the attack:

Alice -> Mallory: E_{Bob}(g^x)
Mallory -> Alice: g^0, H(1)

As far as we can tell, there are two classes of weak keys. The first class
(0, 1, p-1=-1) works great in the above attack. The new versions of Tor
thus refuse handshakes involving these keys, as well as keys < 0 and >= p.

The second class of weak keys are ones that allow Mallory to solve for y
given g^y and some guessed plaintext. These are rumored to exist when the
key has only one bit set [3]. But in Tor's case, Mallory does not know
g^x, so nothing she can say to Alice will be acceptable. Thus, we believe
Tor's handshake is not vulnerable to this second class of weak keys.

Nonetheless, we refuse those keys too. The current Tor release refuses
all keys with less than 16 "0" bits set, with less than 16 "1" bits set,
with values less than 2**24, and with values more than p - 2**24. This
is a trivial piece of the overall keyspace, and might help with next
year's weak key discoveries too.

Yay full disclosure,
--Roger

[1] http://tor.eff.org/doc/tor-spec.txt section 0 and section 4.1
[2] http://tor.eff.org/doc/design-paper/tor-design.html#subsec:circuits
[3] http://www.chiark.greenend.org.uk/ucgi/~cjwatson/cvsweb/openssh/dh.c?rev=1.1.1.7&content-type=text/x-cvsweb-markup and look for dh_pub_is_valid()