More specifically known as the ftPSI-AD ( fuzzy threshold Private Set Intersection with Associated Data ) protocol.
EDIT 2021/09/04: Apparently as I was procrastinating writing this article Apple has agreed to postpone the roll out of the system.
EDIT 2023/09/20: I procrastinated long enough to for the whole thing to have been scrapped. https://appleinsider.com/articles/23/08/31/apple-provides-detailed-reasoning-behind-abandoning-iphone-csam-detection
Disclaimer: As the title suggests, this is not a cryptanalysis of the Apple CSAM cryptography. I’m not a cryptographer nor a cryptanalyst.
In fact I have very little formal training in cryptography and cryptographic techniques – about as much as you’d expect from someone who has struggled with enterprise PKI’s, has done some professional penetration testing and has tried but failed to complete Cryptography I by Dan Boneh (it’s good, check it out).
This is nothing more than my layman’s understanding and subsequent explanation of what I’ve managed to gleam from official and unofficial documentation (all sources cited).
The term “crypto” where used in this article shall exclusively be used to refer to the original meaning: Cryptography -_-
Why is this even a “thing”?
For all of the controversy and hoo-ha surrounding the Apple CSAM scanning announcement, I have yet to see a basic explainer about how the privacy preserving crypto magic actually works. To be honest, I didn’t even think about the complexities of building such a system until my brother linked me to the following tweet.
“LOL”, I acknowledged, “quite an insightful sh**post…how would all this work though?”
Like millions of technology users every day I ignorantly glazed over the detail without giving the technology in question a second thought.
Ignoring the semantics of the wording used in the tweet for a second – it is a completely valid question. How will Apple allow certain images to be “decrypted” while preserving privacy and security of other user content?
Sidebar: For those of you who at this point look at this and think: “The fact that its encrypted implies that it can be decrypted – what’s the big deal?” don’t despair. The author of the tweet assumes you share their understanding of the expected privacy and security controls built into your iPhone and connected services. Let me try and explain.
The assumption here is that the images you store on your iCloud account are encrypted in such a way that Apple, despite being in possession of all of these images, cannot actually see their contents as they are encrypted on-device with keys that are private to that device and/or account (I’m not sure that is actually true and that Apple ever provided that guarantee, but that seems to be the assumption is this tweet.) Here is a thread that speculates on the topic: https://news.ycombinator.com/item?id=28300035
To paraphrase: “You can’t claim my stuff is private and encrypted… until it’s not. If you can decrypt it at any point without my input or consent it means it was never properly encrypted and under my exclusive control in the first place”.
In fact, the core issue is nicely summarised in the first sentence of this paper published by Apple:
The Apple PSI system solves a very challenging problem of detecting photos with CSAM content while keeping the contents of all non-CSAM photos encrypted and private.
My initial response to my brother was a wild guess that basically boiled down to this:
“There is not a lot of detail here and we’ll have to take the statements at face value, but there are fancy crypto-magic ways of encrypting things where more than one key can decrypt it.
I suppose there is a machine learning algorithm running on the phone that classifies these images where they are necessarily in plaintext (or a decrypted state), flags them based on some fancy heuristics and then encrypts it (a copy or the same one) under another key which Apple controls and can simply decrypt server side”
Oh, was I wrong – it’s way more involved and so much cooler than I could have even imagined. Apple really did go out of their way to try and preserve user privacy. Unfortunately, it’s not a perfect system – none are – but more on this later.
This is a good time to note that I’m going to steer clear of commenting on any non-technical aspects of the system.
The ethics and morals of such a system including the “slippery slope” argument has been discussed ad-nauseam (for all the right reasons).
I do not feel I can meaningfully contribute to that discussion any further, nor do I want to in this article. I want to maintain an unsoiled and pure focus on the cool tech by putting on the blinders of moral ignorance. These blinders are temporary though and no technology with such potential impact can be appreciated in isolation only – as much as we’d like to ignore it – there is an inherent link between cool technology with the power to impact society and our moral obligation to ensure it’s the right thing to do when abuse of it possible.
Usually at this point (at the time of writing) I’d go searching for clarity, but was quite disappointed when I couldn’t find anything (at least not anything a mere mortal like me could understand). My usual resource for giving eloquent, if a bit contrived, explanations of complex systems @sggrc was also, unfortunately, silent on the matter. To his credit he did mention in Episode 831 of Security Now that this is potentially an area he’d dive into later – at the time of writing this post however I’ve not seen such a deep dive yet.
So, my deep dive started…
Some preamble
For the avoidance of doubt this post looks exclusively at the crypto that underlies the CSAM detection system (ftPSI-AD) and does not at all touch on any component of the Communication Safety, an on-device feature designed to warn children when they send or receive sexually explicit content over Messages and AirDrop, system announced at the same time which seems to have caused confusion in some circles.
My primary source of information for this article is the the this technical overview released by Apple
But I also heavily relied on this, this, this and this analysis by Sarah Jamie Lewis over at openprivacy.ca to clarify some things that the technical analysis glazes over.
Finally, I also referred to this, this, this and this (Threat Model) paper published by Apple for some clarification and cross validation.
Although this system is notorious for “client side scanning” – the source of much controversy – it is actually quite dependent on server side operations as well. Some components and processes run only on the client and some others only on the server. This separation of concerns is quite intentional and significant to the design of the overall system. If either the client or the server don’t do their bit (intentionally or accidentally) the whole system breaks down. I note this because the interdependency of the client and server (and their associated workloads) should be kept in the back of your mind as you proceed to read this article.
Why is this post even needed?
As I was working through the Apple Technical Overview document, all too often I found myself exclaiming:”But why…?” or “But how…?”.
Respectively these questions can be translated to the following root causes:
- “But why…!?” = “Why are you doing this thing?” or “Why are you doing it in this way?” – Generally this indicated that I was missing or misunderstood a key piece of context from the threat model.
- “But how….!?” = “How is this possible?” or “How does this even work?” – Generally this indicated that I had lack of knowledge or misunderstood something fundamental about the underlying technology (mostly the cryptography)
In following sections I’ll go component by component and break down how each works in much the same structure as the Technical Overview document , the difference being I’ll try and explain things in more detail where the authors assumed the reader had knowledge of the threat model or where they elided some technical detail for the sake of brevity as it relates to the cryptography.
I’m hoping this extra context and “simplifying” of the problem will help others like myself understand a bit more about the system. Let’s start right at the beginning…
NeuralHash
Can’t talk about a NeuralHash without first understating what a bog standard hash is. I suppose technically it’s called a cryptographic hash function and the good ones have a few key properties we should quickly touch on for context:
Skip over the this section to “So what is a NeuralHash?” if you know your SHA’s from your MD’s
- They are deterministic functions (The same input results in the same output – always)
- They are inherently information lossy (The output is of a static length regardless of the input which also implies that the output cannot be reversed to derive the original input)
- They are collision resistant (The probability of 2 or more different inputs generating the same output should be statistically negligible) Really depends on the use case.
- They are sensitive/fragile (Even a seemingly insignificant change in the input should result in a significant difference in the output) – technically this last one is just an extension of the 1st and 3rd points but it’s worth while calling it out.
If you consider these properties it is easy to see why these are often referred to as signatures or fingerprints. They become a unique representation of the input without disclosing the what that input was.
So why hashes in the first place? As noted above the “fingerprint-ness” makes these things a great mechanism to accurately compare two things without actually knowing the exact properties of each. As an analogy we can use human fingerprints – given that you have two fingerprints lifted from different places ( and we assume that no two humans have the same fingerprints) we can compare the fingerprint to see if they match and reasonably assume that the same person made those without knowing anything else about the person (their name, height, eye color, interests etc.).
This then is the key use case for cryptographic hashes and the reason they are the de facto solution for storing passwords where, for instance, a service provider needs to know that you provided the correct password at login without actually getting to see or store your password.
Is the NeuralHash a cryptographic hash then? Well…No. It seems that NeuralHash shares only a single property with a cryptographic hash in that it is inherently information lossy – the input gets reduced to a fixed length output.
A NeuralHash is a lot more “fuzzy” and is actually referred to as a fuzzy hash since the algorithm is not strictly deterministic. Two different inputs can, and importantly should by design, be able to produce the same semantic outcome. There are not a lot of details on the inner workings of NeuralHash at the moment (it’s a bit of a black box) but some researchers have already reverse engineered the algorithm and managed to produce hash collisions ( 1st pre-image and 2nd pre-image collisions) which essentially means that someone can artificially produce images of their choosing that match the NeuralHash of a different known image. Basically like saying you can choose your own fingerprints to match that of a specific target.
NeuralHash, by design, is a type of perceptual hash and the fuzzy-ness of it is inherent in the name. As long as the images are perceptually the same they should produce the same NeuralHash (fingerprint). This is a key design property because the use case here is to not have minor image changes (for instance changing the color of a single pixel, or even the color grading of the entire image) to result in a mismatch since this would make it trivial to hide CSAM from detection.
Apple illustrates this intent quite clearly in their Technical Overview
If you were to generate a cryptographic hash over those 3 images, all of the fingerprints would be vastly different.
This fuzzy-ness is the solution, but also introduces a new problem – it’s fuzzy – and things that are semantically different can be detected as being the same image. For more on these issues please refer to the following two great articles which give a more detailed overview of the issue with perceptual hashes in this context:
The Problem With Perceptual Hashes
NeuralHash, Semantics, Collisions and You (or When is a Cat a Dog?)
Next we move on to the…
Blinded Hashes Database
So what’s the deal with the “Blinded Hashes Database”? Why go through all that cryptographic acrobatics instead of just, you know, distributing irreversible hashes?
Let’s back up a bit. The whole point here is to figure out if someone’s trying to upload known CSAM to iCloud without actually looking at their photos because, obviously, privacy matters. Also, Apple does not want to distribute CSAM or NeuralHashes of CSAM images that may leak the presence of a particular image(s) in the database (even if someone had a similar image).
The Blinded Hashed Database therefore is database of NeuralHashes of known CSAM images. These hashes are generated from CSAM images that child safety organisations (like NCMEC in the U.S.) already know about. The key thing is that Apple doesn’t create this database themselves, because they’re not allowed to have those images in the first place. Instead, they rely on trusted child safety orgs in different countries to send in their image fingerprints. Apple only keeps the ones that show up in at least two different countries’ lists, just to make sure nobody’s slipping in something shady.
But here’s the clever bit: before sending this hash database to user devices, Apple “blinds” it using cryptographic techniques. The blinding process is not encryption in the traditional sense, but it does cryptographically obscure the CSAM hashes using elliptic-curve scalar multiplication with a secret known only to Apple. This provides a one-way transformation that behaves like encryption for privacy purposes, but without a reversible decryption step.
This is due to the Elliptic Curve Discrete Logarithm Problem (ECDLP), which underpins the security of elliptic-curve cryptography.
So now we have a collection of visual derivatives or verified CSAM images that a recipient cannot reverse or derive the original image of (even if in possession of similar images). Cool, so this means, based on a comparison (more on that shortly), your phone might generate a match but still doesn’t know what matched or why.
Which segues nicely into…
Private Set Intersection (PSI)
The NeuralHash (more specifically the comparison of 2 NeuralHashes) is the determinant of A_i_==B_i_. If the result of the NeuralHash function (fNH) calculated over an image from A_i_ and an Image from B_i_ are the same (fNH(A_i_) == fNH(B_i_)) then these two images are considered a perceptual match.
The Private Set Intersection (PSI) scheme is at the core of the privacy “preservy-ness” of the proposed system. It is the mechanism by which Apple can ensure they learn as little as technically necessary about user content (given the requirement to monitor for CSAM and having to see some content) and nothing more. This serves to protect both the user and thier privacy and gives Apple a convenient claim to ignorance – “Sorry we can’t give you these user images, FBI. We can’t decrypt them”.
It’s not entirely clear why this is necessary since it does not seem that Apple is actually doing end-to-end encryption (E2EE) of images stored on iCloud. This means that as cool and novel as the PSI mechanism is, it seems…well….redundant. If there is no E2EE, Apple can potentially see all images uploaded to iCloud – it does not make sense that they would introduce a convoluted privacy mechanism that is immediately undermined by their lack of E2EE. The only reasonable assumption one can draw from this is that there are potential future plans to have E2EE on iCloud – but if that is the case Apple is suspiciously silent about such plans.
How is this achieved?
Lets’s break down my ugly picture step-by-step to make life a little easier.
Client-side (User’s Device)
- Receive blinded CSAM hash database
- The device receives a blinded (cryptographically transformed) hash table of known CSAM NeuralHashes. These hashes are derived from perceptual hashes (NeuralHashes) submitted by at least two independent child safety organizations from different jurisdictions. The hashes are blinded using elliptic-curve cryptography and inserted at deterministic positions in the table based on the original (unblinded) hash.
- User selects or uploads a photo
- When a user takes or uploads a photo to iCloud Photos, the device computes a NeuralHash and a visual derivative (a privacy-preserving low-resolution version of the image).
- Perform PSI protocol lookup
- The NeuralHash is used to determine a deterministic position in the blinded hash table. The device fetches the blinded CSAM hash at that position but cannot interpret or unblind it. Using this data and the NeuralHash, it computes a cryptographic header.
- Build safety voucher
- The device creates a two-layer encrypted safety voucher:
- The inner layer encrypts the NeuralHash and visual derivative using a secret key known only to the device.
- The outer layer includes a secret share of the inner key and encrypts both this share and the encrypted image data using a derived key computed from the blinded hash and cryptographic header.
- This process ensures that only if the NeuralHash matches an entry in the CSAM hash database will the server later be able to decrypt the outer layer.
- Add synthetic vouchers (more on this later)
- The device may generate synthetic match vouchers (fake matches) that resemble real ones and register as matches on the server. These are indistinguishable from real matches and serve to obscure the actual number of matches before the threshold is reached.
- Upload to iCloud
- The photo and its associated safety voucher are uploaded to Apple’s iCloud Photos service.
Server-side (Apple iCloud)
- Receive safety vouchers
- The server receives and stores the images and their safety vouchers. It does not know which are real matches or synthetic matches and cannot decrypt any part of the voucher at this stage.
- Attempt PSI-based outer decryption
- Using the cryptographic header from each voucher and its own blinding secret, the server tries to decrypt the outer layer of the voucher. If the voucher corresponds to a real match (i.e. the image is known CSAM), the decryption reveals the secret share and the encrypted inner layer (NeuralHash and visual derivative). For non-matches, decryption fails, revealing nothing.
- Check match threshold (more on this later)
- If the number of successful outer decryptions (i.e. CSAM matches) reaches or exceeds the predefined threshold (e.g. 30), the server uses the collected secret shares to reconstruct the inner encryption key.
- Decrypt inner layer
- The reconstructed key is used to decrypt the inner layer of each matched safety voucher, revealing the NeuralHash and visual derivative for matched images.
- Run secondary hash verification
- The server may apply a second, independent perceptual hash to reduce the possibility of false positives caused by adversarial manipulation.
- Human review
- Visual derivatives of matching images are reviewed by trained Apple personnel. If the images are confirmed to be CSAM, Apple disables the user’s account and files a report with an appropriate child protection organization (e.g. NCMEC in the United States).
- If threshold is not met
- The server cannot reconstruct the decryption key, and the safety vouchers remain encrypted. Apple gains no knowledge of whether any images matched or how many were close.
I hope the text was slightly more understandable than my scribbles. Let’s more on…
Threshold Secret Sharing
To me the concept, in principle, was easy to grok but the practical implementation a complete mystery and the Technical Overview did not do much to explain any of the cryptography that underlies this mechanism. Other documents did, but it was nothing that could be interpreted and understood by a mere mortal like me.
This was probably one of my biggest “But HOW!!!!?” moments.
Back to the basic concept: Given an aggregate number of thing X above a threshold t, you are enabled to reach outcome O by combining X1, X2,… Xt+1. Or more concretely: Given I have 7 (t) little rocks (X), I can combine them in a novel way construct a larger “rock” with enough mass to be thrown straight through a Cybertruck’s “bulletproof” window (O).
In the case of the Apple Threshold Secret Sharing construct, that translates to: Given I have 30 (t) or more secret shards(X), I’m able to find a secret that allows me to derive a key that enables me to decrypt a subset of identified cipher texts (photo visual derivatives) (O)
Simple right?
Well no. Because if you have a dangerous level (or only a little bit) of knowledge about cryptography like I do, you’ll immediately recognise that it is never sufficient to have part of a key (symmetric or not) to enable the decryption of a cipher text e.g. Even if you have 95% of the key material of an RSA private key, that does not allow you to decrypt a cipher text encrypted under the associated public key. You need the whole thing or bust. Similarly for symmetric keys used for AES for instance, it’s never enough to have only part of a key.
Acknowledged that given one has a significant portion of a key it’s technically feasible to brute force the rest of the key, but that is not the argument and Apple is not brute forcing parts of keys to decrypt cipher texts.
This then bring us to the next logical question. Assuming the most basic setup where we have an AES symmetric key that is split up into Y number of secret shards and randomly distributed amongst image safety vouchers, how likely is it to have received the correct t+1 distinct secret shards (to be able to reconstruct the full AES symmetric key) given a random distribution of t+1 matched images? Without doing the math I can tell you that it’s very unlikely and clearly not how this system would function.
The answer then was so much more fulfilling when I finally managed to track it down. It’s called
Shamir Secret Sharing and the mathematical construct that allows it is called Polynomial Interpolation and was already proposed in 1979 by none other than Mr. A. Shamir himself.
I’m not a position to explain the algebra (with any conviciton) behind this all but Mr. Shamir is, so for those of you so inclined:
I found this article very helpful, not only to understand the problem space, but also the evolution of the potential solution with a nice example of Polynomial Interpolation.
Finally, you can try it out in practice in your browser here (super cool) – this site also links other very cool resources and videos (source of the image above).
We’ll leave it at that then – there is a way to shard secrets in such a way that only a defined subset of shards are required to reconstruct the secret (the key) required to perform decryption.
I’m suer Voldemort is also a fan of Secret Sharding.
So why did Apple bother with this mechanism?
The simplest explanation is that they expect some false positive matches to occur using NeuralHash (as discussed above) and by having a threshold in place they can protect themselves (or whomever they contract to manually validate matches) from arbitrarily gaining the ability to decrypt the images that result from singular false positive matches.
They seem to the make the assumption that an amount of matches above 30 (see their justification for the number here) made up of all false positives is statistically unlikely to occur. This inherently also means that they deem a number of matches below 30 as being not significant, in terms of detection capability.
In summary, this means that Apple will only ever be able to reconstruct a key to be able to decrypt safety vouchers that accompany uploaded images if a total of 30 or more images were matches (false positive or not). Additionally, when the protocol accumulates enough secret shards to derive the key, that key will only enable them to decrypt matched images and nothing more – it is not a “skeleton key” for all things uploaded.
Since writing this I’ve used Shamir Secret Sharing (or Secret Sharding as the cool kids know it) to distribute the master password to my password vault amongst confidants in case something happens to me and my family requires access to all my stuff.
Synthetic Matches/Vouchers
Synthetic Matches are just that – artificially generated Safety Vouchers that are designed to look like legitimate matches against the Blinded Hashes Database to a casual observer on the client or the server.
Notably, the Safety Vouchers associated with Synthetic Matches are empty and without substance. For instance they do not contain valuable Secret Shards nor any actual image metadata or Visual Derivatives.
In the paper Apple goes to some lengths to explain that all devices/accounts will generate a number of Synthetic Matches regardless of any actual CSAM being present on the device, but never makes an effort to explain why. Why would their protocol include a mechanism to create a bunch of noisy junk that muddies the water for both the client and server and wastes valuable CPU cycles?
Because exactly that!
When looking closer at the Threat Model it becomes clear that the intent here is exactly to muddy the water and hide the number of actual matches from casual observers. This serves to protect both the client and server form leaking important metadata via. a side channel.
Remember, any signal in a completely silent environment is significant.
The problem they are trying to engineer around here, in principle, is the same as that of early TOR adoption. If only a few privacy conscious people use TOR, their unique traffic patterns stand out like sore thumb in an ecosystem of non-TOR traffic and their privacy objectives are inherently defeated. To be able to hide something distinct you need some similar looking noise to surround it.
In this case however the objective is twofold:
- Prevent the client from knowing how many actual matches are detected on the device
- Prevent the server from disclosing metadata about accounts that have had CSAM detected.
Why 1?
Quite correctly the Threat Model considers an adversarial client (a baddy with an iPhone) who has an incentive to hide CSAM from detection. If such a client were able to observe the number of true positive matches accurately it leaks important metadata to them that would allow them to essentially test CSAM images against the protocol to find ones that evade detection.
Why 2?
The premise here is that a malicious observer of the Apple services (rouge employees, local or foreign governments, auditors, nationstate hackers) who may be able to see nothing more than an accurate number of matches(since the images are encrypted) can learn important and compromising information about that account (that is has CSAM). In the wrong hands that single data point can be used to target and black mail individuals. This is exacerbated by the fact that there is a very real possibility of false positive matches being perceived as true positives and that may mean that even people with no actual CSAM may become the target of malicious actors or authoritarian governments.
Further reading: Sarah makes a compelling argument for why the noise generated by Synthetic Matches is inadequate to achieve the stated privacy objectives in Obfuscated Apples
So, there you have it. Simple, right?
Putting it all together
“Now draw me a picture, please!”.
Sure, here you go:
Final Thoughts
After writing the bulk of the article I came across this podcast where famous cryptographer Matthew Greene discusses this system with the hosts. It helped understand a bit more about the technical and non-technical problems with this system, the issues with roll out approach, and the efficacy of addressing the actual problem (preventing CSAM distribution).
Some of these points we’ve already touched on in the article, but for clarity here is a summary of valid critiques (ones I agree with) of Apple’s CSAM system?
- It’s wildly over-engineered—for the wrong thing.
Why build this complex, privacy-preserving, cryptographic monster right now if iCloud Photos isn’t even end-to-end encrypted yet? If Apple can already see your photos on the server, why not scan them there like everyone else does (I’m not endorsing that idea btw.)? Instead, they built an entire client-side detection system that makes sense only if they plan to end-to-end encrypt iCloud in the future. But they didn’t say that. So… why the extra fuss?
- It only catches known CSAM images, and misses new abuse.
This system only detects images that are already in the CSAM database. So if someone is creating new CSAM images, this system won’t catch them. It’s blind to anything not already tagged. Worse, you need 30 hits on known images before Apple takes action. So someone with one or two matches can just slip through.
- It’s high risk, low reward.
Green’s take is blunt: “This system does very little to stop real abuse but introduces a huge amount of complexity and potential for misuse.” He says it’s the worst of both worlds:
Very narrow detection (only known CSAM, only if you upload to iCloud), Massive surface area for abuse (runs on every iOS device with iCloud Photos).
Here, I drew an un-magic quadrant for reference:
4. NeuralHash? Kinda sketchy.
Matt and others tore into Apple’s NeuralHash algorithm. They found it: Poorly documented Easy to reverse engineer Vulnerable to adversarial collisions (you can tweak an image and make it falsely match something else) So, he’s not thrilled about this thing sitting on every device and scanning everything before upload.
- The system is ripe for mission creep.
Once this infrastructure is deployed on billions of devices, what’s stopping a government from saying, “Cool, now let’s scan for banned political memes”?
Matt doesn’t buy Apple’s “we’ll never allow that” promise. He points out that Apple has already made concessions to governments (e.g., China), so what’s to say they won’t again?
- Apple dumped too much, too fast, with too little explanation.
Super detailed docs about some parts (like PSI), and Nothing at all about others (like NeuralHash internals). He said it felt “improvisational,” like Apple was scrambling to address criticism instead of transparently explaining the system from the start.
- Why not start small?
If Apple really cared about protecting kids, they could’ve started with: Better iMessage reporting tools, Scanning shared albums only (like other platforms), Watching metadata patterns to catch coordinated abuse. Instead, they pushed a giant surveillance system onto every photo upload.
- This feels driven by government pressure.
Governments (like the U.S., UK) were pressuring companies to “do something” about CSAM. Apple jumped the gun. In Matt’s words, “Snapchat should’ve been the first to fold, but Apple got there first.”
He’s convinced this system was built not just to fight CSAM—but also to preempt looming regulation. I tend to agree.
Anyway, even though this was a complete dud from Apple’s perspective I got to learn soooo much about Privacy Preserving Crypto. Nice!