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

From: "Hosnieh Rafiee" <[email-masked]>
Date: Sun, 1 Dec 2013 22:53:56 +0100

> El 29/11/13 08:28, Hosnieh Rafiee escribió:
> >
> >
> > In CGA, we have a hash function or like the above example, we have a
> > hash password. What is important for us is only find another message
> > that leads to the same hash. This is where birthday paradox applies.
> > So, in CGA, the attacker really does not care what is the content of
> > your message, it cares about the hash value. He only wants to have
> > another message (or in birthday paradox to have another person with
> > the same birthday that matches yours) to match yours.
> >
> 
> sigh, no.
> 
> the birthday paradox applies when you want to find two values that match
> each other and NOT when you have a target and you want to find a hash
> output that matches the target of your attack.
> 
> In other words, the birthday paradox is not about finding another person
that
> has the same birthday than you but about finding two persons that happen
to
> have the same birthday.
> 
> This is a critical distinction when you want to use this for an attack, as
you
> cannot rely on this to attack a specific target, you can only use it for
finding
> two random values that clash.

Birthday attack is still possible with the following approach. Check this
nice article.
http://eprint.iacr.org/2003/065.pdf   

smile,
Hosnieh

---

From: marcelo bagnulo braun <[email-masked]>
Date: Sun, 01 Dec 2013 23:24:15 +0100

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

Regards, marcelo

---

From: "Hosnieh Rafiee" <[email-masked]>
Date: Sun, 1 Dec 2013 23:27:28 +0100

> > Birthday attack is still possible with the following approach. Check
> > this nice article.
> I just skimmed the paper and it seems to state that in some hash functions
> fewer attemps are needed to find a clash.
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

---

From: Tom Taylor <[email-masked]>
Date: Sun, 01 Dec 2013 20:05:20 -0500

> http://eprint.iacr.org/2003/065.pdf
...

This paper is still about collisions between xi and xj where the two 
points are at random locations in a sequence of length q. It does not 
put a new bound on the number of trials needed to find a collision 
between an initially selected x1 and some other randomly selected point 
in a sequence of length q, and that is the problem at hand. Amazing that 
you cannot see the difference!

Tom Taylor

---

From: Greg Daley <[email-masked]>
Date: Mon, 2 Dec 2013 01:07:22 +0000

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:[email-masked]] On Behalf Of Hosnieh Rafiee
Sent: Monday, 2 December 2013 9:27 AM
To: 'marcelo bagnulo braun'; 'Christian Huitema'; 'Ray Hunter'
Cc: [email-masked]; 'Erik Nordmark'
Subject: RE: FW: New Version Notification for draft-rafiee-6man-cga-attack-00.txt

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
[email-masked]
Administrative Requests: https://www.ietf.org/mailman/listinfo/ipv6
--------------------------------------------------------------------