Hacker News Reader

Comment by Retr0id | Hacker News Reader

Beware of having too-small fingerprint hashes though, or not checking enough of the digits.

    $ echo -n retr0id_662d970782071aa7a038dce6 | sha256sum
    307e0e71a409d2bf67e76c676d81bd0ff87ee228cd8f991714589d0564e6ea9a  -
    
    $ echo -n retr0id_430d19a6c51814d895666635 | sha256sum
    307e0e71a4098e7fb7d72c86cd041a006181c6d8e29882b581d69d0564e6ea9a  -

View on HN

The interesting thing about that is that while a fairly impressive number of the beginning and end values match, a trivial side-by-side comparison glance makes it clear they don't match even if you don't directly compare any of the digits. I think humans are actually pretty good at this task if they approach it more like humans than machines and just give the two values a quick glance with the intent of spotting differences rather than a nibble by nibble comparison.

On the other hand, I initially thought this was a collision until a second glance :-S

Yup. Me too.

True, if you can do a side-by-side comparison! On a mobile device, switching between apps and manually comparing, it would have probably fooled me.

For sure, I often just look at the beginning and end

> a trivial side-by-side comparison glance makes it clear they don't match

A "trivial, side-by-side comparison glance" would lead me to believe the two number strings are the same. If I'm just glancing I'm not going to take care to read each and every character out and compare them, that's not what glancing means.

The best such method is dynamic comparison when the position of each string is the same, you just change the value, this also works for pictures, much easier to spot the deference vs having to glance back and forth

Though for this specific case of only needing to check for identity, no human comparison should be involved, copy&search to see if the other is a match if you have no better tools

My favorite way of comparing "things" is to put them next to each other and then use the exact same technique one uses for viewing those "Magic Eye" stereograms [1]. With that you basically overlay both sides and where it doesn't match, you just see the difference.

[1] https://en.m.wikipedia.org/wiki/Magic_Eye

Interesting. I use `diff`.

Well yeah, if I can copy and paste stuff I do that too :-)

This is a good point, and by your example it's obviously feasible to find enough of a "collision" on both ends of the digest to make it look like a match at a careless first glance.

In your particular example, I counted at least 96 bits that match on the ends (in total...from 48 bits on each end), and now I'm curious what kind of hardware you used and how long it took to find this match.

If you have the available RAM/SSD for a birthday attack, you only need 48 bits worth of complexity, which makes this a manageable problem. I suppose the ASICs for bitcoin mining don't have the needed bandwidth to storage devices which would put my guess onto GPUs. Assuming 32 bytes of storage per hash (probably more but you wouldn't store the full hash, instead a hash table with the prefix+postfix up to a certain amount, then of course some hash table management overhead), you'd have to write around 9 PB if you write once, 1 petabyte if you write 64 times, for the raw hashes only.

You don't need to store all the hashes, just the Distinguished Points[1]. It took me a couple of days on a single AMD RX6700XT desktop GPU, using some negligible amount of RAM (it was a few GB of main system memory iirc).

[1] https://www.cs.csi.cuny.edu/~zhangx/papers/P_2018_LISAT_Webe...

On way to deal with this is to hash it again. For demonstration purposes I used CRC8, but a longer hash is probably less prone against further collisions):

    307e0e71a409d2bf67e76c676d81bd0ff87ee228cd8f991714589d0564e6ea9a = 0x7B

    307e0e71a4098e7fb7d72c86cd041a006181c6d8e29882b581d69d0564e6ea9a = 0xFC

Um, not sure what you aim to solve here.

You are effectively increasing collision risk by an arbitrary amount by running hash output as input to a crc algorithm.

Kids, don't roll your own security.

I think you misunderstood:

This is if you compare two hashes and they look really similar but you want to be really sure.

Of course a real equality check is better but visual check of original hash + this is better than visual check alone.

Ah, thanks. Yes, I did not understand this properly.

A similar technique is employed by git to get past SHA-1 collision risk, so I wouldn't say it's entirely without merit.

Before: two hashes that might pass a manual check

After: four hashes that don't pass a manual check

The short ones are there so you can easily spot the collision in the long one, even if the start and the end are the same. If you read just the short ones your criticism applies, but that was not the idea. You read the long one first, then the short one. This is a logical AND not a logical OR, thus it gets harder to make both collide at once (because there are less similar looking values for the first one that produce the same values in the second one + your attacker might not know which one you are using).

Maybe if you read my comment, you will also realize I pointed out that CRC8 is the wrong choice for this, but I was on my phone and this was the hash calculator I found first.

More structure can help here. My fave example:

    9999 9999 9999
    9999 9999 9999
    9999 9999 9999

Now the users will not always pick the beginning or the end when they fail to compare the whole thing. That is because they can easily identity each group to the other person (combinations of top, middle, bottom, left, right, centre).

If I randomly check 4 digits sampled uniformly across all positions you won’t have a higher chance than 1/16 to convince me unless you match 128 digits

1/16 is several orders of magnitude too high for comfort. There are only 64 hex digits total, so I'm not sure where 128 comes from?

If you meant bits, the two example hashes I gave already match 184 out of 256 total bits.

Exactly. A 1 in 16 chance to send money to a scammer instead of the intended party is unacceptably high, for example.

The software should check the hashes

The whole point of fingerprinting is to produce something that's feasible to manually verify, as described in the article. If you're comparing in software there's no need to hash first (unless it's part of a certificate chain etc.)

There is a need... If you compare untrusted files with trusted software.... At the very least, it should be an additional check because I'm pretty sure that this example could have fooled me... But diff would have had no issues

Honestly I really wish I could have my shell recognize this situation and highlight differences for me automatically. The number of extra steps and the low number of negatives you get promotes complacency.

Reply on news.ycombinator.com