Re: [DNA] Ordering Hash-based RAs

[James Kempf <kempf@docomolabs-usa.com>]

1 sounds fine.

            jak

----- Original Message ----- 
From: "Brett Pentland" <brett.pentland@eng.monash.edu.au>
To: <greg.daley@eng.monash.edu.au>
Cc: <dna@eng.monash.edu.au>
Sent: Sunday, May 22, 2005 11:25 PM
Subject: Re: [DNA] Ordering Hash-based RAs


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