Re: CGA Use with HBA in Shim6 IETF Meeting July 10, 2006

[Jari Arkko <jari.arkko@piuha.net>]

Iljitsch van Beijnum wrote:

> On 24-jul-2006, at 10:02, Francis Dupont wrote:
>
>>    Too weak for what?
>
>
>> => direct attack against the hash (the O(2^56)).
>
>
> Hm, even if you build a machine that can test 1000 hashes in parallel 
> every microsecond, it will take you more than a year on average to 
> find a hash collision. And when you've found one, you get to redirect 
> traffic, which is only a denial of service attack. If you have enough 
> money to build such a hash breaking machine and enough patience to 
> wait for it to work, I'm sure other, more dangerous avenues of attack 
> are also open to you...

Yes.

> An interesting issue is that after some 10 million hosts start using 
> HBA, there is a 50% chance of two hosts using the same hash, i.e., 
> sort of a distributed birthday attack.

Yes (but only if the hosts are all on the same link. Otherwise the
prefixes will
be different).

Inclusion of prefixes in the hash computation was added in order to
prevent a precomputation attack. In this attack someone calculates
all possible hash values and stores the corresponding keys in a table.
A few years ago when we did the calculations, the required storage
space with highest possible density storage was in the order of several
World Trade Centers worth of office space. Storage technology has
improved since then, but with the prefix as a part of the input to the
hash, you'd have to compute the table for every prefix.

--Jari