10 ms·

I wrote this article/originally created this list, and I would like to emphasize that there is a second generation of this technology that probably uses ditheri

by schoen 9y ago

I wrote this article/originally created this list, and I would like to emphasize that there is a second generation of this technology that probably uses dithering parameters or something of that sort, and that does not produce visible dots but still creates a tracking code. We don't know the details but we do know that some companies told governments that they were going to do this, and that some newer printers from companies that the government agencies said were onboard with forensic marking no longer print yellow dots. That makes me think that it may have been a mistake to create this list in the first place, because the main practical use of the list would be to help people buy color laser printers that don't do forensic tracking, yet it's not clear that any such printers are actually commercially available.

SomeStupidPoint 9y ago
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
  - 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.
RachelF 9y ago
What is annoying is that the user pays for this. How much more yellow toner do I need to buy because my print outs are covered in yellow dots? I wonder how many million extra gallons of yellow toner and ink are wasted every year printing these tracker dots?
- therein 9y ago
  On some printers, this is the reason why the printer will refuse to print a BW-only printout while the only empty cartridge is the color one.
  - yummybear 9y ago
    I can feel my blood pressure rising...
  - anc84 9y ago
    That needs a citation or a sarcasm tag.
    - mcv 9y ago
      Does an anecdote count? My Samsung refuses to print b&w when a color cartridge is empty.
      - dom0 9y ago
        I heard that before, I think it's a tactic to bully people into buying more ink they don't need. Ensuring tracking dots is maybe just an unfortunate side effect.
      - josefx 9y ago
        Most likely it tries to print rich black, which uses color to make the b&w printout look better ( and use up all that costly color). You can disable that in your printer settings with most printers.
      - dspillett 9y ago
cm2187 9y ago
What about B&W printers?
- dspillett 9y ago
  There are methods of varying dithering/half-tone patterns in a way that is invisible to they eye but can carry enough bits of information that forensic analysis can identify an encoded printer serial number. Methods of making practically invisible changes to pure text are available too. Colour printers are starting to use these techniques instead of the (more easily noticed by the general public) extra yellow dots. See the reply to SomeStupidPoint by schoen a few hours ago (and a couple of other posts on this thread) for more detail.
  - cm2187 9y ago
    But that would be possible for a photo. But typically you would print some text. I wouldn't expect any dithering / half-tone in a text document.
    - dspillett 9y ago
      "Methods of making practically invisible changes to pure text are available too" as mentioned in the post referred to. If using printer fonts rather than explicit vectors then it is possible to hide enough data in small "mistakes" invisible to the naked eye. I'm not sure what would be possible for pure vector graphics.
      - CapacitorSet 9y ago
        For vector graphics, I suppose you could encode information in the least-significant bits (with redundancy, error correction and whatnot) if the printer can guarantee sufficiently high precision (not accuracy, mind you: https://www.tutelman.com/golf/measure/precision.php https://www.tutelman.com/golf/measure/precision.php)
captainmuon 9y ago
Is somebody working on identifying these modern watermarks? A start would be to print out test pages and compare high resolution scans. Maybe also multiple printouts from the same printer to see what the natural variation is, and if there is a timestamp component. I would start, but I'm currently not around a printer...
- amelius 9y ago
  Shouldn't we be able to control a printer on the pixel (dither) level in the first place?
  - leni536 9y ago
    This would be nice for other reasons too. There can be better halftoning algorithms to the typical pattern based halftoning of laser printers. It's hard to calibrate though, printers don't print "pixels". They print dots that typically overlap a lot, DPI for printers is the resolution for positioning the dots, not the size of the dots.
    - kpil 9y ago
      I think that ALL algorithms are better than the default halftone algorithms. I think it's possible to send saturated pixels using PCL, and tell the printer to disable half-toning. It requires that a full page fits in memory, which isn't much (512MB) but typically more than the default. For some reasons all printers use really vintage memory, so 512MB extra memory is crazy-expensive.
  - verytrivial 9y ago
    Even if we are able to, if the default is to divulge the printer ID via a dithering pattern either at the driver or machine level when given a blob of image data, I think this problem becomes similar to "Can't we all just encrypt our email?" i.e. largely academic.
    - lucideer 9y ago
_cereal 9y ago
FWIW: the link in "Other forensic marking techniques have been invented" is broken, now it points to: https://engineering.purdue.edu/~prints/ https://engineering.purdue.edu/~prints/ But it does not redirect anymore, I had to use archive.org
lazyjones 9y ago
Isn't this mostly a driver issue, i.e. something that could change for any model at any time should the vendor decide to add tracking to a driver update?
- helb 9y ago
  I'm afraid it's probably built into the printer firmware, not drivers in OS.
  - lazyjones 9y ago
    Driver updates can usually modify the firmware in modern devices. I don't see a real dichotomy here...
4684499 9y ago
Is there a notice/agreement tells customers there are tracking dots before buying? If there isn't, how is this not illegal?
- matthewmacleod 9y ago
  It's hard to imagine what law this would break.
  - 1001101 9y ago
    By the same token, what is compelling them to do this? A sense of patriotic duty? The kindness of their hearts? There's a lot of work that would go into designing, implementing, and testing this. Then you've got logistics in manufacturing. That's time and money.
    - gumby 9y ago
      > By the same token, what is compelling them to do this? A sense of patriotic duty? The GSA Schedules: https://www.gsa.gov/portal/content/197989 https://www.gsa.gov/portal/content/197989
      - schoen 9y ago
        The original motivation seems to have been a deal between a printer industry association and a central banks' association, perhaps as an alternative to threatened legislation, although we've never been able to get ahold of the details of that deal.
- schoen 9y ago
  Sometimes, for example https://duckduckgo.com/?q=docucolor+"not+visible+under+normal+viewing+conditions" https://duckduckgo.com/?q=docucolor+"not+visible+under+norma... We originally found that in German, https://duckduckgo.com/?q=docucolor+"unter+normalen+bedingungen+nicht+sichtbar" https://duckduckgo.com/?q=docucolor+"unter+normalen+bedingun... However, I don't think that most printers currently disclose this, at least for sales in the U.S.
kefka 9y ago
Well, that being said, it sounds like there needs to be a more rigorous way of detecting these new codes. One way I can think of, is to record data on the CMYK pins on the inkjet head itself. IIRC, they activate between 17v and 22v, and pulse per high. The goal here is to make the printer think its printing, while recording all the data of the pulse operations. We would get a lengthy file out. Ideally, the pulse coding should be consistent if printing the same image. "Printing" the same thing over multiple times could show time/date codes embedded. I should also be able to compare underlying system internals too, with multiple clones of VMs with small config details different. They should be the same data. If they aren't, we know its encoding system stuffs. But yeah, there is a way to attack this, and that's by going lower in the stack and treating the printers as a black box. It's not the best way, but a way I've thought of that could at least detect this new technique.
- nobodyorother 9y ago
  Would filling all the color tanks with black ink before printing make initial detection easier?
  - kefka 9y ago
    I doubt it. There's tons of tricks and things that can be done to steganographically hide data in images. And given the algo is hidden, and the data is hidden in plain sight, we have to go to a level that can't be hidden from us. Printing in different inks also wouldn't show us a way to diff 2 printed images. Whereas, saving the pulses from the CMYK pins would do that. When you have a datalog of lots of pulses that represent a picture, you can back-calculate it into an image. You can also diff it without relying on losing data from scanning (or paying attention to the wrong thing). And with enough samples, we can recalculate the algorithm. With the knowledge of what they're doing, we can then start scanning other images for this... But only once we know what they're doing.
    - dajt 9y ago
      What about printing two images, each with only 1 black pixel in a different place?

by schoen 9y ago

SomeStupidPoint 9y ago

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
- 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.

RachelF 9y ago

What is annoying is that the user pays for this. How much more yellow toner do I need to buy because my print outs are covered in yellow dots? I wonder how many million extra gallons of yellow toner and ink are wasted every year printing these tracker dots?

therein 9y ago
On some printers, this is the reason why the printer will refuse to print a BW-only printout while the only empty cartridge is the color one.
- yummybear 9y ago
  I can feel my blood pressure rising...
- anc84 9y ago
  That needs a citation or a sarcasm tag.
  - mcv 9y ago
    Does an anecdote count? My Samsung refuses to print b&w when a color cartridge is empty.
    - dom0 9y ago
      I heard that before, I think it's a tactic to bully people into buying more ink they don't need. Ensuring tracking dots is maybe just an unfortunate side effect.
    - josefx 9y ago
      Most likely it tries to print rich black, which uses color to make the b&w printout look better ( and use up all that costly color). You can disable that in your printer settings with most printers.
    - dspillett 9y ago

cm2187 9y ago

What about B&W printers?

dspillett 9y ago
There are methods of varying dithering/half-tone patterns in a way that is invisible to they eye but can carry enough bits of information that forensic analysis can identify an encoded printer serial number. Methods of making practically invisible changes to pure text are available too. Colour printers are starting to use these techniques instead of the (more easily noticed by the general public) extra yellow dots. See the reply to SomeStupidPoint by schoen a few hours ago (and a couple of other posts on this thread) for more detail.
- cm2187 9y ago
  But that would be possible for a photo. But typically you would print some text. I wouldn't expect any dithering / half-tone in a text document.
  - dspillett 9y ago
    "Methods of making practically invisible changes to pure text are available too" as mentioned in the post referred to. If using printer fonts rather than explicit vectors then it is possible to hide enough data in small "mistakes" invisible to the naked eye. I'm not sure what would be possible for pure vector graphics.
    - CapacitorSet 9y ago
      For vector graphics, I suppose you could encode information in the least-significant bits (with redundancy, error correction and whatnot) if the printer can guarantee sufficiently high precision (not accuracy, mind you: https://www.tutelman.com/golf/measure/precision.php https://www.tutelman.com/golf/measure/precision.php)

captainmuon 9y ago

Is somebody working on identifying these modern watermarks? A start would be to print out test pages and compare high resolution scans. Maybe also multiple printouts from the same printer to see what the natural variation is, and if there is a timestamp component. I would start, but I'm currently not around a printer...

amelius 9y ago
Shouldn't we be able to control a printer on the pixel (dither) level in the first place?
- leni536 9y ago
  This would be nice for other reasons too. There can be better halftoning algorithms to the typical pattern based halftoning of laser printers. It's hard to calibrate though, printers don't print "pixels". They print dots that typically overlap a lot, DPI for printers is the resolution for positioning the dots, not the size of the dots.
  - kpil 9y ago
    I think that ALL algorithms are better than the default halftone algorithms. I think it's possible to send saturated pixels using PCL, and tell the printer to disable half-toning. It requires that a full page fits in memory, which isn't much (512MB) but typically more than the default. For some reasons all printers use really vintage memory, so 512MB extra memory is crazy-expensive.
- verytrivial 9y ago
  Even if we are able to, if the default is to divulge the printer ID via a dithering pattern either at the driver or machine level when given a blob of image data, I think this problem becomes similar to "Can't we all just encrypt our email?" i.e. largely academic.
  - lucideer 9y ago

_cereal 9y ago

FWIW: the link in "Other forensic marking techniques have been invented" is broken, now it points to: https://engineering.purdue.edu/~prints/ https://engineering.purdue.edu/~prints/ But it does not redirect anymore, I had to use archive.org

lazyjones 9y ago

Isn't this mostly a driver issue, i.e. something that could change for any model at any time should the vendor decide to add tracking to a driver update?

helb 9y ago
I'm afraid it's probably built into the printer firmware, not drivers in OS.
- lazyjones 9y ago
  Driver updates can usually modify the firmware in modern devices. I don't see a real dichotomy here...

4684499 9y ago

Is there a notice/agreement tells customers there are tracking dots before buying? If there isn't, how is this not illegal?

matthewmacleod 9y ago
It's hard to imagine what law this would break.
- 1001101 9y ago
  By the same token, what is compelling them to do this? A sense of patriotic duty? The kindness of their hearts? There's a lot of work that would go into designing, implementing, and testing this. Then you've got logistics in manufacturing. That's time and money.
  - gumby 9y ago
    > By the same token, what is compelling them to do this? A sense of patriotic duty? The GSA Schedules: https://www.gsa.gov/portal/content/197989 https://www.gsa.gov/portal/content/197989
    - schoen 9y ago
      The original motivation seems to have been a deal between a printer industry association and a central banks' association, perhaps as an alternative to threatened legislation, although we've never been able to get ahold of the details of that deal.
schoen 9y ago
Sometimes, for example https://duckduckgo.com/?q=docucolor+"not+visible+under+normal+viewing+conditions" https://duckduckgo.com/?q=docucolor+"not+visible+under+norma... We originally found that in German, https://duckduckgo.com/?q=docucolor+"unter+normalen+bedingungen+nicht+sichtbar" https://duckduckgo.com/?q=docucolor+"unter+normalen+bedingun... However, I don't think that most printers currently disclose this, at least for sales in the U.S.

kefka 9y ago

Well, that being said, it sounds like there needs to be a more rigorous way of detecting these new codes. One way I can think of, is to record data on the CMYK pins on the inkjet head itself. IIRC, they activate between 17v and 22v, and pulse per high. The goal here is to make the printer think its printing, while recording all the data of the pulse operations. We would get a lengthy file out. Ideally, the pulse coding should be consistent if printing the same image. "Printing" the same thing over multiple times could show time/date codes embedded. I should also be able to compare underlying system internals too, with multiple clones of VMs with small config details different. They should be the same data. If they aren't, we know its encoding system stuffs. But yeah, there is a way to attack this, and that's by going lower in the stack and treating the printers as a black box. It's not the best way, but a way I've thought of that could at least detect this new technique.

nobodyorother 9y ago
Would filling all the color tanks with black ink before printing make initial detection easier?
- kefka 9y ago
  I doubt it. There's tons of tricks and things that can be done to steganographically hide data in images. And given the algo is hidden, and the data is hidden in plain sight, we have to go to a level that can't be hidden from us. Printing in different inks also wouldn't show us a way to diff 2 printed images. Whereas, saving the pulses from the CMYK pins would do that. When you have a datalog of lots of pulses that represent a picture, you can back-calculate it into an image. You can also diff it without relying on losing data from scanning (or paying attention to the wrong thing). And with enough samples, we can recalculate the algorithm. With the knowledge of what they're doing, we can then start scanning other images for this... But only once we know what they're doing.
  - dajt 9y ago
    What about printing two images, each with only 1 black pixel in a different place?