[Hipsec] 28 + 4 + 96 bit HIT crypto agility

[Tobias Heer <[e-mail]>]

Hello, 

we have been discussing about different options to include the HIH (host identity hash) index in HIP packet or in the HIT. The most compelling option (at least to me and Bob) is encoding the HIH in the HIT directly. Advantages of this procedure are: 

a) No need to supply additional parameters with the HIT to convey the HIH.
This simplifies things like referrals and DNS (you just transfer an IPv6-comatible address instead of an address plus the HIH index).

b) A host can immediately determine if it can use a HIT.
There won't be any chance of receiving a HIT without knowing the type.

However, encoding the HIH in the HIT means that we have to sacrifice bits that could have been used for crypto / collision resistance.
The first question is how many bits we would have to sacrifice. I remember Tom asking if we could work with 4 bits for the HIH. I think one could work with four additional bits. This means that 16 different hash functions could be encoded at the same time. Of course we have to use crypto agility carefully then (i.e., we only introduce new HIH algorithms when the previous becomes insufficient). With 16 possible hash functions, this should give us plenty of time to completely phase out HIH #0 before #15 becomes insecure. If we look at the life-cycle of popular hash functions (MD5, SHA-1) 16 replacements represent a huge time frame. We could start over with #0 when #15 becomes insecure. 

Tom also asked whether 100 bits are enough or if we need more. From Julien's reply I take that it's not likely to get anything else than a /28 ORCHID prefix. So now the question is if fewer than 100 bits would do. Using 4 bits for crypto agility leaves us with 96 bits for the actual hash of the HI. Where will that put us in terms of collision resistance and security? I did some calculations based on the birthday paradox to give some examples and to get a feeling for the strength of 96 bits. However, I am not an expert on this, so please tell me if you have deeper insight into the required strength.

The following table gives the number of hashes you have to compute for a given output hash length until you reach a certain collision probability (CP). I put 128 bit there as a reference. 100 bit is the status quo with a 28 bit ORCHID prefix. 96 bit is with 28 bit ORCHID prefix and 4 bit HIH index.

  +---------+---------+---------+---------+---------+---------+       
  | Bits/CP | 0.5     | 0.25    | 0.01    | 0.001   | 0.0001  |       
  +---------+---------+---------+---------+---------+---------+       
  | 128 bit | 2.2E+19 | 1.4E+19 | 2.6E+18 | 8.3E+17 | 2.6E+17 |              
  | 100 bit | 1.3E+15 | 8.5E+14 | 1.6E+14 | 5.0E+13 | 1.6E+13 |       
  | 96 bit  | 3.3E+14 | 2.1E+14 | 4.0E+13 | 1.3E+13 | 4.0E+12 |       
  +---------+---------+---------+---------+---------+---------+ 

I pushed the collision probability down to 0.0001. For 96 bits you need a hash population of 4.0E+12 (4.000.000.000.000 / 4 trillion) to reach a collision with a probability of 0.0001.
100 bits will allow a population of 16 trillion before you reach the same probability.

Some closer-to-real-world-examples that Bob asked me to do take a given population (e.g., entries in an ACL). 
Given an ACL size of 10.000.000 (10 M) the chance of a collision is about 0,0000000000000007 (7E-16) for 96 bits.
Assuming an ACL of 680 billion (current world population x 100), the collision probability is 0,00000000000292 (2.92E-12) for 96 bits. For 100 bits the probability of a collision is 0,000000000000183 (1.83E-13)

These numbers are for benign collisions. For an attacker, it is important to compute a HIT (including public key) that matches another HIT. From the numbers above it seems to me that creating a collision for a determined HIT is out of scope. Creating any HIT collision (e.g. by creating a large number of HITs) will probably not be dangerous either, because the chance that the HIT for which you find the collision is in use is rather small (the address space will be very sparsely populated). What remains is to find a collision for a set of HITs (the HITs that are in use). I found some work on how to compute the probability for sets of random variables but I was unable to come up with useful results because of the very large (and very small) numbers involved. Even Scheme with its good math support was unable to handle the numbers. Maybe someone with matlab skills can help.

What I would like to know from the group: Do you think that a 28 + 4 + 96 bit HIT is a good choice? Do you think the cryptographic strength is sufficient? Do you have other preferences/alternatives?

BR, 

Tobias

--  

Dipl.-Inform. Tobias Heer, Ph.D. Student
Distributed Systems Group 
RWTH Aachen University, Germany
tel: [phone]
web: http://ds.cs.rwth-aachen.de/members/heer