1
$\begingroup$

This is my first post on this forum, apologies if this post is naive. I want to learn cryptography and I want to start with this question.

Context: Designing a TinyUrl system. The user inputs a lengthy URL and the system computes the hash and encodes it binary64 and sends it back to the user.

From what I understood so far (from this forum and also from Wikipedia) that SHA-2 algorithms are not collision-free. If these functions are indeed not collision-free, how to make them collision-free? There are resources on the internet that recommend adding jitter, for example, a unique string at the beginning of the URL, a viable solution in software systems design. This not only makes the different URLs produce different hashes, but it also makes the same URL produces 2 different hashes on 2 different tries (presumably for 2 different users). In the reverse lookup, the system can ignore the prefix and redirect the user to the original URL using HTTP 302. However, this adds its own complexity to the system that is generating/using unique prefixes across different servers of a distributed system.

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

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.

Appreciate any help. Thanks in advance!

PS: Happy to get started with cryptography.

$\endgroup$
1
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks so much! I took some time to grasp the pigeonhole principle citation. I think I got it now. If the hash function produces the same output size for any variable input size, then some of the inputs will produce the same hash design. I think I also understood the remaining part of the answer in general, but I will surely need to read up more to grasp all of it. $\endgroup$ – bp4D Apr 26 at 0:17
  • 1
    $\begingroup$ Welcome. Any part that is not clear, can be extended. $\endgroup$ – kelalaka Apr 26 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.