CODEWITHSUNDEEP
hashcryptographysha1shahash-collision
James
James

Reputation: 31738

What is the maximum number of SHA-1 hashes?

Clearly since SHA-1 hashing produces 40 characters each time, there is a finite number of possible hashes—does anyone know exactly how many?

Upvotes: 8

Views: 5463

Answers (3)

JSON
JSON

Reputation: 1835

SHA-1 is made up of 5 32 bit integers.

That's 4294967296^5 or 2^160

or 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976 possibilities

To put that into perspective

Total Possible SHA-1 Values: 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976

Total gallons of Water on Earth: 365,904,000,000,000,000,000

That includes every ocean, sea, lake, swimming pool, bath tub, etc - source

The possibility of collisions is only theoretical at this point. Still waiting to hear of one.

Upvotes: 1

Thomas Pornin
Thomas Pornin

Reputation: 74382

SHA-1 produces 160-bit outputs, and it should be able to produce just about any sequence of 160 bits, There are 2160 such sequences, i.e. close to 1461 billions of billions of billions of billions of billions. That's kind of big.

However we have no proof that every single one of them is reachable. It would be bad for SHA-1 security if the number of possible outputs would be significantly lower than 2160; for instance, if only 1/4 of them were reachable (2158), security against preimage attacks would be divided by 4, and security against collisions would be halved. No such issue is currently known with SHA-1 (there are known weaknesses of SHA-1 when it comes to resistance to collisions, but not that one).

It is possible (but it would be at least mildly surprising) that a few 160-bits outputs cannot be reached. It is expected that this will be remain unknowable. To some extent, being able to prove that SHA-1 possible outputs cover the whole 160-bit space would be worrisome: such a proof would require a good deal of analysis of the mathematical structure of SHA-1, and the security of SHA-1 largely relies on such an analysis being intractable.

Upvotes: 11

NullUserException
NullUserException

Reputation: 85458

SHA-1 hashes have 160 bits, so 2160 of them.
(2160 = 1461501637330902918203684832716283019655932542976 ~= 1.46 x 1048)

Note that since you have a much larger message space than possible hashes, collisions are bound to occur.

Also note that the probability of collision is much higher than you might think. At just 280 messages the probability of a collision is 50%, thanks to the Birthday paradox. (ie: with just 23 people the probability that 2 people have the same birthday is 50%).

Upvotes: 16

Related Questions