# Non-linear Collusion Attack on a Watermarking Scheme for Buyer Authentication

1

Non-linear Collusion Attack on a Watermarking Scheme for Buyer Authentication

Yongdong Wu

Abstract This paper presents an adaptive collusion attack on a buyer authentication watermarking scheme. To accomplish this attack, the traitors (i.e., dishonest buyers) select the pixels of their watermarked images generated from the same original image and average the selected pixels so as to remove the watermark information. Additionally, the forged image is of higher quality than any watermarked image. Both theoretical and experimental results demonstrate that our attack is very effective.

I. I NTRODUCTION

T

HE rapid development of computer networks and the increased use of multimedia data via the Internet have resulted in faster and more convenient exchange of digital information. With the ease of editing and

perfect reproduction, protection of ownership and prevention of unauthorized manipulation of digital audio, image and video materials become important concerns. Digital watermarking is a technique used to identify ownership and ?ght piracy in digital distribution networks. Its principle is to embed special labels in digital contents so as to degrade the quality of piracy, or con?rm at least one traitor with high probability given that the probability of implicating an innocent is reasonably low. In recent years, researchers have made considerable progress in watermarking schemes [1]-[6] which are more and more robust to defeat many traditional attacks, such as nonlinear geometric attacks and common image transformations.

This manuscript is submitted to IEEE Transactions on Multimedia. The author is with Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore, 119613, Tel: +65-6874 2585, Fax:+65-6775 5014. email:wydong@i2r.a-star.edu.sg.

2

However, most of the invisible watermarking schemes are prone to average collusion attack [7]. Technically, a group of traitors average their individually watermarked copies and escape from being identi?ed. Ergun et al. proved that the upper bound on the size of the traitor group is O( n ln(n)) when no traitor is captured, where n is the size of the cover signal. This result is of more importance in theory than in practice because the number of traitors is too big unless the target image is of high value. For a low-value image, it is probably not worth collecting that many watermarked images. Although it may be not valuable to start the general collusion attack [7] on watermarking schemes, a dedicated collusion attack which exploits the vulnerability of a speci?c watermarking may be of interest. For instance, the schemes [8][9] are vulnerable to the collusion attacks presented in [10][11]. Mukherjee et al [1] proposed a spatial domain watermarking which is used to identify the buyer of an image. Unfortunately, their scheme is vulnerable to the present collusion attack. Our attack is adaptive in nature. Technically, when the traitors ?nd two different pixels produced from the same original pixel, they average these two pixels to obtain a new pixel. Those new pixels and the unchanged pixels in the original watermarked image constitute a pirated image. The pirated image not only has no watermark for identifying the traitors, but also is of higher quality than any original watermarked image. Because the quality of the pirated image is improved gradually when the number of traitors increases, buyers may be interested in joining the traitor group in order to get a high quality copy. The experiment result demonstrates the effectiveness of the present attack. This paper is organized as follows. Section II introduces the buyer authentication watermarking scheme addressed in [1]. Section III elaborates our collusion attack on the buyer watermarking in [1]. Section IV contains the results of our experiments which demonstrate the ef?ciency of our attack and the quality improvement on the watermarked image. II. OVERVIEW OF B UYER AUTHENTICATION WATERMARKING In the watermarking scheme [1], an image I of N pixels is divided into m disjoint groups evenly. Denote a pixel as I(j ), j = 0, 1, · · · , N ? 1 in raster scan order, and the pixel indexes in a group constitute a set

Gk , k = 0, 1, · · · , m ? 1, i.e., Gk = {j | I(j ) in the k th group}. Each buyer is identi?ed with a unique secret key B = B0 B1 · · · Bm?1 ∈ {0, 1}m which is a binary codeword of an error correcting code to tolerate e = 0.5d ? 1 or

3

fewer errors, where d is the minimum hamming distance of the code. The scheme [1] targets for identifying at least one buyer from an inspected watermarked image. Thus, it includes two major steps: Generating watermarked image and identifying the buyer. For simplicity, we only investigate the modi?ed watermarking schemes (see Section V in [1]) in the present paper.

A. Generating Watermarked Image To generate a watermarked image for a buyer with speci?c key B = B0 B1 · · · Bm?1 ∈ {0, 1}m , the original image is manipulated pixel by pixel. The embedding process is very simple. Speci?cally, Embedding: ?j ∈ {0, 1, · · · , N ? 1}, if j ∈ Gk , Iw (j ) = I(j ) + Bk Γ(j ), where Γ(j ) varies with the pixel locations, but the sequence {Γ(j )}0≤j ≤N ?1 is ?xed for an original image, and

j ∈Gk

Γ(j ) = δk for a prede?ned

threshold δk which determines the quality of the watermarked image. Then all the pixels Iw (j ), (j = 0, 1, · · · , N ? 1) constitute a watermarked image Iw .

B. Identifying Buyer To identify a buyer from an inspected image ? Iw , the buyer’s key should be recovered. Technically, the identifying method is as follows.

? ?

for 0 ≤ k ≤ m ? 1, let the k th group’s distortion σk = 0. for 0 ≤ j ≤ N ? 1 if | ? Iw (j ) ? I(j ) |>| Γ(j ) |, then ? Iw (j ) = I(j ) + Γ(j ). if j ∈ Gk , then σk ← σk + ? Iw (j ) ? I(j ).

?

for 0 ≤ k ≤ m ? 1 if | σk |> ck | δk |, then qk = 1, else qk = 0, where ck is a prede?ned threshold value for controlling the detection error.

In order to increase the robustness, the buyer’s key B is recovered from the sequence {q0 , q1 , · · · , qm?1 } with the error correcting code.

4

III. A DAPTIVE ATTACK S CHEME Generally speaking, it is the minimal security requirement to defeat average attack [7] for a robust watermarking. Recently, Wu et al. [12][13] addressed several non-linear collusion attacks. Due to the large number of variants of collusion attacks, it is hard to prove that a watermarking scheme is resistant to all collusion attacks. Meanwhile, the attack performance of the collusion attack varies with the watermarking scheme. This section describes the weakness of the authentication watermarking [1] and gives an ef?cient collusion attack. The present attack adaptively selects the pixels of traitor’s images so as to create a pirated image of high quality but no traitor is identi?ed. In the Subsections III-A and III-B, we introduce the attack on the scheme where the group Gk is independent with the buyers (i.e. the modi?cation 1 in Section V of [1]). Then, Subsection III-D extends the security analysis to the complicate case where Gk depends on the buyers (i.e. the modi?cation 2 in Section V of [1]). A. Adaptive Collusion Attack

2 t Suppose that there are t traitors whose watermarked images are I1 w , Iw , · · · , Iw . Denote the image to be created

as I = {I(0), I(1), · · · , I(N ? 1)}. The process of constructing a pirated image is as follows: 1) Let j = 0.

t 1 2) If I1 w (j ) = · · · = Iw (j ), then I(j ) = Iw (j ) and go to step (4). 1 3) If ?i ∈ {2, 3, · · · , t} such that Ii w (j ) = Iw (j ), then, according to the embedding method introduced in

Subsection II-A,

1 Ii w (j ) = I(j ) + Γ(j ) and Iw (j ) = I(j ),

or

1 Ii w (j ) = I(j ) and Iw (j ) = I(j ) + Γ(j ).

In either of the above two cases,

1 Ii w (j ) + Iw (j ) = 2I(j ) + Γ(j ).

Hence, the traitors output

1 I(j ) = 0.5(Ii w (j ) + Iw (j )) = I(j ) + 0.5Γ(j ).

4) Let j ← j + 1. If j ≤ N ? 1, go to step (2), else all the pixels I(j ) constitute the pirated image.

5

B. Resilience to Traitor Tracing The goal of the watermarking scheme [1] is to trace the buyers’ keys when an image is con?scated. Denote the

i , Bi , · · · , Bi key for the ith buyer as B i = {B0 1 m?1 }, for i = 1, 2, · · · , t. De?ne two disjoint sets for the bit indexes

of the keys:

1 2 t S≡ = {k | Bk = Bk = · · · = Bk , 0 ≤ k ≤ m ? 1}

and its complement set

S= = {k | k ∈ S≡ , 0 ≤ k ≤ m ? 1}.

t Therefore, ?j ∈ Gk∈S≡ , I1 w (j ) = · · · = Iw (j ). Hence, any pirated pixel whose index is in the group Gk∈S≡ will be

generated in step (2) in Subsection III-A.

1 On the contrary, ?j ∈ Gk∈S= , there exists i ∈ {2, 3, · · · , t} such that Ii w (j ) = Iw (j ). Consequentially, any pirated

pixel whose index is in group Gk∈S= will be generated in step (3) in Subsection III-A. Therefore, for any k ∈

{0, 1, · · · , m ? 1}, the distortion for each group is λk =

j ∈Gk

(I(j ) ? I(j )) =

? ? ? 1δ ? Bk k k ∈ S≡ ? ? ? 0.5δk k ∈ S=

(1)

Thus, any key bit whose index k ∈ S≡ can be identi?ed correctly. However, for any key bit whose index k ∈ S= , there are two cases if the number of 0s and 1s in a key are almost equal.

?

ck < 0.5: According to the identifying method in Subsection II-B, any key bit whose index is in S= is always

regarded as 1 because | λk |= 0.5 | δk |> ck | δk |. It means that half of key bits whose index are in S= are wrongly identi?ed statistically.

?

ck ≥ 0.5: because | λk |= 0.5 | δk |≤ ck | δk |, any key bit whose index is in S= is always regarded as 0. i.e.,

half of key bits whose index are in S= are wrongly identi?ed statistically. In summary, no matter what ck is, half of key bits whose indexes are in S= are wrongly identi?ed. Thus the expect number of wrongly identi?ed bits is

Ne = 0.5p(k ∈ S= )m = 0.5(1 ? 21?t )m

6

given that the probability p(·) is uniform. From the viewpoint of the traitors, the number of wrongly identi?ed bits should be greater than the error correcting capability so that no traitor is traced. That is to say, a successful piracy requires

Ne = 0.5(1 ? 21?t )m > e

Thus,

t > 1 ? log2 (1 ? 2e/m).

(2)

In other words, if t = 1 ? log2 (1 ? 2e/m) traitors conspire to generate a pirated image, the tracer can not identify any traitor given that the probability of implicating an innocent is reasonably low. Fig.1 illustrates the relationship between the number of traitors required and the error correcting rate. From Fig.1, four traitors can create a pirated image without being identi?ed if the rate e/m < 0.4. On the other hand, although a lot of traitors are required if e/m → 0.5, the effective embedding capability (i.e. the number of legal buyers) is very small such that the watermarking scheme itself is impractical.

C. Quality of the Pirated Image A successful pirated image not only prevents from identifying the traitors, but also is of high quality. To study the quality of the pirated image, we compare the noise energy in the watermarked image Iw with that in the pirated image I. Concretely, the noise energy for the original watermarked image is

?w =

0≤k≤m?1 j ∈Gk

(I(j ) ? Iw (j ))2 Bk

0≤k≤m?1 j ∈Gk

= ≈ 0.5m

Γ(j )2

Γ(j )2

j ∈ Gk

(3)

= 0.5mδ 2

In the above Eq.3, we assume the number of 0s and 1s in a buyer key are almost equal, and the noise energy for each group is the same value δ 2 . The assumptions are sound for invisible watermarking. Meanwhile, the expect noise inserted into the pirated image is

7

10 9

8

7

6

N um be ro ft r a i t o rs re q ui r e d

5

4

3

2

1 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Error correcting rate e /m

Fig. 1.

The number of traitors required for successful pirate vs. error correcting rate e/m.

? = ?

0≤k≤m?1 j ∈Gk

(I(j ) ? ? I(j ))2

1 Bk k∈S≡ j ∈Gk 1 S≡ , Bk 2

=

Γ(j )2 +

k∈S= j ∈Gk

(0.5Γ(j ))2 (0.5Γ(j ))2

j ∈Gk

≈ p(k ∈

?t

= 1)mδ 2 + p(k ∈ S= )m

1?t

= 2 mδ + (1 ? 2

)m × 0.25δ

2

(4)

= 0.25(1 + 21?t )mδ 2 = (0.5 + 2?t )?w

1 = 1) = 2?t and p(k ∈ S ) = 1 ? 21?t . Obviously, ? > ? ? if t > 1. Since PSNR In Eq.4, p(k ∈ S≡ , Bk w =

(peak signal noise rate) is suitable for qualitatively describing the improvement on the watermarked gray images,

8

we select the ?P N SR (the difference of PSNR) to measure the quality change. Thus,

? ? 10(log10 2552 ? log10 N ?w ) ?P N SR = 10(log10 2552 ? log10 N ?) ? = 10(log10 ?w ? log10 ?) = ?10log10 (0.5 + 2?t )

In other words, the quality of the pirated image resulted from our attack is better than any watermarked images! As a result, the traitors generate a pirated image of high quality but all the traitors are not identi?ed. D. Extension to Variable Group In above Subsections III-A and III-B, we elaborate the attack method given that the group Gk is ?xed for any buyer. In order to enforce the security, authors [1] suggested a second modi?cation that Gk is variable with buyers. Now, let us consider the security of the modi?cation in [1].

1, B1, · · · , B1 Without loss of generality, let’s verify the ?rst traitor whose key B 1 = {B0 1 m?1 }. For any group Gk of 2 t the ?rst buyer, let T≡ = {j |I1 w (j ) = Iw (j ) = · · · = Iw (j ), j ∈ Gk } for the pixel indexes where all the watermarked

pixels are equal, and its complement set T= = Gk ? T≡ . Apparently, p(j ∈ T≡ ) = 21?t , and p(j ∈ T= ) = 1 ? 21?t . For any group Gk (k = 0, 1, · · · , m ? 1) of the ?rst traitor, based on Eq.1, the expect distortion of the pirated image is

λk =

j ∈Gk

(? I(j ) ? I(j ))

1 Bk Γ(j ) + j ∈T≡ j ∈T= 1? T≡ )Bk δ+

=

0.5Γ(j )

? ≈ p(j ∈ 0.5p(j ∈ T= )δ ? ? ? ? B1 = 0 ? 0.5(1 ? 21?t )δ k = ? ? ? + 0.5(1 ? 21?t )δ ? B1 = 1 ? 21?t δ k ? ? ? ? B1 = 0 ? (0.5 ? 2?t )δ k = ? ? ? B1 = 1 ? (0.5 + 2?t )δ k

(5)

(6)

? To simplify the analysis, we assume that all the Γ(j ) are over the same uniform distribution with expect value δ

in the above Eq.5. According to Eq.6, a reasonable threshold ck = 0.5 based on decision rule in Subsection II-B.

9

However, the interval (0.5 ? 2?t , 0.5 + 2?t ) is too small to make a correct decision if we consider computation deviation (e.g. round operation). Indeed, our experiments demonstrate that the number of the detected key bits is roughly 50% of the key length when 4 traitors conspire. Moreover, the interval decreases exponentially with the number of traitors involved. That is to say, the present attack is effective even if it is buyer-dependent to divide the original image in the embedding process.

IV. E XPERIMENTS Because the buyer-dependent segmentation does not obviously enhance the security strength of the original scheme [1], our experiments merely focus on the modi?cation with invariable segmentation group (i.e., modi?cation 1 in [1]). The present experiments target for demonstrating attack ef?ciency and quality improvement. The original image is a 254 × 256 gray image. In the experiment, ck = 0.5 for any group of 512 pixels. {Γ(j )} is over a pseudo-random uniform distribution as round(4(rand() + 0.1) ? 2), where round(·) and rand(·) are MATLAB functions, therefore, δk ≈ 205, k = 0, 1, · · · , 126.

A. Resilience to Tracing Based on the original watermarking scheme [1], select the buyer’s key from the BCH(127,8) code which is able to correct up to e = 31 errors. It enables that 28 buyers to own different watermarked images. Given a pirated image generated by 2 or more traitors, the experimental result indicates no traitor is traced. According to Eq.2,

t = 1 ? log2 (1 ? 2 × 31/127) = 1.97 = 2 traitors can create a pirated image without being identi?ed. It means

that the theoretical analysis is in concert with the experimental result.

B. Quality Improvement In our experiment, PSNR of the pirated image generated by 4 traitors is 50.82dB, while the watermarked image is 49.34dB. That is to say, the experimental result proves that the pirated image is of higher quality than that of the watermarked image. Fig.2 illustrates the PSNR improvement gradually on the watermarked images against the number of traitors. The dash line is the theoretical value and the solid line is the experimental result. The reason that the experimental

10

3.5

3

2.5

Theoretical result

2

Im pr ove m e nt o nP S NR

1.5

Experimental Result

1

0.5 2 3 4 5

Number of traitors

6

7

8

9

10

Fig. 2.

PSNR improvement vs. number of traitors.

improvement is smaller than the theoretical value lies in that the round operation restricts the pixel values to be in the interval [0, 255].

V. C ONCLUSION The buyer authentication watermarking scheme [1] divides an image into small groups and modi?es the intensity of some pixels depending on a secret key. Our paper presents an adaptive collusion attack to the buyer watermarking scheme by selectively manipulating the watermarked pixels. Concretely, when the traitors ?nd two unequal watermarked pixels generated from the same original pixel, they average these two pixels so as to alleviate the watermark information. This attack not only removes the watermark so that the traitors escape from being identi?ed, but also increases the watermarked image quality. We present a theoretical analysis on the size of traitor group and quality improvement. Our experimental result and theoretical analysis show that the attack is effective.

11

R EFERENCES

[1] D.P. Mukherjee, S. Maitra, S.T. Acton, “Spatial Domain Digital Watermarking of Multimedia Objects for Buyer Authentication,” IEEE Transactions on Multimedia, 6(1):1-15, 2004 [2] I.J. Cox, J. Kilian, T.Leighton and T. Shamoon, “Secure Spread Spectrum Watermarking for Multimedia”, IEEE Trans. on Image Processing, 6(12):1673-1687, 1997. [3] I. Pitas, “A Method for Signature Casting on Digital Images”, IEEE Int. Conf. On Image Processing, Vol.3, pp. 215-218, 1996. [4] R.B. Wolfgang and E.J. Delp, “A Watermark for Digital Images”, IEEE Int. Conf. On Image Processing, Vol.3, pp. 219-222, 1996. [5] M.D. Swanson, B.Zhu and A.H. Tew?k, “Transparent Robust Image Watermarking”, IEEE Int. Conf. On Image Processing, Vol.3, pp. 211-214, 1996. [6] J.F. Delaigle, C. De Vleeschouver and B. Macq, “Digital Watermarking”, SPIE, Optical Security and Counterfeit Deterrence Techniques, Vol.2659, pp. 99-110, 1996. [7] Funda Ergun, Joe Kilian, and Ravi Kumar, “A Note on the Limits of Collusion-Resistant Watermarks”, Advances in Cryptology EUROCRYPT’99, LNCS 1592, pp. 140-149, 1999 [8] Tanmoy Kanti Das and Subhamoy Maitra, “A Robust Pixel Oriented Watermarking Scheme in Spatial Domain”, International Conference on Information and Communications Security (ICICS’02), LNCS 2513, pp. 184-196, 2002 [9] W. Trappe, M. Wu, Z. Jane Wang and K. J. Ray Liu, “Anti-collusion ?ngerprinting for Multimedia,” IEEE Trans. on Signal Processing, 51(4):1 069-1087, 2003. [10] Yongdong Wu, and Robert Deng, “Adaptive Collusion Attack to a Block Oriented Watermarking Scheme,” International Conference on Information Communication Security (ICICS), LNCS2836, pp.238-248, 2003 [11] Yongdong Wu, “Linear Combination Collusion Attack and its Application on an Anti-Collusion Fingerprinting,” IEEE International Conference on Acoustics, Speech, and Signal Processing, II.13-16 Philadelphia, USA, Mar. 2005 [12] M. Wu, W. Trappe, Z. Wang, and K.J.R. Liu, “Collusion Resistant Fingerprinting for Multimedia”, IEEE Signal Processing Magazine, Special Issue on Digital Rights Management, pp.15-27, 2004 [13] Hong Zhao, Min Wu, Z. Jane Wang and K. J. Ray Liu, “Nonlinear Collusion Attacks on Independent Fingerprints For Multimedia,” IEEE International Conference on Acoustics, Speech, and Signal Processing, V664-667, 2003

12

Yongdong Wu Received the B.A and M.S. in Automation Control from Beijing University of Aeronautics and PLACE PHOTO HERE Astronautics in 1991 and 1994 respectively, and the Ph.D. degree in Pattern Recognition and Intelligent Control from Institute of Automation, Chinese Academy of Science, 1997. He is currently the head of Information Security Lab, Institute of Infocomm Research (I2 R), a-star, Singapore. His interests includes multimedia security, e-Business, Digital Right Management and Network security. Dr. Wu won the Tan Kah Kee Young Inventor’s award (Singapore) in 2004 and 2005.

13

L IST OF TABLES

L IST OF F IGURES 1 2 The number of traitors required for successful pirate vs. error correcting rate e/m. . . . . . . . . . . PSNR improvement vs. number of traitors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 10