Subject: [DNA] Ordering Hash-based RAs

From: Greg Daley <[email-masked]>
Date: Mon, 23 May 2005 15:48:43 +1000

Dear DT,

I really like the hash based RA scheme indicated in the
document draft-pentland-dna-protocol-00.

I think there's an issue with its robustness to false
or hijacking routers, which may limit its usefulness though.

The text presented allows a particular router to select an
interface identifier such that its SHA-1 hash will XOR with
the solicitor's received IID to provide the fastest ranked
response with high likelihood?

This is because the hijacking router knows the other Router's
addresses and their SHA-1 hashes.  It can precompute a hash likely
to XOR with the lowest value.  That is: it can generate a hash with
all leading zeros, by repeated computation of SHA-1 with different
link-local addresses.

With existing EUI-64 addresses, the high order bits of the
IPv6 IID aren't well distributed.  In fact, there's a likelihood
that the seven of the first 8 bits of the IID will be zero.

Considering that, the XOR will be lowest if the first few bits in the
usurping router's SHA-1 hash are zero.

In this way, a router has to perform O(2^zeros) SHA-1 computations
in order to find out a valid IID for generating a sequence of
leading zeros for the hash.

Link-local addresses with known low hashes could even be precomputed.

The essential issue here is that the solicitors' addresses aren't
well distributed.

Two alternatives which overcome this issue are:

1) Perform the XOR comparison with the low order bytes of the IID
    first (either reverse the XORed bit strings, or do bytewise
    comparisons starting at the 16th byte).

2) Ensure that the solicitors' input values are well distributed,
    perhaps using a hash.

I'd lean towards 1).  It's probably fastest computationally, and
   was easy to implement in 16th-to 1st byte comparison form.

Please let me know what you think...

Greg

---

From: Brett Pentland <[email-masked]>
Date: Mon, 23 May 2005 16:25:09 +1000

> document draft-pentland-dna-protocol-00.

:)  That's good to hear.

> or hijacking routers, which may limit its usefulness though.

Aside:  There will be many things that rogue devices can do to
disrupt things if SEND is not used.  If SEND is used then I don't
think the following scenario is a problem, however...

> The essential issue here is that the solicitors' addresses aren't

Agreed.

>   was easy to implement in 16th-to 1st byte comparison form.

I'd also lean towards 1) since it doesn't require calculating a hash
for each RS received.  Doing the bytewise comparison starting at the
low order byte (the 8th since there's only 64 bits in the IID) sounds
like the better option to me, and sounds worth doing.

Cheers,
Brett.

---

From: James Kempf <[email-masked]>
Date: Mon, 23 May 2005 09:30:00 -0700

1 sounds fine.

            jak

---

From: Erik Nordmark <[email-masked]>
Date: Mon, 23 May 2005 14:03:55 -0700

> response with high likelihood?

Greg,

I'm not sure I understand the attack and the impact of it.
Are you saying that an attacker on the link can pretend to be a DNA 
router and select its IID so that it is more or less guaranteed to be 
the router ranked first?
Then the "attack" is that this router will just ignore the RAs, with the 
impact being that the hosts have to wait a few tens of milliseconds 
until the next ranked router responds?

That doesn't sound like a serious attack, given that an attacker on the 
link can cause all sorts of havoc (listed in the SeND threats RFC).

However, it seems like the algorithm in the draft doesn't do a good job 
of spreading which router will respond first, since as you point out, 
the first bits of the IID of the host are the same for EUI-64 based IIDs.
So I think we need to fix this for reasons other than security.

>   was easy to implement in 16th-to 1st byte comparison form.

#1 sounds good to me.

    Erik

---

From: Greg Daley <[email-masked]>
Date: Tue, 24 May 2005 10:55:42 +1000

Hi Erik,

Erik Nordmark wrote:
[cut]
> So I think we need to fix this for reasons other than security.

I agree that the effects aren't necessarily severe.

In some environments though, it may be possible for a bogus router to
then advertise additional addresses to generate further delays.
This is much harder to do if the ordering of the router ranks is
unpredictable.

Spreading out the responses sounds like a good thing to do in any case,
as you point out though.

Greg

---

From: Greg Daley <[email-masked]>
Date: Tue, 24 May 2005 10:56:19 +1000

Hi Brett.

> think the following scenario is a problem, however...

The trick with SEND is to allow explicit trust of the other routers
using common trust anchors, and then most importantly, closing
FastRA to non-trusted SEND or non-SEND routers.

This is not really what the hash based RA mechanism was aimed at,
without diminishing the usability significantly.

There's a SEND configuration flag already (defaulting to off)
which allows unsecured messages to be ignored.
I don't think we'd need to define anything for DNA.

Unless that flag is used, the hash-based RA scheme is subject to
the attacks you alluded to (but may be fairly robust to them).

[cut]
> like the better option to me, and sounds worth doing.

Oops
Sorry about that.

Greg

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 24 May 2005 11:54:42 -0700

> This is much harder to do if the ordering of the router ranks is

Yes, but it is probably much easier to just generate RAs claiming to be 
a router (and generating "spoofed" RAs declaring that the real routers 
have a zero default router lifetime), which would make the link more or 
less stop functioning.

> Spreading out the responses sounds like a good thing to do in any case,

Yep.

    Erik