2
$\begingroup$

Is it possible to have strings of two (Unicode) symbols with equal SHA-1 hash?

For example, smth like "ab", "ba".

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
4
$\begingroup$

No, that's actually pretty easy to compute, because you only have to compute all possible hashes of possible two strings, which would be $n^2$, where $n$ is the number of possible characters / symbols.

Edit:

As fgrieu correctly explained in the comment: Because of the birthday attack we would expect a natural collision between two SHA-1 hashes to occur at $\approx 2^{80}$ hashes.

And $2^{80}$ is a lot larger than $1,111,998^2$.

2nd Edit:

There are a lot of different sources for the exact amount of Unicode characters / symbols there could be (see comments below), but most of them are around $1'100'000$ and are either way far too small to reach $2^{80}$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Maybe you can explain in terms of math behind SHA-1? Blocks, permutations... Brute force way I understand, thanks. $\endgroup$
    – Vlad
    Commented Jan 18, 2019 at 12:20
  • 2
    $\begingroup$ @Woland: no, that can't be explained in the way that you suggest. The only known way to prove what you ask to prove is to compute the hash of all strings of two unicode characters ($1112064^2$ if you extend that to all pairs of valid unicode points), and find there is no duplicate (feasible though not trivial, using distinguished points). It is not really useful to check, because under a random oracle model of SHA-1 (which as far as we know applies well, save for the length-extension property, irrelevant here) it is overwhelmingly likely, because $1112064^2\ll2^{80}$; see birthday problem. $\endgroup$
    – fgrieu ♦
    Commented Jan 18, 2019 at 12:33
  • $\begingroup$ Could you explain where the number 1,112,064 comes from? There seem to be 1,114,112 possible code points and over 113,000 (presumably normalized) characters defined for Unicode. I'm just wondering by the way, the first one is very near the stated number and the second one only makes the difference greater, so the answer would not change. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 18, 2019 at 13:54
  • 1
    $\begingroup$ @MaartenBodewes There are apparently 1,111,998 possible code points as this answer explains $\endgroup$
    – AleksanderCH
    Commented Jan 18, 2019 at 14:06
  • $\begingroup$ @AleksanderRas OK, that explains the number, but I'd still question the logic. I'd actually assume that the characters should exist though, as the question is about "symbols". In that case Unicode 9 has less than 130K characters. Oh well, Unicode is tricky, the answer will fortunately survive any of these possible values. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 18, 2019 at 14:11
0
$\begingroup$

This answer is not a theoretical answer rather a practical one.

First of all the hash functions are need paddings in order to prevent the basic collisions, that is, a, a0, a00, etc. all will have a collision if not padded correctly, or you can see at

In this answer, there is a C++ code that searches for a collision for your cause. You can reach it by editing.

My test run computer can run it upto $43,000,000$ hashes due to the limit of the memory size of the system, that is 8GB. The test ran uses unordered_map that requires a hash function. Interestingly, we need to hash of hash, the trick is to use the least significant bits hash result. Therefore, there will be false positive collisions, too. According to the birthday paradox, we expect that in $2^{32}= 4,294,967,296$ one have to see a false collision with $50\%$ if the size_t of the system is 8-byte. To see one, you have to hash 100 times more if you are lucky.

To able to search for all input space that the number is given by the AleksanderRas' answer you may need to implement a Rainbow table to search all of your input space, and this is the ultimate choice for this kind of searches to reduce the memory storage. This, however, will increase the CPU-time since you are running only once.

Note: If you somehow find a real collision, note it somewhere. It has academical value.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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