PROCESS FOR INSECURE ENVIRONMENTS

DESCRIPTION CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] This application claims priority benefit of United States Patent Application

No. 12/806,768, filed August 20, 2010. The entire content of that application is hereby incorporated by reference herein.

FIELD OF THE INVENTION

[0002] This invention relates to data security and cryptography and more generally to improving the security of computer enabled cryptographic processes and algorithms.

BACKGROUND

[0003] Cryptographic algorithms are widely used for encryption of messages,

authentication, encryption signatures and identification. The well-known DES (Data Encryption Standard) has been in use for a long time, and was updated by Triple-DES, which has been replaced in many applications by the AES (Advanced Encryption Standard).

[0004] DES, Triple-DES and AES are exemplary symmetric block ciphers. Block ciphers operate on blocks of plaintext and ciphertext, usually of 64 or 128 bits but sometimes longer. Stream ciphers are the other main type of cipher and operate on streams of plain text and cipher text 1 bit or byte (sometimes one word) at a time. With a block cipher, a particular plain text block will always be encrypted to the same cipher text block using the same key. However, to the contrary with a stream cipher, the same plain text bit or byte will be encrypted to a different bit or byte each time it is encrypted. Hence in the ECB (electronic code book) mode for block ciphers, each plain text block is encrypted independently.

[0005] AES is approved as an encryption standard by the U.S. Government. Unlike DES, it is a substitution permutation network. AES is fast to execute in both computer software and hardware implementation, relatively easy to implement, and requires little memory. AES has a fixed block size of 128 bits and a key size of 128, 192 or 256 bits. Due to the fixed block size of 128 bits, AES operates on a 4x4 array of bytes. It uses key expansion and like most block ciphers a set of encryption and decryption rounds (iterations). Each round involves the same processes. Use of multiple rounds enhances security. Block ciphers of this type use in each round a substitution box or s-box. This operation provides non-linearity in the cipher and significantly enhances security.

[0006] Note that these block ciphers are symmetric ciphers, meaning the same algorithm and key are used for encryption and decryption, except usually for minor differences in the key schedule. As is typical in most modern ciphers, security rests with the (secret) key rather than the algorithm. The s-boxes or substitution boxes were introduced in DES and accept an n bit input and provide an m bit output. The values of m and n vary with the cipher. The input bits specify an entry in the s-box in a particular manner well known in the field.

[0007] To implement AES (having 128 bit blocks, and 10 rounds) arithmetically involves the following operations: (1) 11 AddRoundKey operations (1 prior to 10 rounds), (2) 10 Sub- Byte operations, (3) 10 ShiftRow Operations, and (4) 9 Mix-Column Operations. Each round of rounds 1 to 9 consists of operations (1) to (4), where output from one operation is input to the next operation, and output from operation (4) is input to operation (1). Round 10 consists of operations (1) to (3), where output from operation (3) is the output used. Arithmetic implementations of AES do not provide much security against an attacker recovering a secret key, if the attacker has privileged access to the system implementing the cipher.

[0008] Many encryption algorithms are primarily concerned with producing encrypted data that is resistant to decoding by an attacker who can interact with the encryption algorithm only as a "black box" (input-output) model, and cannot observe internal workings of the algorithm or memory contents, etc due to lack of system access. The black box model is appropriate for applications where trusted parties control the computing systems for both encoding and decoding ciphered materials.

[0009] However, many applications of encryption do not allow for the assumption that an attacker cannot access internal workings of the algorithm. For example, encrypted digital media often needs to be decrypted on computing systems that are completely controlled by an adversary (attacker). There are many degrees to which the black box model can be relaxed. An extreme relaxation is called the "white box" model. In a white box model, it is presumed that an attacker has total access to the system performing an encryption, including being able to observe directly a state of memory, program execution, and so on. In such a model, an encryption key can be observed in or extracted from memory, and so ways to conceal operations indicative of a secret key are important.

[0010] The publication "White-Box Cryptography in an AES implementation" Lecture Notes in Computer Science Vol. 2595, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography pp. 250-270 (2002) by Chow et al. discloses implementations of AES that obscure the operations performed during AES by using table lookups to obscure the secret key within the lookup tables, and obscure intermediate state information that would otherwise be available in arithmetic implementations of AES.

[0011] Chow et al. (for his "white box" implementation where the key is known at the computer code compilation time) uses 160 separate tables to implement the 11

AddRoundKey operations and 10 SubByte Operations (10 rounds, with 16 tables per round, where each table is for 1 byte of the 16 byte long— 128 bit— AES block). These 160 tables embed a particular AES key, such that output from lookups involving these tables embeds data that would normally result from the AddRoundKey and SubByte operations of the AES algorithm, except that this data includes input/output permutations that make it more difficult to determine what parts of these tables represent round key information derived from the AES key.

[0012] Chow et al. uses 1008 separate tables to implement the nine MixColumn Operations (there is no MixColumn operation in the 10 ^th round of AES). One type of these tables implements a multiplication of one byte with the AES MixColumn polynomial (per the specification), and another type implements the logical XOR (exclusive OR) part of

MixColumn. Each table is used once during the nine rounds.

[0013] The Chow et al. solution is clever, but several attacks already have been made on it. Chow et al.'s white-box implementation of a given block cipher encryption process decomposes the block cipher (with its key) as a set of table-lookups. The table-lookups are then masked using permutation functions. (A permutation as used here refers to a bijection operation that changes the order of bits in a data byte or word in a predetermined fashion.) This is explained in Chow et al., and this method can be extended to any block cipher.

[0014] The most recent and the most powerful such extension was published by Olivier Billet et al. "Cryptanalysis of a White Box AES Implementation" in SAC 2004, LNCS 3357 pp. 227-240, 2005. The details of the processed basic operations are necessary to mount this attack. This means the attacker has to distinguish the set of operations to extract the operations per rounds, the MixColumn operation, etc.

SUMMARY

[0015] The present method and its associated apparatus, which are intended to thwart such attacks, include constructing an AES (or other cryptographic algorithm including any block cipher algorithm) implementation as a set of basic table operations which are each undistinguishable from one another and are masked. Thereby the attacker is lost in or confused by the computer code embodying the cipher (for a passive attack) and/or in the computer code execution path (for an active attack). This approach is also implementable in a hardware (circuit based) apparatus designed to carry out the cryptographic process.

[0016] The above -referenced Billet et al. attack is a process decomposed into a set of basic problems to gain information step-by- step on the masks used to hide the cipher operations and the key. When the masks are known it is then easy to recover the cipher key itself.

[0017] The Billet et al attack enables the attacker to recover the non-linear part of the output transforms as soon as the attacker is able to regroup tables that make up a round of the AES algorithm. For instance, Billet et al. shows how to recover the non-linear part of the functions Q used in the MixColumns "box" 10 such as shown in FIG. 1, from Billet et al and which shows one of the four mappings in box 10 between four input bytes and four output bytes. The input bytes are xo, xi, x ₂ , x ₃ , and the output bytes are yo, yi, y ₂ , y ₃ . Each such box is constructed of four 8 bit to 8 bit permutations with respective output permutations. Q. So in a first phase, one recovers the role of each of the tables that appear in memory in order to be able to compute the tables that are involved in one AES round, to construct the following combination of operations for one round.

[0018] A goal of the present cryptographic process is to make this task harder. Indeed, in the current well known version of AES, some tables are bigger than others and some operations are not "white -boxed." The MixColumn tables as in FIG. 1 have a size of 8x32 elements instead of 8x8 elements of the other tables. Furthermore, certain tables' outputs are logically XORed (exclusive OR), contrary to the outputs of the other tables. [0019] Since the operations are thereby distinguishable, it is possible for the attacker in a white box environment to determine when an AES round finishes and when a new one begins.

[0020] A goal of the present method is to construct such tables to all be each of exactly the same size, thereby hardening drastically against such an attack. Due to the structure of the computation of the AES cipher algorithm, one may use tables of sizes 8-bit input x 4-bit output (which has a size of 128bytes), 16-bit input x 8-bit output (65 Kbytes) or 32-bit input x 16-bit output (8GBytes). An exemplary choice is tables each of size 8-bit (one byte) x 4-bit (1 nibble). The following presents this process with an 8x4 table size, but the process is readily generalized to other table sizes. Note that these tables are for permutation and logical operations; they are not the "S-box" substitution operations characteristic of the AES cipher.

[0021] Incorporated by reference here in their entireties are commonly owned U.S. Patent Application Publications US 2009/0252327 A 1 "Combination White Box/Black Box

Cryptographic Processes and Apparatus" Ciet et al. and US 2010/0054461A1 "Systems and Methods for Implementing Block Cipher Algorithms on Attacker-Controlled Systems" Ciet et al.

[0022] FIG. 1 shows in the prior art a mapping for the AES MixColumns Operation. [0023] FIG. 2 shows diagrammatically an XOR operation table or "box". [0024] FIG. 3 shows a permutation box.

[0025] FIGs. 4A, 4B show the permutation of FIG. 3 decomposed.

[0026] FIG. 5 shows a twin of an XOR table.

[0027] FIG. 6 shows a general form of the FIG. 5 table.

[0028] FIG. 7 shows a completed XOR table.

[0029] FIGs. 8A, 8B, and 8C show a mask permutation.

[0030] FIG. 9 shows a computing system.

[0031] FIG. 10 shows detail of the FIG. 9 system. DETAILED DESCRIPTION

[0032] The tables of the type described above input a data byte but only return a data nibble (a nibble is a half byte). Considering the AES cipher as an example, the present inventors have determined that two kinds of 8x4 tables are sufficient for the AES algorithm:

(a) The tables that implement 8-bit input (2 nibbles) with a 4-bit (1 nibble) output are thus restricted to one nibble on the output side. In this case, to represent a permutation function of one byte of input data, two each 8x4 tables are required.

(b) The tables that implement the logical XOR operation on masked nibbles.

These tables input two masked nibbles, compute the logical XOR of the two nibbles on a bit by bit basis and return a single masked nibble.

[0033] Having same size tables in accordance with the invention does not imply the tables are indistinguishable. This is even the case if the tables are masked using input and output permutations. The present inventors have identified a first way to distinguish between tables which an attacker can use. So even if all the involved tables have the same size, they are easily distinguishable. Indeed, an XOR operation table is the table of a group law. Hence for any nibble, there exists a unique nibble such that the output through the "box" (table) is 0. (The term "box" refers to a table or logical or mathematical operation embodied in a table, not to the "white box" environment.) This property (distinguisher) is also verified for any value in the group [1, 2 ⁴ -l], which are the other possible outputs of the XOR operation table.

[0034] This last property ensures that each output of an XOR operation table has exactly 16 pre-images. (A pre-image in cryptography is a value or values that maps to a particular output.) Hence, if XOR operation tables are used within a computation, an attacker is able to detect them using a known pre-image attack and is able to obtain useful information on the implementation including the structure of such tables.

[0035] The present inventors also identified a second way (property) to distinguish between these two types of tables. Each 8x4 table, which represents half of a permutation, necessarily has a "twin" table that is the second part of the permutation. A "twin" to a particular table A is table B if the concatenation table C of A and B in the sense that C[i] = A[i] || B[i], A, B and C accept the same input and for any input, the output of table C is the concatenation of the A and B outputs and C is a permutation, where " || " denotes concatenation. So given a particular XOR operation table A, it does not necessarily have a twin table B present in any particular cryptographic algorithm. But it is indeed possible to construct such a table B. So in the present process such an additional table B is constructed for each XOR operation table A, and these additional tables B are used. Note that in order to economize on computer code in a software embodiment, one can construct input and output permutations on two such XOR operation tables such they are twins.

[0036] An 8x4 table that implements an XOR operation has no such twin as explained above since it inputs two nibbles and returns a single nibble. Hence a priori, among a set of 8x4 tables, it is easy to distinguish an XOR operation table from other tables, and this undesirably gives information on the implementation to the attacker regarding the type of table.

[0037] The following is a computationally efficient method for hiding the nature of a table which is either part of a permutation or is an XOR operation table, so as to defeat these two ways of distinguishing tables. Let a data byte designated X be the concatenation of two nibbles designated Xo and Xi, expressed algebraically as:

Xo II Xi-

[0038] Here, the XOR operation table of inputs X ₀ and Xi is represented by box 12 in FIG. 2.

[0039] Let the result of a permutation designated P on the input byte X (= Xo || Xi) be the concatenation of two permutations designated P ₀ , Pi so P ₀ (Xo || Xi) and PI (X ₀ 1| Xi), where P ₀ and Pi are applied on X and not only on one part of X, expressed as:

Po (Xo || xo II Pi (Xo II xo.

[0040] One also represents a permutation P by box 14 of size 8x8 as shown in FIG. 3. As explained above, a permutation can be decomposed into two sub tables P ₀ 16 and Pi 18 as shown respectively in FIGs. 4A, 4B.

[0041] The following describes constructing a twin table for the XOR operation table to defeat the second way of distinguishing between tables. As explained above, the XOR operation table in the algorithm does not have any twin table, which is defined (see above) as a table that makes a permutation when it is associated with the XOR operation table.

However, constructing such a table is readily accomplished. Indeed, there exist many tables that are a twin of the XOR table. For instance the function 20 designated Q shown in FIG. 5 is one of them. The general form of such a table 22 is shown in FIG. 6 where F is a function such that the function designated φ, that takes as input byte (X ₀ , Xi) and outputs: φ (Xo, Xi) = (Xo ® Xi, F(Xo, Xi)) and which is a bijection.

[0042] The following describes making the XOR tables indistinguishable thereby defeating the first way of distinguishing. This involves hiding the property on the number of pre- images of the XOR operation tables. Assume that there is permutation that is a completed XOR operation table 24 as described above and shown in FIG. 7. To hide that its upper part is made from an XOR operation table, in a first step, one computes two permutations designated respectively M and R such that for all nibbles Xo and Xi where M is the mask 26 in FIG. 8A, and R is the concatenation of M ^"1 and Q in FIG. 8B:

M(R( Xo, XO) = (Xo ® Xi, F(Xo, XO)

[0043] The letter M indicates "mask," since this permutation masks that the table is actually an XOR operation table. Permutation M 26 as show in FIG. 8A is randomly selected, e.g., from a predetermined set of permutations. This selection is typically performed when the computer source code is compiled into object (executable) code. From the inverse permutation of M designated M ^"1 one computes the composition of M ^"1 with the completed XOR operation table. There are now two permutations M ^"1 27 and Q 28 as shown in FIG. 8B which combine into permutation R 29 in FIG 8C. Advantageously, none of these permutations, taken separately, have any particular property which would enable an attacker to distinguish them from a random permutation.

[0044] In a second step of the masking, one masks the output of the XOR operation table. Indeed, it is in general better for security never to expose the correct data in the computation. To do so, two methods can be applied:

(a) The first method includes computing a 4x4 random permutation and

composing it with the upper part of second permutation. (b) The second method includes computing an 8x8 random permutation and composing it with the entire second permutation.

[0045] In both cases, the inverse of the last computed permutation is reused. Indeed, the goal is to have a set of permutations that can be chained.

[0046] So in accordance with the invention one is able to represent any table of a white-box implementation of AES or a similar cryptographic algorithm as a set of indistinguishable table-lookups using the above described construction of these tables.

[0047] The resulting cipher process is expressed (in computer code or hardware) as a set of indistinguishable table-lookups of tables each of size 8x4 for example. This makes it hard for an attacker to retrieve what does correspond to a complete round to mount his attack since it is difficult for him to determine when each round begins or ends. This is especially true when several "useless" operations (each involving an additional permutation) are added where desired in the process to add complexity and where these additional and useless tables are indistinguishable from the useful ones. These additional permutations enhance security by making some rounds of the cryptographic algorithm longer than others. In another embodiment, additional operations of this type are added on a per-byte basis within each round.

[0048] The present method can be extended to cryptographic processes using tables of other sizes such as 18x8 or 32x16. However 8x4 tables may be preferred.

[0049] FIG. 9 shows in a block diagram relevant portions of a computing device (system) 30 in accordance with the invention decryption. This is, e.g., a computer, mobile telephone, Smart Phone, personal digital assistant or similar device, or part of such a device and includes conventional hardware components executing in one embodiment software (computer code) embodying the above examples of a cryptographic (e.g., encryption or decryption) process. This code may be, e.g., in the C or C++ computer language or its functionality may be expressed in the form of firmware or hardware (circuitry) logic; writing such code or designing such logic would be routine in light of the above disclosure.

[0050] The computer code is conventionally stored in code memory (computer readable storage medium, e.g., ROM) 40 (as object code or source code) associated with processor 38 for execution by processor 38. The incoming message (data) to be ciphered or deciphered or otherwise processed is received at port 32 and stored in computer readable storage medium (memory, e.g., RAM) 36 where it is coupled to processor 38. Processor 38 conventionally partitions the message into suitable sized blocks at software partitioning module 42. Other software (code) modules in processor 38 include the algorithm module 46 which carries out the block cipher cryptographic algorithm functionality set forth above.

[0051] Also coupled to processor 38 is the computer readable storage medium (memory) 52 for storing the tables, as well as a third storage 58 for the resulting output data, e.g., the decrypted or encrypted input data. Storage locations 36, 52, 58 may be in one or several conventional physical memory devices (such as semiconductor RAM or its variants or a hard disk drive).

[0052] Electric signals are conventionally carried between the various elements of FIG. 9. Not shown in FIG. 9 is the subsequent conventional use of the resulting ciphered or deciphered message.

[0053] FIG. 10 shows further detail of the computing device in one embodiment. FIG. 10 illustrates a typical and conventional computing system 60 that may be employed to implement processing functionality in embodiments of the invention and shows additional detail of the FIG. 9 system. Computing systems of this type may be used in a computer server or user (client) computer or other computing device, for example. Those skilled in the relevant art will also recognize how to implement embodiments of the invention using other computer systems or architectures. Computing system 60 may represent, for example, a desktop, laptop or notebook computer, hand-held computing device (personal digital assistant (PDA), cell phone, palmtop, etc.), mainframe, server, client, or any other type of special or general purpose computing device as may be desirable or appropriate for a given application or environment. Computing system 60 can include one or more processors, such as a processor 64 (equivalent to processor 38 in FIG. 9). Processor 64 can be implemented using a general or special purpose processing engine such as, for example, a microprocessor, microcontroller or other control logic. In this example, processor 64 is connected to a bus 62 or other communications medium.

[0054] Computing system 60 can also include a main memory 68 (equivalent to memories 36, 52, 58), such as random access memory (RAM) or other dynamic memory, for storing information and instructions to be executed by processor 64. Main memory 68 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 64. Computing system 60 may likewise include a read only memory (ROM) or other static storage device coupled to bus 62 for storing static information and instructions for processor 64.

[0055] Computing system 60 may also include information storage system 70, which may include, for example, a media drive 62 and a removable storage interface 80. The media drive 72 may include a drive or other mechanism to support fixed or removable storage media, such as flash memory, a hard disk drive, a floppy disk drive, a magnetic tape drive, an optical disk drive, a compact disk (CD) or digital versatile disk (DVD) drive (R or RW), or other removable or fixed media drive. Storage media 78 may include, for example, a hard disk, floppy disk, magnetic tape, optical disk, CD or DVD, or other fixed or removable medium that is read by and written to by media drive 72. As these examples illustrate, the storage media 78 may include a computer-readable storage medium having stored therein particular computer software or data.

[0056] In alternative embodiments, information storage system 70 may include other similar components for allowing computer programs or other instructions or data to be loaded into computing system 60. Such components may include, for example, a removable storage unit 82 and an interface 80, such as a program cartridge and cartridge interface, a removable memory (for example, a flash memory or other removable memory module) and memory slot, and other removable storage units 82 and interfaces 80 that allow software and data to be transferred from the removable storage unit 78 to computing system 60.

[0057] Computing system 60 can also include a communications interface 84 (equivalent to port 32 in FIG. 9). Communications interface 84 can be used to allow software and data to be transferred between computing system 60 and external devices. Examples of

communications interface 84 can include a modem, a network interface (such as an Ethernet or other network interface card (NIC)), a communications port (such as for example, a USB port), a PCMCIA slot and card, etc. Software and data transferred via communications interface 84 are in the form of signals which can be electronic, electromagnetic, optical or other signals capable of being received by communications interface 84. These signals are provided to communications interface 84 via a channel 88. This channel 88 may carry signals and may be implemented using a wireless medium, wire or cable, fiber optics, or other communications medium. Some examples of a channel include a phone line, a cellular phone link, an RF link, a network interface, a local or wide area network, and other communications channels.

[0058] In this disclosure, the terms "computer program product," "computer-readable medium" and the like may be used generally to refer to media such as, for example, memory 68, storage device 78, or storage unit 82. These and other forms of computer-readable media may store one or more instructions for use by processor 64, to cause the processor to perform specified operations. Such instructions, generally referred to as "computer program code" (which may be grouped in the form of computer programs or other groupings), when executed, enable the computing system 60 to perform functions of embodiments of the invention. Note that the code may directly cause the processor to perform specified operations, be compiled to do so, and/or be combined with other software, hardware, and/or firmware elements (e.g., libraries for performing standard functions) to do so.

[0059] In an embodiment where the elements are implemented using software, the software may be stored in a computer-readable medium and loaded into computing system 60 using, for example, removable storage drive 74, drive 72 or communications interface 84. The control logic (in this example, software instructions or computer program code), when executed by the processor 64, causes the processor 64 to perform the functions of

embodiments of the invention as described herein.

[0060] This disclosure is illustrative and not limiting. Further modifications will be apparent to these skilled in the art in light of this disclosure and are intended to fall within the scope of the appended claims.