Wednesday, August 18, 2021

NeuralHash Implementation and Collision

Joseph Cox et al. (Slashdot, Hacker News, Reddit):

On Wednesday, GitHub user AsuharietYgvar published details of what they claim is an implementation of NeuralHash, a hashing technology in the anti-CSAM system announced by Apple at the beginning of August. Hours later, someone else claimed to have been able to create a collision, meaning he tricked the system into giving two different images the same hash.

Juli Clover:

In a statement to Motherboard, Apple said that the version of the NeuralHash that Yvgar reverse-engineered is not the same as the final implementation that will be used with the CSAM system.

[…]

Matthew Green, who teaches cryptography at Johns Hopkins University and who has been a vocal critic of Apple’s CSAM system, told Motherboard that if collisions “exist for this function,” then he expects “they’ll exist in the system Apple eventually activates.”

“Of course, it’s possible that they will re-spin the hash function before they deploy,” he said. “But as a proof of concept, this is definitely valid,” he said of the information shared on GitHub.

Hector Martin:

“Early tests show that it can tolerate image resizing and compression, but not cropping or rotations.”

Like every other perceptual image hash. It’ll also have collisions. Keep in mind that the matching is fuzzy (you have to allow some wrong bits).

It’s not hard at all to attack such a hash to make it produce false positives.

Say I am law enforcement and I want access to your photos. I send you >30 messages with non-CSAM but colliding images. Your phone now thinks you have CSAM and grants Apple access to your data.

Then I just have to subpoena Apple for the data they already have, and I have your photos.

Meanwhile the people who actually have CSAM just have to add a frame to their images to completely neuter the system.

A lot rests on how much we can trust Apple’s human reviewers.

Also, apparently Apple’s neural network, by virtue of having 200+ (!) layers and due to floating point rounding issues, actually produces wildly different hashes on different hardware (9 bits difference between iPad and M1 Mac!). That’s... garbage. That’s 9 bits of match noise.

[…]

Actually, how does this even work at all? You have to do fuzzy matching of perceptual image hashes like NeuralHash. But they’re doing some PSI crypto stuff after that that would seem to be incompatible with it, and at no point do they talk about this.

This is not a thing. This cannot mathematically be a thing. There is no way to design a perceptual image hash to always result in the same hash when the image is altered in small ways. This is trivial to prove.

Bruce Schneier:

This was a bad idea from the start, and Apple never seemed to consider the adversarial context of the system as a whole, and not just the cryptography.

Russell Brandom:

In a call with reporters regarding the new findings, Apple said its CSAM-scanning system had been built with collisions in mind, given the known limitations of perceptual hashing algorithms. In particular, the company emphasized a secondary server-side hashing algorithm, separate from NeuralHash, the specifics of which are not public. If an image that produced a NeuralHash collision were flagged by the system, it would be checked against the secondary system and identified as an error before reaching human moderators.

[…]

But actually generating that alert would require access to the NCMEC hash database, generating more than 30 colliding images, and then smuggling all of them onto the target’s phone.

Previously:

Update (2021-08-21): See also: Hacker News.

Bruce Schneier:

I’m not convinced that this secondary system was originally part of the design, since it wasn’t discussed in the original specification.

Sarah Jamie Lewis:

The Apple system dedupes photos, but burst shots are semantically different photos with the same subject - and an unlucky match on a burst shot could lead to multiple match events on the back end if the system isn’t implemented to defend against that.

Jonathan Mayer:

We wrote the only peer-reviewed publication on how to build a system like Apple’s — and we concluded the technology was dangerous. We’re not concerned because we misunderstand how Apple’s system works. The problem is, we understand exactly how it works.

Brad Dwyer (via Hacker News):

In order to test things, I decided to search the publicly available ImageNet dataset for collisions between semantically different images.

[…]

There were 2 examples of actual collisions between semantically different images in the ImageNet dataset.

Update (2021-09-08): thishashcollisionisnotporn.com (via Hacker News):

Given that it’s possible to generate a false positive, it is also possible to deliberately create images that match a given hash. So, for example, someone who wants to get another person in trouble can send them innocent-looking images (like images of kittens) and manipulate those images to match a hash of known CSAM.

This site is a proof of concept for collision attacks. The images of the kittens are manipulated to match the hash of the image of the dog (59a34eabe31910abfb06f308). As a result, all images shown on this page share the same hash. When these images are both hashed with the Apple NeuralHash algorithm, they return the same hash.

15 Comments RSS · Twitter

Apple will probably never be allowed to activate the anti-CSAM system in the EU, e.g. due to GDPR & ePD. But if they are & do, and if at some point they "expand" that system's functionality, or if we hear reports about too many false positives, Manjaro GNOME plus PinePhone or Librem 5 look like nice alternatives to me.

One nit to pick with one of the quotes from Hector Martin:

"Say I am law enforcement and I want access to your photos. I send you >30 messages with non-CSAM but colliding images. Your phone now thinks you have CSAM and grants Apple access to your data."

As I understand the algorithm, the algorithm doesn't grant Apple access to *everything* if there are 30 matches. It only grants Apple access to *those images where the hash matches*.

So if someone managed to successfully pull this stunt, they would only get back their own seed images, which would not be very useful when trying to convince a prosecutor to go to trial.

But this is all moot (at least for now), because iCloud Photos are not encrypted. If law enforcement wants access to all your photos, they just need to get a judge to sign a warrant and Apple will hand them all over.

No need to go through any of this logic until some hypothetical future where iCloud Photos are end-to-end encrypted.

@David Yes, Apple already has the data. I think the idea is that if the reviewer makes a mistake or is secretly working for a government, the stunt might be enough to get a subpoena because an actual report was made to NCMEC. Whereas, before this system, in theory the judge would need to see some actual evidence.

"the idea is that if the reviewer makes a mistake"

I think the idea is that Apple will have OKRs for reviewers telling them to review way more images than they reasonably can, and so it'll end up being essentially random, just like App reviews.

>So if someone managed to successfully pull this stunt, they would only get back their own seed images, which would not be very useful when trying to convince a prosecutor to go to trial.

Planting evidence in order to go to trial is a thing that happens, though.

> A lot rests on how much we can trust Apple’s human reviewers.

Possibly not. You can have the most trustworthy reviewers in the world - but they'll still have to do what the USA government says if they get a warrant or an NSA letter.

And that's before you have to worry about (for example) the Chinese government. Currently Apple aren't rolling this system out in China; But what if China demands that they do roll it out? And then demands that they use the image database provided by the Chinese government? Apple have nowhere to hide - the system is built already.

It’s good to see outside scrutiny of the system. However, some of the reaction is over the top which doesn’t help. For instance the quote from Hector Martin:

"Say I am law enforcement and I want access to your photos. I send you >30 messages with non-CSAM but colliding images. Your phone now thinks you have CSAM and grants Apple access to your data."

Aside from the issue David C. Points out above, Apple is only scanning iCloud Photo Library images. So photos sent to someone in Messages (or WhatsApp, etc) won’t be scanned. I’m not sure there’s a known vector for surreptitiously inserting photos into someone’s iCloud Photo Library. This kind of unrealistic made up scenario detracts from valid criticism of the system.

@Jolin If you AirDrop someone a photo it goes directly into the photo library with no user interaction. There are also probably exploits.

> If you AirDrop someone a photo it goes directly into the photo library with no user interaction.

WhatsApp also has a setting to automatically save received photos to the "camera roll". (I'm not sure iOS itself even uses that term any more.) And, supposedly, that's the default.

Sounds like we'll need more granular permissions on this.

Kevin Schumacher

@Michael Every time I AirDrop a photo to my husband, with us both on each other's contact lists and AirDrop set to Contacts Only, it prompts him every single time to accept. What setting is it that allows AirDrop with zero interaction?

Also what is the default permission for AirDrop, Everyone, Contacts Only, or Off? Because it would have to set to Everyone for this drive-by theory to work, also.

Isn’t there some sort of salt to this hashing? If Apple has a secret salt,

ProfessorPlasma

It seems inevitable that if deployed, some reviewer will illicitly take false positive photos and they will be distributed online. This sort of thing has happened before with “trusted” sources having access to photo libraries, let alone ones which are flagged.

But this whole concept seems a bit out of left field. This has to be related to some other issue, like using third party (e.g., AWS) servers to store data, right? Or a future law that they know is coming? It’s a huge undertaking that pretty obviously flies in the face of privacy, and I have a little bit of a hard time believing that no one in Apple management saw at least part of a backlash coming. Rather, given all of the fires that apple is currently facing why would it potentially light a new one? There must be more to this story, I feel.

Kevin Schumacher

@ProfessorPlasma Given that they apparently aren't currently scanning for it at all, I don't think it's hard to imagine the pressure is simply to be scanning for it in some way. Companies are required to report the discovery of any CSAM. I'm guessing Apple is now getting prodded by somebody (DOJ?) to be more proactive about the discovery of it.

@Kevin Yes, I am seeing that same AirDrop behavior with family members. Oddly, for me it doesn’t prompt when AirDropping a photo to myself, even though it does prompt when AirDropping myself a file. I’ve heard other reports of photos working without a prompt, but I’m not sure what determines that.

@Michael My experience with AirDrop is that it always prompts to accept if you send it to a device not signed into your Apple ID. When AirDropping a file to yourself, I don't think the device is prompting you to accept or not, I think it prompts to ask where you want the file to go since there are usually multiple options. But Photos and URLs that are AirDropped automatically go to Photos or your default browser, so no prompt is displayed.

Leave a Comment