Re: Collision in SHA-0

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 08/17/04 

Date: Tue, 17 Aug 2004 11:31:12 +0200

Paul Rubin wrote:

> s_vinder@mail.com (S. Vinder) writes:
>
>>All hash algorithms (including ideal ones) produce collisions. The
>>question is *how often* they produce collisions. When you mount a
>>brute force attack, it is perfectly ok for any hash algorithm to
>>produce 1 collision per 2^n/2 generated n-bit hashes (it is
>>statistically expected). Only when you have discovered more than one
>>collision, you can claim an algorithm "broken". Even if they mount
>>some other kind of attack (other than brute force), more than one
>>collision per 2^n/2 attempts have to be discovered to be able to claim
>>that the algorithm has been "broken".
>
>
> I wouldn't say that. If someone discovers a 256 bit key K such that
> AES_K(0x 0000 0000 0000 0000 0000 0000 0000 0000) produces
> 0x 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111, then I'd
> say AES is broken. The security claim is that no adversary can
> find such a key (or hash collision or whatever) with probability
> better than brute force. If they've found some faster way to do it,
> the claim fails.

I suppose the concept of 'probability' plays a role here. In
other words, what does 'with probability better than brute
force' exactly mean? Let's take an analogy: The top win in
lottery has a known probability. Imagine that one plays
lottery the first time and one wins, what would that signify?
I mean the 'probability with brute force' is an aveage one
that manifests itself only when a sufficiently large number
of trials are undertaken. Or do I miss something? Thanks.

M. K. Shen

Relevant Pages

  • Re: Collision in SHA-0
    ... > All hash algorithms produce collisions. ... > brute force attack, it is perfectly ok for any hash algorithm to ... > some other kind of attack (other than brute force), ... find such a key (or hash collision or whatever) with probability ...
    (sci.crypt)
  • Re: Collision in SHA-0
    ... >>All hash algorithms produce collisions. ... >>brute force attack, it is perfectly ok for any hash algorithm to ... >>some other kind of attack (other than brute force), ...
    (sci.crypt)
  • Re: Birthday Problem
    ... > array - reads the array and tries to detect an ... > exact match The problem is that the match is ... unless you were specifically told to use brute force. ... consider a naive way to do it by hand: check the probability if the ...
    (comp.lang.cpp)
  • Re: what is the probability of getting at least a doubble six in 24 throws?
    ... > Does this mean throwing two dice 24 times and getting ... but we can do this with a state transition matrix easily: ... the the probability of the last state after 24 throws. ... Doing this by brute force gives ...
    (sci.math)
  • Re: Select a subset of paths
    ... >than brute force, ... You might as well enumerate all the paths and then ... Of course this will result in a different probability distribution ... on the space of paths than the first method (which gives all paths ...
    (sci.math)