Verifiable, leak-resistant encryption and decryption

219906/2

FIELD

This patent relates to techniques for processing encrypted data inputs, and more specifically, to protecting such systems and data against external monitoring attacks.

BACKGROUND

Systems that operate on sensitive data need to protect against the unauthorized access to, or disclosure or alteration of, such data by attackers. Attackers who gain access to cryptographic keys and other secrets could steal or tamper with the sensitive data, leading to severe consequences such as subversion of critical operations of the system through the introduction of unauthorized commands and the exposure of confidential or proprietary information. One compromised element may also be used to mount further attacks, endangering other elements of a system. More specifically, previous research has shown that an attacker can monitor a device' s external characteristics such as operation timing, power consumption and/or electromagnetic radiation and use this additional information to extract the secret keys being used within the device. For example, as described by Kocher et al (see P. Kocher, J. Jaffe, B. Jun, “Differential Power Analysis,” Advances in Cryptology - Crypto 99 proceedings, Lecture Notes In Computer Science Vol. 1666, Springer-Verlag, 1999), it is well known in the art that external monitoring of a device performing a sequence A.S. 23/04/2013 1 WO 2011/068996 PCT/US2010/058768 of cryptographic operations using the same set of keys with different data can result in the leakage of the key.

Because external monitoring attacks are typically passive and non-invasive, traditional tamper resistance defenses which are based on thwarting physical access or 5 detecting improper usage are insufficient or impractical to provide protection against such attacks. For example, methods for managing secret keys using physically secure, well-shielded rooms are known, in the background art. However, in many applications, requiring cryptographic systems to remain in physically isolated facilities is not feasible, given the environments in which they are expected to operate. 10 In addition, such facilities are expensive to build and operate, and may still be imperfect in their ability to prevent small amounts of information from leaking to adversaries.

Of course, other methods are known in the background art that can mitigate the problem of information leakage from monitoring attacks without necessarily 15 relying on physical shielding. These include methods for reducing the amount (or rate) of information leaking from transactions, modifying cryptographic algorithm implementations to randomize computational intermediates, and/or introducing noise in power consumption and operation timing.

For example, United States Patent 6539092, entitled “Leak-Resistant 20 Cryptographic Indexed Key Update,” provides methods for converting a shared master key and an index value (e.g., a counter) into a transaction key, where the derivation is protected against external monitoring attacks. Those methods work well in applications where the device(s) being protected against external monitoring attacks can contribute to the derivation of the transaction key. For example, the '092 25 patent describes how a smartcard can maintain an index counter which increments with each transaction, then use the index counter in the key derivation.

There are applications, however, where the participant(s) in a protocol should be protected against external monitoring attacks, but lack the ability to store sequence counters and updated keys, as described in the '092 patent. For example, consider the 30 case where a device needs to regularly process the same input data, such as a device which contains a fixed and unchanging embedded key that is repeatedly used to decrypt ciphertexts in arbitrary order. Firmware encryption is an example of such an application; a microprocessor may be manufactured having an embedded key in fuses, and on every reboot the microprocessor needs to re-decrypt its firmware image loaded 2 WO 2011/068996 PCT/US2010/058768 from an untrusted external flash. The firmware image may occasionally be updated, but the same ciphertext may also be decrypted repeatedly. Thus, both the application requirements and the physical manufacturing limitations (such as the inability to modify stored keys due to the use of one-time-programmable fuses to hold keys) can make it impractical for the device to limit the number of times the decryption key will be used. The firmware publisher could use the methods described in the '092 patent with a new index value each time a new encrypted firmware image is released, but the decrypting device cannot use a different index value on each reboot, since changing the index value to a value other than the one used by the encrypting device would result in an incorrect decryption. Thus, an attacker can potentially supply the decryption device with tampered data sets, then attempt to recover the secret key by monitoring external characteristics while the device processes (e.g., decrypts, etc.) these ciphertexts. Statistical side channel attacks, such as differential power analysis (DPA), can deduce a secret key from a set of measurements collected when a device uses the same key. repeatedly to operate on different input values (such as the different firmware ciphertexts or tampered versions of the same firmware ciphertexts in the foregoing examples). Measurements from a single long message (e.g., comprising many block cipher inputs) or a collection of legitimate messages (such as multiple firmware versions) may also provide sufficient data for a side channel attack, even if ciphertext messages are not tampered.

Of course, in some situations where a device uses the same key for every transaction, the device could theoretically implement a lock-out (e.g., by self-destructing if a transaction or failure threshold is exceeded) to limit the number of transactions an adversary can observe. Lock-out mechanisms, however, introduce numerous practical problems, however, such as reliability concerns and the difficulties associated with storing a failure counter (e.g., many semiconductor manufacturing processes lack secure on-chip nonvolatile storage, and off-chip storage is difficult to secure).

In light of all the foregoing, a method that provides a verifiably secure way for devices to communicate and exchange data, with protection against external monitoring attacks and the ability for devices to reject non-genuine data, wouid be advantageous. 3 WO 2011/068996 PCT/US2010/058768

SUMMARY

This patent describes ways to secure devices which utilize secret cryptographic keys against external monitoring attacks, as well as to provide 5 improved security against conventional cryptanalysis and other attacks (such as DPA and other forms of external monitoring attacks) which gather information correlated to the device’s internal operations. Various exemplary embodiments for encrypting sensitive data are disclosed in the specification.

While these various embodiments may vary considerably in their details, they 10 are all encompassed within the following general technique, as may be readily verified with respect to the various embodiments described in the specification: With respect to encryption, each set of data to be encrypted is associated with a message identifier (such as a transaction/message counter, a hash of the plaintext, a random value, or another unique or semi-unique value). The encryption device derives a 15 message key using the message identifier and an initial secret internal state that is shared with the decryption device(s). This derivation is performed in an iterative manner through a succession of one or more intermediate keys, starting from at least a portion of the shared secret internal state and leading up to the message key, where, in each iteration, the next key depends on at least one prior key and at least a portion of 20 the message identifier. The plaintext may be decomposed into one or more segments. Each plaintext segment is encrypted with one or more secret keys that can include the message key, or keys further derived from the message key, to create the corresponding encrypted segment. Typically, a different key (or a different set of keys) is used for each segment. 25 The encrypting device then uses a secret key shared with the decrypting device (such as tlie message key, the secret internal secret, a different key, keys derived from the foregoing, etc.) to compute at least one validator. Derivation of the validator may be performed using an iterative process similar to that used to produce the message key, whereby a sequence of transformations are applied to the secret key to produce 30 successive values (for example, where the generation of each intermediate includes hashing its parent value).

The encrypting device outputs the one or more encrypted segments and one or more validators. Additional information may also be output as needed to enable the recipient to determine the message identifier. 4 WO 2011/068996 PCT/US2010/058768

During the corresponding decryption process, a decrypting device receives the one or more encrypted segments, one or more validator(s), and the message identifier corresponding to the encrypted segment(s). It then uses one or more validators to verify that at least the first encrypted segment to be decrypted has not been modified. 5 Verification of the validator may include computing a sequence of successive intermediate values, starting with a secret shared with the encrypting device and where each intermediate is the hash of its parent (and the specific hash operation depends on a portion of the hash of said encrypted segment(s)). Typically, the decryption process for an encrypted segment is only permitted to proceed if it is 10 verified that the segment is not modified. If verification is successful, the decrypting device computes the message key (if not already derived), using tlie secret internal state that it shares with the encryption devices, by following the same iterative key derivation process followed by the encrypting device (i.e., starting from at least a portion of the shared secret internal state, leading to the final message key, through a 15 sequence of intermediate keys, where at each step the next key depends on at least a portion of the message identifier and at least one prior key). Each encrypted segment (if determined to be unmodified) is decrypted with the one or more corresponding secret keys derived from the message key to recover the corresponding plaintext segment. 20

BRIEF DESCRIPTION OF THE FIGURES

Figure 1 shows an exemplary embodiment of the overall process for verifiable, 25 leak-resistant encryption using key and ciphertext hash chaining.

Figure 2 shows an exemplary embodiment of a leak resistant, key-tree-based key derivation process starting from a shared cryptographic secret, Kstart, and continuing through a path Pj. ..Pq. The key derivation process of Figure 2 is usable in connection with the first exemplary encryption process of Figures 1 & 3 and the first 30 exemplary decryption process of Figure 4. It is also usable in connection with the other exemplary encryption processes of Figures 5, II & 13, and the other exemplary decryption processes of Figures 6,12 & 14. 5 WO 2011/068996 PCT/US2010/058768

Figure 3 shows an exemplary embodiment of a leak-resistant key and ciphertext hash chaining process for encryption (e.g., comprising part of the overall encryption process shown in Figure 1).

Figure 4 shows an exemplary embodiment of a verifiable, leak-resistant 5 decryption process using key and ciphertext hash chaining corresponding to the encryption process of Figure 1 (and Figure 3),

Figure 5 shows an exemplary embodiment of a process for verifiable, leak-resistant encryption using key and plaintext hash chaining.

Figure 6 shows an exemplary embodiment of a process for verifiable, leak-10 resistant decryption using key and plaintext hash chaining corresponding to the encryption process of Figure 5.

Figure 7 shows an environment in which verifiable, leak-resistant cryptographic operations are used for loading firmware onto a system on a chip.

Figure 8 shows an environment in which verifiable, leak-resistant 15 cryptographic operations are used within a secure CPU chip, where external memory such as flash and/or RAM is untrusted.

Figure 9 shows an environment in which verifiable, leak-resistant cryptographic operations are used for loading a bitstream image on to a field programmable gate array. 20 Figure 10 shows an environment in which verifiable, leak-resistant cryptographic operations are used in a packet based network communication device.

Figure 11 shows an exemplary embodiment of a process for verifiable packet-level leak-resistant encryption that can be used with the environment described in Figure 10, as well as in other embodiments. 25 Figure 12 shows an exemplary embodiment of a process for verifiable packet- level leak-resistant decryption corresponding to the encryption process described in Figure 11.

Figure 13 shows an exemplary embodiment of an exemplary ENC() operation, using cipher block chaining (CBC) with intra-segment key changes. 30 Figure 14 shows an exemplary embodiment of an exemplary DEC() operation, using cipher block chaining (CBC) with intra-segment key changes, corresponding to the encryption operation of Figure 13. 6 WO 2011/068996 PCT/US2010/058768

DETAILED DESCRIPTION

The techniques described in this patent enable parties to communicate cryptographically-protected sensitive data with increased security against external monitoring attacks. Although exemplary embodiments are described involving two parties, typically referred to as an “encrypting device” and a “decrypting device”, the term “device” is chosen for convenience and need not necessarily correspond directly to any particular role in a system design. The devices may, but are not required to, utilize different form factors or implementations. For example, the encrypting and decrypting devices could both be portable hardware devices. Alternatively, the encrypting device could be a software application running on a server operating in a facility, while the decrypting device could be a portable hardware device (or vice versa). Furthermore, although most cryptographic operations involve two parties, the techniques of this patent can, of course, be applied in environments involving only one party (such as in secure memory or storage systems in which both roles are under a single party’s and/or device’s control, e.g., in the exemplary environment illustrated in Figure 8) or in environments involving more than two parties and/or devices (such as the exemplary embodiment which is illustrated in Figure 10).

ENTROPY REDISTRIBUTION OPERATIONS

As used herein, an “entropy redistribution operation” (or “entropy distribution operation”) is an operation which mixes its input(s) such that unknown information about input bits is redistributed among the output bits. For example, suppose an x bit cryptographic key Ko is processed repeatedly with an entropy redistribution operation f such that key Kj = f(Kj.|) for each i>l. Next, suppose an adversary obtains y bits of information (e.g., obtained as pail of an attempted external monitoring attack) about each of n different keys Kj, providing more than enough information to solve for key K-ο (e.g., y*n > %). The use of the entropy distribution operation f can make such solution computationally infeasible. A cryptographic hash function H is an example of an operation that may be used as an entropy redistribution operation. For example, consider a strong hash function H that produces a 256-bit result. Given a random 256-bit initial key Ko, let Kj=H(Kj.i) for each i>l. An adversary with knowledge of 7 WO 2011/068996 PCT/US2010/058768 (for example) the least-significant bit of each Ko. ..1^999,999 has 1,000,000 bits of data related to Ko. A hypothetical adversary with infinite computing power could find Ko by testing all possible 2 values for Ko to identify a value which is consistent with the known sequence of least-significant bits. Actual adversaries have finite 5 computational power available, however, and the entropy redistribution operation prevents there from being a computationally practical way to solve for Ko (or any other Ki) given the information leaked through attempted external monitoring attacks.

Entropy redistribution operations may be implemented, without limitation, using cryptographic hash functions, operations constructed using block ciphers (such 10 as AES), pseudorandom transformations, pseudorandom permutations, other cryptographic operations, or combinations thereof. As a matter of convenience, certain exemplary embodiments are described with respect to a hash, but those skilled in the art will understand that, pursuant to the foregoing, other entropy redistribution functions may also be used instead or in addition. 15 Multiple entropy redistribution operations can also be constructed from a base operation. By way of example, if two 256-bit entropy redistribution operations fo() and fiQ are required, fo() could comprise applying the SHA-256 cryptographic hash function to the operation identifier string “fo” concatenated with the input to %(), while f|() could comprise applying SHA-256 to the operation identifier string “f 1” 20 concatenated with the input to fi(). Entropy redistribution operations can be construed using the well-known AES block cipher. For example, to implement f0Q. -M), each fiO can use its inPut as an AES-256 key to encrypt a pair of 128-bit input blocks that are unique to the choice of 1 within 0...b-l, yielding 256 bits of output. A wide variety of block cipher based hash function and MAC constructions 25 are also known in the background art and may also employed.

SHARED CRYPTOGRAPHIC VALUES AND OPERATIONS 30 This section describes certain cryptographic value(s) and/or operation(s) shared by both the encryption device, and its corresponding decryption device, used to perform verifiable leak-resistant cryptographic operations as described in this patent. 8 WO 2011/068996 PCT/US2010/058768

The encrypting device and decrypting device are set up so that each has access to a base shared secret cryptographic state value, such as a secret key denoted as Kroot· This secret state may, for example, be stored in one or more of EEPROM, flash, fuses, or other storage on a tamper-resistant chip, and may be derived in whole or in part from other values or processes, or may be obtained externally. The method by which each of these devices obtained Kroot could include, without limitation, each being manufactured with Kroot> the devices negotiating Kroot directly with each other or via third parties (e.g., using protocols utilizing RSA, Diffie-Hellman, or other public key cryptographic techniques, or symmetric techniques), by receiving of Kroot via a physical keying interface, randomly generating Kroot (e.g*» if the encrypting and decrypting device are the same), etc.

In addition, the encrypting device and decrypting device also are both able to compute a set of non-linear cryptographic entropy redistribution operations fo(), fiQ,..., ft-iO, where b > 1 is a positive integer. These b entropy redistribution functions can be configured in a tree structure. For example, a simple b-ary tree structure of height Q (i.e., having Q+l levels, from 0 through Q) can be created by using b distinct entropy distribution functions, foO..Jb-iO, t0 represent the b possible branches of this b-ary tree at each node of the tree, each node representing a possible derived key. In such a tree, starting from a root cryptographic key Kstart (which is at level 0), b possible derived keys can be computed at level 1: Fo(Kstart) for the leftmost branch; ft (Kstart) for the next branch; and continuing until ft-i(Kstart) for the rightmost branch. At level 2, b2 possible keys can be derived, since each of foO„fb-iO could be applied to each of the b possible level 1 keys. Of course, computing a specific level 2 node only requires two, not b2, computations (i.e., the nodes not on the path are not computed). The tree continues for successive levels 1 through Q, where each possible key (i.e., a different node) of a prior level can be processed by applying fo(),.fb-iO *n turn to derive b additional possible derived keys, The entire key tree has Q+l levels, starting with a single node at level 0, continuing with b1 nodes at level i, and ending with bQ nodes at level Q. Thus, there are b^ possible paths from the root node at level 0 to the bQ final nodes at level Q. Each such possible path, corresponding to a unique the sequence of functions applied at the different levels, can be represented as a sequence of Q integers, each integer being selected from (0...b-l). 9 WO 20.11/0689% PCT/US2010/058768

For example, in an exemplary embodiment, b=2. Thus, two entropy redistribution operations, foQ and fi() are used (and may be constructed from a base operation, e.g., as described above). If Q— 128 (i.e., the height is 128), 2128 paths are possible and 128 entropy redistribution function computations are required to derive the level Q key from the level 0 node (i.e., the starting key).

As a variation, embodiments can involve more variety in the choice of b, such as varying the value of b among levels, and/or varying b based on the route taken to a particular level. Likewise, the entropy redistribution operations can also be varied, such as by making the entropy redistribution operations fi() differ at different levels or making these operations depend on the sequence taken to a particular level.

The encrypting and decrypting devices are also able to perform a cryptographic, non-linear key chaining operation g(), which may be (but is not necessarily) distinct from the functions fiO- For example, in one embodiment, gQ consists of a cryptographic hash operation. Variant embodiments can use different functions for different applications of g(), including variants constructed from a base function (e.g., by hashing the input data with a counter or another value representing the application of gQ).

The encrypting device and decrypting device also have a cryptographic, collision-resistant, one-way hash function h() (e.g., employed as a segment hashing function), which may be (but is not necessarily) distinct from the operations fj() and from g().

In an exemplary embodiment, each of the operations fjQ, g(), and h() is constructed from a common cryptographic hash function by computing each operation as the cryptographic hash of an operation identifier and the input data. The operation identifier may, for example, be a zero-terminated string consisting of “f “g” or “h” where # is the value of i for a given fiQ such that the operation identifier for foQ would be “f 0”. The HMAC of an operation identifier using the input as a key may also be used to implement these operations. Hash functions usable with the techniques of this patent include, without limitation, MDS, SI-JA-1, SHA-256, SHA-512, any SFIA3 candidate operation, as well as combinations of the foregoing and constructions using the foregoing (such as HMAC). As used herein, each of the functions BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grostl, Hamsi, JH, Keccak, LANE, Luffa, Shabal, SHAvite-3, SIMD, and Skein is a “SHA3 10 WO 2011/0689% PCT/US2010/058768 candidate operation”. In other embodiments, the hash function is derived using other well known constructions such as, without limitation, Matyas-Meyer-Oseas, Davies-

Meyer, Miyaguchi-Preneel, Merke-Damgard, etc, that convert block ciphers such as AES, DES or other ciphers into a hash function. Transformations that are not 5 collision-resistant (such as MDS, reduced-round variants of hash transformations, or other mixing operations) can also redistribute entropy present in the input, but would be less attractive for use as the one-way function hQ.

Still other embodiments may utilize stream ciphers, potentially including lightweight and potentially cryptographically weak stream ciphers, in implementing 10 entropy redistribution operations fo...b-i(). For example, the stream cipher RC4 may be employed, where the entropy redistribution operation input is used as the RC4 key and the RC4 output bytes are used as (or used to form) the entropy redistribution operation output.

The encrypting device and decrypting device have a secret key encryption 15 function (or set of functions) ENCQ with a corresponding decryption function DEC(). In some embodiments, such as those with fixed-length messages, ENCQ and DEC() may utilize conventional cipher constructions such as AES in ECB or CBC mode. Constructions of ENC() and DEC() for other embodiments are described later with respect to Figure 13 and Figure 14, respectively. 20 EXEMPLARY EMBODIMENT IN FIGURES 1 AND 2

This section describes an exemplary embodiment of the general technique for verifiable leak-resistant encryption and decryption. This first exemplary embodiment 25 uses key chaining and ciphertext hash chaining.

Encryption

For convenience, following the traditional nomenclature in cryptography, we 30 use the term "plaintext" to refer to the data to be encrypted. As those skilled in the art will understand, this does not necessarily mean that the input data is human-readable, and indeed, nothing precludes such data from itself being compressed, encoded, or even encrypted, prior to its being protected with the techniques of this patent. Similarly, those skilled will understand that the term "data" encompasses any 11 WO 2011/0689% PCT/US2010/058768 quantity being processed, and could include, without limitation, content, data, software, code, and any other type of information.

Given a sensitive plaintext data message D to be protected, and with knowledge of a shared base secret cryptographic value ICroot, the encrypting device performs the following steps, as outlined in Figure 1. First it decomposes the sensitive plaintext data D into a sequence of L segments Di, ..., Dl (step 100), where (L > 1), each of which is small enough to fit into the memory for incoming segments in the receiver(s). In addition, the size of each of these segments should be sufficiently small to meet the leakage requirements of the application and implementation. The segments can be, but are not necessarily, the same size. In addition, other variants can also support segments of unlimited size by changing keys (e.g., within ENC() and DEC()) as will be shown below with respect to Figures 13 and 14.

The encrypting device also generates (step 101) a nonce N which (as will be shown below) may be used as a message identifier (or a precursor thereto) for use in connection with the encryption of D. For example, the nonce could be generated using a true random number generator, a pseudorandom number generator, some combination of true and pseudorandom number generators, a counter value or other (preferably unique or seldom-repeating) parameter, or by deriving N from keys and/or data (including without limitation D, e.g., by setting N to the hash of part or all of D) available to the encryption device. In Figure 1, for a given Kroot, the value of N used to encrypt a particular message is preferably not used to encrypt any other message (or if so, any reuse should be limited, unlikely and/or infrequent).

In the exemplary embodiments that follow, a message identifier Hi is formed using nonce N. In the most straightforward implementation, in which N serves as the message identifier, Hi may simply equal N. As another example, in which N serves as a precursor to the message identifier, the encrypting device could compute Hi (step 102) as the hash of N using the function h(). Hashing is useful in situations where one wishes to produce a fixed-size message identifier, for example, to permit the incorporation of longer data values (such as text strings) while operating on shorter quantities for computational efficiency, or to convert variable-length data values to a uniform length message identifier for computational simplicity, or to reduce any ability adversaries may have to influence the selection of Hi. Of course, hashing is 12 WO 2011/068996 PCT/US2010/058768 only one way to produce the message identifier, and those skilled in the art will appreciate that functions other than h may be employed to produce Hj.

After computing Hi, the encrypting device computes a message key, K-message, using the shared base secret cryptographic value Kroot and Hi (103) as input to a leak resistant, key-tree-based key derivation process. For convenience of discussion, the key derivation process is presented here in the context of encryption (e.g., performed by the encrypting device), and more specifically, in the context of the first exemplary encryption process of Figure 1. However, the same key derivation process will also be used in the first exemplary decryption process of Figure 4, in which case it will be performed by the decrypting device. Similarly, the key derivation process will also be used in connection with other processes, including the exemplary encryption processes of Figures 5, 11 & 13, and the exemplary decryption processes of Figures 6,12 &, 14.

An exemplary key derivation process is diagrammed in Figure 2. The process begins with a starting point of the tree, which is denoted Kstart (201), and a path Pi...Pq (202). For example, in Figure 1 step 103 above, Kstart is the value of the shared secret key Kroot and path Pi...Pq (202) is determined by Hi. (The conversion of Hj into Pi...Pq is discussed below.) The path specifies a succession of entropy redistribution operations to be applied to Kstart·

In an exemplary implementation, message identifier Hi is decomposed into Q parts P|,P2,...,Pq. In an exemplary decomposition, each part Pj is an integer from 0 thru (b-1) (e.g., if b=4 then each Pj is a two-bit value (0, 1, 2, or 3)). Likewise, if b=2, each Pj is a single bit (0 or 1). Hence, the path parts Pi...Pq can be used to specify a specific path from Kstart to Kstart,path by applying functions fo(), fiQ, ..., fb-iO to produce a plurality of intermediate keys leading to Kstart,path as follows. First, the function fPl is applied to Kstart (203) to yield an intermediate key Kstart,p,, followed by the application of fp2 on Kstart.p, to yield the intermediate key Kstart.p,,p2 (204) and so on, until the final application of fpQ on the intermediate key Kstart.p, ,p2,... ,pq„, (205) to yield the final derived key, Kstart.p,,p2i... ,pq (206). Note that the derivation of each intermediate key depends on at least one predecessor key (e.g., in the case of Figure 2, its immediate parent) and the relevant portion of the message identifier. For convenience, we shall denote this final derived key with the notation Kstart.path (indicating the key that was reached by starting with Kstart and following PATH). 13 WO 2011/0689% PCT/US2010/058768

Likewise, in the case of Figure 1 step 103, the final derived key (the message key which is assigned to Kmessage) is denoted Kroot.Hj since the starting key is in fact

Kroot> and the path is in fact Pi,P2,... }Pq which is simply the decomposition of Hi. (In alternate embodiments, Kmessage may be derived from Kroot.h ,, e.g., by hashing 5 Kroot.h,· Either way, Kmessage is based on Kroot.h,.)

At step 104, the data segment(s) are encrypted using at least one cryptographic key based on said message key Kmessage, producing ciphertext E=Ei, ,.,, El is from the input segment(s) D=Di,...,Dl . An exemplary embodiment lor step 104 is shown in Figure 3, which depicts the steps and states involved in computing the encrypted 10 segments Ei, ..., El.

The process of Figure 3 uses Kmessage to compute L individual segment encryption keys, Κ,· (i-1 to L), each key being used to encrypt a corresponding segment Dj (i-1 to L) of the secret message data D. First, the function g() is applied to Kmessage to yield Ki (302), the encryption key to be used for the first segment. 15 Then, the function g() is applied to the key Ki to yield K2, the encryption key for the second segment (303), and so on. Finally, tlie function g() is applied to key Kl-i to produce Kl the encryption key for the final segment (305). We refer to this type of process as key chaining because the encryption keys are chained to one another.

After the L keys Kb ..., Kl for encrypting the L segments have been 20 determined, the encryption of the segments proceeds as follows. The final (L’th) segment is processed first, where the plaintext input (306) to the ENC() function is the L’th data segment Dl, concatenated with message integrity value computed by cryptographically hashing the entire plaintext D] ...Dl. (The inclusion of the hash of D)..Dl is optional; embodiments may omit this, or concatenate other data such as 25 sequence of ‘0’ bytes or some other form of padding). This L’th plaintext segment is encrypted by the key Kl to yield the encrypted segment El (307).

Next, the L-l’th segment is processed at (308) by applying the hash function h() to El, appending this hash value to data segment Dl-i, and using the result as the encryption input to the L-l’th segment. At (309), the L-1 ’th plaintext segment is then 30 encrypted using the key Kl-i to yield encrypted segment El-i. This process is repeated for the other segments. For instance, the encryption input (310) corresponding to the second plaintext segment is composed of the second data segment D2 followed by h(E3), tire hash of the third encrypted segment, and input 14 WO 2011/068996 PCT/US2010/058768 (310) is then encrypted using the key K2 to yield the encrypted segment E2 (311). Finally, the encryption input (312) corresponding to the first plaintext segment is composed of the first data segment Di followed by h(E2), the hash of the second encrypted segment (311), and input (311) is then encrypted using the key Kj to yield 5 the encrypted segment Ej (313). (As a variant of the foregoing, the subsequent segment hashes do not need to be encrypted, e.g., Ej could be formed by encrypting Dj then concatenating the encryption result with the hash of Ej4-i.)

The encrypted segments Ei.. .El form the ciphertext E. Step 104 in Figure 1 is then completed. Using the hash of each Ej+i in the computation of Ej effectively 10 chains together the encrypted values, which serves to enable decrypting devices to detect modified (or defective) ciphertext segment(s) prior to decrypting the defective segment(s). We refer to this as “ciphertext hash chaining.” In the example shown above, each ciphertext segment Ej (1 < i < L) depends on the hash of the next ciphertext segment, e.g., a validator V is used to authenticates the hash of the first 15 ciphertext segment (EJ, then Ei yields (after decryption to Di if necessary) the expected hash of E2. Likewise, E2 yields (after decryption if necessary) the hash of segment E3, and so forth.

Note that the process of Figure 3 can still be performed where all the data is in one segment (i.e., L=l) (e.g., because the input message is small or an encryption 20 process ENC() such as the process shown in Figure 13 is employed). For the L=1 case, only Ki is required and Ki - g(KMESSAGE)· Alternately, Kmessage may be used directly as Ki, in which case the operation g() can be omitted altogether. As described above, inclusion of the hash of Di..Dl (which, in this case, would just be Di since L=l) is optional. The result of the process E = Ei, since this is the only 25 segment.

Referring back to Figure 1, after the data segments Di have been computed, a validator V is computed that will enable authorized recipients of the encrypted message to authenticate the ciphertext prior to decryption. First, a value H2 is calculated (105) as the hash of the first encrypted segment Ei. Recall that the first 30 segment Ei incorporates the hashes of all other segments. Thus, the hash of Ei actually reflects the contents of all the segments, including segment Ej, and can be used to verify that none of the segments has been changed. (Optionally, in addition to Ej, the input to the hash producing H2 may also include additional information about the message, such as the length, version number, sender identity, value of N, etc.). 15 WO 2011/0689% PCT/US2010/058768

Next, the encrypting device uses a secret key to compute V (106), which is a validator of the message identifier, and ciphertext segment(s) E,·. Validator V is computed using the hash of at least one ciphertext segment (e.g., the hash H2= h(Ei)) and an initial secret (e.g., Kmessage, or other values as described in the following 5 paragraph). Computation of V may be performed using the leak resistant, key-tree-based key derivation process described in Figure 2, with the starting key Kstart being Kmessage and the path being determined using H2 (106). Thus, the derivation of V includes computing a plurality of successive intermediate values leading to V, where each depends on at least one predecessor (e.g., in the case of Figure 2, its parent 10 value) and the relevant portion of the hash (e.g., H2). Note that the functions £(), the value b, etc. may be (but are not required to be) the same as were used in (103). This process results in the derivation of the key Kmessage,h3 which is (or is further processed to form) the validator V.

The foregoing description commenced with Kmessage in deriving the 15 validator, but alternate embodiments may start with a different value. For example, the key Kmessage at step 104 and the key Kmessage at step 106 may be different from each other but both derived from Kroot.h,· Likewise, the key used at step 106 may be derived from the Kmessage used at step 104, or vise versa, or a different base key (besides Kroot) may be employed as Kstart- Of course, Kroot itself may even be 20 used as Kstart (e.g., if H2 is a hash of N and/or Hi and one or more ciphertext segments).

The validator, as utilized in this patent, is a verifiable cryptographic proof that some putative ciphertext is an unmodified version of an encryption of some plaintext message data associated with a particular message identifier, and was produced by an 25 entity with access to a secret cryptographic value. The validator constructed at step 106 can be conveniently validated by a recipient, such as a decryption device, in a manner that avoids susceptibility to differential power analysis and related external monitoring attacks. In addition, the validator creation process (i.e., the performance of step 106) also enables the encryption device to avoid susceptibility to differential 30 power analysis and related external monitoring attacks.

After computing the validator, the encryption process is complete. At step 107, the result is output. The output data consists of the information (if any, e.g., nonce N) required to enable a recipient to derive the message identifier, the validator 16 WO 2011/068996 PCT/US2010/058768 V, and the encrypted result E (comprising encrypted segments Εμ ..., Εν). By combining key chaining and ciphertext hash chaining, this type of encryption process is able to yield crypto graphically-strong output with message authentication, while avoiding the re-use of secret keys located in the encrypting device in ways that would 5 facilitate differential power analysis and related attacks against the encrypting device. The encryption result is created in a form which enables a decryption device to perform the decryption without re-using secret keys in ways that would facilitate differential power analysis and related attacks against the decryption device. The key-tree process limits the re-use of keys in the formation of Kmessage and the 10 validator V, while the ciphertext hash chaining method limits the use of keys used in the data encryption.

The next section explains how the output data can be subsequently decrypted by the decrypting device. 15 Decryption

Figure 4 shows an exemplary decryption process corresponding to the exemplary encryption process of Figures 1 and 3. As stated earlier, this requires that both the decryption device and the encryption device have the ability to derive the 20 same message identifier (e.g., because each device knows nonce N it can compute HQ, base secret cryptographic value Kroot, cryptographic functions f(), g() and h(). The exemplary decryption process will use the same key derivation process (and key chaining) depicted in Figure 2.

The exemplary decryption process begins at step 400 with obtaining (e.g., over 25 an untrusted digital interface) the putative result of the encryption (namely, the message identifier (e.g., nonce N), the validator V, and the encrypted result E comprising segments Ej, ..., EN). At step 401, the device next computes the value Hi by hashing the received nonce N. Note that, unless the nonce was received incorrectly, the derived Fh will equal the Hi used in the encryption process. At step 30 402, the decrypting device computes the value H2 by hashing the segment Ei (and, if previously used during the encryption, other information about the message that was incorporated into the derivation of H2). At step 403, the device attempts to compute the message key, Kmessage, using the leak resistant, key-tree-based key derivation process described in Figure 2, with Kstart^Kroot and PATH = Hj. At step 404, the 17 WO 2011/068996 PCT/US2010/058768 device computes the expected validator V’, by using the same leak resistant, key-tree- based key derivation process as the encrypting device (e.g., the process in Figure 2 using the key Kstart^Kmessage and PATH^HQ. At step 405, the computed value V’ is compared with the received validator V. If the expected validator V’ does not 5 match the provided validator V, the process terminates with an error (step 406) since the provided data may have been corrupted or maliciously modified, or some other error has occurred.

If the check at step 405 is successful, then the process moves to step 407 where a counter i is initialized to the value 1, a key register K is initialized to the 10 result of computing g(K-MEssAGE) which is the key for decrypting the first encrypted segment Ei (i.e., the value of Ki which is labeled 302 in Figure 3). Also at step 407, a variable H is initialized to 1¼ The following operations are then performed in a loop as shown Figure 4. First, the hash of the next ciphertext segment to be decrypted (i.e., h(Es)) is computed and compared with the expected hash H (step 408). If the 15 comparison fails, the encrypted segment has been altered, so the process terminates with an error (409) and no further decryption is performed. If the comparison succeeds at step 408, the segment Ej is decrypted at step 410, using the decryption function DECO, with the key K to yield the decrypted segment, which is interpreted as containing the plaintext Dj followed by the purported hash of the next ciphertext 20 segment. H is set to this purported hash value. Next, at step 411, a check is performed to see if all the L segments have been decrypted (i.e., whether the counter i equals L). If the counter has not yet reached L, then in step 412, the counter i is incremented and the register K is updated to the decryption key for the next segment by computing K = g(K), and the process is repeated from step 408 onwards. If step

25 411 determines that i has reached L, a check is performed at step 413 to see if H equals the expected pad data (e.g., the hash of D]...Dl). If this check fails, the decryption ends with a failure condition (414). If the check succeeds, then the decryption process is successful and the recovered decrypted output D - D i, ..., Dl is returned at step 415. 30 Note that in this embodiment, the decryption process can be done in a streaming manner (i.e., the decryption device could initially obtain Ν, V and Ei and then receive the remaining segments E2,..,El one at a time), and still be able to carry out the steps outlined above. Streaming operation is, for example, useful if the decrypting device lacks sufficient memory to hold the entire message, or if initial 18 WO 2011/068996 PCT/US2010/058768 portions of the decrypted data need to be available before the all of the data has been received and decrypted..

SECOND EXEMPLARY EMBODIMENT 5

This section describes a second exemplary embodiment of the general technique for verifiable leak-resistant encryption and decryption. In contrast to the first exemplary embodiment which used ciphertext hash chaining, the second exemplary embodiment uses plaintext hash chaining. However, in both cases, the re- 10 use of keys is controlled at both the encrypting device and the decrypting device to prevent differential power analysis and related attacks.

Encryption 15 The second exemplary embodiment of encryption by the encrypting device is shown in Figure 5 which, for the sake of conciseness, is depicted as a combined process diagram and state diagram. The encrypting device creates or obtains the message to encrypt, D, and a message identifier N, which may be a counter, randomly-generated value, plaintext hash, etc. 20 The input message D is divided into a sequence of segments Di, ..., Dl (although L=1 is permitted), and these segments are used to create the plaintext segments Bi, ..., Bl as follows. First, segment Bi (501) is formed by concatenating message segment Dj with the hash of any desired message data (denoted as X, which may include elements such as length L, message identifier N, a transaction identifier 25 or counter, etc.) Next, B2 (502) is formed by concatenating D2 with h(B|) (i.e., the hash of Bi). Each subsequent Bj up to Bl-i is then formed by concatenating Dj with the hash of Bm. Finally, the last plaintext segment Bl (504) is formed by concatenating Dl with h(BL-i).

The next steps of the process (505-508) generate encryption keys for each of 30 the plaintext segments using a key chaining process so that, similar to the first exemplary embodiment, each encryption key is directly or indirectly based on the message key. In the second exemplary embodiment, the first encryption key Ki is simply set to the value of message key Kmessage derived (505) by computing h(N) and then Kj= Kmessage = Kroot, h(N) using the leak resistant, key-tree-based key 19 WO 2011/068996 PCT/US2010/058768 derivation process as described in Figure 2 with Kstart - Kroot and PATH =h(N). Key Kj for i>l is computed as g(Ku), where g(). Thus, the second key K2 is the result of computing g(Ki) (506). This process is repeated so that the L-l ’th key (Kn) is computed as g(Kt-2) (507), and the final segment key Kl is computed as g(KL-i) (508) .) Thus, every key Kj is based on (e.g., equal to or derived using) the message key Kmessage·

The next step in the process is the encryption of each of the plaintext segments Bi, ..., Bl with the corresponding keys Ki, ..., KL to yield the encrypted segments Ei,...,El- For instance, encrypted segment E( is created by encrypting Bi with Ki (509) , E2 is created by encrypting B2 with K2 (510), and so on, with El-i created by encrypting Bl-i with Kl-i (511), and El is created by encrypting Bl with Kl (512). The encrypted result E consists of the segments Ei,..., El-

The next step in the process is the computation of the validator V for the encryption (513). First, the hash function h() is used to compute h(N || Ej ||. · II El) 11 1i(Bl)), where “||” denotes concatenation. Next, Z - h(N || Ei || ... || El || h(BL)) is computed, then Kroot. z is computed using leak resistant key-tree-based key derivation process (e.g., as described in Figure 2, with Kstart^Kroot and the PATH=Z). The validator V is then computed as the hash of the key tree result (i.e., h(KRooT,z))· Finally, the result of the encryption process is provided, comprising N, h(BL)> E, and the validator V (514).

The encryption process above can be employed in systems where the input data D arrives by streaming, or where for other reasons D cannot be processed all at once (e.g., because of memory limitations). In this case, the encrypting device commences by obtaining N, h(X), and Kj. In addition, a running hash computation is initialized with N,

1. Create or obtain N 2. Initialize running hash calculation 3. LetH = h(X) 4. Let K - Kroot,h(N)

5. Update running hash calculation with N 6. Let i - 1 7. Receive input data Dj (e.g., streaming in)

8. Create Bi - concatenation of Di and H 9. Let H - h(Bs)

10. Create Ei = ENC(K, DQ 11. Update running hash calculation with E, 12. Output Ej 13. Increment! 20 219906/2 14. If there is more input data, go to step 7

15. Update running hash calculation with H

16. Finalize running hash calculation and store in Z 17. Compute V= h(KROOT,Z)

18. Output H (which equals h(BL)), N, V

Decryption

The process of decryption is illustrated in Figure 6. At step 600, the decrypting device receives (typically from an untrusted interface) the purported results of the encryption process, namely E, h(BL), nonce N, and validator V. The decrypting device divides E into E1,...,EL, initializes a counter i to be 1, and sets a register H to be the received value hash h(BL). The length of the message L is also received or determined (e.g., if a segment size of 1 kilobyte is used for all but the last segment, which may be less than 1 kilobyte, then L is the length of the message in kilobytes, rounded up). At step 605, the decrypting device computes Z= h(N ll E1 ll... ll EL, ll H), where “ll” denotes concatenation. At step (610), the decrypting device computes the value of KROOT,Z using the leak resistant key-tree-based key derivation process described in Figure 2, with the root being KSTART=KROOT and the PATH=Z., and then hashes the result to yield h(KROOT,Z). Then it compares the computed h(KROOT,Z) with the received validator V. If the result does not equal V, there is data corruption and the process is stopped at 611 without performing any decryption. If the check succeeds, then at step 620 the decrypting device computes h(N), then initializes key register K with the result of computing KROOT, h(N) using the leak resistant key-tree-based key derivation process described in Figure 2, with KSTART=KROOT and PATH=h(N) and sets a counter i to be 1.

Next, the following operations are performed in a loop: At step 630, the segment Ei is decrypted with the key in key register K to produce a plain text segment Bi which consists of a data segment Di and a hash value. At step 640 the hash from of the decrypted current segment is checked. For the first segment (i.e., i=1), the hash is compared against h(X), where X consists of the same fields as X during encryption. For segments after the first one (i.e., i>1), the hash from Bi is compared against the hash of the prior segment (i.e., h(Bi-1)). If the comparison fails, the decryption process fails at step 641. Otherwise, at step 650, the message portion of Bi (i.e., Di) is added to the output buffer (e.g., in RAM), and key register K is advanced to the next segment key by computing g(K) then storing the result in K. The counter i is also 21 WO 2011/068996 PCT/US2010/058768 incremented by 1. At step 660, the value of i is compared with L and, if the value of i does not exceed L, the decryption process loops back to step 630. Otherwise, the decryption process is complete and at step 670, where the hash of the last plaintext segment (i.e., h(Bt)), is compared to the received hash H. If the comparison at step 5 670 fails (i.e., the values are not equal), an error has occurred and the decryption fails (step 671). Otherwise the result data D|,...,Dl are output in step 680.

In this embodiment, the hashes of the plaintext are chained, with plaintext segment Bi containing the hash of the plaintext Bj-i. This chaining, while not strictly necessary for leakage resistance, provides the additional property that any faults that 10 occur during the decryption process can be detected because the plaintext is verified to be that same as what was encrypted. Thus, this embodiment is advantageous for use in environments where there is potential for corruption the decryption process.

15 SYSTEMS, APPLICATIONS, AND VARIANTS

Up to this point, this patent has described a general technique for leak-resistant encryption and decryption, together with some exemplary embodiments of that technique. This section will describe some exemplary systems and/or applications in 20 which the foregoing can be utilized, as well as additional variants of aspects of the exemplary embodiments described above.

Secure Firmware Loading 25 Figure 7 shows the application of verifiable leak-resistant cryptography for securely loading sensitive firmware on a central processing unit (CPU), e.g., as part of a so-called system on a chip (SoC). For convenience, depending on context, the reference numerals may refer to steps in a process, and/or to quantities used (or produced) by such process steps. In this embodiment, the SoC consists of a single 30 integrated circuit (700), containing a CPU (703), and various types of memory. The memories may include, without limitation, random access memory (RAM) (701) from which code may be executed, read-only-memory (ROM) (704) containing trusted bootstrap code, and a secret state storage memory (702) that holds a shared cryptographic secret Kroot· The key storage memory could be implemented using a 22 219906/2 variety of techniques, such as, without limitation, fuses/antifuses, battery backed RAM, and EEPROM. The SoC may have an external power input (707) which may receive power from an untrusted source (e.g., potentially under the control and/or observation of adversaries). An externally supplied clock (708) may also be received (and may be used with PLLs to form additional clocks). The SoC has a cryptographic hardware component (705) with an AES engine for data encryption and decryption, a hash function engine, such as, without limitation, a SHA-1 or SHA-256 or a AES based hash function engine, and an implementation of the leak resistant, key-tree-based key derivation process based on Figure 2, with functions f0 0,...,fb-1 .() implemented using the hash function and/or the AES function or their variants. It should be obvious to those skilled in the art that, in other embodiments, the entire functionality of the cryptographic hardware component (705), or some subset thereof could be performed by software (e.g., by the CPU).

Upon bootstrap from the trusted bootstrap code in ROM, the SoC loads its sensitive software/data, over an untrusted interface (706), from an external, untrusted storage device, which in this embodiment is flash memory (709). To protect the sensitive software/data from disclosure or unauthorized modification, it is encrypted using the verifiable leak-resistant techniques (e.g., as shown in Figures 1 or 5) by a device manufacturer or other code issuer using the shared secret cryptographic value KROOT. The encryption result is stored in the flash memory (709). The SoC first loads the encrypted code/data from the flash memory (709) to its internal RAM (701). It then performs the leak resistant decryption (e.g., as shown in Figure 4), where the process is implemented in the trusted bootstrap code store in ROM (704) cryptographic hardware component (705), and is performed using the shared secret key KROOT from keystore (702). If successful, this process creates a validated and decrypted sensitive code/data image within RAM memory (701), which may then be executed. In case the decryption process fails, the encrypted code/data (and any partially decrypted code/data) in RAM is flushed and the operation restarted from the beginning when required.

In an optional enhancement to this embodiment, security is complemented by storing a minimum acceptable software version number in fuses, battery backed memory, or other local storage of the device onto which the software is to be loaded. All software to be loaded into the device would carry a version number, and the device would only accept software with a version number greater than the minimum. 23 WO 2011/068996 PCT/US2010/058768

In addition, some software versions might specifically instruct the SoC to update the minimum acceptable software version number, thereby preventing malicious rollback of software to a prior version that was deemed unacceptable. The foregoing anti rollback methods could be implemented independently of (i.e., as an adjunct to) the 5 verifiable leak-resistant operations. Alternatively, the anti-rollback methods could be implemented as part of the message identifier, the validator, or the other secured quantities used in the verifiable leak-resistant operations.

Those with ordinary skill in the art will easily recognize that SoC applications are not limited to the specific architecture presented herein, and SoCs or other devices 10 with a different internal architecture and/or components from the embodiment presented in Figure 7 may be protected.

For example, Figure 8 shows the application of verifiable leak-resistant cryptography to a secure processor architecture (800). For convenience, depending on context, the reference numerals may refer to steps in a process, and/or to quantities 15 used (or produced) by such process steps. In this setting, the device contains a CPU, a keystore that holds internal secret state including a base secret cryptographic key Kroot- Non-volatile storage, such as, without limitation, fuses (801) may be employed for storing the internal secret state. The cryptographic hardware subcomponent (804) encrypts and/or integrity protects and/or replay protects all data 20 moving out of the on-chip data/instruction cache (803) to external insecure RAM memory (806), and decrypts and/or integrity checks and/or replay checks all data being fetched from external insecure RAM memory. In addition, all code is stored in encrypted and integrity protected form in the insecure flash (805) and is decrypted and integrity checked when brought into the on-chip data/instruction cache (803). 25 Exemplary processor architectures of the background art whose security could be improved through the addition of verifiable leak-resistant cryptography include, without limitation, the Secure Blue design from IBM (announced in an IBM press release entitled “IBM Extends Enhanced Data Security to Consumer Electronics Products” on April 6th 2006) and the AEGIS design from MIT (described in AEGIS: 30 Architecture for Tamper-evident and Tamper-resistant Processing, Proceedings of the 17th Annual International Conference on Supercomputing, pages 160- 171, 2003).

The use of verifiable leak-resistant cryptography substantially improves the security of existing processor designs by providing protection against monitoring attacks. In particular, this embodiment enhances the cryptographic hardware 24 219906/2 subcomponent (804) to include a hash function and a key tree processing capability that reuses the (e.g., AES) encryption capability of an existing secure processor design and implements the steps and method of the first exemplary embodiment to create a secure leak-resistant secure processor. In particular, any data written from cache (803) to the RAM memory (806) is encrypted using the leak resistant encryption process (e.g., as shown in Figure 1) and any code read from untrusted flash (805) and untrusted RAM is decrypted using the leak resistant decryption process outlined in Figure 4. When data are written to a particular segment, a counter corresponding to the segment is incremented, and the counter value is incorporated in the encryption and/or integrity check creation process for the segment, thereby enabling the detection of attacks that involve substitution of old data. FPGA Bitstream Loading

The logic to be loaded into a field programmable gate array (FPGA) often contains highly sensitive trade secrets, cryptographic secrets, and/or other sensitive information that needs to be protected from disclosure or copying. This loaded logic or upgraded logic is typically supplied to the FPGA as a bitstream from an external source, such as, without limitation, a flash memory device or a CPU or some other source (907). Some FPGAs contain nonvolatile memory for storing configuration data, while others must be reloaded each time the chip is powered on. Existing FPGAs have the ability to decrypt bitstreams, typically using a key that is held in a battery-backed memory or stored locally (such as using on-chip flash, EEPROM, or fuses). The FPGA decrypts the supplied encrypted bitstream before (or while) installing it into the programmable slices present within the FPGA. Differential power analysis attacks and related external monitoring attacks can be attempted against the bitstream decryption processes, posing a serious security risk as a successful attack can result in disclosure of the bitstream decryption key and/or the bitstream itself.

Referring to Figure 9, verifiable leak-resistant cryptography can be used to create a secure bitstream decryption capability on an FPGA. Prior to decryption, the sensitive bitstream is encrypted by an external device (using software, hardware or some combination thereof) using a leak-resistant encryption process (e.g., as described in the first exemplary embodiment), producing the encrypted bitstream. 25 WO 2011/068996 PCT/US2010/058768

The encrypted bitstream may be located (907) in an untrusted memory, such as an external flash or hard drive, or retrieved from an untrusted source such as a CPU etc.

Within the FPGA, the cryptographic secret Kroot for leak-resistant decryption is kept in the keystore (902) which stores the internal secret state, and which may be 5 implemented using technologies such as, without limitation, irises, battery-backed RAM (902, 903), EEPROM, flash, etc. The FPGA (900) receives the encrypted bitstream over interface (906). This bitstream could, for example, have been encrypted using either of the first embodiment or the second exemplary embodiment (corresponding to Figures 1 and 5). 10 If the embodiment of Figure 1 was used for encryption, the FPGA first receives nonce N, validator V, length L, and initial segment E|. Ei is stored in encrypted segment buffer (905). Using a leak-resistant decryption process as described above (e.g., see Figures 4), the hash of Ei is computed, and validator V is verified, with KROot, L, and the hash, yielding (if successful) Kmessage or a fatal error 15 (in which case the process halts). If successful, the FPGA uses the segment decryption processing component (904) to perform the leak resistant decryption process on Ei, The decryption of Ej yields the hash of segment E2, which is loaded, verified, and decrypted. The process continues one segment at a time, until the final segment is decrypted and verified. If an error occurs, the process halts and all partial 20 FPGA decrypted data are wiped. (Upon failure the process can be re-started again from the beginning.) One or more status registers 910 are used to track the status of the bitstream loading process (e.g., tracking whether the process is in-progress, failed, or complete). The status can also be exported for diagnostic purposes and for use by external components. Once all segments have been loaded successfully, the FPGA is 25 now configured and can be used (e.g., the FPGA can now permit I/O, clocking, etc. to be applied to the loaded bitstream image). FPGA operation can be prevented until the bitstream is fully loaded (e.g., to avoid revealing information about an incomplete FPGA image and to avoid unpredictable behavior of the overall circuit arising from incorrect FPGA configuration). 30 If the second embodiment of Figure 5 was used for encryption, the FPGA first receives Ε, V, N, and XBl), and stores E in a buffer. The FPGA’s segment decryption processing component 904 then uses the method described in Figure 6 to validate and decrypt the provided encrypted segments. Status register(s) 910 are used to track the status of the bitstream loading, validation, and decryption processes, and 26 WO 2011/068996 PCT/US2010/058768 any serious error results in the halting of the process and the wiping of any partial decrypted data.

Network Communications and Other Packet-Based Applications

Figure 10 shows the application of verifiable leak-resistant cryptography to protecting network communications from external monitoring attacks. In this embodiment, multiple network devices, such as Device A (1000), Device B (1030) and Devices C, D, E, etc. (1040) communicate with each other over a network (1020). Some or all of these communications may contain sensitive information, making it useful to encrypt and authenticate the data. Moreover, some of these devices (such as Device A in this embodiment) are required to protect their cryptographic computations and keys from external monitoring attacks.

Device A has a keystore (1001) to store a table of shared cryptographic root keys with other devices it needs to communicate with. These keys may have been previously stored, or may be negotiated (e.g., using public key cryptography). Methods for using public key cryptosystems to negotiate keys are well known in the background art, and are utilized in protocols such as SSL and IPSEC, This embodiment could easily be integrated into these or other protocols.

Outbound packets or data segments to be encrypted originate from an application, operating system, driver, or other component (1002) and enter plaintext packet buffer (1003), Each packet is then processed using the segment encryption/decryption processing component (1004), where it is encrypted using a verifiable leak resistant encryption method (e.g., as described in Figure 1). The root key for this encryption is the shared key between Device A and the destination device, which is obtained from the keystore (1001). For this processing, the message identifier nonce N may be any (preferably) unique value, including a counter. For example, the nonce could equal a packet identifier, a TCP sequence number with possibly the incorporation of additional most-significant bits to prevent overflows), the hash of a value, a random value, etc. For each packet, the leak resistant encryption operation produces an encrypted segment and a validator V. The nonce may be transmitted or may be implicit (e.g., based on the number of packets received previously). The encrypted segment, V, and any other required data are assembled 27 WO 2011/068996 PCT/US2010/058768 into an outgoing packet and moved to the network interface component (1006) and then to the network (1020) for routing to the appropriate destination device.

For inbound encrypted packets, it is assumed that the sending device has performed the encryption as described above. These packets are received from the network (1020) by the network interface component (1006) and then moved to the ciphertext packet buffer (1005). Each packet is then processed by segment encryption/decryption processing component (1004), where a leak-resistant decryption process (e.g., as described in Figure 4) is performed. For this decryption process, (i) the shared key between the receiving and sending device (e.g., Kroot or a precursor used to derive Kroot) is obtained from keystore (1001), (ii) the nonce N is recovered from the packet or otherwise determined, (iii) the validator is verified against N and the encrypted packet, and (iv) if the validator is correct, the packet data are decrypted. The shared cryptographic secret between Device A and the sending device may be used as Kroot· If the decryption or validation fails, the packet is dropped. Otherwise, upon successful decryption, the decryption result can be provided to the application, operating system, driver, etc.

This process is outlined in Figures 11 and 12, Figure 11 illustrates the verifiable packet level leak-resistant encryption process and Figure 12 illustrates the corresponding decryption process. The verifiable packet level leak-resistant encryption process is the following: Given an input packet data D (1100) with the source and destination sharing a base cryptographic value Kroot, a message identifier N is generated in step 1101 (e.g., using a random source and/or information present in the packet D and/or some packet identifier such as a sequence number associated with the communication protocol). For TCP/IP communications, N can be constructed from a session identifier, the sequence number (optionally with additional most significant bits appended to prevent rollover), the source port, the destination port, and/or other values. Next, in step 1102, the hash of N is computed. (Optionally, this step may be omitted and N may be used instead of h(N) in deriving Kmessage·) Subsequently, in step 1103, message key Kmessage = Kroot, h(N) is computed using the leak resistant key-tree-based key derivation process described in Figure 2, with Kstart^Kroot and PATH=h(N). The input packet data D is encrypted with the key Kmessage to yield the encrypted result E (1104).

Next the hash of E is computed (1105) (e.g., using SHA-256). Then the validator V for the encryption is computed as Kmessage,h(E) (1106) using the leak 28 WO 2011/068996 PCT/US2010/058768 resistant key-tree-based key derivation process outlined in Figure 2, with Kstart^Kmessage and PATH=h(E). Finally the output packet is formed to include V, E, and N (or any other information, if any, required to enable the recipient to recover N) (1107). The output data E is then transferred to a remote device (such as a remote computer over the Internet) in a packet.

As an optional optimization, if the encrypting device has multiple packets buffered for sending, it can encrypt multiple packets simultaneously such that only a single validator is required for all packets. For example, the encryption process may be performed as shown in Figure 3, where each segment Dj is a packet. Combining packets in this manner reduces the number of key tree operations required for both the sender and the recipient. A corresponding verifiable packet level leak resistant decryption process is illustrated in Figure 12. Given an encrypted packet including V, E, N (or data sufficient to recover N, e.g., a sequence number), and the shared cryptographic secret Kroot (1200), the decryption process proceeds as follows: First, the value of h(N) is computed (1201) is computed (or, if the encrypting device used N directly, then this step is omitted). Then the hash of E is computed (1202). Next Kmessage “ Kroot, h(N) is computed at step 1203 using the leak resistant key-tree-based approach diagrammed in Figure 2 with Kstart^Kroot und PATH=h(N). Next V’ - Kmessage, h(E) is computed using the leak resistant key tree process outlined in Figure 2, with Kstart^Kmessage und PATH=h(E) (1204), Subsequently, the decryption device checks whether V’-V (1205). If they are not equal, processing is stopped for this packet and the packet is discarded (1206). If the check succeeds, then E is decrypted with Kmessage to yield D, the plaintext packet (1207) (e.g., using the DEC() process shown in Figure 14).

Smart Card Applications

Verifiable leakage-resistant encryption and decryption can be implemented in smart-cards (e.g., in connection with protocols where the smart-card is required to perform encryption and/or decryption in a manner that is secure from differentia] power analysis and related external monitoring attacks). Examples of such systems and protocols include, without limitation, the derivation of keys (control words) for the decryption of pay television signals, payments (including off-line payments), identity verification/network login, mobile telephone SIM cards, and transit passes. 29 WO 2011/068996 PCT/US2010/058768

The exemplary cryptographic techniques disclosed in this patent can be used to ensure that the secret keys within smart-cards are protected from externa] monitoring attacks while performing such protocols. Smart cards (or other security chips) can also be used to implement part or all of the leak resistant encryption or decryption processes 5 utilized in a larger system, such as if the small card implements the key-tree based key derivation process of Figure 3 so that Kstart never needs to leave the smart card.

Mutual Authentication Applications 10 In many applications, two or more devices need to authenticate each other and/or exchange sensitive information amongst them. Example applications of such protocols include, without limitation: (i) authentication between a printer and a cartridge to ensure that both devices are genuine and not counterfeit; (ii) authentication between a set-top box and a smart-card to ensure that components are 15 authentic (e.g., to prevent the introduction of stolen video decryption keys); (iii) authentication between a garage door and an opener; (iv) keyless entry systems (such as may be used in cars) which authenticate keys (e.g., prior to unlocking doors or starting the engine); (v) authentication protocols performed by frequently stolen items (such as car radios, GPS units, cell phones, etc.) to prevent stolen or tampered devices 20 from being operated; and (vi) entry systems such as those found in secure buildings that authenticate keys/tokens prior to permitting entry. In these applications, challenge response protocols between the devices have traditionally been used both for mutual authentication and to set up a shared secret key for the exchange of sensitive information. Simple protocols to perform these authentications while 25 resisting DPA can be constructed by using the methods of this patent to perform any required encryption or decryption operations. For example, a device can demonstrate its authenticity using techniques disclosed in this patent through its ability to supply a valid validator and/or decrypt a message. 30 Segment Encryption and Decryption with Intra-segment Key Changes

This section describes exemplary variants of the ENCQ and DECQ operations which can be used in place of conventional encryption processes (such as AES in ECB or CBC mode) in implementing the exemplary embodiments (e.g., as shown at 30 WO 2011/068996 PCT/US2010/058768 step 320 of Figure 3, step 410 of Figure 4, step 509 of Figure 5, step 630 of Figure 6, step 1104 of Figure 11, and step 1207 of Figure 12). In the ENCQ and DEC() variants shown in Figures 13 and 14 respectively, the cryptographic keys are changed frequently, for even greater security. Specifically, additional cryptographic key updates occur within the encryption of a data segment Dj to E; (or vice versa). Accordingly, we refer to these variants as implementing intra-segment key changes.

Other than the changes to ENC() and DEC(), the remainder of the operations in the first and second exemplary embodiments can be implemented as previously described. For example and without limitation, the operations involving the initial message key Kmessage, the validator V, and so forth, need not be changed.

Figure 13 shows an exemplary embodiment of an ENC() operation for encrypting data segments. Figure 14 shows a corresponding exemplary embodiment of a DEC() operation. In this embodiment, these operations are built using the block cipher AES in cipher block chaining (CBC) mode, but it should be clear to those skilled in the art, that other block ciphers or encryption/decryption primitives or encryption modes could be used as well.

The inputs to the encryption process for segment i are segment key Kj (1301) and data segment Dj (1310). The input data segment Dj (1310) is divided into sub-segments Djj (1311), Dj,2 (1312), etc. Figures 13 and 14 show the data segment D being divided into sub-segments of 3 AES blocks, although other sizes can also be used and algorithms other than AES may, of course, also be employed. (Smaller sub-segments increase computational overhead, while larger sub-segments cause keys to be used in more operations, increasing the potential for information to leak.) Segment key Kj is transformed with a hash operation m(), yielding Kjj (1302) which is the key for the first sub-segment Djj. If an initialization vector (IV) (1314) is to be used, it is XORed with the first AES block of Djj. (If no IV is to be used, this XOR step may be omitted. If an IV is used, it can be authenticated, e.g., by incorporating it into the validator computation, or by deriving the IV from a validated value such as a message identifier.) The first bits of (Dj XOR IV) are encrypted with AES (1315) using the segment key Kjj (1302), forming the first portion of ciphertext sub-segment Ejj (1320). This ciphertext portion is also XORed with the next bits of sub-segment Djj (1311), yielding another AES input which is subsequently encrypted using segment key Kjj (1302) to produce the next portion of sub-segment Djj (1311). A similar cipher block chaining operation is performed to form the input to the third AES 31

<img img-format="tif" img-content="drawing" file="IL219906AD00021.tif" id="idf0001" />

219906/2 encryption, which is also performed with key Ki,1. The results of the three AES operations is the ciphertext sub-segment Ei,1 (1320). The fourth AES operation is performed on the first block of the next data sub-segment Di,2, (1312), and a new key is used, notably Ki,2 (1303), which is derived by applying m))to Ki,1 (1302). The last ciphertext from processing Di,1 becomes the IV (1317) for the first portion of Di,2 (1312). The encryption process continues until all blocks of all s data sub-segments have been encrypted, ultimately yielding the encrypted sub-segments Ei,2 (1321), ..., E^ (1322), and where a new key is derived usingmO for each sub-segment. Finally, the ciphertext sub-segments are assembled to form the final ciphertext segment E1 (1330).

Referring to Figure 14, the decryption process DEC () is the reverse of the ENC )) process. The subkeys Ki,1 (1402), Ki,2, (1403), etc. are derived from the segment key Ki (1401) using m() via the same process as for encryption above. The encrypted segment Ei is divided into sub-segments, each comprising one or more AES inputs, which are decrypted with the subkeys. After each decryption operation, the appropriate IV (if any) or prior ciphertext is XORed with the data. The final data are assembled to form the sub-segments (1420, 1421, 1422, etc.), which are in turn assembled to form Di (1430).

The ENC0 and DEC )) process above are examples which involve rapid key changes so as to provide greater leakage tolerance. Other segment encryption and decryption methods can be used, including the application of stream ciphers and/or block ciphers (such as RC4, SEAL, AES, DES, triple DES, etc.) in ECB, CBC, or counter (e.g., Galois counter) modes. For such operations where the same key is applied to all the data in a segment, it may be advantageous to limit the size of each segment (e.g., by dividing up the data into sub-segments as shown in Figure 3) prior to encryption so as to limit that the number of operations performed with each key, thereby reducing the number of operations an adversary can observe being performed with each key.

Communications Channels

Data exchanges described herein may be accomplished in a wide range of possible manners. For example, and without limitation, conventional buses/interfaces (such as I2C, JTAG, PCI, serial I/O (including USB), PCI Express, Ethernet, etc.), wireless protocols (such as 802.11 family, Bluetooth, cellular telephony protocols, 32 WO 2011/068996 PCT/US2010/058768 ISO 14443, etc.), and intra-chip connections (such as APB, direct connections with other flip flops, etc.) may all be used. For each of the foregoing, the sending device(s) and receiving device(s) would have appropriate interfaces (e.g., interfaces of the foregoing types) with can send, receive, or send and receive (as appropriate). 5

Alternate Forms of Data Validation Prior to Decryption

The exemplary embodiments presented thus far, have utilized the leak-resistant key-tree-based key derivation process (e.g., as illustrated in Figure 2) to compute a validator of the ciphertext which can be verified safely prior to decryption. 10 While this process is well suited to a broad range of applications, other techniques for creating a value that could serve a similar role, and may be adequate in certain settings. For example, in some embodiments the encryption process is not required to be resistant to external monitoring (but the decryption process does require such resistance) and/or algorithm-level countermeasures for public key digital signing 15 processes (such as those described in U.S. Patent 6,304,658) may be present. For these systems, digital signing (digital signature) operations may be used to construct a value which can be verified at decryption time to ensure that the ciphertext is unmodified. For example, the digital signature could authenticate the message identifier and at least one encrypted segment. Examples of public key digital signing 20 algorithms include, without limitation, RSA, USA, and elliptic curve DSA variants (including without limitation EC-DSA). The verification of a digital signature does not require any sensitive information, and accordingly may be performed prior to decryption. However, this flexibility comes at the cost of requiring public key signing logic within the encrypting device and public key verification logic within the 25 decrypting device. It is also possible for a validator (or validator substitute) to be comprised of multiple symmetric validators, public key signatures, or other elements.

Non-Sequential Segment Key Derivation

Segment keys (e.g., Kb K2,... KL in Figure 3) and sub-segment keys (Kjj, Ki&lt;2, 30 etc. in Figure 13) are not required to be derived sequentially. For example, keys can be derived in a hierarchical tree pattern, or more generally each key can be a function of any prior key(s), or could be independently derived from Kroot using the key tree construction, or keys could be derived using some combination of other keys and the key tree construction, 33 WO 201ί/068996 PCT/US2010/058768

Reordering of Data Transmissions and Calculations

The ordering of data transmissions and operations can be altered. For 5 example, the first exemplary embodiment described in Figures 1, 3 and 4 shows the encryption process proceeding from the last segment Dl to the first segment Diwith each segment Dj containing the hash of the encryption result, Ei+i, of the i+l’th segment. A separate validator is computed for the first encrypted segment Ej (e.g., see step 106). This approach can be advantageous for the decrypting device as shown 10 in Figure 4, since it does not need to buffer the entire encryption result before decrypting, whereas the encrypting device has to do so.

Alternatively, the encrypting device could encrypt the segments starting from Di and ending with Dl, with each segment Di+i containing the hash of the encryption Ej of the previous segment. In this example, the segment Di is (for example) 15 extended by a string of 0’s of size equal to the output length of the hash function to indicate it is the first segment. A validator, created using the key-tree is then computed using PATH=h(EL). For this variant, the decryption process is similar to Figure 4, but proceeds in the reverse direction starting from the last encrypted segment to the first. Thus, the encrypting device no longer has to buffer the data 20 segments, although the decrypting device now has to do so.

Substitution of Additional Validators for Hashes

Although some examples show hashes in data segments which authenticate 25 subsequent encrypted segments, the subsequent segments can alternatively carry their own independent validator. For example, Figure 3 shows first data segment (312) carrying a hash h(E2) to validate that segment E2 was not changed. However, such hash is not always required, and in some cases could be omitted (e.g., if the next segment instead carries a validator). This simplifies encryption somewhat, but 30 increases computation time since more validators need to be computed and checked. In streaming applications or if storage/memory are limited, the additional computational effort may be justified given the benefit of avoiding the need to have the subsequent data available and buffered. 34 WO 2011/068996 PCT/US2010/058768

Variations in Hashing

In some diagrams, a single operation, such as h() in Figure 3, is applied multiple times and/or is used for different uses. It is generally not required that these all be the same function. For example, different steps could employ different hash functions.

The output of hash function may be truncated, combined with other hash function outputs, or otherwise modified through post-processing. For example, SHA-2 produces a 256-bit output hash, but a shorter message identifier (such as 160-, 128-, 80- or 64-bits) may be desired. The function h() may use SI4A-2 internally and return only some bits of its result.

Variations in Order of Operations

Some of the exemplary embodiments designate a specific order in which data elements are concatenated or combined. For instance, in Figure 3, steps 303-312, the data Di is concatenated with the hash h(Ej+i). Other examples where data segments are concatenated in sequence before being hashed include Figure 5, elements 501-504 &amp;amp; 513, in step 306 of Figure 3. These specific orderings are just one example of a possible ordering, and a variety of other data orderings could be utilized in alternate embodiments.

Variations in Tree-Based Key Derivation

If operations (such as fj) are invertible, it is possible to use a value other than the top of the tree as the starting value. Similarly, computed values can be cached (e.g., if the message identifier is a counter, the initial operations will usually not change from one message to the next and therefore do not need to be recomputed).

Error Detection and/or Correction

It is well known in the art that incorrect outputs produced as a result of injecting faults in a cryptographic device’s operation can yield information about 35 219906/2 sensitive data and keys. When practical, cryptographic operations can be checked to help prevent the release of incorrect computations which can compromise secrets. For example, a simple and effective technique is to perform cryptographic operations twice, ideally using two (or more) independent hardware processors and implementations, with a comparator to verify that both (or all) produce identical results. If the results produced by the units do not match, the comparator will prevent either result from being used and/or trigger other error conditions. Within individual cryptographic operations (such as hashing steps), error-detection and/or error-correction logic can also be employed to help prevent or detect situations where cryptographic operations are performed incorrectly.

The techniques disclosed in this patent may additionally provide some inherent resistance against certain types of fault injection attacks on the encryption and decryption processes. During the encryption process, a limited or partial fault introduced during the key tree based key derivation process would produce random, unpredictable results due to the usage of entropy redistribution functions within this process. In particular, corrupted intermediates will typically be mixed by subsequent entropy redistribution functions, which will limit adversaries' ability to mount attacks utilizing defective results.

Likewise, during decryption, faults or errors introduced within the ciphertext or the message identifier processing will generally result in the validator being rejected. The second embodiment, with plaintext hash chaining, provides further resistance since the plaintext segments are independently authenticated for correctness prior to being output. Of course, the checking of operations and other well known fault-detection techniques may additionally be utilized.

Self-diagnostic functions such as a POST (power-on-self-test) and random number testing may also be incorporated to verify that cryptographic functions and random number generation capability has not been damaged.

Additional Host Environments and Form Factors

Several exemplary systems and applications for the utilization of verifiable leak-resistant cryptography were described above. However, as those skilled in the art will appreciate, the techniques described above are not limited to particular host environments or form factors. Rather, they can be used in a wide variety of 36 WO 2011/068996 PCT/US2010/058768 applications, including without limitation: application-specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), systems on chip (SoC), microprocessors, secure processors, secure network devices, cryptographic smartcards

of all kinds (including without limitation smartcards substantially compliant with ISO 5 7816-1, ISO 7816-2, and ISO 7816-3 (“ISO 7816-compliant smartcards”)); contactless and proximity-based smartcards and cryptographic tokens (including without limitation smartcards substantially compliant with ISO 14443); stored value cards and systems; cryptographically secured credit and debit cards; customer loyalty cards and systems; cryptographically authenticated credit cards; cryptographic 10 accelerators; gambling and wagering systems; secure crypto graphic chips; tamper-resistant microprocessors; software programs (including without limitation programs for use on personal computers, servers, etc. and programs that can be loaded onto or embedded within cryptographic devices); key management devices; banking key management systems; secure web servers; defense systems; electronic payment 15 systems; micropayment systems and meters; prepaid telephone cards; cryptographic identification cards and other identity verification systems; systems for electronic funds transfer; automatic teller machines; point of sale terminals; certificate issuance systems; electronic badges; door entry systems; physical locks of all kinds using cryptographic keys; systems for decrypting television signals (including without 20 limitation, broadcast television, satellite television, and cable television); systems for decrypting enciphered music and other audio content (including music distributed over computer networks);· systems for protecting video signals of all kinds; content protection and copy protection systems (such as those used to prevent unauthorized copying or use of movies, audio content, computer programs, video games, images, 25 text, databases, etc.); cellular telephone scrambling and authentication systems (including telephone authentication smartcards); secure telephones (including key storage devices for such telephones); cryptographic PCMCIA cards; portable cryptographic tokens; and cryptographic data auditing systems.

All of the foregoing illustrates exemplary embodiments and applications of the 30 verifiable leak-resistant cryptography, from which related variations, enhancements and modifications will be apparent in the context of the spirit and scope of the disclosure. Therefore, the invention(s) protected by this patent should not be limited to the foregoing disclosure, but rather construed by the claims appended hereto. 37