Inverting PhotoDNA (2021)(anishathalye.com)
anishathalye.com
Inverting PhotoDNA (2021)
https://anishathalye.com/inverting-photodna/
23 comments
Does there exist some kind of hash that preserves some notion of distance but which prevents recovery of the original data?
So f(X) is close to f(Y) if X and Y are themselves close, but without telling you about X or Y. Is that mathematically impossible?
So f(X) is close to f(Y) if X and Y are themselves close, but without telling you about X or Y. Is that mathematically impossible?
Yes that is possible. Fully holomorphic encryption schemes allow functions to be evaluated on encrypted data without deciphering the data at any point, for example. The problem is that these techniques are very slow, which limits their practical use.
[deleted]
The problem is that then the distance is also encrypted, which doesn't work here.
> Does there exist some kind of hash that preserves some notion of distance but which prevents recovery of the original data?
I don't think that's possible. If you can hash a test image, and you can evaluate its "distance" from other images, an attacker can use that distance as a metric for a hill-climbing or simulated annealing algorithm.
I don't think that's possible. If you can hash a test image, and you can evaluate its "distance" from other images, an attacker can use that distance as a metric for a hill-climbing or simulated annealing algorithm.
What you say is true for one-way hashes, a.k.a. "secure" hashes.
Hashing functions in general only reduce a long variable-length input string to a short fixed-length output, while preserving as much information as possible within these constraints, so that input strings that differ in some manner that is considered important for the intended application are hashed into distinct values.
So if one wants a non-secure hash that preserves some kind of distance defined on the input strings, that is possible in many cases.
https://en.wikipedia.org/wiki/Perceptual_hashing
Non-secure hashes are not useful for detecting data modifications, but they are useful for searching through large amounts of data, especially when the search is not only for identity, when secure hashes can also be used, but also for similarity, when secure hashes are useless.
Hashing functions in general only reduce a long variable-length input string to a short fixed-length output, while preserving as much information as possible within these constraints, so that input strings that differ in some manner that is considered important for the intended application are hashed into distinct values.
So if one wants a non-secure hash that preserves some kind of distance defined on the input strings, that is possible in many cases.
https://en.wikipedia.org/wiki/Perceptual_hashing
Non-secure hashes are not useful for detecting data modifications, but they are useful for searching through large amounts of data, especially when the search is not only for identity, when secure hashes can also be used, but also for similarity, when secure hashes are useless.
The result here seems pretty lackluster tbh. Like maybe you get a blur of colour in the same place as the original.
I wonder if Apple had some understanding of these advancements in inverting image hashes when they decided to drop their on-device image scanning plans.
They got push back from the "screeching" minority [1] about their needless and wanton surveillance.
[1] https://www.howtogeek.com/746588/apple-discusses-screeching-...
[1] https://www.howtogeek.com/746588/apple-discusses-screeching-...
That screeching minority needs to become a belligerently agitated majority...
... in a more perfect world maybe.
... in a more perfect world maybe.
What Apple forgot to market was the fact that it was only scanning photos that were destined for upload to iCloud Photos, which most people turn off because they don't want to pay more than $1/month for iCloud storage (or $4 if you happen to have a family).
Thankfully, they went forward with "encrypt everything in iCloud E2E"[0] despite not having a way to detect CSAM anymore, probably much to law enforcement's chagrin.
0: https://support.apple.com/en-us/108756
Thankfully, they went forward with "encrypt everything in iCloud E2E"[0] despite not having a way to detect CSAM anymore, probably much to law enforcement's chagrin.
0: https://support.apple.com/en-us/108756
> probably much to law enforcement's chagrin.
It's 2024, we have to stop playing pretend. Apple can't even keep your push notifications to themselves, I'm not convinced they do anything "to law enforcement's chagrin" nowadays. Every sufficiently large American business is partially controlled by American intelligence; FAANG is part of that, whether you love them or not.
It's 2024, we have to stop playing pretend. Apple can't even keep your push notifications to themselves, I'm not convinced they do anything "to law enforcement's chagrin" nowadays. Every sufficiently large American business is partially controlled by American intelligence; FAANG is part of that, whether you love them or not.
I would not call those blurry thumbnail size images as reconstructions of the original image. Sure you can figure out what pose the person was in but you won’t see any detailed content and you won’t be able to identify the person.
No one claimed it was not lossy. The alarnm is you're not supposed to be able to get anything and this is definitely something, and will probably get better still, just like they already have some better than other results for the same image.
It's worth noting that even if PhotoDNA didn't do any extra obfuscation, 144 bytes of grayscale isn't a lot to work with. If we assume each pixel takes up half a byte that's barely a 17x17 image.
raw grayscale downscaling is not the best possible lossy image compression
i have a high-quality 1280×720 color jpeg of macaulay culkin here which is 99191 bytes; that's 0.86 bits per pixel. recompressing it with the gimp with quality set to 15%, 4:2:0 subsampling, arithmetic coding, no color profile, and no progressive reduces it to 13269 bytes, the only visible effect being a subtle posterized blockiness in low-contrast areas of the photo; subtle details of the facial expression and hair texture survive. that's 0.115 bits per pixel
the same compression ratio at 144 bytes would be a 100×100 full-color image. jpeg can't compress small images that well, but plausibly something could
i have a high-quality 1280×720 color jpeg of macaulay culkin here which is 99191 bytes; that's 0.86 bits per pixel. recompressing it with the gimp with quality set to 15%, 4:2:0 subsampling, arithmetic coding, no color profile, and no progressive reduces it to 13269 bytes, the only visible effect being a subtle posterized blockiness in low-contrast areas of the photo; subtle details of the facial expression and hair texture survive. that's 0.115 bits per pixel
the same compression ratio at 144 bytes would be a 100×100 full-color image. jpeg can't compress small images that well, but plausibly something could
The compression ratio depends on the entropy of the image more than anything else.
Chroma subsampling isn't the reason for low bitrates - by your own logic, grayscale would be smaller since it's effectively removing any chroma information.
What gets you from 24 bpp to 0.12 bpp is primarily the arithmetic coder and that only depends on entropy. Just for shits and giggles I took two images (resized and cropped to 1280x720) and saved them as jpeg (15%, 4:2:0).
The high entropy image (a garden with lots of flowers [1]) resulted in 83.476 bytes. The low entropy image (a stylised drawing of hills with a sunrise [2]) resulted in 22.299 bytes using the same settings.
To further confirm the hypothesis, I applied a size 4 average blur to the low entropy image to further reduce details and saved it using the same settings. The result was a 19.104 bytes file. Doing the same to the high entropy image resulted in a 34.646 bytes file - a whopping 60% reduction in size by just reducing the entropy.
This shows that reducing entropy is the significant factor here, not colour. It also means that you can get some 100x100 images to compress down to 144 bytes, but for most that simply doesn't apply.
Chroma subsampling isn't the reason for low bitrates - by your own logic, grayscale would be smaller since it's effectively removing any chroma information.
What gets you from 24 bpp to 0.12 bpp is primarily the arithmetic coder and that only depends on entropy. Just for shits and giggles I took two images (resized and cropped to 1280x720) and saved them as jpeg (15%, 4:2:0).
The high entropy image (a garden with lots of flowers [1]) resulted in 83.476 bytes. The low entropy image (a stylised drawing of hills with a sunrise [2]) resulted in 22.299 bytes using the same settings.
To further confirm the hypothesis, I applied a size 4 average blur to the low entropy image to further reduce details and saved it using the same settings. The result was a 19.104 bytes file. Doing the same to the high entropy image resulted in a 34.646 bytes file - a whopping 60% reduction in size by just reducing the entropy.
This shows that reducing entropy is the significant factor here, not colour. It also means that you can get some 100x100 images to compress down to 144 bytes, but for most that simply doesn't apply.
[1] https://images.hdqwalls.com/wallpapers/sunrise-landscape-minimalism-5k-ex.jpg
[2] https://homesfeed.com/wp-content/uploads/2015/08/wonderful-landscaping-ideas-for-front-of-house-and-backyard-with-cool-walkways-and-colorful-flower-plants-and-trees.jpg>Neither details of the PhotoDNA algorithm nor an implementation is officially available to the public, but the algorithm has been reverse-engineered based on public documents
Sounds totally trustworthy
Sounds totally trustworthy
If we assumed this algorithm extracts all of the information from the hash, PhotoDNA would have many false positives given how poor the reconstructions are, correct?
PhotoDNA is officially non-invertible, because it’s used for CSAM, and if you can invert it, then anyone having the hashes also has CSAM.
Inverting PhotoDNA - https://news.ycombinator.com/item?id=29626911 - Dec 2021 (25 comments)