Collision resistance

[mark...@jungle-monkey.com]

Hi all,

I am stuck on part of my computer science homework:

"Assuming that it is computationally infeasible to launch attacks that
require 2^128 computations of hash values, how long should the hash
values be to achieve weak and strong collision resistance
respectively?" - 5 marks.

I've done some research on the internet, and can't find any hard
definitions for "strong" or "weak" collision resistance. Obviously
collisions are impossible to avoid completely.

But do you have any idea how to arrive at hard and fast numbers for
these terms?

Thanks,

Mike

[Andres Valloud]

Mark,

From what I see there, I assume strong collision resistance means "impossible to find collisions".  Since the exercise is telling you that 2^128 hash value computations are infeasible, then it follows that you must have at least 2^128 different hash values (so you have enough material to brute force).  For such an amount of hash values, you need 128 bits' worth of a hash.  I do not know what weak means, and it is likely that its definition varies with context.

Finally, I am finishing a book on the subject.  Would you mind passing me your homework exercises, with some reference as to the college, course and so on so I can quote them properly?  In exchange for your kind assistance which I am grateful for in advance, I could include your full name in my book.

Thanks,
Andres.

[mark...@jungle-monkey.com]

Hi,

I've done a bit more reading and I think strong collision resistance
has to do with withstanding a "birthday attack" which requires 2^(2*n)
bits. So I think the answer is 128 and 256 bits respectively, but I'm
still not 100% sure.

But I have uploaded all my past papers, assignments and lecture slides
to the following url if you would find them useful:

http://rapidshare.de/files/37952413/CSC324.zip.html

I would rather remain anonymous. This module is called mobile
computing and information security.

It is probably the information security component you would be most
interested in.

Enjoy.

On Nov 28, 4:22 am, "Andres Valloud" <andres.vall...@gmail.com> wrote:
> Mark,
>
> From what I see there, I assume strong collision resistance means
> "impossible to find collisions". Since the exercise is telling you that
> 2^128 hash value computations are infeasible, then it follows that you must
> have at least 2^128 different hash values (so you have enough material to
> brute force). For such an amount of hash values, you need 128 bits' worth
> of a hash. I do not know what weak means, and it is likely that its
> definition varies with context.
>
> Finally, I am finishing a book on the subject. Would you mind passing me
> your homework exercises, with some reference as to the college, course and
> so on so I can quote them properly? In exchange for your kind assistance
> which I am grateful for in advance, I could include your full name in my
> book.
>
> Thanks,
> Andres.
>

[Andres Valloud]

Mark,

Thank you so much!  You shall remain anonymous as you requested.

Thanks again,
Andres.