[DNA] Ordering Hash-based RAs

[Greg Daley <greg.daley@eng.monash.edu.au>]

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