Fwd: Tor security advisory: DH handshake flaw

[Hal Finney]

> ----- Forwarded message from Roger Dingledine <arma at mit.edu> -----
> 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)

I was just at Crypto yesterday and Hugo Krawczyk in his talk emphasized
the difficulty of securely designing key exchange protocols.  He was
talking about "implicit authorization" protocols where the exponentiation
involves the long term public key(s).  This protocol is different but
there are still many ways things can go wrong.

This attack is an example of a "small subgroup" attack where the derived
value is forced into a small subgroup mod p, in this case the trivial
subgroup with one element.  Sometimes other subgroups can be used,
such as the group with order two (consisting of 1, p-1), or potentially
other groups.  But I checked the source code and Tor is using an "Oakley"
prime from RFC2409, with a generator g = 2.  The prime p is such that
q = (p-1)/2 is prime also, and g generates the prime order subgroup of
size q.  The only subgroups of such a p have order 1, 2, q, and 2q==(p-1).
By checking the received bignum is not 1, -1, or 0 (good catch, I forgot
about that one) and also not >= p, you should be okay.

Oh, I just thought of another small-subgroup related attack.  Very minor,
but a leak.  Mallory lets Alice's message goes through but negates Bob's
g^y value:

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

Now, the exchange will complete successfully only if x is even.
So Mallory learns this fact.

You also want to think about replay attacks with these protocols, but
I don't see much of an issue there.  As long as x is fresh each time
then a replay shouldn't be possible.  And if you're re-using x values
you probably have a lot more serious problems than replay attacks.

I'm not in love with publishing H(K), especially with the "iffy" state
of hash functions these days.  Theoretically it provides another avenue
of attack to find the key.  Granted, K is 1024 bits and H(K) only 160,
so even if H were invertable, K would still be unguessable, and we're a
long, long ways from inverting any modern hash functions.

Another way to accomplish the same thing would be to encrypt a known
value under the derived encryption key.  Since you're going to be
encrypting lots of other stuff with the key, some of which you have to
pretty much assume is going to be known plaintext, you aren't exposing
any new weaknesses by doing that.

If you do want to use a hash, it's usually a good idea to throw as much
stuff into it as you have lying around.  I would include g^x and g^y in
the hash.  This would solve the attack you're worried about right there,
because Mallory doesn't know g^x.  Probably include p and g as well,
and Bob's identity.  It may be overkill but you never know when it will
stop an attack you didn't think of.

Ideally, I think Tor should switch to a different key exchange
protocol, one which has some degree of provable security, but
I am hesitant to recommend one.  Looking at your docs I gather
that you have some pretty severe space constraints.  Your article
http://tor.eff.org/doc/design-paper/tor-design.html#subsec:circuits says
that you didn't want to use a signature because you didn't have room
for it in your packet.  It also says, "Preliminary analysis with the
NRL protocol analyzer [35] shows this protocol to be secure (including
perfect forward secrecy) under the traditional Dolev-Yao model."
It's interesting that these attacks exist given this security analysis.
Maybe it was treating the arithmetic as something of a black box?
Chalk it up as another example of the limitations of these kinds of tools.

Hal Finney

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com