Subject: Re: [DNA] Small security flaw in Hash FastRA (with proposal)

From: Greg Daley <[email-masked]>
Date: Tue, 04 Apr 2006 12:02:46 -0400

Hi Julien,

Julien Laganier wrote:
> Hi Greg,
> 
> I agree it is important to assess what you are proposing w.r.t. to the 
> expectation that FastRA scheduling is predictable. 
> 
> I however have one question. If I understood correctly the attack you 
> described:
> 
> - The rogue AR needs to configure an address that would trick other 
> on-link ARs to believe that rogue AR ranks first for a specific host 
> sending an RS (at time t_RS.)
> 
> - To achieve that the rogue AR has to use that address to send an RA 
> (at time t_RA.)
> 
> This implies that t_RA < t_RS. 
> 
> Section 5.1.8 says: 
> 
>  " A Host Token is needed from the RS to calculate the router's
>    ranking. The first 64 bits of an SHA-1 hash of the source address
>    of the RS MUST be used as the RS host token."
> 
> So either the rogue AR knows the IP address of the attacked node 
> before it uses it to send the RS, or it has to discover it in the RS, 
> which would imply that t_RS < t_RA, which contradict with the above. 

You're right, I'm assuming some prior knowledge
(t_RA < t_RS), please see below.

> So do you assume that the rogue AR already knows the attacked node IP 
> address or did I missed something in FastRA or the attack you 
> described? I'd think it's unlikely that the rogue AR knows the IP 
> address of the node in advance...

Yes, I'm assuming that the router can guess the IP address of the host.

This isn't particularly difficult, if the target has been seen before,
is using an EUI-64 or a CGA.   The prefix is unchanging, so this may
have been seen on a different link.  This even works with 3041 addresses
which are preserved after a link-layer hint.

It depends on the value of the target. If there's a value in
tracking the target someone may put in that effort.  For
example, if the person was a government official, or
a movie star, people may want to play man-in-the-middle.

It shouldn't be easy for them to do this though.

> Anyway, if you assumed that the rogue AR already knows the attacked 
> node IP address, a similar mitigation of the attack that would also 
> works with non-SEND nodes would be to add to the RS a source of 
> entropy elsewhere than in the (not present) SEND nonce. 

There's no source entropy except the source address (and the link-layer
address, which is constant) in the RS.  There aren't even any flags.

Always changing the source address (3041-style) will work too,
although it's not clear if this would create a large number of
Neighbour cache entries on peer routers (I guess it would...
but would that be acceptable?)

> This could be achieved by mandating that DNA nodes sending RS includes 
> a random nonce either into a DNA-specific parameter (e.g. DNA_Nonce) 
> or into Fragment header with offset set to 0 and last fragment set to 
> 0 (i.e. no fragmentation.)

Adding an RFC3971 Nonce option even to non-SEND hosts would
achieve the same thing.

It doesn't have to be a new option, it could be the same one.
Let's not hack fragment headers ;)

That's not to say I'm proposing Nonce options for all hosts,
it would work though, without further changes to options and formats.

> Thanks.
> 
> --julien
> 
> PS: I didn't get the email from James replying to your initial post. 
> Perhaps the ML server still has problems...

Please let me check.

Greg

---

From: Julien Laganier <[email-masked]>
Date: Tue, 04 Apr 2006 14:19:37 +0200

Hi Greg,

Section 5.1.8 says:

Thanks.

--julien

On Friday 31 March 2006 22:38, Greg Daley wrote:
> Hi All,
>
> There's a small security flaw in Hash FastRA which
> can be used to force all routers to respond
> more slowly than the bogus router for a particular
> solicitor.
>
> With an initially passive attacker, the host can identify
> all good routers on the link, and identify which of
> the routers will be the first responder, by XORing
> each of the routers' hashes with that of the host,
> and then generating new addresses whose XORs beat
> the leader.
>
> This takes on average O(2^L) passive address generations
> where L is the number of leading one bits in the best
> router's XOR.  For a small number of routers, this is
> likely to be achieveable, with limited computational
> cost for an attacker.
>
> This can be improved greatly for SEND hosts if any
> Nonce received in a solicitation is incorporated into
> the soliciting Host's hash generation.
>
> This will change the hashed value for each incoming RS
> and consequently randomize the XOR values for the
> responding routers.
>
> No router or host will be able to predict which responder
> will be first, until the RS is received.
>
> Original Host token generation:
>
> left_64(SHA-1( host link-local address  ))
>
> Modified Host token generation:
>
> left_64(SHA-1( host link-local address, Nonce  ))
>
> Hosts which don't send Nonces (non-send hosts?) don't
> receive the benefit.
>
> This is detailed in my thesis (not yet submitted :-/ )
> but I'm placing it here now because it may be important
> to consider as people are assuming predictable scheduling
> for all of a host's received RAs.
>
> Greg

---

From: Christian Vogt <[email-masked]>
Date: Mon, 17 Apr 2006 23:25:53 +0200

Greg,

this is an important observation.  I have one comment about your
proposed solution:

Your approach is based on randomizing the XOR input that comes from the
MN.  Given that your proposed security solution is based on SEND, how
about verifying the XOR input that comes from routers?

Specifically, a router identifies neighboring routers by listening to
transmitted RAs.  Currently, it accepts all received RAs.  But if SEND
is used, that router could drop received RAs if they cannot be
authenticated to originate from a legitimate router.  The router would
thus ignore the attacker's FastRA token when doing the XOR.

This approach should have an effect comparable to your proposed solution
(unless I am missing something).  Yet, the order of transmitted RAs
would not change due to randomization.

What do you think?

- Christian

-- 
Christian Vogt, Institute of Telematics, University of Karlsruhe
www.tm.uka.de/~chvogt/pubkey/

---

From: Greg Daley <[email-masked]>
Date: Mon, 17 Apr 2006 17:40:30 -0400

Hi Christian,

> would not change due to randomization.

I think that we have been trying very hard to not require explicit trust
between routers, as we already had a solution which did that,
called Deterministic FastRA.

It doesn't reorder responses, it relies on the trust chains being
mutually authenticated between the routers.  This is an all-or-nothing
approach as a single router on-link which doesn't understand the
other's trusted root will cause scheduling collisions on every RS
reception.

If we could count on them knowing each other, we'd ditch the Hash FastRA
system, and go with Deterministic.  I don't think we want to do that,
because the non-SEND routers are still an important subset of the
networks we want DNA to work on.

(I'm not biased, Deterministic has my name first on the draft, and
Hash FastRA was thought up at the same time by Erik and Brett in an Aha!
design team e-mail thread).

Please remember that any non-SEND node can add a Nonce option to its
packet and gain the same protection against a nasty lurker.

Greg

---

From: Christian Vogt <[email-masked]>
Date: Tue, 18 Apr 2006 02:17:38 +0200

Hi Greg!

> I think that we have been trying very hard to not require explicit
> trust between routers, as we already had a solution which did that, 

I see, so much the better.

Deterministic FastRA could be an option for networks where RA ordering
is important and routers can mutually authenticate each other, such as
NETLMM.  This wouldn't break things; the routers would just ignore the
Nonce option used by MNs in RSs and come up with their own,
deterministic RA ordering.

- Christian

Greg Daley wrote:
>> Your approach is based on randomizing the XOR input that comes from
>> the MN.  Given that your proposed security solution is based on
>> SEND, how about verifying the XOR input that comes from routers?
>> 
>> Specifically, a router identifies neighboring routers by listening
>> to transmitted RAs.  Currently, it accepts all received RAs.  But
>> if SEND is used, that router could drop received RAs if they cannot
>> be authenticated to originate from a legitimate router.  The router
>> would thus ignore the attacker's FastRA token when doing the XOR.
>> 
>> This approach should have an effect comparable to your proposed
>> solution (unless I am missing something).  Yet, the order of
>> transmitted RAs would not change due to randomization.
> 
> 
> 
> I think that we have been trying very hard to not require explicit
> trust between routers, as we already had a solution which did that, 
> mutually authenticated between the routers.  This is an
> all-or-nothing approach as a single router on-link which doesn't
> understand the other's trusted root will cause scheduling collisions
> on every RS reception.
> 
> If we could count on them knowing each other, we'd ditch the Hash
> FastRA system, and go with Deterministic.  I don't think we want to
> do that, because the non-SEND routers are still an important subset
> of the networks we want DNA to work on.
> 
> Hash FastRA was thought up at the same time by Erik and Brett in an
> Aha! design team e-mail thread).
>

---

From: Greg Daley <[email-masked]>
Date: Tue, 18 Apr 2006 10:45:43 -0400

> deterministic RA ordering.

That's not exactly what I meant :)

I'd really prefer there's one solution, if possible.

The solution would drop straight in to a constrained
network scenario, but wouldn't work in a scenario
with any form of mixed deployment (caveat deployer!).

At this stage, let's see what the issues are which
need resolving, and we'll work out what the solutions
are from there (I really like HashFastRA, and it has
the blessing of DT and WG).

Greg

---

From: Christian Vogt <[email-masked]>
Date: Tue, 18 Apr 2006 22:49:20 +0200

>> Deterministic FastRA could be an option for networks where RA
>> ordering is important and routers can mutually authenticate each
>> other, such as NETLMM.  This wouldn't break things; the routers
>> would just ignore the Nonce option used by MNs in RSs and come up
>> with their own, deterministic RA ordering.
> 

:-)

> I'd really prefer there's one solution, if possible.

Yep, that's certainly right.

What I meant is that NETLMM routers could really use any (possibly
proprietary) mechanism for scheduling RAs.  Even if the DNA
specification defined MN-generated nonces to randomize the input for the
FastRA scheduling algorithm, that really would not keep NETLMM routers
from using their own solution for both security and scheduling.

There would certainly be problems where different administrative domains
overlap, but I'm not sure if NETLMM is currently chartered for such
scenarios.  Same thing for deployments with heterogeneous access
technologies.

Be it as it may, I agree with you in that there should be one single DNA
mechanism.

- Christian

Greg Daley wrote:
> Christian Vogt wrote:
> 
>> Hi Greg!
>> 
>>> I think that we have been trying very hard to not require
>>> explicit trust between routers, as we already had a solution
>>> which did that, called Deterministic FastRA.
>> 
>> 
>> Deterministic FastRA could be an option for networks where RA 
>> ordering is important and routers can mutually authenticate each 
>> other, such as NETLMM. This wouldn't break things; the routers 
>> would just ignore the Nonce option used by MNs in RSs and come up 
>> with their own, deterministic RA ordering.
> 
> 
> The solution would drop straight in to a constrained network 
> scenario, but wouldn't work in a scenario with any form of mixed 
> deployment (caveat deployer!).
> 
> At this stage, let's see what the issues are which need resolving, 
> and we'll work out what the solutions are from there (I really like 
> HashFastRA, and it has the blessing of DT and WG).
>
> Greg
>