The blind pattern matching attack on watermark systems

Billions of dollars allegedly lost to piracy of multimedia content have recently triggered the industry to rethink the way how music and movies are distributed on the Internet. As encryption is vulnerable to digital or analog re-recording, currently almost all copyright protection mechanisms rely to certain extent on watermarking, i.e. hiding of imperceptive secrets into a host signal. In this paper, we propose a new breed of attacks on generic watermarking systems, which recognizes that multimedia content is often highly repetitive, identifies subsets of signal blocks that are similar, and finally permutes these blocks. Assuming the permuted blocks have been marked with distinct secrets, it can be shown that any watermark detector is facing a task of exponential complexity to reverse the permutations as a preprocessing step for watermark detection. In this paper, we describe the logistics of the attack and a recipe for its implementation against an audio watermarking technology.