Inverting PhotoDNA

Interesting work. It seems like these lossy photo hashes are more obfuscation and resolution reduction than anything secure.

In the photo of the child, facial features aren't reconstructable. Is it possible that PhotoDNA hashes might be sufficiently potato to not infringe on privacy or meaningfully (if not legally) count as explicit/illicit content?

Are secure lossy photo hashes possible? I feel like it'd require indistinguishability obfuscation (iO), where distinguishing a hash from zillions of random noise preimages would be guaranteed intractable. But I'm not sure if you could guarantee all the preimages matching the hash aren't all still recognizable.

Maybe you could set up some kind of adversarial system using your work as the adversary? (e.g. Set of transformed input images --[hashing neural net]-->hashes, then hashes--[Ribosome]-->preimage, then penalize hashing neural net (and reward Ribosome) based on distance of input image and preimage, along with rewarding the hashing net for distance from its hashes of other images + closeness of its hashes of similar transformed images.)

The reversible restriction is important because otherwise distributing PhotoDNA signatures of CSAM is distributing CSAM.

Yes, that would have made sense, but I was being lazy :)

I also didn't notice this issue until after I had trained the model and tried inverting hashes (didn't want to look through the NSFW dataset myself). And I thought it was amusing to leave it as-is (it demonstrates a point that issues from the dataset can be carried over to the results).

For the "image not available" ones, removing those in an automated way probably would be straightforward (could have used perceptual hashing for this task!).

For removing watermarks, there's some neat work from Dekel et al. in CVPR 2017: https://watermark-cvpr17.github.io/

This is the first paper on the matter. I imagine the techniques will improve.

Hashes aren't strictly reversible, so "reversing" a hash usually means finding data that hashes to a given value. E.g. in the case of PhotoDNA there are 256^144 possible hash values (the hash is 144 bytes long). So you can't avoid collisions in a set with more than 256^144 elements. So recersing PhotoDNA means finding an element that hashes to a given value, but it doesn't mean that that's the image that was hashed to this value that is the real-world source of this hash.

Now as for completely theoretical possibility you can reverse any hash by brute-force. But that may not be computationally feasible. Now let's think what is easier: reversing a hash with few or many collisions? Let's take an edge case: a hash function hashes everything to just one value (not a very good hash function, but bear with me). That will be the easiest hash function to reverse, since any input is a right answer. Now as you reduce the number of collisions, the task becomes harder: you can divide images into disjoint sets such that each of them is defined by the hash value images in this set hash to, so if you have two images, each from distinct set, they hash to distinct values, and if they are in the same set, they hash to the same value. When you reduce the number of collisions the sets get smaller in size, but their amount grows. So for any given hash value which you want to reverse you need to check a bigger number of candidates to figure out which of the sets is the one for the given hash value (one candidate to check from each set). And that's assuming it would be feasible to just keep a list of those sets and their members, which it isn't, but illustrates the correlation. So actually it's easier to reverse when you have more collisions. It's counter-intuitive, because it's a different kind of reversing than what is usually meant by "reversing a function", which requires a function to be injective.

But: with fewer collisions you have higher likelihood that what you got as the result of reversing is what someone else used as input to the hash function (each of the sets is smaller, so with uniform distribution we get 1/n probability, where n is the number of elements in a given set of elements hashing to the same value).

Anyway, the sets I wrote about here are elements of a quotient set defined by the equivalence relation of hashing to the same value. You can read more on Wikipedia, if my description was a bit confusing: <https://en.wikipedia.org/wiki/Equivalence_class#quotient_set>

Exactly. Unlike other hashes, this photoDNA "hash" has to be somewhat of continuous function of its inputs.

Irreversibility is not what defines a general hash function. It’s a critical characteristic for cryptographic hashes, but I serially doubt anyone knowledgeable ever described PhotoDNA as a cryptographic hash function.

Yes and no. If you are thinking about cryptographically-secure hashes, then you're correct. However, not all hashes are intended to be cryptographically secure; this particular kind of hash is called a perceptual hash. Perceptual hashes are specifically intended to be able to identify slightly-modified images; and for that purpose we can't have all of the cryptographic security of, say, SHA-256.

The third type of hashing is the dirt-simple hashing schemes you see used in hash tables; although even there denial-of-service resistance is still a desired property for public-facing web services.

Yea, a "hash" should be maximally non-continuous: Minimal input changes should change the output as much as big input changes.

No, because hash functions are non-continuous, aka they change a lot if the input changes minimally. This is different from imageDNA, which needs to be robust against small changes in input.