What is the maximum number of SHA-1 hashes?

Asked 10/9, 2011 at 16:0 Answered 12/2, 2014 at 8:21

Solved hash cryptography sha1 sha hash-collision

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

Persuasion answered 10/9, 2011 at 16:0 Comment(4)

It doesn't "produce" 40 characters. It does produce 160 bits of hash. If you see them in hex format, you see 40 hex digits. – Bellinzona 10/9, 2011 at 16:8

No. 40 signed/unsigned chars are "normally" 320 bits (8 bits/char). A SHA-1 is 160 bits = 20 bytes = 40 hex digits. You asked a precise question about how many SHA-1 hashes are there. Just to make an example, if I write a SHA-1 in base64 I get a string long 28 characters (of which 1 is fixed and is the terminating =) – Bellinzona 10/9, 2011 at 16:39

Okay, SHA-1 hashes consist of 160 bits = 40 hexadecimal digits, commonly encoded into a 40 character string if that makes it better. My last comment was indeed incorrect, which is bad considering I have written a tight SHA1er in C. – Persuasion 10/9, 2011 at 17:19

My fear was that you were a junior programmer that thought the DVD-ROM was a cup holder :-) But if you wrote a SHA-1er then you can think whatever you want of SHA1 hashes :-) In this case it becomes an "informed choice" :-) – Bellinzona 10/9, 2011 at 17:25

SHA-1 hashes have 160 bits, so 2¹⁶⁰ of them.
(2¹⁶⁰ = 1461501637330902918203684832716283019655932542976 ~= 1.46 x 10⁴⁸)

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 2⁸⁰ 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%).

Donau answered 10/9, 2011 at 16:1 Comment(9)

I guess the question asks whether the hash function is surjective, though. – Bourn 10/9, 2011 at 16:1

Google calc: 1.46150164 × 10^48 :-) – Bellinzona 10/9, 2011 at 16:2

I'll add that the number of possible SHA-1 is very near the sqrt(googol) (a factor of only 100) :-) :-) – Bellinzona 10/9, 2011 at 16:12

@NullUser: You seem to be mixing surjective and bijective. Having a proof of either surjectivity or non-surjectivity would both quite likely constitute a break of some kind of the function. Have a look at Is SHA-512 bijective when hashing a single 512-bit block? for a similar question (and answer). – Kerwon 10/9, 2011 at 16:39

I'll buy you a beer if you can generate a SHA1 collision. Or even if you can generate 2^80 messages without one. – Clubby 12/9, 2011 at 5:12

@Nick I'll do it if you buy me a large enough server :) – Donau 12/9, 2011 at 5:15

@Donau How large is large enough? ;) – Clubby 12/9, 2011 at 5:27

2^80 = 1,208,925,819,614,629,174,706,176. A distributed systems that is able to handle 1 billion SHA1 hashes per second would likely take no less than 1,208,925,819,614,629 seconds to find a single collision. 1 trillion SHA1s per sec would be 1,208,925,819,614 seconds. Good luck! – Seeder 26/1, 2014 at 21:11

Hash collision probability calculator, might be useful for others too: everydayinternetstuff.com/2015/04/… – Summertime 9/9, 2016 at 12:13

SHA-1 produces 160-bit outputs, and it should be able to produce just about any sequence of 160 bits, There are 2¹⁶⁰ 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 2¹⁶⁰; for instance, if only 1/4 of them were reachable (2¹⁵⁸), 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.

Alkmaar answered 11/9, 2011 at 15:16 Comment(0)

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.

Seeder answered 12/2, 2014 at 8:21 Comment(2)

If I may ask, what is a Collision? – Underground 5/4, 2022 at 18:50

Two random records of the same value. – Seeder 18/4, 2022 at 5:14

Recommended topics

Hot tags