"Attack" on PFS in tor-spec

[Roger Dingledine]

On Tue, Sep 09, 2003 at 05:23:25PM -0400, Paul Syverson wrote:
> So I found a handwritten note on a printout dated July 11 of the
> end-April tor-spec outline with the following observation: if we allow
> OR_2 to send back an unencrypted EXTENDED cell with contents g^Y, then
> the previous node in the circuit, OR_1, will be able to substitute a
> different g^Y and hijack the session. No big deal, the hijacker won't
> actually be able to read any traffic since he won't have g^X.  The
> only thing is that, without authenticating the g^Y somehow, if the
> client sends any stuff under g^XY, (maybe an EXTEND cell, maybe a cell
> requesting an application connection to a particular address, etc.),
> and if OR_1 can later break the public encryption key of OR_2, then he
> can read that traffic. This means that PFS is broken (sortof, there
> was never really traffic sent that was readible by OR_2 anyway).  So,
> it looks like there is a break on a desirable property that we thought
> we had. These theoretical breaks leave open the possibility of a later
> practical break.

I think this counts as a practical break, insofar as it means we don't
get the perfect forward secrecy that we want, and you've described a
scenario where things could leak.

> If we authenticate the g^y, the problem goes away, yes? Roger noted
> that signatures doubles the size. We can send a key with the g^x
> which can be used to MAC the g^y. This should keep things neat and
> small, but we should probably think more if it is adequate.

Below is the meat of a letter I've mailed some experts in the field,
to answer my curiosity about attacks on these protocols and why some
are more commonly used than others. (I actually mailed it last week,
but was hoping to get an answer before I sent it to the list. ;)
-------

I'm working on the onion routing handshake, where Alice (the anonymous
client) is extending her virtual circuit and negotiating a session key
with a server Bob in the onion routing network. Bob has a public key that
everybody knows. In Handbook of Applied Crypto's terminology, we want to
get unilateral entity authentication (Alice knows she's handshaking with
Bob, Bob doesn't care who it is) and unilateral key authentication (Alice
and Bob agree on a key, and Alice knows Bob is the only other person
who could know it). I wouldn't mind getting unilateral key confirmation
(Alice knows that Bob actually knows the shared key). We also want PFS,
key freshness, etc.

We'd like to do it in two messages if possible, to reduce the chance that
an outside observer (who can't see through the link encryption, but who
can count messages) will recognize that a handshake is going on. Alice
will be the first party to send sensitive data once the session key is
negotiated (so she has the option of dumping the connection instead).

My first thought is to do the first two rounds of STS:
(1) A -> B: g^x
(2) B -> A: g^y, E_K(S_B(g^x, g^y))
The third step of STS isn't needed for us, since Bob only wants to
know that the person he shares a key with is the person who started
the handshake. Alice gets explicit key authentication (including key
confirmation) from Bob.

This is known to be good, and we should probably go with this. But I'm
curious about some alternate designs. In particular, we don't have
enough room in a single onion routing message for a public key and also
a signature. But we can fit, say, a public key and 20 bytes.

So here's an alternate approach (Variant 1):
(1) A -> B: E_PKB(g^x)
(2) B -> A: g^y, h(K || "handshake")
In message 1, Alice encrypts g^x to Bob's public RSA key. K is the session
key they both think they've agreed on. We haven't explicitly authenticated
the g^y, but rather we've proved that the person generating h(K) knew
g^x and thus is the correct Bob.

Line 2 aims to show both that it was Bob who received g^x, and that
it was Bob who came up with y. So for example, using h(g^x) is not
sufficient, because an intermediate onion router could replace g^y and
Alice wouldn't know.

Variant 2:
(1) A -> B: E_PKB(g^x, k)
(2) B -> A: g^y, hmac_k(g^y)
This proves that Bob got k, and that it was Bob who generated g^y. It's
not key confirmation, but it's pretty good.

Variant 3:
(1) A -> B: E_PKB(g^x)
(2) B -> A: g^y, hmac_K(g^y)

Variant 4:
(1) A -> B: E_PKB(g^x, r)
(2) B -> A: g^y, E_K(r)
This proves that Bob got r and g^x, and that it was Bob who generated
g^y. And the work of initializing the encryption isn't wasted, since we
needed to do that anyway. More generally, it seems if we're using E_K(),
then we can pretty much encrypt anything that Alice knows, and she can
check if K is right.

My first question: do these variants look like they do what I want?

If yes, my second question: how come none of the standard example
protocols encrypt g^x to Bob? Radia's book has a passing reference that
says you can do it, but it doesn't seem to be standard practice. I
guess maybe other protocols try to put off work as long as they can,
so they make the first message cheap. Are there papers that address
this idea, or is it considered too trivial? :)

And a third question, if I've gotten this far without being wrong: do
you have a favorite out of these variants? Or another better version?

Thanks for your help,
--Roger