RE: FW: New Version Notification for draft-rafiee-6man-cga-attack-00.txt

[Greg Daley <[e-mail]>]

Hi Hosnieh, 

I think that the points raised by Marcelo and Christian are important.

Your analysis appears to focus on the field (from the paper referenced) being heavily populated.   For a more usual number of link (or subnet) residents, the rate of collision is lower.   As pointed out by Christian, the attack would be directed at all devices present, but a single (not pre-determined/predictable) device would be collided with under the "birthday" collision.

Please forgive any mistakes in my attempt at analysis.  It has been a while.

>From the referenced paper the probability of a collision on population q on field  r is :

/q\ 
\2/
---
 r^(mu(h))

for:
q is the number of nodes resident on the subnet.
r = 2^62, (or 2^64, omitted for brevity).
q << r
mu(h) ~ 1  (but < 1 for some hash functions)
Following Christian, the number of trials isn't impacted by the SEC value (but each trial is more expensive).  I've not had time to work through this this morning.   Even in the case of the 

~> for the balanced hash function:

/q\
\2/
---
 r

~>

( q! / ( 2* ( q - 2)! )
-----------------------
         r
~>

( q * (q-1) )
-------------
   2r

so for subnets with 1000 hosts:

500*999
------- 
2^62

~> p ~ 2^-43.06 
~> on average 2^42.06 trials to find a single collision.

If SHA-1 was as bad as mu(h) = 0.98, we lose about 1.04 bits:

500*999
-------
2^60.96

~> p ~ 2^-42.02
~> on average 2^41.02 trials to find a single collision on the 1000 nodes.

>From the research presented, this is a generously high side estimate of the SHA-1 imbalance so the impact is between the values presented (0.98 and 1).

For 10000 nodes on the subnet, the possibility of a collision for one of the nodes may be found in:

5000*9999
---------
2^62

~> p ~ 2^-36.42 
~> on average 2^35.62 trials to find a single collision on the 10000 nodes (2^34.58 at high imbalance)


(perfect hash distribution, 2^62 possible values, 
nodes | log2(0.5n*(n-1)) | p(collision) | mean trials for collision.
-----------------------------------------------
32     | 9.1241       | 2^-54.87 | 2^53.87
64     | 10.977       | 2^-51.022 | 2^50.02
128   | 12.988       | 2^-49.011 | 2^48.01
256   | 14.994       | 2^-47.005 | 2^46.00
512   | 16.997       | 2^-45.002 | 2^44.00
1024  | 18.998       | 2^-43.001 | 2^42.00
2048  | 20.999       | 2^-41.000 | 2^40.00
4096  | 23.000       | 2^-39.000 | 2^38.00
8192  | 25.000       | 2^-37.000 | 2^36.00
16384 | 27.000       | 2^-35.000 | 2^34.00
32768 | 29.000       | 2^-33.000 | 2^32.00

* For 2^64 possible values, add 2 bits to the number of trials/subtract two bits for the probability
* For mu(h) of 0.98 subtract 1.04 bits from the number of trials/add 1.04 bits for the probability

Please note that this is for a single collision with a non-predictable CGA. A second collision would be on average slightly harder than the prior one (since the potential targets are fewer, although some of the search space would be processed), and so on, with increasing complexity to collide with subsequent nodes. 

I'll leave it for others to identify if this is accurate, or reflects a significant impact on SEND/CGA when SEC is non-zero (getting back to work).

Greg Daley 



-----Original Message-----
From: ipv6 [mailto:[e-mail]] On Behalf Of Hosnieh Rafiee
Sent: Monday, 2 December 2013 9:27 AM
To: 'marcelo bagnulo braun'; 'Christian Huitema'; 'Ray Hunter'
Cc: [e-mail]; 'Erik Nordmark'
Subject: RE: FW: New Version Notification for draft-rafiee-6man-cga-attack-00.txt

> > Birthday attack is still possible with the following approach. Check 
> > this nice article.
> > http://eprint.iacr.org/2003/065.pdf
> 
> I just skimmed the paper and it seems to state that in some hash 
> functions fewer attemps are needed to find a clash.
> This does not contradicts my statement. Birthday paradox can be used 
> to
find
> tow values that clash, not to find a preimage of a given target value.
> 

What I understood from reading it is that, they want to find the possible collision for any given value. So, I saw the similarity of our case. What we wanna do is to find a collision for the value of legitimate node.

Smile,
Hosnieh

--------------------------------------------------------------------
IETF IPv6 working group mailing list
[e-mail]
Administrative Requests: https://www.ietf.org/mailman/listinfo/ipv6
--------------------------------------------------------------------