Re: [Gen-art] Gen-ART Telechat Review of draft-ietf-csi-hash-threat-09

["McCann Peter-A001034" <[e-mail]>]

Hi, Ana,

Ana Kukec wrote:
> Hi all,
> 
> Pete, thank you for the comments.
> 
> I've changed the draft and took into account all the comments from
> this email. Some comments are below, inline. 
> 
> 
> 
> Suresh Krishnan wrote:
>> 
>>> 
>>> 
>>> Introduction:
>>>    There is a great variaty of hash functions, but only MD5 and
>>>    SHA-1 are in the wide use, which is also the case for SEND
>>> This sentence makes a statement about MD5 and SHA-1 being the only
>>> widely used hash functions, but I can't figure out what it is
>>> saying about SEND. Is it saying that SEND is widely used?  Or did
>>> you mean to say that SEND implementations typically only implement
>>> MD5 and SHA-1? 
>> 
>> The latter. I propose changing the text to
>> 
>> "There is a great variety of hash functions, but only MD5 and SHA-1
>> are widely used. SEND implementations also typically use these two
>> hash algorithms." 
>> 
> 
> I've changed the text according to your suggestion Suresh.

Ok, thanks.
 
>>> But this sentence is just plain
>>> incorrect (see below).
>>>   Due to
>>>    the birthday attack, if the hash function is supplied with a
>>>    random input, it returns one of the k equally-likely values, and
>>>    the number of operations can be reduced to the number of
>>> 1.2*2^(n/2) operations. There is no "birthday attack."  And I think
>>> you meant 2^n instead of k. The result you give is due to an
>>> equation that is commonly illustrated with a problem known as the
>>> "birthday paradox." 
>> 
>> Right. A birthday attack is an attack that exploits the mathematics
>> behind the birthday paradox. It is a fairly commonly used term. Would
>> you like me to change something?
> 
> That's right -- birthday attack is common term, but only in
> cryptography. I was relying on Bruce Schneier's  book "Applied
> cryptography" where he uses both the term "birthday attack" and the
> equation. Maybe i can make the sentence more clear:
> 
> "Due to the birthday attack, if the hash function is supplied with a
> random input, it returns one of the  equally-likely n-bit hash values,
> and the number of operations can be reduced to the number of
> 1.2*2^(n/2) 
> operations."

I would propose replacing all of this:

   Supposing that the hash function
   produces an n-bit long output, since each output is equally likely,
   an attack takes an order of 2^n operations to be successful.  Due to
   the birthday attack, if the hash function is supplied with a random
   input, it returns one of the k equally-likely values, and the number
   of operations can be reduced to the number of 1.2*2^(n/2) operations.

With this:

   If the hash function produces an n-bit long output, then each of the
   2^n outputs can be considered equally likely.  An attacker searching
   randomly or pseudo-randomly through the space of input messages can
be 
   expected to find a hash collision after approximately 1.25 * 2^(n/2)
   trials, due to the mathematics of the birthday problem [ref].

Perhaps find a good reference for "birthday problem."  Schneier might
be good, but wikipedia also suggests this one:

E. H. McKinney (1966) Generalized Birthday Problem, American
Mathematical Monthly 73, 385-387.

> 
> Other comments are fixed.

Thanks,

-Pete

> Ana