# SHA-1 collision for strings of two symbols

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

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

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}$$.

• Maybe you can explain in terms of math behind SHA-1? Blocks, permutations... Brute force way I understand, thanks. Commented Jan 18, 2019 at 12:20
• @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.
– fgrieu
Commented Jan 18, 2019 at 12:33
• 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. Commented Jan 18, 2019 at 13:54
• @MaartenBodewes There are apparently 1,111,998 possible code points as this answer explains Commented Jan 18, 2019 at 14:06
• @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. Commented Jan 18, 2019 at 14:11

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
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.