3 ms·

Could you elaborate/speculate on how dithering patterns would be used?

PatentTroll 9y ago
This isn't an answer, but I used to examine patents in this space. There are very advanced watermarking methods out there that are stable through transcoding, compression, obfuscation, etc. while being invisible to the naked eye. Really amazing stuff, wouldn't be surprised if there were lots of watermarks on media (audio, video, still image) that aren't readily apparent. One of the big use cases I remember was watermarking movies so that it would be possible to identify the time and place that a cam bootleg was recorded. That's a camcorder aimed at a movie screen and then heavily compressed and distributed over the internet, and the watermarks would still be detectable.
- kem 9y ago
  One of the things I wondered when I read this story is if it would be possible to develop software that would somehow circumvent this type of situation. For example, using autoencoding or something to lose watermarking details intentionally or something. But what you're discussing seems more advanced than the yellow dots idea. I was surprised to see printers being involved--I thought something like this leak would all be digital. I was also surprised that the Intercept would not be more savvy about printer identification because it's been publicized so much over the years.
- jerf 9y ago
  A simple, but reasonably robust solution to the cam problem is just to screw around with black frames, that is, the frames in the middle of a fade out. Give yourself 20 places where you can insert an extra frame and choose 10 to insert, and you already given yourself 40 bits to play with. (It's trivial to deal with the audio sync issues.) Cams may have a lot of spatial unreliability, but they have a lot of temporal resolution. And that's just my stupid of-the-cuff answer, which is already off to a decent start. And there are in fact purely-spatial solutions that do work, to which the temporal solutions can be added. The upshot is don't expect to beat these anytime soon. There's just too many bits to hide in, and so few bits needed for the identification.
  - Medaber 9y ago
    No. It's not that simple. For a real example that really works, see, for example, digimarc: https://www.digimarc.com/support/product/digimarc-guardian-for-images-support/faq https://www.digimarc.com/support/product/digimarc-guardian-f... Images can be cropped, rotated, recompressed, scaled, etc. and the digital watermark remains. Also see: https://en.wikipedia.org/wiki/Digimarc https://en.wikipedia.org/wiki/Digimarc and read some of their patents, referenced in the Wikipedia article.
    - hueving 9y ago
      >Images can be cropped, rotated, recompressed, scaled, etc. and the digital watermark remains. And none of those would impact the timing of black interim time lengths. Also, this makes digimarc sound crappy (from their site): >Facebook compresses images once they are posted, sometimes heavily, which can damage our invisible identifiers. Fortunately, there is a simple solution: if you pre-compress your images, then apply our identified, they should survive. So they don't survive compression.
      - Neliquat 9y ago
        Or maybe facebooks own steno overwrites it?
    - jerf 9y ago
      "And that's just my stupid of-the-cuff answer, which is already off to a decent start. And there are in fact purely-spatial solutions that do work, to which the temporal solutions can be added."
  - TeMPOraL 9y ago
    > The upshot is don't expect to beat these anytime soon. There's just too many bits to hide in, and so few bits needed for the identification. I agree. Some of the off the top of my head ideas that I literally just came up with now: - if printing an image, drop a few dots in some rows (or columns); data is hidden in the pattern of dropped dots - if printing text (as in, actual text goes to be rendered on the driver or printer firmware level, and not by the OS / text editor), slightly alter the shape of some letters (by adding or dropping a dot) to hide a pattern - if printing an image, try to hide some data in its FFT (e.g. by adjusting differences between low frequencies and hiding a pattern there) - if recording a video, slightly alter some otherwise stable global characteristic (like avg brightness of a bunch of consecutive frames in an animated movie) - if recording a video, screw with timing patterns, as you mentioned There are just so many properties, that the difficulty is probably mostly in picking something that's stable through usual transformations a document will undergo (e.g. scanning, JPG compression).
- TheHegemon 9y ago
  I have implemented one of those technologies at a previous company. Their claims and what the software was actually capable of were vastly different. I would say about 20% of the files we sent over had enough recoverable watermark to be useful.
schoen 9y ago
Speculation: Dithering algorithms traditionally include randomness. If you can determine a portion of this randomness by inspecting the output of the algorithm, then the dithering can be used to send a message, for example by using the message as a seed to a PRNG or as an input to a hash whose output serves as the randomness for the dithering operation. If the underlying message space is small enough, you could recover the message by brute force, examining each possible message and the results that it would have produced, and seeing which set of results matches the observed document. The hand-waving part of this is "if you can determine a portion of this randomness by inspecting the output of the algorithm", because I don't really understand how easy this could be made without knowing the exact underlying signal that the dithering algorithm needs to quantize. An alternative might be slightly changing some of the values in the matrices at https://en.wikipedia.org/wiki/Ordered_dithering https://en.wikipedia.org/wiki/Ordered_dithering in a way that barely reduces perceptual image quality (although I'm not certain how well that can be done). Perhaps there is an algorithm that uses statistics to deduce what matrix was used, and then the perturbations can be read out of the matrix. This is related to research in digital watermarking that's been going on for decades, and I'm definitely not an expert in that or in digital image processing, so I'd love to hear from people who know more. Nonetheless, looking up close at how printers produce different colors out of CMYK dots, I'm pretty confident that they have some degrees of freedom, and that some of them probably don't make a lot of different perceptually, and can probably be used to encode a message.

This isn't an answer, but I used to examine patents in this space. There are very advanced watermarking methods out there that are stable through transcoding, compression, obfuscation, etc. while being invisible to the naked eye. Really amazing stuff, wouldn't be surprised if there were lots of watermarks on media (audio, video, still image) that aren't readily apparent. One of the big use cases I remember was watermarking movies so that it would be possible to identify the time and place that a cam bootleg was recorded. That's a camcorder aimed at a movie screen and then heavily compressed and distributed over the internet, and the watermarks would still be detectable.

kem 9y ago
One of the things I wondered when I read this story is if it would be possible to develop software that would somehow circumvent this type of situation. For example, using autoencoding or something to lose watermarking details intentionally or something. But what you're discussing seems more advanced than the yellow dots idea. I was surprised to see printers being involved--I thought something like this leak would all be digital. I was also surprised that the Intercept would not be more savvy about printer identification because it's been publicized so much over the years.
jerf 9y ago
A simple, but reasonably robust solution to the cam problem is just to screw around with black frames, that is, the frames in the middle of a fade out. Give yourself 20 places where you can insert an extra frame and choose 10 to insert, and you already given yourself 40 bits to play with. (It's trivial to deal with the audio sync issues.) Cams may have a lot of spatial unreliability, but they have a lot of temporal resolution. And that's just my stupid of-the-cuff answer, which is already off to a decent start. And there are in fact purely-spatial solutions that do work, to which the temporal solutions can be added. The upshot is don't expect to beat these anytime soon. There's just too many bits to hide in, and so few bits needed for the identification.
- Medaber 9y ago
  No. It's not that simple. For a real example that really works, see, for example, digimarc: https://www.digimarc.com/support/product/digimarc-guardian-for-images-support/faq https://www.digimarc.com/support/product/digimarc-guardian-f... Images can be cropped, rotated, recompressed, scaled, etc. and the digital watermark remains. Also see: https://en.wikipedia.org/wiki/Digimarc https://en.wikipedia.org/wiki/Digimarc and read some of their patents, referenced in the Wikipedia article.
  - hueving 9y ago
    >Images can be cropped, rotated, recompressed, scaled, etc. and the digital watermark remains. And none of those would impact the timing of black interim time lengths. Also, this makes digimarc sound crappy (from their site): >Facebook compresses images once they are posted, sometimes heavily, which can damage our invisible identifiers. Fortunately, there is a simple solution: if you pre-compress your images, then apply our identified, they should survive. So they don't survive compression.
    - Neliquat 9y ago
      Or maybe facebooks own steno overwrites it?
  - jerf 9y ago
    "And that's just my stupid of-the-cuff answer, which is already off to a decent start. And there are in fact purely-spatial solutions that do work, to which the temporal solutions can be added."
- TeMPOraL 9y ago
  > The upshot is don't expect to beat these anytime soon. There's just too many bits to hide in, and so few bits needed for the identification. I agree. Some of the off the top of my head ideas that I literally just came up with now: - if printing an image, drop a few dots in some rows (or columns); data is hidden in the pattern of dropped dots - if printing text (as in, actual text goes to be rendered on the driver or printer firmware level, and not by the OS / text editor), slightly alter the shape of some letters (by adding or dropping a dot) to hide a pattern - if printing an image, try to hide some data in its FFT (e.g. by adjusting differences between low frequencies and hiding a pattern there) - if recording a video, slightly alter some otherwise stable global characteristic (like avg brightness of a bunch of consecutive frames in an animated movie) - if recording a video, screw with timing patterns, as you mentioned There are just so many properties, that the difficulty is probably mostly in picking something that's stable through usual transformations a document will undergo (e.g. scanning, JPG compression).
TheHegemon 9y ago
I have implemented one of those technologies at a previous company. Their claims and what the software was actually capable of were vastly different. I would say about 20% of the files we sent over had enough recoverable watermark to be useful.

schoen 9y ago

Speculation: Dithering algorithms traditionally include randomness. If you can determine a portion of this randomness by inspecting the output of the algorithm, then the dithering can be used to send a message, for example by using the message as a seed to a PRNG or as an input to a hash whose output serves as the randomness for the dithering operation. If the underlying message space is small enough, you could recover the message by brute force, examining each possible message and the results that it would have produced, and seeing which set of results matches the observed document. The hand-waving part of this is "if you can determine a portion of this randomness by inspecting the output of the algorithm", because I don't really understand how easy this could be made without knowing the exact underlying signal that the dithering algorithm needs to quantize. An alternative might be slightly changing some of the values in the matrices at https://en.wikipedia.org/wiki/Ordered_dithering https://en.wikipedia.org/wiki/Ordered_dithering in a way that barely reduces perceptual image quality (although I'm not certain how well that can be done). Perhaps there is an algorithm that uses statistics to deduce what matrix was used, and then the perturbations can be read out of the matrix. This is related to research in digital watermarking that's been going on for decades, and I'm definitely not an expert in that or in digital image processing, so I'd love to hear from people who know more. Nonetheless, looking up close at how printers produce different colors out of CMYK dots, I'm pretty confident that they have some degrees of freedom, and that some of them probably don't make a lot of different perceptually, and can probably be used to encode a message.