Block ciphers are an often used primitive in cryptography. A block cipher is an algorithm for encrypting or decrypting a message block of digital data under control of a cryptographic key. The block cipher operates on message blocks of digital data of some predetermined block size, conventionally bit size. Common block sizes include 64, 128, 192, and 256 bit. The operation is a deterministic bijective (and thus invertible) operation. Known block ciphers include DES and AES.
For example, a content distribution system may encrypt content before distribution to counter piracy. Encrypted content may be distributed over less secure channels, say the Internet, whereas the key used for encryption may be distributed using more secure means, say a DRM system. However, even distribution of the key is not without risks. Even DRM implementations may be disassembled to recover their secrets, e.g., their secret keys. For this and other reasons there is a desire for a secure encryption/decryption primitive that may be protected against reverse engineering.
One way to protect a key, e.g., a key used in a DRM implementation, say a master key, may be to use an implementation of a block cipher. A white-box cipher is a software implementation of a block cipher in which the secret key is ‘instantiated’. Instantiating a key in an implementation fixes the key and embeds the key in the implementation by partial evaluation with respect to the key; key input becoming unnecessary. Computations that depend on the key are evaluated so far as is possible without knowledge of the message block input. Typically, the key schedule may be computed, and the round keys may be combined with other steps. Often the round keys may be combined with a substitution layer, i.e., by adding a round key to the output of substitution boxes in a substitution layer.
Next the implementation is obfuscated. Typically this is done by expressing the instantiated cipher as a table network, and encoding of the tables of that network. The goal is that the effort of recovering the instantiated key from the white-box cipher is at least as large as a black box (e.g. brute force) attack on the underlying cipher.
One ideal solution would be to implement the cipher as one big lookup table. However, this is unworkable for practical bock ciphers. A white-box strategy that approaches this ideal was introduced in “A White-Box DES Implementation for DRM Applications” by S. Chow, P. Eisen, H. Johnson, and P. C. van Oorschot, 2002 published in the book Digital Rights Management of the Lecture Notes in Computer Science 2003. Computations, in particular block ciphers may be implemented as a network of lookup tables, randomized so that key information is spread over the entire network. Every building block may be made to be seemingly independent from the key. So that an adversary is forced to analyze the complete network in order to obtain secret key information. Obfuscation of the network of tables is possible by prepending and appending obfuscating transformations to the transformations written out in tables. In this way each individual table is randomized, while the combination of all obfuscating transformations cancels. Another example is given in “White-Box Cryptography and an AES Implementation”, by Chow, Eisen and van Oorschot.
In White-box cryptography a block cipher is implemented in software such that it is difficult for an attacker to extract the key even if he has full access to the implementation. However, the inventors found that a particular kind of block cipher, the so-called Substitution-Linear Transformation Networks have vulnerabilities in this respect which makes them hard to secure using conventional white-box techniques. See the paper “Cryptanalysis of a Generic Class of White-Box Implementations” by Wil Michiels, Paul Gorissen, and Henk D. L. Hollmann for more details. The problem is related to the way SLT (Substitution-Linear Transformation) type ciphers are organized, i.e., any white-box implementation of a block cipher of the type described above using white-box techniques such as used by Chow et al., will be vulnerable.