HK1138449A - Tracing copies of an implementation - Google Patents

Description

Tracing copies of an implementation

Technical Field

The present invention relates to a system for facilitating the tracking of copies of an implementation of a computational method.

Background

The internet provides users with convenient and ubiquitous access to digital content. The use of the internet as a distribution medium for copyrighted content creates a strong challenge to secure the interests of the content provider. In particular, there is a need to grant copyright and a management model to a content provider. Increasingly, Consumer Electronics (CE) platforms are run using processors loaded with suitable software. Such software includes a main part of the functionality for rendering (reproducing) digital content, such as audio and/or video. The control of the reproduction software is a method of enhancing the interests of the content owner, including the term and condition under which the content is used. Many CE platforms (except PCs and PDAs) were turned off in the past, and today more and more platforms are turned on at least partially. Particularly for PC platforms, some users are considered to have complete control over the hardware and software that provides access to content and a significant amount of time and resources to attack and bypass any content protection mechanisms. Thus, content providers must route content to legitimate users across hostile networks to organizations where not all users or devices are trusted.

To prevent piracy of digital content (e.g., movies), it is often sent to the user in an encrypted form. In order to keep the distribution costs low, the content is typically encrypted once, i.e. each legitimate user obtains the same key with which he/she can decrypt the content. This implies a weakness in that an attacker can distribute keys to unauthorized users, which undermines the protection mechanism.

"White-Box Cryptography and an AES immunization" by Stanley Chow, Philip Eisen, Harold Johnson and Paul C.VanOorshot, in Selected Areas in Cryptography: 9th Annual International works shop, SAC 2002, St.John's, Newfound, Canada, August15-16, 2002, hereinafter "Chow 1", and Stanley Chow, Phil Eisen, Harold Johnson and Paul C.Van Oorshot "White-Box presentation for DRM Applications", in Digital rights management: ACM CCS-9 Workshop, DRM 2002, Washington, DC, USA, November 18, 2002, hereinafter "Chow 2", discloses a method that attempts to hide the key by obfuscating the key in the network of look-up tables. This makes it more difficult for an attacker to extract and distribute keys.

Disclosure of Invention

An improved system for facilitating the tracking of copies of an implementation of a computing method would be advantageous. To better explain this idea, in a first aspect of the invention, a system is proposed comprising

A network generator for generating a network of look-up tables representing the steps of the calculation method, the network being formed by using the output values of a first look-up table as input values of a different second look-up table;

a personalizer for generating a plurality of different versions of the network of look-up tables by changing at least one value in the network of look-up tables, the end result of the version corresponding to the relevant field of input values being substantially the same for each version;

correlators for associating respective versions with respective base stations or users of the base stations.

The personalizer uses the inherent redundancy in a network of look-up tables to create different versions of the network of look-up tables. When a (potentially illegitimate) copy of a version is found, the base station or user associated with the version may be established because the versions are different and each version is associated with a respective base station or user of a base station.

The variations employed to produce different versions refer to versions of the watermark. The network generator and the personalizer may be the same, i.e. one unit may produce all versions. The changed value may be a value in one of the look-up tables. It will be appreciated that the structure of the network (i.e. the structure defining which output of the look-up table is provided to which input of the look-up table) may be parameterized. In this case, the value of the change may be related to a parameter defining the structure.

In an embodiment, the calculation method (602) comprises an encryption policy and an encryption key, the network generator (604) and the personalizer (606) being arranged for generating a network of look-up tables capable of performing the encryption policy using said encryption key. The system is particularly useful in this case because the encryption keys are often quite valuable. Such illegal distribution of keys is undesirable. When a (illegally distributed) copy of a version of the look-up table network is found, the system helps to identify the associated base station or user. In the event that an apparently reassigned version copy is found, action may be taken with respect to the associated user.

In an embodiment, the personalizer is arranged for creating a white-box implementation of the computing method. White-box implementations of algorithms using a network of look-up tables are known from e.g. Chow et al. Redundancy and in particular obfuscation in these white-box implementations makes it easier to apply changes to networks that are difficult to isolate and/or remove by third parties (i.e., attackers).

In an embodiment, the output encoding and/or input decoding of the white-box implementation differs in different versions. A relatively simple way of generating variations to create different versions of a network of look-up tables is to encode the output of one of the look-up tables in different ways and decode it in the next look-up table in the network of look-up tables.

In an embodiment, the personalizer is arranged for obfuscating the white-box implementation with operators, which are selected differently for different versions, wherein the operators are integrated in a first plurality of look-up tables in the network and inverses of the operators are integrated in a second plurality of look-up tables in the network.

This makes it relatively complicated for an attacker to remove the watermark completely, since coordinated changes in multiple look-up tables or coordinated changes to the network structure are required. Due to the implementation of multiple lookup tables acting on operators, operators are integrated in multiple nets. However, the results of the operators may not be directly visible in the white-box implementation, as the look-up table provides additional coding of the intermediate and/or final structure.

In an embodiment, at least one of the first plurality of look-up tables or at least one of the second plurality of look-up tables has an input and/or output encoding which is not cancelled by its respective predecessor and/or successor in the network with respect to the data stream passing through the network. This makes it more difficult for an attacker to remove the watermark.

In an embodiment, the operator is a linear hybrid bijective and at least one of the input and/or output encodings is non-linear. The combination of linear mixed bijective and non-linear input and/or output coding is ubiquitous for white-box implementations. The linear hybrid bijections may be efficiently integrated in a plurality of look-up tables. The non-linear input and output encodings make white-box implementations more difficult to break.

In an embodiment, the personalizer is arranged for creating versions in different equivalence classes using operators, wherein the equivalence classes comprise operators whose corresponding networks of look-up tables are obtainable from each other by providing modifications from a predetermined set of modifications to the input and/or output encodings. Providing modifications (including permutations) to the input and/or output code is considered work that an attacker can reach. Thus, the watermark should be "resistant" to modifications that can still be identified with the associated user after such modifications have been made. Each equivalence class is associated with a respective base station or user because each version is associated with a respective base station or user.

In an embodiment, the personalizer is arranged for creating the versions in different equivalence classes, wherein the equivalence classes comprise versions obtainable from each other by providing modifications from a predetermined set of modifications to the versions. The set of predetermined modifications represents those modifications deemed to be within reach of the attacker. The watermark should be "resistant" to modifications that are within the reach of such an attacker. If the versions are in different equivalence classes, the watermark and associated user may still be identified after such modifications have been applied. Preferably, at most one version is generated in each equivalence class. The respective equivalence classes are associated with respective base stations or users, as respective versions are associated with respective base stations or users.

One embodiment includes an output for transmitting versions of the network of look-up tables to an associated base station or user via a single medium. This allows the base station or user to conveniently receive the network of look-up tables via a single medium. The network does not need to be pre-programmed in the base station. In this way, versions that are changed differently over time can be associated with and easily transmitted to various base stations/users without using a second medium or requiring any hardware or firmware changes to the base station. This makes the system more efficient because the base stations can be pre-programmed without being affected by changes made to the individual versions. Optionally, the base stations are identical. Although the version may be (illegally) distributed between users, the origin of the (illegally) distributed version may be tracked, as the version is associated with the base station or the user of the base station to which the network version is first transmitted using the medium. Still, too simple (illegal) allocations can be prevented by sending the version of the look-up table network in encrypted form.

In an embodiment, the system is for controlled distribution of content to a plurality of base stations, and the calculation method comprises a decryption method, the system further comprising

An encryptor for encrypting a version associated with a user using a user-specific encryption key associated with the user to obtain an encrypted version;

a content preprocessor for encrypting the content according to an encryption policy and an encryption key to obtain encrypted content;

an output for providing the encrypted version and the encrypted content to a user.

This embodiment describes a special application case. The versions may be encrypted using a user-specific key and provided to the respective users. Alternatively, the version may be sent without encryption, such as via a secure channel or medium. In another embodiment, a portion of the network of look-up tables is pre-fixed and already present at the user, and only the remaining portion of the network of look-up tables is provided to the user.

One embodiment includes a system for performing computations for a user, comprising

A data processing unit for applying a network of look-up tables representing steps of a calculation method to data, the network being formed by using output values of a first look-up table as input values of a different second look-up table;

the network of look-up tables forming one version of a network of look-up tables of a plurality of different versions obtained by varying at least one value in the network of look-up tables, the final result of the calculation method corresponding to the relevant field of input values being substantially the same for each version;

versions, associated with respective users.

This may be implemented in a base station or user terminal to process data according to the version of the look-up table network.

One embodiment includes a system for identifying a copy of an implementation of a computational method, wherein the implementation includes a network of look-up tables representing steps of the computational method, the network formed by using output values of a first look-up table as input values of a different second look-up table;

the network of look-up tables being one version of a network of look-up tables of a plurality of different versions obtained by changing at least one value in the network of look-up tables, the final result of the calculation method of the relevant field corresponding to the input value being substantially the same for each version;

the system comprises:

a comparator to compare at least one lookup table in the implementation with at least one version.

This helps identify the user associated with the particular version.

One embodiment includes an equivalence class builder to build an equivalence class corresponding to a version in the implementation, wherein an equivalence class includes versions obtained from a starting version by applying modifications from a set of modifications deemed to be within reach of an attacker to the starting version. This helps to identify the user even after the watermark version has been changed.

One embodiment includes a method of facilitating tracking users of copies of an implementation of a computing method, the system comprising

Generating a network of look-up tables representing the steps of the calculation method, said network being formed by using the output values of a first look-up table as input values of a different second look-up table;

generating a plurality of different versions of a network of look-up tables obtained by varying at least one value in the network of look-up tables, the output values of the versions corresponding to the relevant fields of input values being substantially the same for each version;

each version is associated with a respective user.

One embodiment includes a method of identifying a copy of an implementation of a computational method, wherein the implementation includes a network of look-up tables representing computational method steps, the network (28) being formed by using output values of a first look-up table (20) as input values of a different second look-up table;

the network of look-up tables is one version of a network of look-up tables of a plurality of different versions obtained by changing at least one value in the network of look-up tables, the final result of the calculation method of the relevant field corresponding to the input value being substantially the same for each version;

the method comprises the following steps:

comparing at least one lookup table in the implementation to at least one version.

One embodiment includes a computer program product comprising instructions for causing a processor to perform any of the methods described above.

WO 01/31419 discloses a computer-implemented method in which information is encrypted with a key having a personal value and known to the user of the client to prevent the user and others from sharing the key.

Drawings

These and other aspects of the invention will be further elucidated and described with reference to the drawings, in which:

fig. 1 is a diagram illustrating an AES loop operation;

FIG. 2 is a diagram showing an example of obfuscating a table;

FIG. 3 is a diagram showing loops of columns in a white-box AES implementation;

FIG. 4 is a diagram showing a mapping embodied in a type Ia table;

FIG. 5 is a diagram showing a mapping embodied in a type II table;

FIG. 6 is a diagram showing a mapping embodied in a type III table;

FIG. 7 is a diagram showing a mapping embodied in a type IV table;

FIG. 8 is a diagram showing a map embodied in a type Ib table;

FIG. 9 is a diagram showing information bit streams from one look-up table to the next in a network of look-up tables;

FIG. 10 is a diagram showing an embodiment; and

fig. 11 is a diagram illustrating an embodiment.

Detailed Description

White-box cryptography is concerned with implementing block ciphers on a fixed key K so that it is difficult for an attacker to extract the key K from the implementation. The attack pattern identified in white-box cryptography is a white-box attack pattern. In this attack mode, the attacker is considered to have sufficient access to the software and sufficient control over the implementation environment.

One embodiment is directed to a conditional access system for pay TV. The content provider propagates the content encrypted by AES and the content key K. One of the problems that must be solved with respect to conditional access systems is how to distribute the content key K for decrypting the content for the subscriber and not for others. Two methods are described below. First, a simple approach is to keep the content key K fixed over time and only provide the key K to the subscriber. However, this implementation has the following two disadvantages. The first drawback is that we cannot log off the user. As long as the key K is in possession, the user can always decrypt the content. A second drawback of this simple method is that the risk that an attacker can find it is constantly increasing due to the long use of fixed keys.

The second method works as follows. The content key is changed periodically, for example daily or weekly. Each subscriber s obtains a unique private key k_sAnd for each subscriber s the key K is given by its private key K_sAnd (4) encrypting. Encrypted set of keys K E_ks(K) Is a legitimate subscriber } is propagated along with the encrypted content. Then only the legitimate subscriber can obtain K and then decrypt the content. Importantly, the private key k_sHiding is good. This is typically done in hardware. In this way, the user can be logged off. In order to log out the user s, it is not provided with an encrypted content key that will change next time. Thus, if the content key changes from K to K', then E is not provided to user s_ks(K’)。

Although the second method is superior to the first, it still creates vulnerable conditions due to subsequent attacksAnd accessing the system. One of the subscribers may obtain the content key K. This may be the case, for example, because subscriber s can check the decryption algorithm and extract the key from it or because s can determine his/her own private key k_s. When the content key K is subsequently illegally distributed, the content provider cannot identify a malicious subscriber responsible for the distribution. As a result, the content provider has to take drastic actions, such as replacing the decryption algorithm and/or their private key k for all subscribers (including legitimate subscribers)_sThe implementation of (1).

In an embodiment, the implementation of the decryption algorithm for decrypting content with the key K is replaced by a white-box implementation substantially as described by Chow et al. In this white-box implementation, the AES decryption algorithm is performed by a set of look-up tables that are obfuscated by encoding their inputs and outputs. Furthermore, tables for different subscribers are provided with different codes. As a result, each subscriber gets a different white-box implementation. However, all these white-box implementations have the same function (it performs decryption with the key K). If the content key K changes, the user is provided with a new white-box implementation (i.e., with a new set of look-up tables).

If the white-box implementation is reliable enough, it is difficult for an attacker to extract and publish the underlying key K. Instead, he/she has to publish the full white-box implementation (i.e. the set of look-up tables). However, if a malicious subscriber publishes his/her white-box implementation, the content provider can track him/her because he has a unique white-box implementation. As a result, the content provider can revoke the attacker, i.e. revoke the attacker's subscription. This means that for other content encrypted by a different key K ', an attacker will not receive a white-box implementation of the decryption algorithm performed with key K'.

By selecting different encodings, multiple white-box implementations can be created with the same functionality (e.g., they all perform AES decryption with the key K). This difference can be used for traitor tracing: each user is assigned a different white-box implementation variable so that given a white-box implementation, the origin of the white-box implementation can be identified by examining the code. Note that the encoding of the white-box implementation here acts as a forensic watermark.

Next, some embodiments are described using the AES white-box implementation proposed by Chow et al. However, the embodiment is not limited to AES. Those skilled in the art can make the necessary changes to apply the disclosed techniques equally to other encryption schemes, particularly to white-box implementations thereof. Moreover, the techniques may be used outside of the cryptographic context, as long as the algorithm includes applying a network of look-up tables, as will be apparent to those skilled in the art.

White-box implementation of AES

AES is a block cipher with a block size of 128 bits or 16 bytes. The plaintext is divided into 16-byte packets that form the initial state of the encoding algorithm, while the final state of the encoding algorithm is the ciphertext. To conceptually explain AES, the status bytes are organized into a matrix of 4 x 4 bytes. The AES comprises a plurality of loops. Each loop consists of similar processing steps operating on bytes, rows or columns of the state matrix, where each loop uses a different loop key.

Fig. 1 shows some of the main processing steps of an AES loop. The processing step comprises:

each byte of AddRoundKey 2-state is xored by a byte of the loop key.

SubBytes 4-byte-by-byte permutation using a lookup table.

Each row of the ShiftRows 6-state is rotated by a fixed number of bytes.

MixColumns 8-use of GF (2)⁸) Each column is processed by modulo multiplication.

The steps SubBytes 4, ShiftRows 6 and MixColumns 8 are all independent of the particular key used. The key is adopted in step AddRoundKey 2. In addition to step Shift Rows 6, the processing steps can be performed on each column of the 4 x 4 state matrix without knowledge of the other columns. Thus, they can be viewed as 32-bit operations, since each column includes 4 8-bit values. The dashed line 10 shows that the process is repeated until the required number of loops has been performed.

Each of these steps or combinations of steps may be represented by a look-up table or a network of look-up tables (S-boxes). The full loop of AES may also be replaced by a network of look-up tables. For example, the AddRoundKey step may be performed by simply xoring with the loop key, while SubBytes, ShiftRows, and MixColumns steps are performed using a lookup table. However, this means that the key is still visible to an attacker in the context of a white-box attack. The AddRoundKey step can also be embedded in a look-up table, which makes it more difficult to find the key.

Figure 2 shows a method that makes it more difficult to extract the key. Let X and Y be two functions. Consider the operation Y omicron x (c) Y (x (c)), where omicron means a function combination, as shown in diagram 12 in fig. 2, where c is an input value, e.g., a 4-byte state column. However, the method is applicable to any type of input value c. The mapping of X and Y may be implemented as a look-up table that may be stored in memory, however, when they are stored in memory, the values may be read by an attacker. Diagram 14 shows how the contents of the look-up table are obfuscated by using an input encoding F and an output encoding H. As shown, corresponds to X ° F ″^-1The lookup table of H ° Y is stored instead of X and Y, which makes it more difficult to extract X and Y. Diagram 16 shows how an additional, e.g. random, bijective function G is added so that intermediate results of the two tables can also be encoded. In this case, two tables are stored in memory: x ═ G omicron X omicron F^-1And Y ═ H omicron Y omicron G^-1. This is again shown in diagram 18:

Y′οX′＝(HοYοG^-1)ο(GοXοF^-1)＝Hο(YοX)οF^-1，

where X and Y are functions suitable for implementation by a look-up table. In this document, - "refers to the conventional set of functionsAnd (i.e., for any two functions f (x) and g (x)), is defined as f omicron g (x) f (g (x)). Likewise, networks comprising more than two functions may also be encoded. The actual table encoding X and Y passes H DEG Y DEG G^-1Combining in a single lookup table and G [ X ] F^-1The combination is obfuscated in a single look-up table. As long as F, G and/or H remain unknown, the attacker cannot extract information about X and/or Y from the look-up table, and therefore cannot extract the key on which X and/or Y is based. Other cryptographic algorithms, including DES and Rijndael (AES being a special example of this) may also be encoded as look-up tables (expressing concatenation or network), which may be obfuscated in a similar way as described above. This can also be used for ciphers based on, for example, a permute-permutation network or Feistel network. The invention is not limited to the mentioned exemplary cryptographic algorithms.

Chow1 discloses a method that attempts to hide a key by encoding its table with random bijections representing combinations rather than individual steps. Preventing private key extraction has the advantage of preventing attackers from extracting critical material that can cause software protection targets to be bypassed on other machines, or from publishing "global hacking" of security measures that effectively create a large user base that destroys the entire installed software. Given the fact that the restrictions are a purely software solution and enemy-leaders, it provides a greater degree of protection. In the approach of Chow1, the key is hidden by (1) using a table for combining rather than a single step; (2) encoding these tables by random bijections and (3) extending the cryptographic boundaries outside the cryptographic algorithm itself into the containing application forces attackers (as opposed to engineers) to learn significantly larger portions of code to achieve their goals. Chow1 discusses a fixed key approach: the key is embedded in the implementation by a local evaluation of the key so that no key input is required. Local evaluation means that the expression relating to the key is evaluated as much as possible and the result is placed in the code rather than the whole expression. An attacker may extract the implementation of the private key and use it in place of the key, however cryptography is typically a component of a larger containing system that can be manipulated or encoded to provide input to the cryptographic component for which it is designed, but an adversary may find it difficult to remove. Referring to the steps of the code table, since the codes are arbitrary, the result is meaningful only when the output code of one step matches the input code of the next step. For example, if step X is followed by step Y (a calculation yielding Y ° X), the calculation may be encoded as:

Y′οX′＝(HοYοG^-1)ο(GοXοF^-1)＝Hο(YοX)οF^-1。

thus, Y ° X is properly calculated, although the input needs to be encoded with F and the output needs to be encoded with H^-1And (6) decoding. The steps are represented separately as tables corresponding to Y 'and X' so that F, G and H and X and Y are hidden.

In addition to this aliasing step, Chow1 uses a diffusion step using linear transformations to further disguise potential operations. The term hybrid bijective is used to describe the linear bijective mentioned above. The implementation of Chow1 takes input in a controllable form and produces output in a different controllable form, making AES resistant to white-box attack environments (WBAC) difficult to separate from its containing application.

The white-box AES implementation may be described as follows. The input to the AES encryption and decryption algorithm is a simple 128-bit packet. The packet is represented by a 4 x 4 matrix containing 16 bytes. AES typically consists of 10 loops of AES-128. Each loop updates a sixteen byte set which forms the AES state, so each AES loop processes 128 bits. AES-128 uses a 128-bit key. This key serves as the input to an algorithm that converts the key into a different 128-bit ring key. The base loop includes four parts:

·SubBytes

·ShiftRows

·MixColumns

·AddRoundKey。

this sequence of operations is applicable to AES encryption. Although the standard operation order in AES decryption is different, the AES decryption algorithm may be rewritten to have the same operation order as AES encryption.

Before the first loop, an additional AddRoundKey operation occurs, while in loop ten, the MixColumns operation is omitted. The only part of the key used is AddRoundKey, the other three steps do not do anything with the key. In execution, the boundary of the loop is changed to integrate the AddRoundKey step and the SubBytes step of the next loop into one step. The loop starts with addroundkeys and SubBytes, followed by ShiftRows, and finally MixColumns.

First, the key is hidden by combining the SubBytes step and AddRoundKey into one step. This makes the key itself no longer visible. Because the key is known in advance, operations involving the key may be evaluated in advance. This means that the standard S-Boxes used in the step SubBytes can be replaced by S-Boxes for private keys. To generate the private key example of AES-128, the key is incorporated into the SubBytes conversion by creating sixteen 8 x 8 (i.e., 8-bit input, 8-bit output) look-up tables T_i，j ^rIt is defined as follows:

where S is AES S-Box (reversible 8-bit mapping), k_i，j ^rIs the AES sub-key byte at position i, j of the 4 x 4 matrix, which represents the loop key of the loop r. These T-Box's combine the SubBytes step with the AddRoundKey step of the previous loop. The loop 10T-Box absorbs the key after whitening as follows:

where sr (i, j) refers to the new location of cell i, j after the ShiftRows step. The number of all T-Boxes is 10 × 16 ═ 160. However, the key can be easily removed from T-Box because S^-1Are well known. This makes additional encoding necessary. The linear transformation is used to diffuse the input to T-Boxes. These linear transformations are called hybrid bijections and can be represented as an 8 × 8 matrix of GF (2). The mixed bijections are inverted by previous calculations to eliminate their effect.

Fig. 3 shows the tables involved in the white-box AE8 loop for one 32-bit column of states (after ShiftRows are employed). The names of different types of tables are introduced here. This is described in more detail hereinafter. Before the loop, each byte of the 128-bit state is provided to a respective type Ia table. This results in individual 128-bit values that are xored using a network of type IV tables to provide a 128-bit output that is divided into four 32-bit values. Now, the first loop is started. The processing steps for each 32-bit value are outlined here. Four bytes of a 32-bit value are input to four different type II tables 20. Each of the four type II tables 20 produces a 32-bit output. These outputs are bitwise xored using the type IV table 22. Each type IV table 22 performs a 4-bit bitwise xor. By appropriately connecting the inputs and outputs of the type IV table, a bitwise xor of the four 32-bit outputs may be achieved, as will be apparent to those skilled in the art. The result of this step is a 32-bit value. Each of the four bytes of the value is provided to a respective type III table 24. Each type III table 24 provides a 32-bit output. These outputs are bitwise xored again using a network of type IV table 26 similar to that of type IV table 22. The output is a 32-bit value indicating a column of states. Loops 2 through 9 are similar to the first loop. Each byte of the 128-bit value is applied to the type Ib table; the results are xored using a network of type IV tables. The last loop (usually the tenth loop) is absorbed by the outer code.

Fig. 4 shows a type Ia table 100. Fig. 5 shows a type II table 200. Fig. 6 shows a type III table 300. Fig. 7 shows a type IV table 400. Fig. 8 shows a type Ib table 500.

The use of a hybrid bijection is as follows. The AES state is represented by a 4 x 4 matrix containing bytes. The MixColumns step operates column (4 bit cells) at a time. Consider a 32 x 32 matrix MC. If it is represented by a table, the table may cost 2³²X 32-137438953472 bit 16 GB. To avoid such large tables, the matrices are grouped into four parts.

The MCs are grouped into four 32 x 8 parts, the MCs₀、MC₁、MC₂、MC₃(packet 208). 32-bit vector x ═ x₀，...，x₃₁) Multiplication with MC is performed by dividing the bits of x into four bytes and multiplying each portion of MC with one of the bytes, resulting in four 32-bit vectors (z₀，...，z₃). The next three 32-bit xors give the final 32-bit result z. The total cost of four tables is 4 x 2⁸X 32-32768 bits 4 KB.

The three EXCLUSIVE-OR will be divided into 24 4-bit EXCLUSIVE-ORS, each represented by a look-up table that may be encoded, with appropriate concatenation (e.g., ((z [0, 0)]，z[0，1]，z[0，2]，z[0，3])+(z[1，0]，z[1，1]，z[1，2]，z[1，3]))‖((z[0，4]，z[0，5]，z[0，6]，z[0，7])+(z[1，4]，z[1，5]，z[1，6]，z[1，7]) Iib), where iib represents link binding and + represents exclusive or. By using the exclusive-or of these bands and subdivisions, each step is represented by a small look-up table. In particular, for i ═ 0_iComputed using 8 x 32 tables and a 4-bit xor becomes 24 8 x 4 tables. Fig. 7 shows how the input decode 402 and the output encode 406 are placed around the xor 404. These codes are typically non-linear 4 x 4 bijections that are randomly selected. The exclusive-or table is referred to as a type IV table 400. The type IV table takes as input 4 bits from each of the previous two calculations. Those calculated output encodings 212 match the input decoding 402 of the type IV table to invalidate each other. The choice of 4 x 4 non-linear bijections depends on the size of the table. In this case, the type IV table is only 2⁸X 4-bit 128 bytes. 24 tables are required, costing a total of 3 KB. If the XOR is not partitioned, three XOR tables may be needed, which compute a 32-bit XOR. T-boxes 206 and 8 x 32 tables208 may be represented as separate look-up tables. Alternatively, they may be combined to create a new 8 x 32 table 200 that computes SubBytes and AddRoundKey transformations as well as partial MixColumns. This saves both space (to save the T-boxes) and time (to perform the table look-up).

In dividing MC into MC as above_iPreviously, MC was pre-multiplied by a 32 × 32 hybrid bijective MB, as indicated by reference numeral 210 in fig. 5, and selected as a non-individual matrix with 4 × 4 sub-matrices in the overall arrangement. The use of a hybrid bijection increases the number of possible structures for a particular table.

Fig. 5 shows an 8 × 32 type II table 200, including 4 × 4 input decoding 202 and 4 × 4 output encoding 212. These output encodings and input decodings are non-linear 4 x 4 bijections that must match the input decodings and output encodings of type IV table 400. Type II table 200 is followed by type IV table 400. To invert an MB, an extra set of tables is used to compute the MB^-1. Let (x'₀，...，x’₃₁) As an input to MixColumns, let (z)₀，...，z₃₁) As output after MixColumns. Let (z'₀，...，z’₃₁)^TAs a result of multiplication by MB. (z'₀，...，z’₃₁)^TServing as an input to type III table 300. Note that input decoding and output encoding need not be considered here, since the output encoding of a table is eliminated by the input decoding of the next table. In type III Table 300, MB^-1The four input mixing bijections 204 of the four type II tables 200 taken 304 and the next loop are inverted 308.

Fig. 6 shows an 8 × 32 type III table 300, including 4 × 4 nonlinear input decoding and 4 × 4 nonlinear output encoding. These tables are followed by the corresponding type IV table 400.

One loop of data manipulation involves manipulation of a 128-bit state matrix. The data operations performed on each of the four 32-bit bands of the 128-bit state matrix are as follows. The 32-bit band is divided into 4 8-bit bytes. Each of the four bytes is sent to a different type II table 200, resulting in four 32-bit output values. These values must be exclusive-ored using the obfuscated type IV table 400. To this end, each 32-bit output value is divided into 8 4-bit tuples and the appropriate tuple pairs are input to the respective type IV tables so that an xor of the four 32-bit output values is obtained in encoded form.

The 32-bit generated encoded xor result is again divided into bytes, and each byte is input to a different type III table 300. The input decoding of each tuple of the type III table 300 corresponds to the output encoding of the type IV table last used. The type III table again produces four 32-bit output values, which are again xored by the obfuscated type IV table 400.

In summary, the loop is executed by a lookup table. The look-up tables for a single loop are networked as follows. The data is sent to the type II table. The output of these tables is sent to a network of type IV tables representing the encoded xor. The output of these networks is sent to the type III table, which cancels the hybrid bijective coding inserted by the type II table. The encoded output of the loop is finally obtained by sending again the output of the type III table to the network representing the type IV table encoded xor.

Furthermore, the white-box implementation includes a beginning (type Ia table 100) and an ending (type Ib table 500) type I table, for cancelling and inserting outer-coding, respectively. The type Ia table 100 may be used for link combining using the mapping as shown in fig. 4 by providing a single table lookup. In concatenated combining, the 4-byte input decode 102 occurs first. Then, 8-bit to 128-bit double fire 104 occurs; the bijective enables encoding of the input and output of the network; this mapping is not done elsewhere in the program. The result of the bijective 104 is divided into 16 8-bit fragments, to which respective 8-bit bijections 106 are provided. Finally, output tuple encoding 108 is employed. As described above, the concatenation of the mappings 102, 104, 106, and 108 is pre-evaluated and the final results are tabulated in a look-up table. This results in a table with a maximum of 256 entries per 128 bits. The linking incorporation of the mapping into type Ib table 500 is schematically shown in fig. 8. The first mapping is input tuple decoding 502, followed by 8-bit bijective 504, T-box T_i，j ^r506 where r corresponds to the last loop, an 8-bit to 128-bit mapping to provide the output encoding, and an output tuple encoding 510. The 128-bit output of such a table is xored with the outputs of the other type Ib tables, again using the tuple input and output encoded type IV table 400. The output encoding 508 is not performed elsewhere in the program (i.e., outside the cryptographic portion of the program). This makes it more difficult for an attacker to break the encoding of the table by analyzing only the inputs and outputs of the cryptographic part of the program.

White-box cryptography involves performing block ciphers in software so that an attacker cannot extract keys in a white-box attack pattern. The white-box attack pattern belongs to the strongest possible attack pattern, since the attacker is considered to have sufficient access to the implementation and full control over the execution environment. White-box implementations exist for AES, DES, and other encryption strategies. These white-box implementations can be based on similar ideas as described above, and one skilled in the art can employ the principles of white-box implementations to create white-box implementations of other encryption strategies.

Forensic watermarks may be added to the white-box implementation so that if a malicious user has assigned his/her implementation, we can track the user. That is, multiple white boxes implement X₁，X₂，...，X_nMay be created so that if a particular white-box implementation Y is given it can be determined that it corresponds to the implementation X₁，X₂，...，X_nWhich is the other. Executing Y does not require and executing X_iExactly the same, since the malicious user u can make some modifications to his/her implementation without changing its functionality.

In an embodiment, a white-box AES implementation is added with forensic watermarks. In this way, a plurality of white-box AES implementations are created by selecting different encodings to obfuscate the table of white-box implementations. For example, define X₁，X₂，...，X_nSo that they differ only in the non-linear tuple encoding f of the first output tuple of a given type II table U (212 in fig. 5). Note that this implies that for the following type IV XOR table V, one of the two input tuple decodes g is also differentThe implementation is different. The reason for this is that g ═ f¹: the output encoding f placed on the first output tuple of U is cancelled by the tuple decoding incorporated in the xor table V. It is clear to the person skilled in the art that this is not limited to the first output tuple of the type II table. Any corresponding output tuple encoding and input tuple decoding pair may be used to provide the watermark. And any combination of such pairs may be used as a watermark. A particularly strong watermark can be obtained by randomly selecting all the tuples to encode/decode, differently for each user. This has the further advantage that if an attacker can modify only some of the tuple encoding/decoding pairs, the user can still be identified by the remaining tuple encoding/decoding pairs.

Changing the tuple encoding does not affect the result of the decryption. The final result is the same because the tuple output encoding is not done in the tuple input decoding of another table. It is thus possible to assign a plurality of different versions of the table to different users, wherein all of these versions represent the same cryptographic method with the same encryption key.

An attacker can change the tuple encoding as follows. Let U, V be the continuous table in the white-box AES implementation, and let f be the output encoding of the tuple returned by table U. Note that this means that table V has an input tuple decoding f¹I.e. table V will f¹Applied to the tuples from U. The output code can be changed to an arbitrary (non-linear) code g. H is defined so that g ═ h ° f. The output of U is then encoded by h and the tuple is decoded h^-1And V is incorporated. In fig. 9, this principle is shown for the specific case of a type IV table. The result of this is that the output code of table U is given by g. Furthermore, since the attacker does not need any information about the codes used in U and V, he/she can perform the procedure. A second modification that an attacker can implement includes resetting the output and input bits of the table. The output bits of table U forming the input bits of table V may be given a different order by an attacker. The change in the order of the bits is not made in table V. These potential changes that an attacker may employ increase the risk of removing watermarks from the network of look-up tables.

It has been shown above that an attacker can modify a network of look-up tables containing watermarks. In this context, the following play a role in providing a robust watermark. First, how to manufacture multiple white-box AES implementations X that all function identically₁，X₂，...，X_nI.e. all perform AES for a given key K. Second, it helps identify which modifications are considered to be attackers u will be implementing X_uHe tries to remove the watermark and still has the desired functionality. Third, let Y be (can be) realized from a white box by employing such a modification_uThe resulting modified white-box implementation. It is desirable to still be able to determine that Y has been derived from X_uObtain, rather than from any other execution X_i. These three items may be used as forensic watermark items.

In an embodiment, the watermark is added in such a way that it can be overwritten even if an attacker has changed one or more tuple encodings and/or has changed the bit order from one table stream to the next. More generally, an attacker can apply any transformation to the set of output bits of the table that forms the input bits to the same next table. One implementation can be better understood by the following mathematical principles.

Problem of equivalence

The following concept is used. The tuple (nibble) is a 4-bit example, the byte (byte) is an 8-bit example, and for tuple x₁，...，x_nEach (4n) -bit vector x is considered to be divided into e.g. x ═ x₁，...，x_n) N tuples of (a). The divided (4n) -bit vector x can therefore be referred to as a tuple vector of length n. The tuple transformation is the mapping f ═ f (f)₁，...，f_n) Wherein each f_iIs a tuple mapping, i.e. mapping a tuple to a tuple; such mapping is implemented in a (4n) -bit vector x ═ x (x) divided into tuples as described above₁，...，x_n) And mapping such vector x to

f(x)＝(f₁(x₁)，...，f_n(x_n))。

Note that this tuple transformation f is invertible, if and only if the tuple mapping f_iIt is reversible. Reversible tuple transformations can be used at the output of the lookup table, where they act as output tuple encodings, or at the input of the lookup table, where they act as input tuple decodings. The tuple permutation is a permutation of pi ═ pi (pi)₁，...，π_n) Where { pi₁，π₂，...，π_nN) which is considered to act on a (4n) -bit vector x-x (x) by permuting its tuples₁，...，x_n) (ii) a Such π is said to map x to

Operation 0, implemented by type II table 200, would contain two tuples a₁，a₂Input byte a ═ a₁，a₂) Conversion to contain 8 tuples z₁，...，z₈Is equal to (z) the 32-bit output vector z₁，...，z₈) And take the form of

O＝fοBοCοTοAοg， (1)

Wherein the various operations have the following forms.

Mapping g ═ g (g)₁，g₂) Indicating that the input byte a is (a)₁，a₂) 202 and maps a to g ═ g (g)₁(a₁)，g₂(a₂) ); here each g_iIs an invertible mapping from tuple to tuple.

Map A represents a non-single linear mapping 204 from byte to byte.

The mapping T represents a "T-box operation" 206 that maps bytes to bytes.

Map C represents a portion of the blend operation 208 and includes a linear mapping from bytes to 32-bit vectors.

Map B is a hybrid bijection 210. It maps a 32-bit vector to a 32-bit vector. In an embodiment, this mapping B is used to encode a watermark.

Finally, f ═ f (f)₁，...，f_n) Representing tuple encoding 212, to be divided into tuples u₁，...，u₈Is a 32-bit vector of (u ═₁，...，u₈) Mapping to output vector z ═ (z)₁，...，z₈)＝(f₁(u₁)，...，f₈(u₈))。

If a is⁽¹⁾，...a⁽⁴⁾Is four input bytes which are applied to output column b, there are four involved type II tables 0⁽¹⁾，...0⁽⁴⁾In the form of

O⁽ⁱ⁾＝f⁽ⁱ⁾οBοC_iοT_iοA_iοg⁽ⁱ⁾. (2)

Then output column b satisfies

b＝(f⁽¹⁾)^-1z⁽¹⁾+(f⁽²⁾)^-1z⁽²⁾+(f⁽³⁾)^-1z⁽³⁾+(f⁽⁴⁾)^-1z⁽⁴⁾，(3)

Wherein

z⁽ⁱ⁾＝O⁽ⁱ⁾a⁽ⁱ⁾。

Note that the 32 × 32 matrix C ═ C₁C₂C₃C₄]Denotes the entire mixing operation, where C_iAre those in (2).

(3) The required operation is implemented by the type IV table of some layers. Here, operation A, implemented by type IV table 400, converts the tuple input pair (x, y) into tuple z and takes the form

A＝fοSοg， (4)

Wherein the various operations have the following forms.

Mapping g ═ g (g)₁，g₂) The expression decodes 402 the tuples of the input tuple set (x, y), maps them to g ═ g (g)₁(x)，g₂(y)); here each g_iIs an invertible mapping from tuple to tuple.

The mapping S represents a 4-bit XOR operation in 404.

Finally, f denotes the tuple encoding 406, mapping the tuple u to the tuple f (u).

Therefore, to achieve the sum of output column b in (3), first, Table 0⁽ⁱ⁾Is z is an addend of 32 bits⁽ⁱ⁾Is divided into eight tuples z_j ⁽ⁱ⁾J is 1. Then outputs the tuple b of column b_jCalculated from the type IV table of the two layers as

As a result of the final output encoding in each type IV table in the last layer, the partial network of look-up tables actually computes c ═ h (b) for some output tuple encoding h.

Hope forAn attacker who hides its forensic watermark B has many possibilities to make an output vector c h (B). First, each vector z is permuted by the same permutation π⁽ⁱ⁾The tuple permutation in (1) has the effect that the tuples in the output vector are also permuted by pi. Second, changing the output tuple encoding in the last layer type IV table (in a reversible manner) effectively applies that encoding to tuple c. Note that by first permuting the successor network to which the c bytes are sent, the attacker does not do both.

The attacker can thus ensure that instead of the output c ═ h (b), the output actually produced is

b′＝ποfοb， (6)

Wherein

π＝(π₁，...，π₈)

Is an unknown reversible tuple permutation, and

f＝(f₁，...，f₈)

is an unknown reversible tuple transformation such that b '═ b'₁，...，b’₈) Satisfy the requirement of

Given the (fictitious) non-obfuscated (standard) AES implementation of the system, which is here implemented in the present table look-up network, all intermediate results of the computation can be checked, even set to some predetermined value by the decoding operation. In particular, all intermediate results

x⁽ⁱ⁾＝C_iοT_iοA_iοg⁽ⁱ⁾(a⁽ⁱ⁾)

In Table 0⁽ⁱ⁾In the calculation performed, it also occurs in the standard AES calculation, and therefore their sum

x＝x⁽¹⁾+x⁽²⁾+x⁽³⁾+x⁽⁴⁾，

Can be set to any predetermined value regardless of the attacker's actions. Due to the fact that

z⁽ⁱ⁾＝f⁽ⁱ⁾x⁽ⁱ⁾，

(3) After that is

b＝Bx. (8)

However, as a result of the attacker manipulation (and the original tuple output encoding), instead of b, the vector b' obtained from b as in (6) is monitored, with the π and tuple transformations f being permuted by unknown but fixed tuples.

As a result, the input/output behavior of the unknown map T can be monitored, which is, however, known from the following forms

T＝ποfοB， (9)

From the unknown tuple permutations pi, the reversible tuple transformations f and the reversible linear mapping B representing the (unknown) watermark, information about the original forensic watermark B is obtained therefrom.

It can be said that if there are tuple permutations π, σ and reversible tuple transformations f, g, the two 32 × 32 reversible matrices (or forensic watermarks) B and B' are equal, whereby the two operations

T＝ποfοB，T＝σοgοB′

The same is true. As a result of this analysis, it is clear that in the above-described mode, it is not possible to distinguish between equal forensic watermarks.

For later use, the necessary and sufficient conditions for the matrix to be equal are first obtained. For this reason, some lemmas are obtained. The first lemma roughly states that the order of tuple permutation and tuple transformation can be permuted. The second lemma studies when the tuple permutation before tuple transformation can be a linear mapping.

And (5) leading to 1. Let pi be permuted as a tuple, and let f be (f)₁，...f₈) As a reversible tuple transformation. Then f ═ f^πO pi, wherein

f^π＝(f_π(1)，...，f_π(8))。

And (3) proving that: if (x)₁，...x₈)^TIs any 32-bit vector with a tuple x₁，...x₈Then said vector y ═ pi omicron (x) satisfies

y_i＝f_π(i)x_π(i)，

This applies to all i. Now, for all vectors x, pi (x) ═ x (x)_π(1)，...，x_π(8)) And thus f^ποπ(x)＝y＝ποf(x)。

□

2 in the introduction. Let τ be permuted as a tuple, let h be (h)₁，...h₈) As an invertible tuple conversion and let K be an invertible linear mapping, so that τ omic. Suppose that the mapped matrix K is divided into 4 x 4 sub-matrices K_i，jFor i, j ═ 1. Then each h_iIs a reversible linear mapping over tuples; furthermore, for each j, K may be obtained if and only if τ (i) ═ j_i，j≠0。

Certifying that: let K be (K)₁，...K₈)^TIs divided into 8 4 x 32 matrices K₁，...，K₈. Now, if x ═ x (x)₁，...x₈)^TIs any 32-bit vector with a tuple x₁，...x₈Then said vector y ═ pi ° h (x) ═ Kx satisfies

y_i＝h_τ(i)x_τ(i)＝K_ix， (10)

For all i. Now let j be random and let j be τ(s). Assume matrix K_s＝(K_s，1，...K_s，8) Sub-matrix K divided into 4 x 4_s，1...K_s，8. Now if x is not equal to j for all i ≠ j_i0, and x_jZ is random, then can be derived from (10)

y_s＝h_j(z)＝K_s，jz；

Thus, it is possible to provide

Is a linear mapping, which is non-zero since it is reversible. Further, by letting x_s＝z，x_rU, and x_i0 (for all i ≠ r, s), and z, u are random, then the following is for all i ≠ τ^-1(j)。□

From these two arguments, the following can be obtained.

Theorem 3. Let N be (N)₁...N₈)^TAnd M ═ M (M)₁...M₈)^TAs two matrices, each divided into submatrices N of size 4 × 32₁，...，N₈And M₁，...，M₈. Then if and only if there is a tuple permutation v and a set L of invertible 4 x 4 matrices₁，...，L₈When N and M are equal, so that

N_v(i)＝L_iM_i，

For i 1.

And (3) proving that: m and N are assumed to be equal. Then there is a tuple permutation of pi, sigma and a reversible tuple transformation f, g, such that

ποfοN＝σοgοM。

Thus, it is possible to provide

NM^-1＝f^-1οπ^-1οσοg。

Using theorem 1, τ and the invertible tuple transform h, f are permuted for the appropriate tuple and^-1οπ^-1σ ° g can be written τ ° h. Then K NM for the linear mapping^-1Can maintain

K＝τοh；

Thus, by lemma 2, mappingIs reversible, and K is when τ (i) ≠ j_i，j＝0。

Therefore, we have

Writing i ═ τ (i) and v ═ τ (i)^-1Can obtain

N_v(j)＝L_jM_j 。

Conversely, it can be seen simply that the two matrices N and M are in fact equal if the conditions are maintained. □

And (4) deduction. Having invertible matrix N divided into submatrices N of size 4 x 4_i，jFor i, j ═ 1. Then if and only if exactly one sub-matrix N is present in each tuple row and each tuple column_i，jThe non-zero time N is equal to the identity matrix I of size 32 x 32.

And (3) proving that: direct result of theorem 3.□

In the assumed attack mode, an attacker can transform its watermark (a matrix of size 32 × 32) into an equivalent matrix, and not into others. Theorem 3 can be used to estimate the maximum number of matrices that are equal to any given one, and thus to estimate the forensic water that is different in natureThe minimum number of prints. For this purpose, let N_inv(n) represents the number of n × n (binary) matrices of reversible size. As is well known and can be seen in simplicity,

N_inv(n)＝(2ⁿ-1)(2ⁿ-2)(2ⁿ-4)…(2ⁿ-2^n-1)；(11)

thus, it is possible to provide

N_inv(4)＝(16-1)(16-2)(16-4)(16-8). (12)

Also, the number of permutations on the 8 tuples is 8! 8.7.6.5.4.3.2.1. The result of theorem 3 follows.

Theorem 5. Number N of matrices equal to 32 x 32 matrix of given size_eq(M) satisfies

N_eq(M)≤N_inv(4)⁸8！。

And (3) proving that: in practice, each such matrix N is determined by the tuple permutation τ, by theorem 3, which exists 8! And eight 4 x 4 matrices L of reversible size₁，...，L₈For each of which there is N_inv(4) And (4) selecting. □

It is deduced that at least

N_inv(32)/(N_inv(4)8⁸！)≈5.10²⁶⁸

The unequal invertible sizes are 32 x 32 (binary) matrices (non-equivalent watermarks). Next, assume N forensic watermarks M₁，...，M_NHas been distributed, imagine that an attacker has changed his watermark to the equivalent watermark N. In order to create the original watermark of an attacker, it has been noted above that the input/output behavior of the mapping T can be monitored, the form of which is known

T＝ποfοN，(13)

But with unknown tuple permutations pi, reversible tuple transformations f and reversible matrices N. In order to identify the attacker, it is necessary toIt is possible to test whether the matrix N in (13) is equal to the given matrix M. First note that without loss of generality, M ═ I, the identity matrix can be considered. In practice, instead of T, if necessary, the operation T' is T ° M^-1Can be investigated in the form of

T＝ποfο(NM^-1)；

It is apparent from the analysis that if and only if NM^-1Equal to I, N is equal to M.

In the following, the procedure is outlined to detect whether a given mapping T pi omicron has N equal to I. In this regard, the task is to generate a plurality of 32-bit input vectors x₁，...，x_mSo as to output a vector y for i 1_i＝T(x_i) Is sufficient to determine whether N equals I. In the following, it will be explained how equivalence is tested if the number of input vectors m used is at least 32.

Let m be 33. For j 1.. 32, take x_j＝e_jWherein e is_jIndicating the jth cell vector, with a "1" in the jth bit and a "0" in the other bits. Finally, take x₃₃0, all non-zero vectors. Write out y_j＝T(e_j) To represent the jth output vector for i 1.., 32, and written as c T (0) to represent the final output vector. Imagine c ═ c₁，...，c₈)^THaving a tuple c₁，...，c₈. For i 1.., 8, let C_iWith a representation size of 4 x 4 matrix, all columns of which are equal to c_i。

Now consider a matrix Y of size 32 x 32, with vector Y_jAs its j-th column, 1.., 32 for j. Dividing Y into sub-matrices Y of size 4 x 4_i，j. Now, if (a) each tuple row i is divided by the sub-matrix Y_i，sAll other than C_iAnd (b) each tuple row j except the submatrix Y_r，jAll other than C_rN is equal to I. Conversely, if this is not the case, N is not equal to I. (fact)Above, if N is known to be reversible, it is sufficient to test only (b), since (b) implies (a)).

This is explained as follows. Partitioning 32-bit positions into eight tuple position sets J₁＝{1，2，3，4)，...，J₈{29, 30, 31, 32 }. Dividing N into sub-matrices N of size 4 x 4_i，jFor i, j ═ 1. First, assume that N is equal to I. According to inference 4, if one submatrix N is in each of eight tuple rows and in each of eight tuple columns_i，jPrecisely non-zero, N equals I. There is therefore a permutation of τ so that N_i，jPrecisely non-zero when τ (i) ═ j. Note that if one submatrix N is in each of eight tuple columns_i，jExactly non-zero, then either the statement remains the same for the tuple row, or there is a tuple row where all sub-matrices are zero; if N is reversible, the second possibility does not occur.

First, consider c ═ T (0). Obviously, N (0) ═ 0, and therefore c ═ f (0), so that c is for all i_i＝f_x(j)(0)。

Next consider a tuple set J_jR included in (1), for s of { 1.·, 4}, r is 4j + s. Then, Ne_r＝z_r＝(z_r，1，...，z_r，8)^TWherein z is_r，jIs equal to N_i，jThe s-th column of (1); as a result, z_r，j0, four-bit all-zero vector except when τ (i) is j. Then the r-th output vector y_r＝(y_r，1，...，y_r，8＝ποf(z_r) Satisfy the requirement of

y_r，i＝f_π(i)(z_r，π(i))。

Thus, y_r，i＝f_π(i)(0)＝c_iExcept possibly when τ (i) ═ j. This is for J_jAll r in (1) apply; so due to y_r，jIs a sub-matrix Y_i，jS column of (1), then

Y_i，j＝C_i，

Except possibly at τ (i) ═ j.

Conversely, assume that N is not equal to I. There is a tuple column, called column j, which contains two non-zero sub-matrices, called tuple row i₁And i₂(wherein i₁≠i₂). Thus, in 1, 4 there is a column s₁，s₂So that N is_i1，jColumn s in₁And N_i2，jColumn s in₂Both are non-zero. Now let r₁＝8j+s₁，r₂＝8j+s₂(all in the set of tuple locations) and considering two vectorsNow ifThen two tuplesAndnon-zero and, therefore, for t-1, 2,as a result, a vector is output with t1, 2Group of (ii) ([ pi ])_i) Is not equal toAnd thus the matrix Y does not have the desired form.

A simple formulation of the above procedure is given below. First, c ═ c is calculated₁，...，c₈) And c is T (0). Next, for each tuple j 1.., 8, four element vectors e are compared under the T to c condition_8j+1，...，e_8j+4Image u of₁，...，u₄. Now there should be a unique tuple number τ (j) so that the vector u is only in the tuple τ (j)₁，...，u₄Unlike c. If this is the case for each j, then N is equal to I, and if not, then N is not equal to I.

This process is almost optimal. In fact, the following theorem shows that at least 32 input vectors need to be determined to be equivalent.

Theorem 7 letting x₁，...，x₃₂Is an arbitrary 31 input vectors. There is a matrix N of size 32 x 32 not equal to I so that for all I, Nx_i＝x_i。

And (3) proving that: let b denote all vectors x_iOrthogonal non-zero vectors (such vectors must be present because the dimension of the entire space is 32), and let H be b^⊥. Let v be a vector, (b, v) ═ 1; thus, it is possible to provideFinally letAs the second vector other than H, and w ≠ v. Thus (b, w) ═ 1, and thus (b, v-w) ═ 0, i.e., v-w ∈ H. Consider a linear invertible mapping N that maps H e H onto itself (so that N acts as a unit on N) and v onto w. It holds

N＝I+[β₁(w-v)…β₃₂(w-v)]， (14)

Wherein b ═ β₁，...，β₃₂) By bit beta_iAnd (4) forming. In practice, if x ═ x (x)₁，...，x₃₂) Then, then

Nx＝x+[β₁(w-v)…β₃₂(w-v)]x

＝x+(x₁β₁+…+x₃₂β₃₂)(w-v)

＝x+(x，b)(w-v)，

Thus for x ∈ H, Nx ═ x, and Nv ═ v + (v, b) (w-v) ═ v + (w-v) ═ w.

The final step is to show that w other than H can be selected so that N (with as in (14))Matrix) is not equal to I. For this, for the tuple v₁，...，v₃₂Let v equal (v)₁，...，v₈) And for tuple b₁，...，b₈Let b be (b)₁，...，b₈). Two cases are now distinguished.

If for some j ≠ 1, b_jNot equal to 0, then take w ═ w (w)₁，...，w₈) W for i ≠ j_i＝v_iAnd for some tuples u_j≠0((u_j，b_j) 0), w_j＝v_j+u_j. Then w-v-u ═ w₁，...，w₈) For i ≠ j and u)_jU is not equal to 0_i＝0。

If b is₂＝...＝b₈B is 0₁Not equal to 0 now take w ═ w (w)₁，...，w₈) For i ≠ 2 and w₂≠v₂Say w_i＝v_i. Again w ≠ v and (w, b) ═ w₁，b₁)＝(v₁，b₁) (v, b) is 1, so that

In both cases, the first tuple column of N is non-zero in tuple row 1 and tuple row j ≠ 1 (in the first case) or tuple row 2 (in the second case), and thus in both cases N does not equal I according to the inference 4. To summarize: n ≡ I, and thus N ≡ I. But N ═ T (consider the case where pi and f are units) is also possible.

□

Testing equivalence

Suppose that for some unknown tuple the permutation pi ═ is (pi ═ pi₁，...，π₈) Reversible tuple conversion f ═ f (f)₁，...，f₈) And a linear transformation N of size 32 × 32 is reversible, the form of the mapping T being T ═ pi f omicron. Further assume that given any input vector x, the output can be calculatedVector y is t (x). The next algorithm decides whether N equals any given linear transformation M of 32 x 32 reversible size. (where 0 denotes a 32-bit all-zero vector, e)_iRepresenting a 32-bit ith element vector that is "i" at bit i and zero at all other bits. )

equivalent:＝true；

int array[1:32]c:＝T(0)；

int r:＝1；

while (r≤8and equivalent)do

begin

int n:＝0；//nibble number known to differ

int s:＝1；//testing image of vector e_4r+s

while (s≤4and equivalent)do

begin

int array[1:32]d:＝T(M^-1e_4r+s)-c；

if(d＝(d₁，...，d₈)has more than one nonzero

nibble)

or

(n≠0and d_m≠0andm≠n)

then begin equivalent:＝false；break；end；

if(d_m≠0)then n:＝n；//nibble number n

differs

s:＝s+1；

end；

r:＝r+1；

end

//here M≡N if and only if equivalent＝true.

Creating non-equivalent watermarks

Consider a set { W } containing all binary matrices W of size 32 × 32, divided into submatrices W of size 4 × 4_i，j(for j ═ 1.., 8), it has the following characteristics:

whenever i > j, group W_i，jIs an all-zero matrix

All packets W_i，jIs an identity matrix of size 4 x 4.

Thus any matrix W ∈ { W } is invertible and has the following form

Any two different matrices from W are not equivalent. To see this, theorem 3 is used. Let N, M be the two equivalent matrices from W. Then there is a tuple permutation τ and a matrix L of reversible size 4 x 4₁，...，L₈So that N is for i 1_τ(i)＝L_iM_i. Now, since M and N are in { W }, the tuple row i of M and N starts exactly with the i-1 non-zero packet before packet i; and L_iM_iStarting exactly at some non-zero packet L_iThe previous i-1 all zeros packet. As a result, the number of tuple rows i can be from N_iAnd L_iM_iBut is uniquely identified. Thus, the permutation τ must be identical, each L_iMust be an identity matrix and N ═ M. Note that { W } includes (2)¹⁶)^7+6+...+1＝2⁴⁴⁸＞10¹³⁴A matrix. Different watermark versions may be created by selecting different matrices from W。

An alternative method of creating watermarks in different equivalence classes involves randomly selecting a linear transformation N and using an algorithm for equivalence detection to verify whether the selected N is equal to any previously selected linear transformation.

Please note that in the above, the focus is on some special cases of the look-up table network and its obfuscation and watermarking. It will be appreciated that the watermarking principle can be employed independently of the characteristics of these particular cases. For example, AES has been used as the main carrier to explain white-box implementations using encoding and mixing bijections. However, it is clear to the skilled person that AES, encoding and mixed bijections do not have to be applied to the watermarking of the look-up table network.

Fig. 10 illustrates an embodiment of the present invention. A system 600 is illustrated for facilitating tracking users of copies of an implementation of a computing method 602. The users 632 of the calculation method 602 may have base stations on which they perform, in which case the individual users may be unified through their respective base stations. Alternatively, users may have different IP addresses or may log in to the system from which they obtained execution using their own login ID and password. An object, e.g. a version of a look-up table network, may thus be associated with a user or base station, referring to e.g. an IP address and a login ID. Other allocation systems and methods to associate objects with base stations or their users will be apparent to those skilled in the art. System 600 may be implemented in hardware and/or software. For example, it may be a software module running on a server at the content provider. System 600 is configured to prepare an implementation of computing method 602 for distribution to at least one user 632 (or base station 610). To this end, the system 600 includes a network generator 604 for generating a network of look-up tables representing the steps of the computational method. For example, the network of look-up tables takes the form of the white-box implementation described above in relation to fig. 1-9. However, other methods of generating such a network of look-up tables for a given calculation method may be conceived and employed by those skilled in the art.

The system 600 also includes a personalizer 606. The personalizer generates a plurality of different versions of a network of look-up tables. It is generated by changing at least one value in the network of look-up tables. The end result of the calculations performed by the different versions of the network of look-up tables is substantially the same for the different versions of the network of look-up tables, in particular for the relevant input value ranges. The relevant input value range corresponds, for example, to a value which, depending on its performance requirements, is processed in day-to-day use of the implementation. The change can be made in different ways. For example, the first lookup table may be changed by exchanging pairs of output values of the lookup table. In order to maintain the same output value of the network, the entries of at least the next table in the network of look-up tables may be swapped so that no changes are made to the first look-up table. Depending on the structure of the network of look-up tables, changes may be made to individual look-up tables without changing the output values of the network as a whole. The network may also be extended or reconfigured by additional look-up tables as long as the result of the associated input value range remains substantially unchanged.

System 600 also includes correlator 608. The correlator associates the different networks created with the users or base stations stored in the database 614 by their IP addresses, login IDs or any other type of tag. The resulting network of look-up tables that have been associated with the user is stored in database 614.

In an embodiment, the calculation method is characterized by an encryption policy, such as AES. Other encryption strategies suitable for digital rights management will be apparent to those skilled in the art. The encryption policy works with an encryption key. The personalizer is arranged to generate a plurality of versions of a network of look-up tables, all using the same key to perform the same encryption strategy. Also, each look-up table version is unique so that it is possible to find out from the look-up table version who is the user associated with the version. This is particularly interesting for dissemination systems, where a large number of users are provided with the same dissemination data. The propagated data is encrypted and all users need to employ the same encryption policy and key to decrypt the propagated data. For example, the personalizer generates different white-box implementations of the encryption policy.

In an embodiment, the personalizer is arranged to create a white-box implementation of the computing method. An example of a white-box implementation is given above. They may be created for any computational method, in principle. The personalizer 608 is arranged to change the values in the look-up table in such a way that the final result is unchanged. For example, the tuple encoding or one or more hybrid bijections may be changed. Alternatively or additionally, the network structure may be changed, i.e. the way the data flow through the network is changed. Individual look-up tables may be added to or removed from the network of look-up tables.

In an embodiment, the personalizer is arranged to blur the white-box implementation by a linear or non-linear operator. The operator is integrated in a first plurality of look-up tables in the network and the inverse of the operator is integrated in a second plurality of look-up tables in the network. Different operators are used in different versions. This means that when an attacker wants to remove all traces of a selected operator, he needs to know how much the mutual dependencies of the first and second plurality of look-up tables are. One or more of these tables may have input and/or output encodings. This makes it more difficult to find the operators used and adds more feature features to the watermark when these input and output codes are chosen differently for different versions. When applied to the AES instance, the operator may be a mixture bijection, and the input and/or output encodings may be tuple encodings.

Preferably, the personaliser is arranged to create versions using operators in different equivalence classes, where an equivalence class comprises operators whose corresponding network of look-up tables can be derived from each other by varying the input and/or output encodings. The input and/or output codes can be easily changed by an attacker, so that different operators need to be selected in order to still be able to distinguish them from each other after changing the codes. The equivalence class described in the section entitled "equivalence problems" is an example thereof.

More generally, the personalizer 606 is arranged to create versions in different equivalence classes, where an equivalence class includes versions obtained from each other by applying modifications to the versions from a set of modifications deemed to be within reach of an attacker. This may be accomplished by randomly applying the modification to generate a version and verifying whether it belongs to an equivalence class of a previously generated version. If the result is that versions of the same equivalence class have already been generated, the newly generated version is discarded and another version is generated to replace the discarded version. Alternatively, the personalizer 606 is arranged to (pseudo-) randomly select one of the matrices W e W according to equation (15).

One embodiment includes a distribution server 624. Distribution server 624 retrieves the version associated with subscriber 632 from database 614 and provides the version to subscriber 632 or his base station 610. To ensure that only the intended recipient receives the version, it is encrypted using the user-specific key. Content (e.g., audio data, video data, software, etc.) is encrypted by an encryption policy and encryption key implemented in a version of the look-up table network. The encrypted version and content are transmitted to base station 610 of user 632. It will be appreciated that this is only one embodiment of the allocation method. The personalized version may be distributed in any manner, with or without encryption in whole or in part. They may be distributed via a network, such as the internet, or via a storage medium, such as a CD. One way to securely distribute the versions is by sending only a portion of the network of look-up tables via a distribution channel. This portion may be a type II table 20 (with a corresponding type IV table 22). The type III table 24 (with the corresponding type IV table 26) may be provided to the base station in different ways, for example by a smart card. This enhances the correlation between the watermark and the user, since the watermark may be defined in whole or in part by the part of the look-up table present in the smart card.

One embodiment includes a base station 610. The base station 610 includes a network of look-up tables for receiving data representing steps of a computational method. The network may be encrypted with a user-specific key, in which case it is decrypted first. The network is received from the distribution server 624. The base station 610 comprises a data processing unit 612 for applying a network of look-up tables 634 for processing data. Such as audio or video content, for example, provided from distribution server 624 or from a CD-ROM. The look-up table network has watermarks provided thereto by the system 600. Although in principle the network of look-up tables received from the server 624 is therefore unique, another network of look-up tables may be provided to the input of the base station 610, for example by an attacker. The other network of look-up tables may provide more or different functionality than the look-up tables received from the distribution server 624. Although the base station thus has a different functionality than other versions of the look-up table network, the origin of the look-up table network can be tracked because it has unique characteristics and is associated with the original user or base station.

One embodiment includes a system 616 for identifying a copy of an implementation of a computing method. The system 616 is connected to a database 614 that includes different versions of these implementations. One or more networks of look-up tables (hereinafter referred to as input versions) are provided to an input 618 of the system 616 for matching with versions stored in the database 614. Each implementation includes a network of look-up tables representing steps of a computational method. The system 616 includes a comparator 620 for comparing the lookup table in the implementation with at least one of the versions. The comparator may be implemented by a byte-byte comparison that may report whether the input version matches a version in the database. The degree of similarity between the input version and the versions in the database may also be reported. The version in the database 614 that most closely resembles the input version may also be found.

The system 616 includes an equivalence class builder 622 to build equivalence classes to which the input versions belong and to identify whether one or more versions in the database have the same equivalence class. The equivalence class preferably includes all versions that can be transformed from one another by applying modifications from a set of modifications deemed to be within reach of an attacker to the versions.

Fig. 11 illustrates an embodiment of the present invention, which may be implemented in a server of a content provider, for example. It may also be implemented in a standard PC. A communication section 95 is shown for providing information such as the version of the look-up table network and/or the content to be processed. The communication section 95 is provided to connect to the internet, for example. A version of the network of look-up tables may also be stored on a storage medium 96 such as a DVD or CD. Also shown is a processor 92 and a memory 91. The memory includes instructions for causing the processor to generate a plurality of versions of a network of look-up tables in the above-described manner. The network of look-up tables represents steps of a computational method, such as an encryption strategy with a special encryption key. In the memory 91, the respective versions generated are associated with respective users, for example by means of a table. Also shown are inputs 94, such as a keyboard and/or mouse, and a display 93 for an operator to operate the system.

Another embodiment may also be explained with reference to fig. 11. This embodiment includes a base station, such as a personal computer, a set-top box, a digital video player, a terminal, or a smart card. The base station comprises a communication part 95 for connecting to a server to obtain a version of the look-up table network associated with the user. Additionally or alternatively, the base station comprises means for reading a storage medium 96 (e.g. a CD or DVD) on which a version of the network of look-up tables may be stored. The base station comprises a processor 92 for processing data by employing a look-up table. Data may also be obtained via the communication section 95 and/or the storage medium 96. For example, a network of look-up tables represents steps of a computational method. The calculation method may include any data processing method. For example, one or more processing steps of the video enhancement algorithm (e.g., PixelPlus) may be implemented via a network of look-up tables. Furthermore, the network of look-up tables may perform the steps of an encryption strategy, such as an encryption algorithm or a decryption algorithm. Such decryption algorithms may be used to decrypt content for presentation on display 93. The system includes a user input 94, such as a keyboard or remote control, to allow a user to control the system.

It will be appreciated that the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a code intermediate source and object code such as partially compiled form, or in any other form suitable for use in the implementation of the method according to the invention. The carrier may be any entity or device capable of carrying the program. For example, the carrier may comprise a storage medium, such as a ROM, e.g. a CD ROM or a semiconductor ROM, or a magnetic recording medium, e.g. a floppy disk or a hard disk. Furthermore, the carrier may be a transmissible carrier such as an electrical or optical signal, which may be conveyed via electrical or optical cable or by radio or other means. When the program is embodied in such a signal, the carrier may be constituted by such cable or other device or means. Alternatively, the carrier may be an integrated circuit in which the program is embodied, the integrated circuit being adapted for performing, or for use in the performance of, the relevant method.

It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The use of the word "comprising" and variations thereof does not exclude the presence of elements or steps other than those listed in a claim. The article "a" or "an" preceding an element does not exclude the presence of a plurality of such elements. The invention can be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

Claims (18)

1. A system (600) for facilitating tracking copies of an implementation of a computing method (602), the system comprising

A network generator (604) for generating a network of look-up tables representing the steps of the calculation method (602), the network being formed by using the output values of a first look-up table as input values of a different second look-up table;

a personalizer (606) for generating a plurality of different versions of the network of look-up tables by changing at least one value in the network of look-up tables, the end result of the version corresponding to the relevant field of input values being substantially the same for each version;

a correlator (608) for associating respective versions with respective base stations (610) or users (632) of the base stations (610).

2. A system according to claim 1, wherein the calculation method (602) comprises an encryption policy and an encryption key, the network generator (604) and the personalizer (606) being arranged for generating a network of look-up tables enabling the execution of the encryption policy using the encryption key.

3. A system according to claim 1, wherein the personalizer (606) is arranged for creating a white-box implementation of the computing method (602).

4. The system according to claim 1, wherein the output encoding and/or input decoding performed by the white-box is different in different versions.

5. The system according to claim 1, wherein the personalizer (606) is arranged for obfuscating the white-box implementation by operators, the operators being selected differently for different versions, wherein the operators are integrated in a first plurality of look-up tables in the network and inverses of the operators are integrated in a second plurality of look-up tables in the network.

6. The system of claim 1, wherein at least one of the first plurality of look-up tables or at least one of the second plurality of look-up tables has an input and/or output encoding that is cancelled by its respective predecessor and/or successor in the network with respect to a data stream passing through the network.

7. The system according to claim 1, wherein the operator is linear hybrid bijective and at least one of the input and/or output encodings is non-linear.

8. A system according to claim 1, wherein the personalizer (606) is arranged for creating versions using operators in different equivalence classes, wherein an equivalence class comprises operators whose corresponding network of look-up tables is obtainable from each other by providing modifications from a predetermined set of modifications to the input and/or output encodings.

9. A system according to claim 1, wherein the personalizer (606) is arranged for creating versions in different equivalence classes, wherein the equivalence classes comprise versions obtainable from each other by providing modifications from a predetermined set of modifications to the versions.

10. The system of claim 1, further comprising an output for transmitting the respective versions (634) of the look-up table to an associated base station (610) or user (632) via a single medium.

11. A system according to claim 1, wherein the system (600, 624) is for controlled distribution of content to a plurality of base stations, and the calculation method (602) comprises a decryption method, the system further comprising

An encryptor (626) for encrypting the version associated with the user using a user-specific encryption key associated with the user to obtain an encrypted version;

a content pre-processor (628) for encrypting the content according to an encryption policy and an encryption key to obtain encrypted content;

an output (630) for providing the encrypted version and the encrypted content to the user.

12. A system (610) for performing computations for a user, comprising

A data processing unit (612) for applying a network of look-up tables (634) representing the steps of the calculation method (602) to the data, the network being formed by using the output values of a first look-up table as input values of a different second look-up table;

the network of look-up tables (634) forms a version of a network of look-up tables of a plurality of different versions obtained by varying at least one value in the network of look-up tables, the final result of the calculation method corresponding to the relevant field of input values being substantially the same for each version;

versions associated with respective users.

13. A system (616) for identifying a copy of an implementation of a computational method, wherein the implementation comprises a network of look-up tables representing steps of the computational method (602), the network being formed by using output values of a first look-up table as input values of a different second look-up table;

the network of look-up tables being a version of a network of look-up tables of a plurality of different versions obtained by varying at least one value in the network of look-up tables, the final result of the calculation method corresponding to the relevant field of input values being substantially the same for each version;

the system (610) comprises:

a comparator (620) for comparing at least one look-up table in the implementation with at least one version.

14. The system of claim 13, further comprising an equivalence class builder (622) for building an equivalence class corresponding to the versions in the implementation, wherein an equivalence class comprises versions obtainable from a starting version by applying modifications from a set of modifications deemed to be within reach of an attacker to the starting version.

15. A method of facilitating tracking of users of copies of an implementation of a computing method, the system comprising

Generating a network of look-up tables (28) representing the steps of the calculation method, said network being formed by using the output values of a first look-up table (20) as input values of a different second look-up table (22);

generating a plurality of different versions of the network of look-up tables (28) by varying at least one value in the network of look-up tables, the output values corresponding to the versions of the relevant fields of input values being substantially the same for each version;

each version is associated with a respective user.

16. A computer program product comprising instructions for causing a processor to perform the method according to claim 15.

17. A method of identifying a copy of an implementation of a computational method, wherein the implementation comprises a network of look-up tables (28) representing computational method steps, the network (28) being formed by using output values of a first look-up table (20) as input values of a different second look-up table (22);

a network of look-up tables (28) being a version of a network of look-up tables of a plurality of different versions obtained by varying at least one value in the network of look-up tables, the final result of the calculation method corresponding to the relevant field of input values being substantially the same for each version;

the method comprises the following steps:

comparing at least one lookup table in the implementation to at least one version.

18. A computer program product comprising instructions for causing a processor to perform the method according to claim 17.