Subject: [Hipsec] Basic question about HIP

From: [email-masked] (marcelo bagnulo)
Date: Wed May 5 12:31:01 2004

Hi,

I was wondering which are the risks vulnerabilities by a collision of HITs.
I mean, suppose that a user U has his public key PKu and his hit is HITu =
hash(PKu)
Suppose that another user A finds another key PKa which hash collides with
the previous one,
i.e. HITa=hash(PKa)= hash(PKu)=HITu
would this allow A to perform some sort of attacks to U or to another party?
I am sorry if this topic has already been discussed before, if this is so i
would appreciate a pointer to previous discussion/documents)

Thanks, marcelo

---

From: [email-masked] (Pekka Nikander)
Date: Thu May 6 05:00:01 2004

> i.e. HITa=hash(PKa)= hash(PKu)=HITu

First, as you sure know, the probability of such collisions is extremely
low.  Since HITs are effectively 126 bits long, for any given HIT the
probability that there is a collision is approximately (2^-126) * N 
where
N is the total number of HITs.   If you assume 100 billion HITs, or a 
few
ten hits for each human on earth, the probability that somebody is 
colliding
with your specific HIT is still 2^(-126+37) = 2^-89.  Not very likely, I
would say.

On the other hand, due to the birthday paradox, there is the possibility
that given a large enough population, there may be collisions.

If there are <m> HITs in total, <n> of which are used, the
probability that there is at least one collisions is

             m - 1     m - 2     m - 3           m - n + 1
    p = 1 - ------- * ------- * ------- * ... * -----------
               m         m         m                 m

Since in our case  m >> n , the approximation

   m - 1 = m - 2 = m - 3 = ... m - n + 1

still gives a reasonable bound for the probability, the
real probability being lower.  Hence,

             (m - n + 1)^n
    p < 1 - ---------------
                 m^n

             m^n - n * m^(n-1) * (n+1) + k * m^(n-2) * (n+1)^2 - ....
      = 1 - ----------------------------------------------------------
                                    m^n

             m^n     n * m^(n-1) * (n+1)     k * m^(n-2) * (n+1)^2
      = 1 - ----- + --------------------- - -----------------------
             m^n              m^n                    m^n

Since m >> n, the series is dominated by the first term, and we can
approximate

          n * m^(n-1) * (n+1)     n * (n+1)      n^2
    p ~= --------------------- = ----------- ~= -----  (as n >> 1)
                 m^n                  m           m

Hence, if we have 2^37 HITs used from the population of 2^126
HITs, the probability that there is at least one collision is
in the order of

         (2^37)^2     2^74
   p ~= ---------- = ------- = 2^-52 ~= 2.2 * 10^-16
           2^126      2^126

While this probability is still extremely small, it has less
entropy than the currently used cryptographic keys, and therefore
can't necessarily be completely ignored.  Hence, as a result of
this back-of-the-envelope analysis, the answer is "it depends".

> would this allow A to perform some sort of attacks to U or to another 

As Tom already answered, that depends on whether you use just HITs
to identify trusted parties (you shouldn't) or if you just the
full public key to identify trusted parties.  For opportunistic 
protection,
collisions don't really matter due to the small magnitude of 
probability.

--Pekka