Re: What's the probability that 2 files of n bytes have the same hash using SHA1?



On 2009-12-15, PeterMacGonagan <rodrigue.roland@xxxxxxxxx> wrote:
Ok, thank you for all your answers.

I read about the birthday paradox and I think I undestand it. As we
can read, we can approximate the number of attempts to generate a
collision using brute force by:
Q(H)\approx \sqrt{\frac{\pi}{2}H}.

For a 160-bit hash, there are 2^160 possibilities (approximately
1,4615e+48 different outputs). So, it'll take approximately 1.515e+24
attempts to generate a collision (2^80 = 1.2e+24).

Well, depends on what you mean by "collision". It it means "find two
files with the same hash" you are right. If it means ( find a second
file with the same hash as this given file) then this is wrong. It would
take 2^159 on average.


.



Relevant Pages

  • Re: Two-stage hashing (pre-hash big integer -> hash-array-index)
    ... > hash value instead of the key to generate the probe sequence. ... avoid all hashes with same home index following same collision chain, ... are the same will follow exactly the same collision chain. ... computes what I call the pre-hash, the large unsigned integer, from the ...
    (comp.programming)
  • 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: Panama hash collision question
    ... > No hash is literally collision free. ... We synchronize database systems by forming a checksum for each record ...
    (sci.crypt)
  • Re: keys and counters
    ... how many times can the counter be incremented before there is a collision in the hash, that is what i am asking. ... A hash function operated in such a counter mode as you suggest does not have this property - if I can guess or discover the input to the first block then I will know all the other blocks. ... You might think that some attacks are unreasonable/infeasible but do you really know what is possible to the world's largest employer of mathematicians, who have had for many years the world's largest computer budget and unlimited access to 60 plus years of classified research or what is possible for any of the other multi-billion dollar "smaller" big brothers?. ...
    (sci.crypt)
  • Re: Using hash to see if objects attributes have changed
    ... Storing the entire object instead of the hash is not likely to be *that* ... If all you care about is a flag that says whether the state has changed ... stateNow = hashlib.sha1)) ... across such a collision, leading to a bug that might cause loss of data. ...
    (comp.lang.python)