Re: [DNA] Ordering Hash-based RAs

[Brett Pentland <brett.pentland@eng.monash.edu.au>]

Greg Daley wrote:
> Dear DT,
> 
> I really like the hash based RA scheme indicated in the
> document draft-pentland-dna-protocol-00.

:)  That's good to hear.

> I think there's an issue with its robustness to false
> 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 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.

Agreed.

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

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.