Re: what is probability to create two equal hashes for md5 algorithm

Unruh wrote:

"Sergei" <silentser@xxxxxxxxx> writes:

Joseph Ashwood wrote:
"Sergei" <silentser@xxxxxxxxx> wrote in message
news:1165441615.135737.121220@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

But if SHA-1 is a uniformly distributed function, how the Chinese guys
could claim that it is possible to find a collision in 2^63 hash
operations?

I'll show how by using something we can prove if uniformly distributed, but
is cryptographically weak enough for the process to be seen; modular
division by 2^64, let's call it F(x). It is trivial to prove that the output
of F is uniformly distributed across the integers [0,2^64-1]. However, we
can also trivially compute x's that collide by simply adding 2^64 to the
previous x. F is perfectly uniform across all integers x, but is trivially
weak.

Uniform distribution among the output set is not enough for cryptographic
strength.


Yes. Though Joseph's example is cr*p.


Sorry for another dilettantish question, but what is "a uniformly
distributed function"? I thought this is simply another name for a
random oracle function. If this is a function that simpy gives
uniformly distributed outputs when given a uniformly distributed inputs
then, for example, F(x)=x is also uniformly distributed. But what does
it have to do with the collision probabilities in the case described
here?

It is precisely relevant. He wants to define collisions as collisions
between different inputs producing the same output. Obviously if the inputs
are not uniform, then the outputs are not since the function is
deterministic ( same input always gives the same output.)

No, they aren't. In fact the precise opposite would be true of a good hash
function. A good hash function should give randomly-distributed outputs
whether or not the inputs were randomly distributed (as long as the inputs
are different).

Then assuming that the input is uniform, so is the output (or at least that
is the assumption)

No, that isn't the assumption.

If that is true, then given 2^x different inputs, the
probability
of having a collision is 1-exp(-2^(2x-N)) for x<N.

No, it isn't. It wouldn't be even if that was true (which it sort-of is, but
it's not the assumption)


You know better than this.

--
Peter

who would hide behind your chair
and steal your crystallised ginger

.

Relevant Pages

  • Re: Is this secure?
    ... the main point is that an attacker is not able to guess passwords ... If it's HTTP instead of HTTPS and you're sending the password in the ... the slightly nonuniform distribution and a uniform one, ... To get a more uniform distribution I usually just take a larger n, ...
    (comp.lang.python)
  • Re: Test for uniform distribution for small sample size
    ... high confidence that the unit interval is not appropriate ... but still uniform? ... and the hypothesized CDF. ... case of the uniform distribution. ...
    (sci.stat.math)
  • Re: Detecting linear transformations of a uniform distribution.
    ... uniform distribution =constant over some large ... transformation, how confident would we be of our estimate ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.stat.math)
  • Re: A dynamic unit test framework in C
    ... If one has a function that can create a uniform distribution for the ... probably don't want to generate trap representations with a probability ...
    (comp.lang.c)
  • Re: what is probability to create two equal hashes for md5 algorithm
    ... Uniform distribution among the output set is not enough for cryptographic ... it have to do with the collision probabilities in the case described ... A good hash function should give randomly-distributed outputs ... The outputs are deterministically dependent on the ...
    (sci.crypt)