Cryptanalysis of UCLA Watermarking Schemes for Intellectual Property Protection

Cryptanalysis of UCLA Watermarking Schemes for Intellectual Property Protection Tri Van Le and Yvo Desmedt
Department of Computer Science, Florida State University Tallahassee, Florida, USA {levan,desmedt}@cs.fsu.edu

Abstract. We analyze four recently proposed watermarking schemes for intellectual property protection of digital designs. The first scheme watermarks solutions of a hard optimization problem, namely the graph coloring problem. The other three schemes belong to a family of techniques for watermarking digital circuits on programmable hardware. They are different from the usual image and audio watermarking since they must maintain correctness of the watermarked objects. Thus their watermarks cannot be embedded in the form of small errors as usually done in audio and visual watermarking. Although constraint-based watermarking schemes existed long before, these schemes are the first ones to protect hardware designs. In this paper, we apply a novel method to break the first of these schemes. We show how to modify a watermarked object in such a way that every signature strings can be extracted from it. Thus anyone can claim ownership of the object, yet leave no traces of who leaked the object. According to our best knowledge, this method is new and it may be of its own interest. In the remaining three schemes, we show how to locate and to remove the watermark embedded in the object, without knowing the secret key used in the embedding. Keywords: cryptanalysis, watermarking, watermark analysis.

1

Introduction

As pressures for fast time-to-market and high quality hardware components increase, design reuse and a market for design reuse effectively provides a viable way to tackle the preasures. Not only they reduce the complexity, but also they minimize the time and risks of the development process. The healthiness of such a design market, however, depends on the existence of good schemes to protect intellectual properties against illegal usages. This necessity is natural since intellectual property creators often need to protect and to recoup their investments in developing the designs. Digital watermarking is one among many solutions towards this end. The main purpose of this paper is to analyze several constraint-based watermarking schemes proposed recently by UCLA team [3, 4, 5, 6, 7, 8, 9, 10].


The authors were partially supported by NFS 0096247.

F.A.P. Petitcolas (Ed.): IH 2002, LNCS 2578, pp. 213–225, 2003. c Springer-Verlag Berlin Heidelberg 2003


214

Tri Van Le and Yvo Desmedt

It is well known that in order to be effective against malicious users, a watermarking scheme must satisfy at least the following requirements [4]: – Validity The embedding must produce a watermarked object that is both syntactically valid and functionally equivalent to the original object. If the watermarking process destroys the product then we can not use it anymore. – Quality Besides validity and functionality, the watermarked object must also maintain the high quality of the original object. This means the overhead of the watermark inside the intellectual property must be small so that the commercial grade of the object stays intact. – Undeniability The watermarked object is claimable by the owner, but attributable to any other user. Thus the verification algorithm must have high probability of success when executed by the legitimate owner, and have very low probability of success when performed by any non-legitimate owner. This guarantees the creator a high credibility in claiming his ownership of the object. – Robustness It is difficult for any user to destroy the watermark without downgrading the quality, or altering the functionality of the object. Therefore, even when a watermarked object is modified by a malicious user, the verification algorithm still succeeds with high probability when run by the possessor, but nevertheless succeeds with low probability when carried out by malicious users. – Resiliency Since it is usually desirable in practice to sell one intellectual property to many users, any coalition of legitimate users should not be able to destroy the watermark. It means given multiple watermarked copies of the same object, a malicious is unable to locate and to remove, or to change, the watermark into one of his own. Otherwise, a malicious group of users will be able to claim illegal ownership of a copyrighted object, or be able to transfer it to another third party. It is often (miss) believed that one needs to destroy the watermark in order to render it useless. Several schemes were indeed proposed in this view [3, 4, 5, 6, 7, 8, 9, 10], and we will show later that this belief is quite untrue. One of the above schemes is broken without touching the original watermark. The idea of constraint based watermarking, initially reported in [2] and then extensively applied in [3, 4, 5, 6, 7, 8, 9, 10], is that in order to watermark an object, a secret signature is embedded into the object by adding artificial design-time constraints to the object’s creation process. When the object is discovered being used illegally, the owner runs a verification algorithm that extracts the embedded watermark, and then shows it to a court that the watermarked object belongs to him. Depending on the particular scheme, he may also be able to trace back the origin of mis-appropriation, i.e. to identify the customer, or group of customers, who transferred the watermarked property. Contrary to the believes of [3, 4, 5, 6, 7, 8, 9, 10], we show here that the newly proposed watermarking schemes are not quite robust. Their watermarks can be destroyed entirely in the first scheme, or completely located and removed in the

Cryptanalysis of UCLA Watermarking Schemes

215

last three schemes. The functionality and high quality of the attacked objects remain unaltered. We first give sketches of these schemes here, and will describe them in more details later. In the first scheme [9, 10], a new approach is applied to embed a signature into the coloring solution of a graph. The considered scenario is: assume someone has developed an efficient heuristic algorithm to solve a hard optimization problem but wishes to keep it secret, in order to recover his investment in developing the algorithm. The graph coloring problem is used extensively in automatic tools in computer aided design, and thus it is important. The watermarking algorithm is following: instead of directly embedding a watermark into a good solution obtained, the owner of the graph coloring algorithm modifies his algorithm accordingly to his secret signature so that the obtained solution implicitly contains the signature. The verification algorithm then consists of showing that the watermarked solution satisfies a secret set of constraints, which are very unlikely satisfied by a randomly chosen object. This unique set of constraints represents the secret signature of the owner. In the other three schemes, an encrypted signature is suitably embedded into unused configurable logic blocks (CLB) of a field programmable gate array (FPGA) which contains the design of a digital circuit. The embedding of the signature bits into each non-functional CLB is done by modifying its lookup table (LUT) accordingly to the bits. Usually, there are many unused CLBs available on a typical FPGA design. The purpose of encrypting the signature with a secret key is to whiten it out so that the users cannot tell apart which CLBs are non-functional. The non-functional CLBs are further disguised by randomly relocating and connecting them to other functional CLBs. In order to deter users from detecting or locating the watermark, the pseudo random numbers used in the embedding and hiding process above are generated from a secret random key. Along with the hiding operations, the watermark is additionally strengthened by preprocessing the signature string with an error correcting code, and interleaving the code blocks [7]. In order to verify the signature, the owner first captures the configuration loaded onto the FPGA, for example by monitoring its bus, then uses his secret key to locate the non-functional CLBs, and finally decrypts the embedded watermark using the same secret key [3, 4, 5, 6, 7, 8]. Since the key used to generate the pseudo random numbers and to encrypt the watermark is kept secret, the authors of the papers believed that it is difficult to detect and to hence remove the watermark. Contribution We show that these schemes are not as secure as they are believed to be. For the first scheme, we employ a new approach to destroy the original creator’s watermark. We modify the watermarked solution in such a way that any signature string can be extracted by the verification algorithm, and thus the original owner can neither claim his ownership nor make use of the watermark to identify the origin of mis-appropriation. For the other three schemes, we show that after successful capturing of the program (configuration) that is loaded into an FPGA (as presumed possible in [4]), a malicious user can detect all

216

Tri Van Le and Yvo Desmedt

non-functional CLBs embedded into the FPGA program by the original owner, and remove them from the design. In the next sections, we describe each of the schemes, and how to break them in turn. Our two approaches to break the above schemes are the complement of each others. The first one makes sure that every user can claim ownership of the watermarked object, while the later one ensures that no user can claim it.

2

Watermarking for Graph Coloring

Given an undirected graph G, a coloring of G is an assignment of colors to the vertices of G so that the end points of each edges of G have different colors. The objective is to use the fewest possible number of colors. A watermarking scheme for this problem embeds a secret signature into the final coloring so that it can later be detected or extracted. Graph coloring problem has many real life application such as in register allocations, scheduling problems, and other resource allocation problems similar to those in computer aided design. Therefore a watermarking scheme for graph coloring problem is an interesting aspect of watermarking in digital designs. 2.1

Scheme Description

We first describe the embedding and verifying procedures of [9]. In our descriptions, E(G) denotes the set of edges of the graph G, and (vi , vj ) denotes an edge joining vertices vi and vj . The idea of the scheme is to add additional constraint in the form of “ vi and vj are to be assigned with different colors” to the original coloring problem. This type of constraints is satisfied by adding the additional edge (vi , vj ) to the original graph G. The choice of the additional edge (vi , vj ) is calculated based on the secret signature string M , and the graph G. In the followings, let C be a coloring solution of G. Embedding Let M =m0 m1 . . . mk be the signature string. Let v0 , v1 , ..., vn−1 be the vertices of G. Let [vi , vj ] = {vi+1 , vi+2 , . . . , vj−1 } if i < j, and [vi , vj ] = {vi+1 , vi+2 , . . . , vn−1 , v0 , v1 , . . . , vj−1 } if i > j. The embedding process is done incrementally, one bit at a time until all bits are embedded. To embed bit mi into C, one does the following: – Let {vi1 , vi2 } be the next two nearest vertices in G that are not directly connected to vi0 , where i0 := i mod n. Here the term nearest means (vi0 , vi1 ), (vi0 , vi2 ) ∈ E(G); (vi0 , vj ) ∈ E(G) for all vj ∈ [vi0 , vi1 ] ∪ [vi1 , vi2 ]. – Add the edge (vi0 , vi1+mi ) to G. Let G be the final graph obtained after adding all the edges accordingly to the bits of M to G. Let C  be a coloring of G , then output C  as the watermarked version of C. In the verification stage, one verifies that all the added constraints are indeed satisfied. Note that in order to keep the location of the watermark secret, one must also keep M secret.

Cryptanalysis of UCLA Watermarking Schemes

217

Verification Let input be a graph G with a coloring C  . – Using the secret key, one reconstructs the binary string M , and the graph G with all the extra edges added as in the embedding process. – If C  is a valid coloring of G then outputs Yes. Otherwise, if C  is not a valid coloring of G then outputs No. It is easy to see that the above scheme is valid since any valid coloring of G is also a valid coloring of G. Additionally, it has been shown in [9] that the watermarked coloring C  almost always uses only one additional color, and that the probability of a random valid coloring C of G being a valid coloring of G is small, too. Hence the scheme has high quality and undeniability property. We show here that, however, this scheme is not robust against a malicious user. 2.2

Scheme Analysis

Our attack algorithm modifies the watermarked coloring C  to obtain a new coloring C  of G, using approximately only two additional colors, in such a way that any signature string can be extracted from C  . That means for every secret signature string M , the verification algorithm described above will succeed. In other words, everyone can claim ownership of the new coloring C  . Therefore the original owner cannot claim his exclusive ownership. Further, since any input signature string can be extracted from the coloring C  , it is difficult for the owner to tell who is the real malicious user who leaked this solution. Our dewatermark algorithm is described bellow. Destroy Let input be a graph G with a valid coloring C  . – Let c =  nk , where k is the length of the embedded signature. – For each i ∈ {0, 1, . . . , n − 1}, let Ei = {(vi , vi1 ), (vi , vi2 ), . . . , (vi , vic+1 )} such that (vi , vit ) ∈ E(G) for t ∈ {1, 2, . . . , c + 1}, and that (vi , vj ) ∈ E(G) for all j ∈ [vi , vi1 ] ∪ [vi1 , vi2 ] ∪ . . . ∪ [vic , vic+1 ]. – Let G∗ be the result of adding E0 , E1 , . . . , En−1 to G. – Loop i from 0 to n − 1: If ∃0 ≤ j < n : (vi , vj ) ∈ E(G∗ ) and C  [vi ] = C  [vj ] then: • If there exists a color c in C  such that no neighbor of vi in G∗ has color c, then let c be any one of such colors. Otherwise, let c be a new color not already in C  . • Assign the new color c to vi and let C  [vi ] := c. – Let C  be the result of C  after the loop and exits. We now analyze our destroy algorithm. Using the same model as in [10], we assume in the next analysis that: – G is a randomly chosen graph of n vertices with edge probability p. n 1 – The number of colors in C is exactly χ =  2 log n , where b = 1−p . b

218

Tri Van Le and Yvo Desmedt

Theorem 1. The number of additional colors used in the destroy algorithm is at most 2bc logb n, which is negligible with respect to χ. Proof. Let C  be the output of our algorithm. It is clear that C  is a valid coloring of G∗ , and thus also a valid coloring of G. For each vertex vi , the number of neighboring vertices of vi is about np. The number of all vertices of the same color as vi s is about  nn  < 2 logb n. Consequently, the probability 2 logb n

that a randomly chosen pair of non-adjacent vertices (vi , vj ) having the same logb n color is at most 2n−np . Therefore the probability that vertex vi needs a different c
logb n logb n ≈ 2cn−np . Hence color in our destroy algorithm is at most 1 − 1 − 2n−np

logb n = 2bc logb n in almost all graphs, our destroy algorithm uses at most 2nc n−np additional colors. This number is exponentially small, or negligible, compared n ) to color G. Therefore the to the original number of colors needed ( 2 log bn 

dewatermarked coloring C  is of very high quality compared to C  .

See Subsection 2.3 for experimental results of our algorithm. We show bellow that the destroy algorithm described above indeed removes the watermark from C  . Theorem 2. Let C  be the output of the destroy algorithm on input (G,C  ), where C  is the output of the embedding algorithm on input graph G. Then the verification algorithm will always output yes on input (G,C  ,M ) for arbitrary signature M . Proof. We note that for some i < j, Ei ∩ Ej = ∅ if and only if (vi , vj ) ∈ Ei ∩ Ej . This implies that |Eij | ≤ c, and |Eji | ≤ c where Eij = {(vi , vt ) ∈ E(G) | vt ∈ [vi , vj ]}, and Eji = {(vj , vt ) ∈ E(G) | vt ∈ [vj , vi ]}. Therefore the probability that Ei ∩ Ej = ∅ is at most the probability that |Eij | + |Eji | ≤ 2c. Let q = 1 − p, n! , then the later probability is: and Ckn = k!(n−k)! n−2 n−2−2c 2c pn−2 + C1n−2 pn−3 q + . . . + C2c p q < c(n − 2)2c pn−2−2c .

Since c ∈ o(log n) when n → ∞, this probability is negligible when n → ∞. Hence for almost all graphs G, we have Ei ∩ Ej = ∅ for all i < j. Let G be the graph constructed by verification algorithm on input string signature M , and let G∗ be the graph constructed in the destroy algorithm. Since Ei ∩ Ej = ∅ for i = j, we see that: regardless of the content of the message M , all the edges that were added to G are added to G∗ as well. Hence we have E(G ) ⊂ E(G∗ ). Further, C  is a valid coloring of G∗ , therefore a valid coloring of G . That means the verification algorithm will succeed on (G,C  ,M ). 

2.3

Experimental Results

In the numerical simulation, we take a random graph of n = 1000 vertices with edge density varied accordingly to sparse graphs (p = 0.1), normal graphs

Cryptanalysis of UCLA Watermarking Schemes

219

(p = 0.5), and dense graphs (p = 0.9). The length of the signature is either 1000 bits or 2000 bits. These parameters are the same as thouse suggested in [9, 10]. The numbers in each lines of the table are measured by watermarking and then dewatermarking 10 random graphs of the same edge probability p. The watermark column shows the number of colors in the watermarked graph coloring solution. The dewatermark column is the number of colors in the dewatermarked graph coloring solution. The last column is the difference between the previous two columns, and it represents the number of additional colors used by our destroy algorithm. G1000,p bits watermark dewatermark additional p = 0.1 k=1000 27.0 27.4 0.4 p = 0.5 ” 109.1 109.6 0.5 p = 0.9 ” 271.3 273.2 1.9 p = 0.1 k=2000 27.0 27.6 0.6 p = 0.5 ” 109.2 109.5 0.3 p = 0.9 ” 272.1 273.2 1.1 From the above table, we see that even in the hardest cases, i.e. when the graph is highly dense, our destroy algorithm uses less than two additional colors to remove the watermark. For all other cases, only one or even no additional colors is needed. In all of our tests, the destroy step runs in under 10 seconds for each graph. This shows that our destroy algorithm uses very small number of colors, and preserves the very high quality of the dewatermarked object. Therefore we demonstrated that it is not necessary to alter the original watermark in order to break a scheme.

3

Watermarking for FPGAs

We now analyze three watermarking and fingerprinting schemes for digital circuits on programmable hardware [3, 4, 5, 6, 7, 8]. While FPGA may not be the largest sector of custom circuits market, it is interesting to see how watermarking for digital circuits works in this case. All these schemes consist of three common stages which we describe bellow: 1. Preparation This step prepares the binary signature string so that it can be embedded into the design. The preparation is a combination of the following operations: compression with a secure hash function, encryption with a secret key, encoding with an error correcting code (ECC), interleaving across ECC blocks. While the application of a secure hash function makes the signature shorter and thus easier to embed, the purpose of the encryption is to whiten out the signature so that it will be harder to detect its presence and location. The ECC and interleaving of ECC blocks make the embedding of the signature more resistant against damages in small number of bits. 2. Embedding This step searches for unused locations in the design, i.e. CLBs in an FPGA that can be used to embed the signature. The possible locations

220

Tri Van Le and Yvo Desmedt

for consideration are: non-functional (unused) CLBs, and multiplexers of unused outputs of functional CLBs. For example, in an unused CLB of the Xilinx XC4000 series, 16 bits can be embedded into its lookup table (LUT). Further, for each output of a CLB, there can be a multiplexer attached to it, in order to select which signal will be copied to the output. Therefore an unused output that has a 2-to-1 multiplexer attached to it can be used to embed 1 bit of information, while an unused output with an attached 4-to-1 multiplexer can contain 2 bits of information. 3. Hiding Since non-functional CLBs and functional CLBs’ unused outputs can be both removed without affecting the digital design, they should be well hidden. The operations available to hide these elements are: a secure hash function to randomly replace the unused CLBs, randomly connecting their inputs and outputs to nearby passing lines, and to dont-care inputs of other CLBs. These techniques make the non-functional CLBs appear like functional ones. In the followings, we describe each of the schemes, from simple to complex ones. For each schemes, we show how to find the locations of the embedded bits and consequently delete them from the FPGA. Since our technique depends only on the particular scheme’s embedding and hiding operations, we just need to present these operations for each scheme, and then present our corresponding deletion algorithm. In our deletion algorithms, the capture of an FPGA configuration can be done, for example, by using image inspection tools [1], or by simply monitoring the bus of the targeted FPGA [4]. However, the later technique is known to work with static RAM devices only. 3.1

Basic Scheme

This scheme is introduced in [5, 6]. It is the first scheme that use the unique characteristics of FPGA to protect digital circuit designs. Embedding The locations to embed the bits are unused CLBs. They are found by inspecting the FPGA configuration. Since unused CLBs are disconnected from other functional CLBs and from the outputs of the FPGA design, they can be found easily using any graph connectivity algorithm. Next, the prepared signature bits are embedded into the lookup tables of the non-functional CLBs. The CLBs are then randomly placed back into the FPGA configuration. The other functional CLBs are simply placed and routed around these unused CLBs. Note that the unused CLBs are disconnected from other functional CLBs, and the outputs of the FPGA. Therefore using any connectivity checking algorithm, we can locate these hidden CLBs efficiently, even after they have been embedded with signature bits and randomly relocated. Below is the deletion algorithm. Deletion Locate CLBs that are disconnected from output pins of the FPGA. Delete these CLBs and output the result.

Cryptanalysis of UCLA Watermarking Schemes

221

It is easy to see that our algorithm completely remove all embedded nonfunctional CLBs that were used to embed the signature. Therefore this simple scheme is easily defeated. 3.2

Intermediate Scheme

This scheme is introduced in [4, 8], and also used in [7]. It differs from the basic scheme in the preprocessing and hiding operations. A secure hash function is applied to the signature before embedding, in order to reduce its size. The locations of the embedded CLBs are also fingerprinted with the identity of the user in order to trace back the origin of mis-appropriation. Additional hiding operations are also put in. Embedding The signature bits are embedded into the unused CLBs. They are found by inspecting the FPGA configuration, and then pseudo-randomly placed back into the FPGA configuration. Instead of routing the other functional CLBs around these embedded CLBs as done in Scheme I, one connects their outputs to dont-care inputs of functional CLBs, and connects their inputs to other functional CLBs’ outputs. This scheme is better than the previous scheme in hiding the non-functional CLBs since they cannot be simply located with connectivity property anymore. Unused CLBs appear as functional ones since their inputs and outputs are used and connected to other CLBs. However, we see that each CLB is a small size finite-state machine, therefore we can find all of its dont-care inputs by searching. Consequently we locate all the non-functional CLBs. Therefore the deletion algorithm is: Deletion – For each CLB in the configuration, and for each input of this CLB: if the output of this CLB does not depend on the value of this input then delete all connections to this input. – Find CLBs that are disconnected from the outputs of the FPGA and delete them. After the first step, all embedded non-functional CLBs are disconnected from the outputs of the FPGA. Hence they are removed in the second step, i.e. the watermarking scheme is broken. This deletion algorithm breaks the scheme of [8] too because this scheme also uses the same embedding and hiding algorithm. 3.3

Advanced Scheme

This scheme is proposed in [3]. Since non-functional CLBs can be located as we have seen in the previous two schemes, this scheme tries to embed the signature into functional CLBs too so that users cannot simply delete all unused CLBs.

222

Tri Van Le and Yvo Desmedt

Embedding For all unused outputs of functional CLBs that have a multiplexer attached to the output, embed the signature bits into the multiplexer. If the multiplexer is a n-to-1 multiplexer then log2 n bits can be embedded. Connect the unused outputs to dont-care inputs of other CLBs. Nevertheless, similarly to the second scheme, unused outputs can be located since they are not connected to any CLB. Therefore we have the deletion algorithm as follow. Deletion – For each CLB in the configuration, and for each input of this CLB: if the output of this CLB does not depend on the value of this input then delete all connections to this input. – Find all CLB outputs that are not connected to any other CLB inputs nor the FPGA’s outputs. – Zero the multiplexers attached to each of these outputs. – Remove all CLBs that are isolated from the output of the FPGA. – Output the resulting board. 3.4

Discussions

From the three preceding subsections, we see that a real life attack consists of three steps: reverse engineering low-level hardware to obtain corresponding high-level design, running the deletion algorithm, and recompiling the newly trimmed design back into hardware. In contrast, a typical design process more or less consists of the following steps: specifying, constructing, debugging, and compiling the design into hardware. Thus by hacking, a crook will gain the cost of specifying, constructing, and debugging the design. However, he or she will have to pay for the cost of reverse engineering the hardware (plus the cost of running the deletion algorithm, but this cost is negligible compared to other steps, as we have already seen in previous subsections). Assuming that the thief is rational, so an attack is practical only if there are incentives for the thief to hack. In this case, that means the cost of reverse engineering should be less than the cost of specifying, designing and debugging a circuit from scratch. While this is indeed the case for FPGA circuits, which have relatively simple design process, one expects that it may not be the case for a complex non-FPGA circuit design project, which typically has much more design layers. For this later case, the cost of reverse engineering should be much higher. Hence attacks based on reverse engineering may not be attractive in this new case. However, it may be surprise that in practice one should not take this as a motivation or additional assurance to use any watermarking scheme in the later case because in such case one does not need any watermarking at all. The reason is that in such case, one simply keeps the original design (which was usually done in practice already) as a legitimate proof of ownership. Because recovering high level design from hardware, i.e. reverse engineering, is more costly than designing a circuit oneself, the attacker will either have no proof of ownership (since he can

Cryptanalysis of UCLA Watermarking Schemes

223

not do reverse engineering), or he must have obtained one by designing it from scratch himself (since he may be able to do reverse engineering but it is more costly). This is exactly what one wants from a watermarking scheme. Therefore whether the owner does in fact own the design is not a real problem in this later case. In reality, this is true not only for digital designs but also for other non-tech objects such as a magazine article or a photo. For example, the spec and the creation history (i.e. successive versions, editor’s comments, email correspondence between publisher and author, cancelled royalty cheques, etc.) are indeed good proofs of originality. Therefore, we should stress that watermarking for proving ownership is only needed in the case where reverse engineering is actually easier than designing. There are conjectures that the above three schemes may be quickly fixed by running a pseudo random generator through a live data scheme twice, where the later run will clear all the effects of the earlier one. This may make the non-functional CLBs that were used as the pseudo-random generator appear functional. While this heuristics is interesting, we will show later in the appendix that it does not work for this case. It may not be a trivial task to fix these schemes.

4

Conclusion

We shown that several constraint-based watermarking schemes for intellectual property protection of digital designs can be broken. We used different approaches to analyze these schemes. In the first scheme, we did not remove the signature but modified it so that arbitrary signature could be extracted, thus nullified the creditability of the original watermark. This also made it more difficult for the owner to trace back to the origin of mis-appropriation of his design. In the other schemes, we completely located the embedded signature and then removed it. These two methods are quite complement of each other. In the first scheme, we shown how to destroy the watermark without knowing where it is. While in the other schemes, we shown how to remove the watermark by first locating them. This shows that one should not base the robustness of a watermark on the secrecy of its location and content alone. We also shown further that in many practical situations, watermarking may not be the best solution to proving ownership of intellectual properties.

Acknowledgement We are thankful for anonymous comments that helped improving the presentation of this paper. We thank Professor Ross Anderson for interesting discussions regarding real life examples of ownership proofs that do not involve watermarking at all.

224

Tri Van Le and Yvo Desmedt

References [1] Ross Anderson and Markus Kuhn. “Tamper Resistance - A Cautionary Note”, 1996 USENIX Electronic Commerce Workshop, pp. 1-11, Oakland, California, November 1996. 220 [2] Ross Anderson and Fabien Peticolas. “On The Limits of Steganography”, IEEE Journal on Selected Areas in Communications, vol. 16, pp. 474-481, May 1998. 214 [3] Andrew B. Kahng, John Lach, William H. Mangione-Smith, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak, Paul Tucker, Huijuan Wang, and Gregory Wolfe. “Watermarking Techniques for Intellectual Property Protection”, 35th ACM/IEEE DAC Design Automation Conference, pp. 776-781, San Francisco, CA, June 1998. 213, 214, 215, 219, 221 [4] John Lach, William H. Mangione-Smith, and Miodrag Potkonjak. “Fingerprinting Digital Circuits on Programmable Hardware”, 1998 Information Hiding Workshop, pp. 16-31, Portland, Oregon, April 1998. 213, 214, 215, 219, 220, 221 [5] John Lach, William H. Mangione-Smith, and Miodrag Potkonjak. “FPGA Fingerprinting Techniques for Protecting Intellectual Property”, 1998 Custom Integrated Circuits Conference, Santa Clara, CA, pp. 299-302, May 1998. 213, 214, 215, 219, 220 [6] John Lach, William H. Mangione-Smith, and Miodrag Potkonjak. “Signature Hiding Techniques for FPGA Intellectual Property Protection”, 1998 International Conference on Computer-Aided Design, pp. 186-189, San Jose, CA, November 1998. 213, 214, 215, 219, 220 [7] John Lach, William H. Mangione-Smith, and Miodrag Potkonjak. “Robust FPGA Intellectual Property Protection Through Multiple Small Watermarks”, 36th ACM/IEEE Design Automation Conference, pp. 831-836, New Orleans, LA, June 1999. 213, 214, 215, 219, 221 [8] John Lach, William H. Mangione-Smith, and Miodrag Potkonjak. “Enhanced Intellectual Property Protection for Digital Circuits on Programmable Hardware”, 1999 Information Hiding Workshop, pp. 331-345, Dresden, Germany, September 1999. 213, 214, 215, 219, 221 [9] John Lach, William H. Mangione-Smith, and Miodrag Potkonjak. “Hiding Signatures in Graph Coloring Solutions”, 1999 Information Hiding Workshop, pp. 391-408, Dresden, Germany, September 1999. 213, 214, 215, 216, 217, 219 [10] G. Qu and Miodrag Potkonjak. “Analysis of Watermarking Techniques for Graph Coloring Problem”, 1998 International Conference on Computer-Aided Design, pp. 190-193, San Jose, CA, November 1998. 213, 214, 215, 217, 219

A

Appendix

It is believed by some that running a pseudo random generator through a live data scheme twice, where the later run clears all the effects of the earlier one, will make the non-functional CLBs appear as functional ones. We show now that this fix unfortunately does not work for this case. The reason is that by having the output from the pseudo random generator used twice, one can easily detect which CLBs are used to construct the pseudo random generator. If the

Cryptanalysis of UCLA Watermarking Schemes

225

second run of the pseudo-random values was generated by the same CLB as in the first run then one can easily detect these CLBs by simple trial and error removing as we will show later. So in order for this fix to succeed, one should have the second run of the pseudo-random values in different CLBs. However, this makes the two types of CLBs pop out because in a typical circuit, not very often there are two CLBs that always have identical outputs. Therefore the real attack is follows: first capture the configuration of the FPGA, then simulate the execution of FPGA with a large number of random inputs. If there are two CLB connections such that the values sent over each of them are identical to each other all the time, then we know that these two may be outputs from the mentioned pseudo random generator. Hence we can safely disconnect them. If later we discover that by disconnecting these connections, the circuit does not work correctly anymore, i.e. does not output the same values as before, then we know that we made a mistake and reconnect them. Using this trial and error attack, we can remove all the output from the hidden pseudo random generators, and then using earlier breaking algorithm, we eventually remove all of them. Note that our attack is different from the usual attacks in which one locate the watermark in order to remove them. Here we test if we can remove them in order to detect the watermark. Note also that one can always generalize the above approach so that the same random output does not occur twice anymore, but rather occurs as related, for example. This new relation (instead of the previous equality relation) is needed to ensure that the output of the modified circuit stay unaltered. However, we believe that all such approaches to fix the above schemes will eventually be broken because it is quite hard to hide the relation between the two runs of the pseudo random generator. Therefore it will be a non trivial task to fix these schemes.