relation. Only a choice of good amplification parameters can zero the correlation.
In some cases the image to be marked has certain fea- tures that help a malicious attacker to gain information about the mark itself. An example of such features is where a picture, such as a cartoon, has only a small number of dis- tinct colours, giving sharp peaks in the colour histogram. These are split by some marking algorithms. The twin peaks attack, suggested by Maes , takes advantage of this to recover and remove marks. In the case of grayscale images, a simple example of digital watermarking based on spread spectrum ideas is to add or substract randomly a fixed value d to each pixel value. So each pixel’s value has a 50% chance of being increased or decreased. Let nk be the number of pixels with gray value k and suppose that f o r a p a r t i c u l a r g r a y v a l u e k 0 t h e d t h n e i g h b o r i n g c o l o u r s d o n Consequently, the watermarking are: o t o c c u r , s o n k 0 − d k 0 = 0. =n + d expected numbers of occurencies after
˜ n k 0 − d
˜ n k 0 + d
= nk0 /2
original distribution of embedded watermark.
C. The mosaic attack
There is a presentation attack which is quite general and which possesses the initially remarkable property that we can remove the marks from an image and still have it ren- dered exactly the same, pixel for pixel, as the marked image by a standard browser.
It was motivated by a fielded system for copyright piracy detection, consisting of a watermarking scheme plus a web crawler that downloads pictures from the net and checks whether they contain a client’s watermark.
Our mosaic attack consists of chopping an image up into a number of smaller subimages, which are embedded one after another in a web page. Common web browsers render juxtaposed subimages stuck together as a single image, so the result is identical to the original image. This attack appears to be quite general; all marking schemes require the marked image to have some minimal size (one cannot hide a meaningful mark in just one pixel). Thus by splitting an image into sufficiently small pieces, the mark detector will be confused . One defence would be to ensure that the minimal size would be quite small and the mosaic attack might therefore not be very practical.
But there are other problems with such ‘crawlers’. Mo- bile code such as Java applets can be used to display a pic- ture inside the browser; the applet could de-scramble the picture in real time. Defeating such techniques would entail rendering the whole page, detecting pictures and checking whether they contain a mark. Another problem is that pirated pictures are typically sold via many small web ser- vices, from which the crawler would have to purchase them using a credit card before it could examine them.
D. Interpretation attacks
StirMark and our attack on echo hiding are examples of the kind of threat that dominates the information hiding
literature – namely, a pirate who removes the mark directly using technical means. Indeed, the definition commonly used for robustness includes only resistance to signal ma- nipulation (cropping, scaling, resampling, etc.). However, Craver et al. show that this is not enough by exhibiting a ‘protocol’ level attack in .
The basic idea is that as many schemes provide no intrin- sic way of detecting which of two watermarks was added first. If the owner of the document d encodes a watermark w, publishes the marked version d + w and has no other proof of ownership, then a pirate who has registered his wa- termark as w can claim that the document is his and that the original unmarked version of it was d + w − w. Their paper  extends this idea to defeat a scheme which is non-invertible (an inverse needs only be approximated).
Craver et al. argue for the use of information-losing marking schemes whose inverses cannot be approximated closely enough. Our alternative interpretation of their at- tack is that watermarking and fingerprinting methods must be used in the context of a larger system that may use mechanisms such as timestamping and notarisation to pre- vent attacks of this kind.
Environmental constraints may also limit the amount of protection which technical mechanisms can provide. For example, there is little point in using an anonymous digital cash system to purchase goods over the Internet, if the pur- chaser’s identity is given away in the headers of his email message or if the goods are shipped to his home address.
E. Implementation considerations
The robustness of embedding and retrieving algorithms and their supporting protocols is not the only issue. Most real attacks on fielded cryptographic systems have come from the opportunistic exploitation of loopholes that were found by accident; cryptanalysis was rarely used, even against systems that were vulnerable to it .
We cannot expect copyright marking systems to be any different and the pattern was followed in the first attack to be made available on the Internet against one of the most widely used picture marking schemes. This attack exploited weaknesses in the implementation rather than in the underlying marking algorithms, even although these are weak (the marks can be removed with StirMark).
Each user has an ID and a two-digit password, which are issued when he registers with the marking service and pays a subscription. The correspondence between IDs and passwords is checked using obscure software and, although the passwords are short enough to be found by trial and er- ror, the published attack first uses a debugger to break into the software and disable the password checking mechanism. As IDs are public, either password search or disassembly enables any user to be impersonated.
A deeper examination of the program allows a villain to change the ID, and thus the copyright mark, of an already marked image as well as the type of use (such as adult versus general public content). Before embedding a mark, the program checks whether there is already a mark in the picture, but this check can be bypassed fairly easily using