4 ms·

> The only downside is that trivial image modification will make the hash not match, but that's also true for the perceptual hashes... just with a slightly more

> The only downside is that trivial image modification will make the hash not match, but that's also true for the perceptual hashes... just with a slightly more complicated definition of trivial Well, the difference between the two version of "trivial" is the difference between "incidental" and "purposefully". Re-compressing, resizing or cropping the image changes the SHA256, but (with high probability) not the NeuralHash. Those operations happen all the time in the normal course of image distribution. Unlike "running through a tool designed to alter the NeuralHash value". In other words, your suggestion trades false positive rate for false negative rate, under the argument that any nonzero false negative rate is effectively the same. This argument is not convincing, particularly when your suggestion would reduce the true positive rate from (a hypothetical) 99% to a much lower value.

nullc 5y ago
One could still adopt a scheme which would be robust against recompression much of the time. E.g. downsample the image to a specific bounding size (e.g. 360x360), drop the least significant bit or two of each pixel value. SHA256 the result. This would be robust against a significant percentage of recompression pipelines, and yet would still maintain a clear guarantee against false positives: Unless SHA256 is successfully attacked, no one can find two images with the same hash unless their 360px/6-bit-per-color downsample is identical. (And small crops-- are they really that common?-- could be handled by adding them to the database. For significant crops the neuralhash won't be preserved in any case.) I'm aware that attackers can make contrived images that look rather different when downsampling. But that is still a much much stronger promise than neuralhash could make since the downsample hack requires obviously contrived false positive images (unlike neuralhash false positive images). Essentially neuralhash (and similar approaches) is the solution you get when you weigh maximally in favor of false positives to avoid false negatives. SHA256 the pixels (or the whole image files) is the solution you get when you favor false negatives to avoid false positives. You can hit many points in the middle. Given that no scheme can be robust against intentional false negatives and that apple is happy to allow 30 hits before treating it as a match, I'd argue that the apple scheme (or similar) is just an objectively bad choice.
- MauranKilom 5y ago
  Ok, let's do some math. Let's assume image compression randomly flips the last bit of every pixel (this is a crude approximation but it should do). Let's further assume your original image was 1k x 1k and was shrunk by a factor of 3, so each downscaled pixel is the average of 9 original ones. Let's then assume that all nine pixels have to "flip" in a specific way to change the downscaled one, so a 1/2^9 chance. The odds of this bit flip propagating past the last two bits you dropped are 1/4 (dropping bits is not very effective at combating random behavior!). That means there is a 1/2^11 chance that adding compression to the pipeline changes any given downsampled channel-pixel in the 360px/6-bit-per-color hash input. The SHA256 stays the same if this does not happen in any of the 360 x 360 x 3 channel-pixels. The odds of that are (1 - 1/2^11)^(360*360*3) = 3.4e-83. You could drop two more bits and the odds would still be 2.4e-21 (each dropped bit amounts to taking the square root). In effect, your suggested scheme would simply never assign the same hash with any amount of compression happening. Fundamentally, you still have way too many pixels that might spuriously change from tiny perturbations of the input image. Reducing resolution further is actually much more effective than dropping bits, because it both increases the averaging effect and reduces how many pixels have a chance to flip.
  - nullc 5y ago
    Indeed, you're right.

nullc 5y ago

One could still adopt a scheme which would be robust against recompression much of the time. E.g. downsample the image to a specific bounding size (e.g. 360x360), drop the least significant bit or two of each pixel value. SHA256 the result. This would be robust against a significant percentage of recompression pipelines, and yet would still maintain a clear guarantee against false positives: Unless SHA256 is successfully attacked, no one can find two images with the same hash unless their 360px/6-bit-per-color downsample is identical. (And small crops-- are they really that common?-- could be handled by adding them to the database. For significant crops the neuralhash won't be preserved in any case.) I'm aware that attackers can make contrived images that look rather different when downsampling. But that is still a much much stronger promise than neuralhash could make since the downsample hack requires obviously contrived false positive images (unlike neuralhash false positive images). Essentially neuralhash (and similar approaches) is the solution you get when you weigh maximally in favor of false positives to avoid false negatives. SHA256 the pixels (or the whole image files) is the solution you get when you favor false negatives to avoid false positives. You can hit many points in the middle. Given that no scheme can be robust against intentional false negatives and that apple is happy to allow 30 hits before treating it as a match, I'd argue that the apple scheme (or similar) is just an objectively bad choice.

MauranKilom 5y ago
Ok, let's do some math. Let's assume image compression randomly flips the last bit of every pixel (this is a crude approximation but it should do). Let's further assume your original image was 1k x 1k and was shrunk by a factor of 3, so each downscaled pixel is the average of 9 original ones. Let's then assume that all nine pixels have to "flip" in a specific way to change the downscaled one, so a 1/2^9 chance. The odds of this bit flip propagating past the last two bits you dropped are 1/4 (dropping bits is not very effective at combating random behavior!). That means there is a 1/2^11 chance that adding compression to the pipeline changes any given downsampled channel-pixel in the 360px/6-bit-per-color hash input. The SHA256 stays the same if this does not happen in any of the 360 x 360 x 3 channel-pixels. The odds of that are (1 - 1/2^11)^(360*360*3) = 3.4e-83. You could drop two more bits and the odds would still be 2.4e-21 (each dropped bit amounts to taking the square root). In effect, your suggested scheme would simply never assign the same hash with any amount of compression happening. Fundamentally, you still have way too many pixels that might spuriously change from tiny perturbations of the input image. Reducing resolution further is actually much more effective than dropping bits, because it both increases the averaging effect and reduces how many pixels have a chance to flip.
- nullc 5y ago
  Indeed, you're right.