4 ms·

If images have cardinality N and hashes M and N > M, then yes, by pigeonhole principle you will have collisions regardless of hash function, f: N -> M. N is us

by mirker 5y ago

If images have cardinality N and hashes M and N > M, then yes, by pigeonhole principle you will have collisions regardless of hash function, f: N -> M. N is usually much bigger than M, since you have the combinatorial pixel explosion. Say images are 8 bit RGB 256x256, then you have 2^(8x256x256x3) bit combinations. If you have a 256-bit hash, then that’s only 2^256. So there is a factor of 2^(8x256x3) difference between N and M if I did my math right, which is a factor I cannot even calculate without numeric overflow.

klodolph 5y ago
The number of possible different images doesn't matter, it's only the number of actually different images encountered in the world. This number cannot be anywhere near 2^256, that would be physically impossible.
- mirker 5y ago
  But you cannot know that a-priori so it’s either an attack vector for image manipulation or straight up false positives. Assume we had this perfect hash knowledge. I’d create a compression algorithm to uniquely map between images and the 256 bit hash space, which we probably agree is similarly improbable. It’s on the order of 1000x to 10000x more efficient than JPEG and isn’t even lossy.
  - klodolph 5y ago
    You’re going to have to explain that—what is an attack vector for image manipulation? What is an attack vector for false positives? > Assume we had this perfect hash knowledge. It’s not a perfect hash. Nobody’s saying it’s a perfect hash. It’s not. It’s a perceptual hash. It is specifically designed to map similar images to similar hashes, for the “right” notion of similar.
    - mirker 5y ago
      It’s an attack vector because, either directly or indirectly, people will get access to the hash function. Therefore, they will have a testbed to launch attacks against the hash. Once they learn an attack, they will hash your harmless pictures into being classified as CP by applying a potentially perceptually invisible modification to your images. Imagine every image on reddit’s frontpage being classified as CP. The distribution of natural images is irrelevant as long as people can modify images arbitrarily. The hashing isn’t really so relevant apart from pigeonhole arguments. It’s a machine learning problem of classification between CP and not, and hashing is an implementation detail. The way I would attack this reading a few papers would be to approximate any non-differentiable parts of the hashing with a smooth proxy function, then use an off-the-shelf gradient-based attack such as Fast Sign Gradient Method. The hashing guarantees that even at hashing distance 0, you have a huge amount of collisions, so that is blind spot 1. Blind spot 2 is the CNN is not-robust to mild-perturbations, so you can “squeeze” inputs together in hash space by modifying them. You can likely attack both simultaneously by doing the attack I said above.
      - mirker 5y ago
        For what it’s worth, an attack similar to above is now demonstrated. https://news.ycombinator.com/item?id=28219068 https://news.ycombinator.com/item?id=28219068

by mirker 5y ago

klodolph 5y ago

The number of possible different images doesn't matter, it's only the number of actually different images encountered in the world. This number cannot be anywhere near 2^256, that would be physically impossible.

mirker 5y ago
But you cannot know that a-priori so it’s either an attack vector for image manipulation or straight up false positives. Assume we had this perfect hash knowledge. I’d create a compression algorithm to uniquely map between images and the 256 bit hash space, which we probably agree is similarly improbable. It’s on the order of 1000x to 10000x more efficient than JPEG and isn’t even lossy.
- klodolph 5y ago
  You’re going to have to explain that—what is an attack vector for image manipulation? What is an attack vector for false positives? > Assume we had this perfect hash knowledge. It’s not a perfect hash. Nobody’s saying it’s a perfect hash. It’s not. It’s a perceptual hash. It is specifically designed to map similar images to similar hashes, for the “right” notion of similar.
  - mirker 5y ago
    It’s an attack vector because, either directly or indirectly, people will get access to the hash function. Therefore, they will have a testbed to launch attacks against the hash. Once they learn an attack, they will hash your harmless pictures into being classified as CP by applying a potentially perceptually invisible modification to your images. Imagine every image on reddit’s frontpage being classified as CP. The distribution of natural images is irrelevant as long as people can modify images arbitrarily. The hashing isn’t really so relevant apart from pigeonhole arguments. It’s a machine learning problem of classification between CP and not, and hashing is an implementation detail. The way I would attack this reading a few papers would be to approximate any non-differentiable parts of the hashing with a smooth proxy function, then use an off-the-shelf gradient-based attack such as Fast Sign Gradient Method. The hashing guarantees that even at hashing distance 0, you have a huge amount of collisions, so that is blind spot 1. Blind spot 2 is the CNN is not-robust to mild-perturbations, so you can “squeeze” inputs together in hash space by modifying them. You can likely attack both simultaneously by doing the attack I said above.
    - mirker 5y ago
      For what it’s worth, an attack similar to above is now demonstrated. https://news.ycombinator.com/item?id=28219068 https://news.ycombinator.com/item?id=28219068