Is this way of encoding cryptographic hashes safe?

Question

I'm looking at the code of a particular web application that handle file uploads. For some reason, instead of using the cryptographic hash function (SHA-256 in this case), they derive an ID from it, and use that everywhere instead, to identify files uniquely.

The steps involved are as follows:

• Calculate the SHA-256 sum of the required file.
• Take a maximum of 3 characters per iteration, and treating it as a hex string, convert it to its equivalent base62 notation (i.e. 0-9a-zA-Z => 0 - 62).
• Append these strings in that order, and obtain the "ID".

For example:

hash (file) = 26ba0a896923d2de4cad532a3f05da725d9cc08d371eaf96905f5bbc1901b56f

26b  -------> 9Z
a0a  -------> Fs
896  -------> zs
923  -------> BJ
d2d  -------> Sp
e4c  -------> X2
ad5  -------> IJ
32a  -------> d4
3f0  -------> gg
5da  -------> oa
725  -------> tv
d9c  -------> Uc
c08  -------> NG
d37  -------> Sz
1ea  -------> 7U
f96  -------> 12m
905  -------> Bf
f5b  -------> 11p
bc1  -------> Mx
901  -------> Bb
b56  -------> KO
f    -------> f

ID = 9ZFszsBJSpX2IJd4ggoatvUcNGSz7U12mBf11pMxBbKOf

To me, this does not seem to be a safe way to truncate the hash at all. In particular, it looks to me that the probability of collisions increases this way.*

Do the above operations pose a problem, or do they not interfere with the cryptographic strengths of SHA256?

* The resistances of the SHA-2 functions may prevent an attacker from exploiting this. However, I'm just concerned about the premise of the function itself.

Answer 1

This is almost a perfectly fine practice, but it has a bit of a flaw.

In general, a hash is just a numeric value, and you can express it in whatever base you please. For example, you could convert your hash to binary and express it as base64:

   2   6   b   a  ...
   |   |   |   |
0010011010111010  ...
      |      |
      T      u

However, the serious problem with your approach here is the clustering of the output. Three hex digits may transform into either one, two, or three base62 digits. There is no reliable way to decide how to cluster the base62 values. If you had leading zeros (i.e., you transformed three hex digits into three base62 digits) and/or used a larger base (e.g., three hex digits could map onto exactly two base128 digits with leading zeroes), you could avoid this problem.

To see a practical example of this, consider that hex f43 maps to base62 111 and 03f maps onto base62 11. Consider the impossibility of distingusinging between the base62-forms of the following hashes:

f43f43f43f43f43f43f43f43f43f4303f03f03f03f03f03f03f03f03f03f9991
03f03f03f03f03f03f03f03f03f03ff43f43f43f43f43f43f43f43f43f439991
03ff4303ff4303ff4303ff4303ff4303ff4303ff4303ff4303ff4303ff439991

All of these hashes transform into

11111111111111111111111111111111111111111111111111CC1

There is no way to know which 1s are part of a three-character group and which are part of a two character group. Obviously, this is an extreme example, but the problem will arise any time a group has a leading 1 that is ambiguous.

However, three- and one-digit output groups only happen for 314 out of the possible 4096 values that group can be, and there will only be ambiguity for a fraction of those cases. A comment from Gilles, below, estimates the resultant truncated value will preserve 254 bits:

As far as we know, the bits of a SHA-2 hash are independent. This truncation doesn't exactly strip bits, but it's close enough that it should be independent too. The non-uniqueness concerns only about lg(12³-62²)≈0.1 bit per 3 hex digits, so the result should have roughly the strength of a 254-bit hash.

The loss of two bits is obviously not optimal, but it's far from a devastating loss.

Answer 2

From what I can see, this isn't truncation at all. Each 12-bit section (3 ASCII hex characters) is converted to its equivalent base62 representation, which is a bijective operation. You can take the values on the right and turn them back into the values on the left.

The operation doesn't truncate the value, but rather reduces its resultant length by using a more efficient encoding, just like computing the base64 value of the raw hash bytes would.

Answer 3

"Truncate" means to remove a portion altogether. In this example, if I truncated the right half of the hash characters, the remainder would look like this: 26ba0a896923d2de4cad532a3f05da72

So yes, truncation will increase your collisions, but that's not what is happening here.

Answer 4

If the length of the hex representation of the hash is unacceptable, and one wants to uniquely represent hashes in a shorter string using a limited character set, using base-64 rather than base-64 would allow a nice easy mapping (even if one has to replace . and / with different characters); if there are only 62 acceptable characters, one could subdivide the data into 64-bit chunks and use 11 base-62 characters to store each for a fixed total length of 44, only one character more than the optimal fixed-length encoding using 43 characters (your encoding would sometimes use 43 characters, but sometimes require more, and wouldn't be unique). Encoding 64 bits in base-62 should be reasonably easy on any platform that has a 64-bit unsigned integer type; on platforms that don't, one could encode 53 bits as 11 base-31 characters and add one of the remaining 11 bits to each of the base-31 characters to yield a base-32 character.

Answer 5

I don't think there is enough information to really give a good answer. The possible 'weakness' with this approach is that by reducing the representation length, you have increased the change of collision. Two files with different hashes may end up with the same transformed code. However, this may not be an issue, depending on the application or the risk of collision may be of less concern than the need to reduce representation length. there really isn't enough info to judge.

However, having said that, on the face of it, it seems difficult to justify the increased potential for collision given the minimal amount of representation length, especially given that if the length of the representation is the problem, you would assume that there must be a lot of these hashes to store, which means collision is possibly more likely. Then again, perhaps it is all just about the increase in efficiency obtained by comparing shorter signatures where possible collisions are not an issue