After re-reading this document, I think I understand what’s going on. For those who can follow a technical document, I strongly recommend reading it, since there are a lot of important details that I don’t think anyone will be able to summarize accurately (and I’m including myself and this message in that category.
That being said, let me see if I can provide a good-enough summary for everybody else.
Core technologies
These three cryptographic technologies are all used together. Note that they are all used together. Individually, any one could be vulnerable, and I think this has led to a lot of confusion among people discussing the subject.
-
NeuralHash
This is a neural network algorithm designed to generate a hash (a large number) based on an image’s content. The algorithm is designed to minimize the possibility that basic transformations will change the hash. Apple’s example shows an image converted from color to grayscale (color space conversion). It stands to reason that they also trained the neural net to deal with other similarly basic transformations like rotation, reflection and cropping out background.
Apple doesn’t describe all the details in their document, but it must be something they have published because they have said that NCMEC is generating the hashes of the CSAM database images. (Apple isn’t receiving a copy of the images to generate the master database).
-
Private Set Intersection (PSI)
This is a very interesting cryptographic protocol that allows two parties (e.g. you and Apple) to compare data sets without either party knowing what the other has. In this case, Apple has the master set of NeuralHashes for the CSAM data and you have the set of NeuralHashes for all your images, both of which are encrypted. The PSI algorithm allows the server to know where these two sets intersect (that is, which of your images match the CSAM database) without gaining any information about non-intersecting data (any other images you have).
-
Threshold Secret Sharing (TSS)
This is another cryptographic technique that allows a critical secret to be split into many pieces, where someone receiving the data needs a minimum number of pieces in order to reconstruct the secret. For example, you may distribute your secret in 1000 pieces with a threshold of 10. Someone with any 11 pieces can reconstruct the secret, but someone with only 10 can’t.
In this case, your phone is generating a secret encryption key that is split among all your images. Apple needs a minimum number (Craig said 30 in the interview) in order to reconstruct the key
Creating the master CSAM database
Apple receives NeuralHashes from NCMEC (and other related organizations). They perform a number of (unspecified) mathematical transformations, the last of which is a blinding step that is based on a cryptographic secret known only to Apple.
The result of this is that the set of NeuralHashes is transformed into a “blinded hash” database, which is stored on everybody’s phones. The nature of this database is that you can check to see if a given NeuralHash is in it (if you have Apple’s secret key), but you can’t determine which entry in the database actually matches. You can also use it (without Apple’s secret key) to generate encryption keys from NeuralHash values, which will only be valid for NeuralHash values that are in the database.
On-device PSI processing
Note that this is only the PSI part of the on-device processing. Additional processing happens first (see below).
The security voucher’s payload (Neural Hash and other data, see below) is encrypted and wrapped as follows:
- A crypotgraphic header (including a derived encryption key) is computed from the image’s NeuralHash and the local copy of the blinded hash.
- The derived key is used to encrypt the voucher’s payload.
- If there was a database match, then server can use the cryptographic header and the server-side secret to compute the derived encryption key and decrypt the payload.
- If there was not a database match, then bogus key data will be generated. The server won’t be able to decrypt the payload (so Apple learns nothing about non-matching images)
- The device doesn’t know if the image matches or not. It just gets an encryption key from the blinded hash.
The server attempts to compute the decryption key using the cryptographic header in the voucher and the server-side blinding secret key. If the image matches something in the master database, the decryption succeeds and the payload is visible. If the image is not in the database, the decryption fails and the payload remains opaque.
Voucher generation
If only PSI was used, Apple could immediately detect even a single matching image, but they chose to limit the system to only allow Apple to do anything when a threshold (30, according to the interview) of matches is received.
This is done by using TSS on the payload before passing it to the PSI processing layer.
- A per-device encryption key (unknown to Apple) is generated, one per device.
- The payload starts as the image’s NeuralHash and a “visual derivative”.
They don’t say what this derivative is, but I assume it’s some kind of low-resolution small-size version of the original image, so humans can review it without seeing the original image. - The payload is encrypted with the per-device encryption key
- A cryptographic header containing a piece of the per-device key (according to the TSS algorithm) is also stored in the payload. So Apple can’t decrypt the payload from just one image - they need 30 or more in order to reconstruct the key.
- This payload is then passed to the PSI algorithm to create the security voucher, which is uploaded to iCloud.
The full set of server-side processing
- Apple receives the security voucher along with the image.
- The PSI algorithm is used to try and decrypt the security voucher.
- If decryption fails, then the image is not in the CSAM database, Apple can’t view the contents of the security voucher and processing stops.
- If decryption succeeds, then the image is in the CSAM database, but the payload is further encrypted by the TSS algorithm.
- If Apple receives more than a threshold number of matching images (30), then it can use the full set of the (PSI-decrypted) voucher payloads to derive the per-device encryption key used to create those payloads. It can then decrypt them all, revealing the original NeuralHashes and the visual derivative images, which Apple people can review before referring the account to law enforcement.
- If Apple receives fewer than the threshold number of matching images, then the TSS algorithm can’t reconstruct the per-device key and Apple can’t view the payloads.
Synthetic vouchers
So far, although Apple can’t view the hashes until a threshold of matches has been received, they could still know how many matches there are, which could still be problematic. It might even be worse to have a report that there are (for example) 5 matches, but no ability to check whether they are true or false positives.
To deal with this, your device also occasionally produces synthetic vouchers for images (instead of ones that correspond to the image). A synthetic voucher:
- Uses dummy data for the underlying image information
- The secret share of the inner key (for the TSS algorithm) is replaced with random data
- The cryptographic header and outer encryption key are chosen so they always make a PSI match on the server.
The percentage of synthetic vouchers generated is designed to match the same order of magnitude as the TSS threshold number.
So, everybody with a non-trivial number of images will have at least 30 PSI matches on the database, but the TSS layer can’t be decrypted using data from synthetic vouchers because the key fragments are random data.
If the TSS decryption succeeds, then we know that at least 30 of the images are real (not synthetic) matches, because it was able to reconstruct the device key. Then Apple can review the payloads and take action.
In other words, Apple knows absolutely nothing about whether you have CSAM data or not until 30 or more matching images have been uploaded, but once that threshold is crossed, they can immediately identify them all for manual review (but still without having any ability to access non-matching images).
It’s a really slick algorithm. I’m quite impressed.