Re: Complex Theoretical One Way Hash Question

xmath wrote:
none wrote:

Another question : take the MD5 hash of the phrase " the MD5 hash of
this phrase is n", where n is a string of hex digits. For what number n
is this true? Birthday paradox, should find one in about 2^64 tries...


There's no birthday paradox here, since there's no collision between
two elements of a set. Finding a match to that question has only
chance 2^-k on every try (k = size of hash in bits) regardless of how
many attempts you made. On average you'll therefore only find a
solution after 2^(k-1) tries, which is too much even when using MD5.

- xmath

I must admit that I jumped to conclusions here, assuming that this was similar to a collision, rather than the 2^128 case of finding n for which md5(phrase,n)=(some_fixed_number). Unfortunately, I am not adept enough to be sure either way, but I will take your word for it.
(/me goes back to the textbooks)
P.S. if you read my other post describing the competition, can I assume that my beer money is safe? And no, I wont raise the prize to 2^64 beers :)
.

Relevant Pages

  • Re: Whats the probability that 2 files of n bytes have the same hash using SHA1?
    ... I read about the birthday paradox and I think I undestand it. ... collision using brute force by: ... 'balance' of a hash function quantifies the resistance of the function ... Let say that one file is fixed: it's the reference ...
    (sci.crypt)
  • Re: Dont understand birthday attack on cryptographic hash -- newbie
    ... Translated to a wider space of size N, the "birthday paradox" becomes: ... SHA-1 outputs, which are 160-bit words, and you suppose that you get ... this means that if you get a collision before collecting ... There is no guarantee except that if you collect only one output, ...
    (sci.crypt)
  • Re: Random Number
    ... I'm not sure about Python 2.3 or 2.4. ... Is the underlying generator biased enough to make such a collision ... after the birthday paradox. ...
    (comp.lang.python)
  • Re: Musings on uniqueness
    ... The Birthday Paradox reduces it considerably when you're dealing with a ... chance of a collision. ... probability of collision would be unacceptable. ...
    (comp.programming)