Fingerprints are not unique

[Skycoder42]

Hi,

I am currently working on a dart port of etebase. While working on the fingerprint, I found that it is in fact not unique and can produce the same fingerprint for two different hashes.

The following is a constructed scenario to prove that it does overlap (code automatically converted from dart to js):

const testData1 = new Uint8Array([1]);
const testData2 = new Uint8Array([2]);
const testHash1 = new Uint8Array(32).fill(0x00);
const testHash2 = new Uint8Array(32).fill(0x00);
testHash2[12] = 0x01;
testHash2[13] = 0x86;
testHash2[14] = 0xA0;

// mock libsodium so that:
// sodium.crypto_generichash(32, testData1) returns testHash1
// sodium.crypto_generichash(32, testData2) returns testHash2

const result1 = sut.prettyFingerprint(testData1);
const result2 = sut.prettyFingerprint(testData2);

console.log(result1);
console.log(result2);
console.assert(result1 != result2);

This code produces a fingerprint that is all 0 for both cases.

This happens because of how data is truncated. the bytes 12-14 produce one segment for the fingerprint. combining these three numbers into one chunk produces 0X0186A0 which in decimal is 100000. So the mod operation turns this into 0. Now, since the lastNum only uses the 10 first bytes of the hash for it's calculation, the fact that 12, 13 and 14 look different is taken into account anywhere, thus the collision.

I have not calculated the entropy loss yet, but since an attacker does not have to find two keys that produce the same hash, but only two keys that produce the same fingerprint, this string conversion definitely increases the attack risk! I will post an update soon with the actual collision test results.

[Skycoder42]

Okay, so if I only check for a single chunk (3 bytes) of data, each possible output has 167 to 168 possible inputs, this basically means the usual 24bit of entropy are reduced to ~17 (not exactly, as not all 17 bits can be fully used, but lets go with that number for now), so we have a loss of 7 bit. This applies for all chunks between 10 and 29, so 5 chunks in total, which reduces the total entropy by 35. As the hash itself is 32 bytes - 256 bit, that reduces the total entropy to 221. It might be worse, as it is very likely more duplicate can be found in the first 10 or last 3 bits.

221 is still relatively high for a fingerprint, but it still does not sit right with me. Also, the manipulation is limited to the middle of the hash, not the whole thing, but I do not know if that influences the chances.