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

From: Greg Daley <[email-masked]>
Date: Fri, 31 Mar 2006 15:38:44 -0500

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