5 ms·

Inverting PhotoDNA (2021)

76 points by jxmorris12 3y ago

bawolff 3y ago
The result here seems pretty lackluster tbh. Like maybe you get a blur of colour in the same place as the original.
DJPocari 3y ago
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.
- echelon 3y ago
  They got push back from the "screeching" minority [1] about their needless and wanton surveillance. [1] https://www.howtogeek.com/746588/apple-discusses-screeching-voices-of-the-minority-in-internal-memos/ https://www.howtogeek.com/746588/apple-discusses-screeching-...
  - rustcleaner 3y ago
    That screeching minority needs to become a belligerently agitated majority... ... in a more perfect world maybe.
    - judge2020 3y ago
      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 https://support.apple.com/en-us/108756
      - smoldesu 3y ago
        > 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.
changoplatanero 3y ago
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.
- Brian_K_White 3y ago
  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.
KTibow 3y ago
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.
- kragen 3y ago
  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
  - qayxc 3y ago
    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. [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
cf1241290841 3y ago
>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
dr_kiszonka 3y ago
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?
chipsa 3y ago
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.
chpatrick 3y ago
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?
- qayxc 3y ago
  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 3y ago
    [deleted]
  - chpatrick 3y ago
    The problem is that then the distance is also encrypted, which doesn't work here.
- duskwuff 3y ago
  > 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.
  - adrian_b 3y ago
    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 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.
programjames 3y ago
It'd be interesting to see a diffusion model for this.
- 127361 3y ago
  Well said.
dang 3y ago
Discussed at the time: Inverting PhotoDNA - https://news.ycombinator.com/item?id=29626911 https://news.ycombinator.com/item?id=29626911 - Dec 2021 (25 comments)

76 points by jxmorris12 3y ago

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.

echelon 3y ago
They got push back from the "screeching" minority [1] about their needless and wanton surveillance. [1] https://www.howtogeek.com/746588/apple-discusses-screeching-voices-of-the-minority-in-internal-memos/ https://www.howtogeek.com/746588/apple-discusses-screeching-...
- rustcleaner 3y ago
  That screeching minority needs to become a belligerently agitated majority... ... in a more perfect world maybe.
  - judge2020 3y ago
    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 https://support.apple.com/en-us/108756
    - smoldesu 3y ago
      > 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.

changoplatanero 3y ago

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.

Brian_K_White 3y ago
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.

KTibow 3y ago

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.

kragen 3y ago
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
- qayxc 3y ago
  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. [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

cf1241290841 3y ago

>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

dr_kiszonka 3y ago

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?

chipsa 3y ago

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.

chpatrick 3y ago

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?

qayxc 3y ago
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 3y ago
  [deleted]
- chpatrick 3y ago
  The problem is that then the distance is also encrypted, which doesn't work here.
duskwuff 3y ago
> 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.
- adrian_b 3y ago
  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 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.

programjames 3y ago

It'd be interesting to see a diffusion model for this.

127361 3y ago
Well said.

dang 3y ago

Discussed at the time: Inverting PhotoDNA - https://news.ycombinator.com/item?id=29626911 https://news.ycombinator.com/item?id=29626911 - Dec 2021 (25 comments)