[Printers] software release: yellowdot

[I Miller]

Thanks for the rapid reply, Seth!  I'm extremely interested in the brochure
produced by EFF - is there an online copy available?

A question: are there known printer watermarking schemes that involve
permutations of the watermark across the printed sheet?  In the case of
Xerox DocuColor, it appears that there isn't any "room" in the watermark for
such information, and it suggests to me that the same watermark is repeated
across the sheet.  Therefore, in the case of DocuColor printers, the
logical-AND method propose proposed by Seth Schoen would be a trivial attack
against the random-dot overlay generated by yellowdot.

However, a more sophisticated watermarking technique (checksumming the row
and column, or perhaps encryption) would require more sophisticated analysis
to disambiguate yellowdot noise.  For what it's worth, there is a density
parameter in yellowdot that roughly (though not directly) corresponds to how
much noise appears in the generated PNG.  This parameter is currently
hardcoded, but the next release will make this available as a command line
parameter.

Although the proposed attack methodology is completely straight-forward, I
am curious to know how time-consuming it is to employ.  It sounds a little
tedious to scan the page at an appropriate DPI, extract and align the
"watermark tiles," then apply a logical-AND (e.g. with GIMP and multiple 50%
opacity layers)...  but to get a good sample of the "signal" should only
require a few such tiles.

An attack that had multiple pages of output from a single printer could be
optimized to select only the top-most, left-most watermark from each page,
which might make extraction more efficient.  To mitigate this risk, in the
case of a multi-page document, the same yellowdot noise should be used for
all pages.  In fact, perhaps this suggests that the same yellowdot overlay
should be used for all documents produced by a single printer, and never for
any document produced by another printer.

I think Seth Schoen's challenge sounds like lots of fun.  I don't have a
laser printer, but I'm happy to find a local print shop for this purpose.
However, if anyone else has faster access to a DocuColor printer, by all
means take advantage of that access!

Finally, as a general question to the list: I have followed the printer
watermark _decoding_ meme for several years now, but have there been other
proactive attempts, aside from yellowdot, to _obfuscate_ printer
watermarking?

-Ian

On Fri, Oct 24, 2008 at 1:02 AM, Seth David Schoen <schoen at eff.org> wrote:

> I Miller writes:
>
> > This software will create a PNG containing yellow dots that can then be
> > overlaid onto existing printer output. These dots are randomly
> distributed
> > across the image, and are therefore not useful for securely obfuscating
> the
> > identity that is encoded within the printer's generated dot pattern.
> > However, ``yellowdot'' raises the amount of resources that must be
> expended
> > to successfully identify the printer that generated a given document. It
> is
> > hoped that ``yellowdot'' can be used to thwart amateur attempts to breach
> > privacy, such as could conceivably be practiced in an office environment.
>
> This is an interesting idea, but I'm concerned that a lot of people
> won't realize just how easy and automatic it could be to undo this.
> (EFF has also just produced a brochure in which I argue against this
> idea for the reasons below, in a lot less technical detail.)
>
> Suppose we're talking about DocuColor or Dell dots, which we understand
> well and where the repeating unit of the tracking pattern is relatively
> small.  We probably don't need Fourier transforms or anything fancy to
> find the repeating periodic signal; if we know its period accurately
> enough we can take n identically-sized adjacent rectangular regions of
> the appropriate size, do a color separation and then invert the blue
> channel values, and then multiply (or logical-AND) to find yellow pixels
> that are present in each such region.  Then a false positive added noise
> dot will only occur at a given location with probability p^n, where p is
> the probability that the added noise will turn on a dot at a particular
> randomly chosen location.  If p is very high, the output image quality
> would be adversely effected, and anyway choosing even a moderately large
> n makes p^n pretty small.  What's worse, the resulting image can probably
> be manually edited to remove false positive dots because the normal
> structure of a tracking pattern is predictable enough.  (There's also
> the problem that even the grid alignment of the tracking pattern is
> probably extremely constrained, and of course the DocuColor and Dell
> tracking patterns have row and column parity, sufficient to correct a
> single bit error.)
>
> I'm not an image-processing expert, but I know that there are an enormous
> number of techniques and tools to remove noise from periodic signals,
> and to detect changes (or the lack of changes) in related images.  For
> instance, I know of an astronomy project where students get time-lapse
> imagery from telescopes and then digitally subtract images from one
> another in order to remove the fixed stars and find asteroids.  In a way,
> these obfuscation techniques are like taking a number of images of fixed
> stars (the forensic tracking dots) and adding asteroids (the noise dots)
> to them.  If the students can distinguish the two in telescope images, I
> bet they could distinguish them in forensic images.
>
> I think it's valuable to understand how practical this attack is, so I'd
> be happy to try a challenge -- if someone wants to print a "yellowdot"
> document (mostly whitespace for simplicity) on a DocuColor or Dell, write
> down the printer serial number but don't tell me what it was, and then
> send it to me in the mail, I'll make an attempt to read the serial number
> and tell the list the results.
>
> --
> Seth Schoen
> Staff Technologist                                schoen at eff.org
> Electronic Frontier Foundation                    http://www.eff.org/
> 454 Shotwell Street, San Francisco, CA  94110     1 415 436 9333 x107
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://frotz.zork.net/pipermail/printers/attachments/20081024/6c57c5e2/attachment.html