Making JFK DOS resilient for Message-3

[Yogesh.Swami@nokia.com]

Hi,

I have a few comments on the JFK draft:

JFK does a great job for DOS protection against blind attacks and
it also makes the right engineering compromises by defining a PFS
interval, however the message 3 of JFK is still prone to DOS
attacks by an attacker who can eavesdrop on the channel.
Fortunately, it's possible to counter that attack also without
requiring any changes to the protocol, except for adding one more
piece of information in message-3. Let me first explain the attack
and then how to counter it.

Let's say Alice wants to establish a secure channel with Bob, and
Eve is capable of eavesdropping on their channel. Let's also
assume that the round trip time between Bob and Eve is much
shorter than the round-trip time between Bob and Alice (Eve could
potentially be on the same LAN as Bob). Since Eve can see all
messages coming from Bob, she is capable of collecting the
following information based on Message-1 and Message-2:

Ni, Nr, g^r, g^i, IPi, GRPINFOr, HMAC{HKr}(g^r, Nr, Ni, IPi)

( Note that snooping on Message-2 alone is not sufficient since
g^i is not returned by Bob. By the way (BTW), why should Message-1
contain g^i? In message-2, the HMAC does not cover g^i. This can
cause some problems--in the proof of the protocol the HMAC does
cover g^i--but I will send a separate e-mail for this. )

Having collected this information, Eve can now fabricate a
message-3 as follows:

Fake-Message-3(k,j):    Ni, Nr,  g^i, g^r, HMAC{HKr}(g^r, Nr, Ni,
                        IPi), Garbage(k), Garbage(j)

Please note that IPi is sent in clear in Message-1, and therefore
the authenticator alone cannot prevent Eve from sending a valid
message before one complete round trip (it's still needed in the
authenticator for cookie jar). Eve can now flood Bob with several
Fake-Message-3(k,j) in which she copies the authenticator, IPi,
etc., that she had snooped, and fills the rest of the fields with
garbage for different values of (k,j). For example, Eve can send
1000 copies of Message-3 to Bob with the same HMAC but different
Garbage(j,k).


Note that Alice needs to sign some fields in Message-3, and the
keys for signing the document *might* reside on a separate server.
This means that there could be considerable delay (~sec) from the
time when Bob sends Message-2 and receives Message-3. During this
time, Eve can generate a large number of Fake-Message-3 and send
it to Bob.

When Bob receives Fake-Message-3, he will find the authenticator
intact, so he will proceed with calculating Ke and Ka.

Unfortunately, calculating Ke and Ka will require DH
exponentiation. After performing the DH exponentiation, Bob will
try to verify the identity of Alice, and he will try to decrypt
Garbage(i) and Garbage(j) only to find that the identities do not
match. Unfortunately by this time it would be too late because Eve
would have forced Bob to unnecessarily compute the DH exponential.

As the draft suggests, Bob will mark this connection as one which
has some trouble, but it cannot do anything more than that. Bob,
for example, cannot say that he will not process future Message-3
with the same authenticator. Doing so will allow Eve to prevent
Alice from communicating with Bob since Eve can always send
Message-3 before Alice can. In fact, Bob has no other option than
to move to the next message Fake-Message-3(k+1, j+1) and run the
same exponentiation again and again until he finally receives a
legitimate Message-3 from Alice. This is a typical down side of
stateless mechanism--yet its worth keeping ... Read on ...

Please also note that if Alice's Message-3 gets lost in the
network (or Alice crashes and reboots), Eve will have one complete
PFS interval to keep sending Fake-Message-3. This could be
potentially exhausting to Bob if the PFS interval is large.

To summarize, There are two problems with this:

a) Bob will run out of computation resources if Eve could send
sufficiently many Fake-Message-3 before Alice's Message-3 arrives,
and

b) Alice will receive several identity-match-failure messages, and
depending upon how agile she is (wants to be), she might try to
initiate new SAs for each rejection. BTW, the draft should mention
that if Message-3 is rejected, then Bob MUST echo back Ni in
Message-4 so that if new rejects with same Nis arrive to Alice,
she does not immediately start new key exchange. In addition, Bob
must also send a valid proof for his own identity for the rejected
message, otherwise Eve can send a reject message on behalf of Bob
and prevent Alice from communicating with Bob.

Fortunately, its possible to counter this DOS attack without
having to change anything, expect for adding one more piece of
(64-128bit) information in Message-3.

The basic idea is that Alice must provide a computationally
inexpensive proof in Message-3 that can convince Bob that Ni came
from Alice, and Alice alone. Once Bob has this information, he has
evidence *beyond reasonable doubt* to go ahead and compute the
exponentials.

This is how Alice can prove this (this protocol can be used with
any DH scheme that uses cookies to avoid DOS attack):

Message-1 (Alice->Bob) : Instead of generating *any* random number
Ni, Alice should generate Ni as follows:

 Ni = HMAC{rand_key}(IPi|IPr|rand_key)

In other words, Alice generates a random number rand_key, and uses
that number as a key to compute the HMAC on the concatenation of
the IP addresses and the rand_key itself. Alice then sends
Message-1 as usual. Alice MUST keep rand_key and Ni in a table
because she will later need this in Message-3 (this is not a 
threat).

Message-2 (Bob->Alice): Bob returns the Message-2 as before,
computing the HMAC as usual. No new processing/states for Bob.

When Alice receives Message-2 from Bob, she must return all the
usual information in Message-3, but she must also send back
rand_key--in plain text!--to Bob. In other words, Message-3 will
now look like:

Message-3 (Alice->Bob): rand_key, Ni, Nr, g^i, g^r, HMAC{HKr}(g^r,
					Nr, Ni, IPi)

When bob receives Message-3, he should first calculate,

HMAC{HKr}(g^r, Nr, Ni, IPi) .... (1)

and verify that it matches with the value of authenticator
returned. If it does, then Bob should compute:

HMAC{rand_key}(IPi|IPr|rand_key) == Ni .... (2)

If the above expression also matches, Bob should compute the DH
exponential.

If either (1) or (2) fails to match, Bob should reject the
message-3, but he *should not* inform Alice about it.

Why should this seemingly stupid protocol that sends keys in plain
text work? The reason it works is because Eve does not know about
rand_key, and therefore she cannot return the rand_key in
Message-3. Since Bob verifies (equation-2) that Ni was calculated
using the right HMAC, He can discard those messages where it does
not match and this way he can prevent himself from computing the
exponential.

What if Eve tries to respond with a fake value of Ni computed with
her own rand_key. Well, the HMAC{HKr}(g^r, Nr, Ni, IPi) in (1)
will not match and Bob can safely reject the message even in that
case.

There is, however, a potential problem. Let's say Alice's Message-3
reaches Eve, but gets lost/dropped after that. This can happen
since Alice is using UDP (using TCP does not help either; Eve can
see the TCP sequence number in clear...). In that case, Eve can
send the right key, rand_key, and Bob will have to compute the DH
exponential. Bob can however prevent himself from computing a
large number of exponentials in this case.

If Bob finds that Ni's and HMAC{rand_key}[*] match, but the signed
document does not, he can mark such a connection as "In Trouble,"
and stop processing all future message with the same authenticator
returned in Message-3. In addition, Bob can ask Alice to
re-initiate key exchange. In present JFK protocol, Bob could not
have rejected all future messages because Eve could have always
sent a message before Alice, potentially denying Alice the access
to Bob. But now for Eve's attack to be successful, she must
somehow get Alice's packet dropped. Getting Alice's packet dropped
is beyond the control of Eve (if Eve can control packet dropping,
she can drop Message-1 itself, preventing Alice from communicating
with Bob. She does not have to do all this eavesdropping
acrobatics in that case) and therefore her attack will be
successful only if packets are dropped even the second time.
Please note that if Alice's packet is lost in the network before
Eve sees it, then Eve cannot take advantage of a longer PFS
interval because Bob will never compute the exponentials.

It's possible to make this protocol resilient to packet loss also
by adding a few extra "tricks," but that would require more
computation, so I will not describe it...(besides this e-mail is
already too long. Apologies ...)

To make this protocol robust to packet reordering that can happen
between Alice and Eve, Bob should not immediately stop processing
the DH exponential if the Ni's match but the signatures don't. He
should process at least 3 messages before marking the packet as
"In Trouble." If Bob is under-loaded he can process a few more
than 3 messages.

JFK is a very nice protocol; I hope it totally replaces all 
IKEvXYZ. JFK draft does however requires a few more paragraphs 
on how to reject messages. Don't forget that rejecting a 
key initiation is as big a decision as accepting it, and 
it should too get it's fair share of attention. If rejection 
details are left unmentioned, there might be interpretability 
problems later on.

Please let me know what you think.

--Yogesh