"Attack" on PFS in tor-spec

[Paul Syverson]

On Mon, Sep 15, 2003 at 07:50:01PM -0400, Roger Dingledine wrote:
[snip]
> 
> 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.
> 

Seems potentially OK. I've intrigued Cathy Meadows enough about this
that she's going to run the variants through the NRL Protocol Analyzer.
(This is a very good thing.)

> 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.
> 

Knee jerk reaction is against it. It contains a key that doesn't belong
on Occham's key chain. k here just introduces an avenue of attack that
doesn't exist in variants 1 or 3. Maybe there's some modularity of
purpose to justify it, but I don't see it immediately.

> 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.
> 

Similar point about r to comment on k in variant 2 (perhaps to a lesser
degree?). More importantly it breaks the rule of thumb against using
keys in unaltered form I think. Cf. my paper with Ran Canetti and
Cathy Meadows, called something like Environmental Requirements
on Authentication Protocols.

> 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?

Because it breaks one of the Abadi-Needham design principles that begins
something like "Encryption is not entirely cheap..." and basically
says don't encrypt unless you've got a good reason and you know exactly
what that reason is. When I first showed this to Cathy her reaction
was the complementary, why would you do that? Only when she saw that
there was a space motivation to not do authentication in a long researched
and examined way did she see a point in looking at these variants.

> 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?
> 

Probably variant 1 or 3, but it still needs further investigation.

aloha,
Paul