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

[Tom Taylor <[e-mail]>]

On 01/12/2013 4:53 PM, Hosnieh Rafiee wrote:
>> 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
>
...

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