Return to Answer

Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs sizes $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size. However, there are upper limits on SHA-256 and 512 for SHA-512 due to the MOV attack on the Merkle-Damgard construction's artifact. To protect agains this attack the message size is padded. SHA-256 can hash at most $2ˆ{64}-1$ bits ( approx 2.305 exabytes) and SHA-512 has at most $2ˆ{128}-1$ bits ( NIST allows null message)

By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon placed on the hole, there must be at least one hole more than one pigeon.

This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need 2^{37} years to find one with 50%.

We don't try to make them collision-free, we live with it by knowing the boundaries.

Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$ probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;

$$(2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4}$$

We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision. You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.

Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs sizes $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size. However, there are upper limits on SHA-256 and SHA-512 due to the MOV attack on the Merkle-Damgard construction's artifact. To protect against this attack the message size is padded. SHA-256 can hash at most $2^{64}-1$ bits ( approx 2.305 exabytes) and SHA-512 has at most $2^{128}-1$ bits ( NIST allows null message)

By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon is placed on the hole, there must be at least one hole more than one pigeon.

This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need $2^{37}$ years to find one with 50%.

We don't try to make them collision-free, we live with it by knowing the boundaries.

Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$ probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;

$$(2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4}$$

We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision. You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.

Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs like 256 for SHA-256 and 512 for SHA-512. $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size.

By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon placed on the hole, there must be at least one hole more than one pigeon.

This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need 2^{37} years to find one with 50%.

We don't try to make them collision-free, we live with it by knowing the boundaries.

Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$ probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;

$$(2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4}$$

We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision. You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.

Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs sizes $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size. However, there are upper limits on SHA-256 and 512 for SHA-512 due to the MOV attack on the Merkle-Damgard construction's artifact. To protect agains this attack the message size is padded. SHA-256 can hash at most $2ˆ{64}-1$ bits ( approx 2.305 exabytes) and SHA-512 has at most $2ˆ{128}-1$ bits ( NIST allows null message)

By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon placed on the hole, there must be at least one hole more than one pigeon.

This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need 2^{37} years to find one with 50%.

We don't try to make them collision-free, we live with it by knowing the boundaries.

Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$ probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;

$$(2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4}$$

We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision. You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.

Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs like 256 for SHA-256 and 512 for SHA-512. $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size.

By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon placed on the hole, there must be at least one hole more than one pigeon.

This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need 2^{37} years to find one with 50%.

We don't try to make them collision-free, we live with it by knowing the boundaries.

Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$ probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;

$$(2^{32.48})^2/2^{256}/2 = 2^{64.96 - 256-1} \approx 1/2^{192.04}$$

We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision. You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.

Cryptographic hash functions by design cannot be collision-free since they operate on arbitrary-sized input to fixed-sized outputs like 256 for SHA-256 and 512 for SHA-512. $$H:\{0,1\}^* \to \{0,1\}^b$$ where $b$ is the $H$'s output size.

By the pigeonhole principle, collisions are inevitable. Simply consider 100 holes and 101 pigeons. With this condition when the pigeon placed on the hole, there must be at least one hole more than one pigeon.

This doesn't mean that one can find a collision very easily. For SHA-256 you need around $2^{128}$ inputs to see at least one colliding pair with 50% probability. For SHA-512 that is $2^{256}$. This is due to the generic birthday attack that has cost $\mathcal{O}(2^{n/2})$ with 50% for $n$-bit output hash function. Those numbers are huge to be considered. For example, the collective power of the Bitcoin Miners can reach $~2^{93}$ SHA-1 hashes per year. This means that they need 2^{37} years to find one with 50%.

We don't try to make them collision-free, we live with it by knowing the boundaries.

Currently, neither for SHA-256 nor SHA-512 there is a collision attack better than the generic collision attack. There are attacks on the reduced rounds, however, this simply indicates that better than generic is hard! We will be surprised that one can find two inputs colliding. This happened on MD4 even randomly. MD5 collisions are trivial and SHA-1 has been shattered. Don't confuse that those are not secure hash functions even in the early 2010s.

What are the chances that 2 different strings/URLs produce the same hash when used SHA-256 or SHA-512?

If we model the SHA-256 uniform random then $1/2^{256}$. This is a simple probability; the first element can get any position then the second element has $1/2^{256}$ probability to hit the first one.

Question-2: Assuming that the system saves 30billion URLs their hashes in database, what is a recommended hashing function, if not SHA-2? Please note that a requirement of the system is it should be highly available, meaning: hash computation should not take very long.

30 billion URL ($\approx 2^{32.48}$ URL ) have the probability of collision;

$$(2^{32.48})^2/2^{256}/2 = 2^{69.6 - 256-1} \approx 1/2^{187.4}$$

We call an event is-not-gonna-happen if it has probability $<\frac{1}{2^{100}}$. You can use any 512-bit cryptographic hash function like SHA-512, SHA3-512, and BLAKE2b without fear of collision. You may look at BLAKE2b quite fast compared to alternatives and its parallel version BLAKE3.

Are SHA-256 and SHA-512 collision resistant?

Yes, currently as of 2021 and in the near future, yes.