Perceptual hashing, and how NeuralHash collided

One of the images is a photo of a beagle. The other looks like a gray square that someone sneezed static onto. They have the same NeuralHash, all 96 bits of it, and that pair, posted to a GitHub issue last Wednesday, is the reason a lot of people spent the weekend reading about perceptual hashing.

The background, quickly. On August 5th Apple announced that, starting with iOS 15 in the US, photos being uploaded to iCloud Photos would be checked on the device against a database of hashes of known child sexual abuse material from NCMEC and other child-safety groups. The hash is NeuralHash, Apple’s own. Then last week a developer who goes by Asuhariet Ygvar found that the NeuralHash code was already present in iOS 14.3, extracted the model, converted it to ONNX so anyone could run it, and put it on GitHub. A few hours later Cory Cornelius, a researcher at Intel Labs, posted the beagle and the blob.

I want to get to the collision, but it only makes sense once you know what a perceptual hash is trying to do, and why it’s so different from the hashes we normally talk about.

A hash that’s supposed to be fuzzy

A cryptographic hash like SHA-256 is designed so that changing one bit of the input changes about half the bits of the output, unpredictably. That’s what you want for passwords or Merkle trees, and it’s useless for images, because the same photo saved twice at different JPEG quality settings, or resized, or with a tiny watermark, gives completely different hashes. If you want to recognize a known image after it’s been through a few apps, you need the opposite property: similar images should give similar, ideally identical, hashes.

That’s a perceptual hash. The simplest one, usually called aHash, goes like this. Shrink the image to 8×8 pixels and convert to grayscale, so you have 64 numbers. Work out their average. Then write a 1 for each pixel brighter than the average and a 0 for each darker one. That’s a 64-bit hash.

You compare two hashes by counting how many bits differ, the Hamming distance, and treat anything under some threshold, say 5 or 10 bits out of 64, as the same picture. Resizing the image barely changes the 8×8 thumbnail. Recompressing it barely changes it. So the bits mostly survive.

dHash is the same idea except each bit says whether a pixel is brighter than its neighbor to the right, using a 9×8 thumbnail, which turns out to be more stable. pHash goes a step further: shrink to 32×32, take a discrete cosine transform (the same transform JPEG uses, which I went through in the video compression post), keep the 8×8 block of lowest frequencies, and compare each coefficient to the median. Low frequencies are the broad shape of the image, which is exactly what survives compression and resizing. We actually use a dHash at work, to spot near-duplicate images in customer uploads, and it’s about 20 lines of code.

The big one in this space is PhotoDNA, which Microsoft developed with Hany Farid around 2009 and gives to NCMEC and to companies that scan for this material, and which the large platforms have been using on their servers for years. Its details aren’t public, but it’s in the same family: a fingerprint designed to survive the edits people make.

These hashes hold up against the edits they were designed for and not much else. Flip an aHash image horizontally and nearly every bit changes. Crop it, rotate it by a few degrees, or put a border around it, and it’s a different picture as far as the hash is concerned. That’s the motivation for something like NeuralHash.

NeuralHash

Apple’s version swaps the thumbnail for a neural network. From the extracted model, and Ygvar’s write-up of it, the steps are:

1. Resize the image to 360×360 and scale the RGB values to between −1 and 1.
2. Run it through a convolutional network, more than 200 layers, which outputs 128 floating-point numbers, an embedding of the image.
3. Multiply that 128-number vector by a fixed 96×128 matrix, giving 96 numbers.
4. Take the sign of each one. Positive is a 1, negative is a 0. That’s the 96-bit hash.

The network is trained so that two versions of the same image (cropped, recompressed, color-shifted, and so on) end up with embeddings pointing in nearly the same direction, and different images point in different directions. The last step is a classic trick called locality-sensitive hashing with random hyperplanes. Each of the 96 rows of the matrix defines a hyperplane through the origin of the 128-dimensional space, and each bit just records which side of that hyperplane the embedding falls on. Two vectors that point in almost the same direction will be on the same side of nearly every hyperplane.

This is one of the few times my math degree has been directly relevant to a news story. For truly random hyperplanes there’s a neat result, from a 2002 paper by Moses Charikar: the chance that a single random hyperplane separates two vectors is the angle between them divided by π. Two embeddings 10 degrees apart differ in each bit with probability 10/180, about 5.6%, so across 96 bits you’d expect about 5 to differ. Two unrelated images, roughly 90 degrees apart, differ in about half. Apple’s matrix may not be random, but the geometry is the same.

That’s also where one wrinkle shows up. Apple’s matching, as described in its technical summary, requires the hashes to be identical, and the matching is done cryptographically so that the device never learns whether anything matched. So the network has to be stable enough that minor edits move the embedding without moving it across any of 96 hyperplanes. Ygvar found that the same image can give hashes that differ by a few bits on different Apple hardware, because of floating-point differences, which Apple presumably handles somewhere.

Why the collision was always coming

A neural network is a differentiable function. You can ask, for any pixel of the input, which way to nudge it to make a particular output number go up or down, and that’s exactly the machinery used to train the network in the first place. Researchers have been using it for years to build adversarial examples, images that look like one thing to a person and like something else entirely to a classifier.

So once the model is in your hands, you can pick a target hash, start from any image, and repeatedly nudge the pixels to push each of the 96 values toward the sign that target wants, while penalizing changes a person would notice. The hash only cares about signs, so you don’t even have to hit exact values, just get each one onto the right side of its hyperplane. That’s how you get a collision, and with more care, a natural-looking photo that hashes to a value you chose. It’s also how you’d go the other way, adding a faint, nearly invisible pattern to an image so its hash changes. I’m not going to go further into the how than that, and it’s all described at a conceptual level in the GitHub thread anyway.

This would be true of any perceptual hash, PhotoDNA and pHash included. A perceptual hash is a deliberately lossy summary of an image, with 2⁹⁶ possible outputs for an essentially unlimited number of possible images, and its entire purpose is to make many different inputs map to the same output. It can’t have the collision resistance of a cryptographic hash, because that would defeat the point. What kept the classic ones relatively safe from this sort of attack was mostly that you couldn’t just run gradient descent on them, and that the server-side ones were run on servers. NeuralHash is a differentiable model that ships inside the operating system of every iPhone.

What Apple says

Apple’s response has been that the extracted model is a generic version and not the final one that will ship, and that the system was designed knowing collisions could be found. Its threat model document, published on the 13th, lays out the defenses. The hash database on the device is blinded, so you can’t read the target hashes off your phone. An account is only flagged after about 30 matches. A flagged image is checked on Apple’s servers against a second, independent perceptual hash that isn’t public, before any human sees it. And then a human reviews it.

That’s a reasonable set of layers against someone trying to frame a person with forged collisions. The attacker needs real target hashes they can’t easily get, needs to get around 30 crafted images into the victim’s photo library, needs them to also collide under a hash they can’t see, and then has to get past a person looking at them. I don’t think the framing attack is likely to work as described.

The evasion side is a different story. Making a known image not match is much easier than making an innocent image match, and that only needs the on-device model. That’s what I’d expect people with something to hide to do, and I’m not sure anything in Apple’s design addresses it, apart from the second hash on the server, which only sees images that already matched.

My bigger problem with all this was never the hash function, and it’s the same one a lot of people have raised: once the machinery exists on the device, what goes into the database is a policy decision, and policies change under pressure. But that’s a different post. On the technical question, I’d say the beagle doesn’t break the system, and it does show that the first line of defense is a model anyone can now run, and that “the attacker doesn’t have the model” didn’t survive the first two weeks.