Source: https://patents.google.com/patent/US9940463B2/en
Timestamp: 2019-04-25 08:13:28+00:00

Document:
A method for device authentication comprises receiving, by processing hardware of a first device, a message from a second device to authenticate the first device. The processing hardware retrieves a secret value from secure storage hardware operatively coupled to the processing hardware. The processing hardware derives a validator from the secret value using a path through a key tree, wherein the path is based on the message, wherein deriving the validator using the path through the key tree comprises computing a plurality of successive intermediate keys starting with a value based on the secret value and leading to the validator, wherein each successive intermediate key is derived based on at least a portion of the message and a prior key. The first device then sends the validator to the second device.
This is a Continuation of pending U.S. patent application Ser. No. 15/395,809 filed Dec. 30, 2016; which is a continuation of U.S. patent application Ser. No. 14/617,437 filed Feb. 9, 2015, which issued Feb. 14, 2017 as U.S. Pat. No. 9,569,623; which is a continuation of U.S. patent application Ser. No. 14/201,539 filed Mar. 7, 2014, which issued Mar. 10, 2015 as U.S. Pat. No. 8,977,864; which is a Continuation of U.S. patent application Ser. No. 13/762,703 filed Feb. 8, 2013, which issued on Apr. 22, 2014 as U.S. Pat. No. 8,707,052; which is a continuation of U.S. patent application Ser. No. 12/958,570 filed Dec. 2, 2010, which issued on Feb. 26, 2013 as U.S. Pat. No. 8,386,800; which claims priority to U.S. Provisional Patent Application Ser. No. 61/266,948, filed Dec. 4, 2009, each of which is incorporated by reference herein in their entirety.
Multiple entropy redistribution operations can also be constructed from a base operation. By way of example, if two 256-bit entropy redistribution operations f0( ) and f1( ) are required, f0( ) could comprise applying the SHA-256 cryptographic hash function to the operation identifier string “f0” concatenated with the input to f0 ( ) while f1( ) could comprise applying SHA-256 to the operation identifier string “f1” concatenated with the input to f1( ). Entropy redistribution operations can be construed using the well-known AES block cipher. For example, to implement f0( ) . . . fb−1( ), each fi( ) 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 i within 0 . . . b−1, yielding 256 bits of output. A wide variety of block cipher based hash function and MAC constructions are also known in the background art and may also employed.
In addition, the encrypting device and decrypting device also are both able to compute a set of non-linear cryptographic entropy redistribution operations f0 ( ) f1 ( ), . . . , fb−1( ) 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+1 levels, from 0 through Q) can be created by using b distinct entropy distribution functions, f0 ( ) . . . fb−1( ) to 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: f0 (KSTART) for the leftmost branch; f1 (KSTART) for the next branch; and continuing until fb−1(KSTART) for the rightmost branch. At level 2, b2 possible keys can be derived, since each of f0 ( ) . . . fb−1( ) 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 f0 ( ) . . . fb−1( ) in turn to derive b additional possible derived keys. The entire key tree has Q+1 levels, starting with a single node at level 0, continuing with bi nodes at level i, and ending with bQ nodes at level Q. Thus, there are bQ 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−1).
For example, in an exemplary embodiment, b=2. Thus, two entropy redistribution operations, f0 ( ) and f1 ( ) 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).
In an exemplary embodiment, each of the operations fi( ), 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 fi( ) such that the operation identifier for f0 ( ) would be “f0”. 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, MD5, SHA-1, SHA-256, SHA-512, any SHA3 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 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 collision-resistant (such as MD5, 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 h( ).
Given a sensitive plaintext data message D to be protected, and with knowledge of a shared base secret cryptographic value KROOT, the encrypting device performs the following steps, as outlined in FIG. 1. First it decomposes the sensitive plaintext data D into a sequence of L segments D1, . . . , 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 FIGS. 13 and 14.
Note that the process of FIG. 3 can still be performed where all the data is in one segment (i.e., L=1) (e.g., because the input message is small or an encryption process ENC( ) such as the process shown in FIG. 13 is employed). For the L=1 case, only K1 is required and KI=g(KMESSAGE). Alternately, KMESSAGE may be used directly as K1, in which case the operation go can be omitted altogether. As described above, inclusion of the hash of D1 . . . DL (which, in this case, would just be D1 since L=1) is optional. The result of the process E=E1, since this is the only segment.
The foregoing description commenced with KMESSAGE in deriving the 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,H1. Likewise, the key used at step 106 may be derived from the KMESSAGE used at step 104, or vice versa, or a different base key (besides KROOT) may be employed as KSTART. Of course, KROOT itself may even be used as KSTART (e.g., if H2 is a hash of N and/or H1 and one or more ciphertext segments).
FIG. 4 shows an exemplary decryption process corresponding to the exemplary encryption process of FIGS. 1 and 3. As stated earlier, this requires that both the decryption device and the encryption device have the ability to derive the same message identifier (e.g., because each device knows nonce N it can compute Hi), 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 FIG. 2.
The next steps of the process (505-508) generate encryption keys for each of 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 K1 is simply set to the value of message key KMESSAGE derived (505) by computing h(N) and then K1=KMESSAGE=KROOT, h(N) using the leak resistant, key-tree-based key derivation process as described in FIG. 2 with KSTART=KROOT and PATH=h(N). Key Ki for i>1 is computed as g(Ki−1), where g( ). Thus, the second key K2 is the result of computing g(K1) (506). This process is repeated so that the L−1'th key (KL−1) is computed as g(KL−2) (507), and the final segment key KL is computed as g(KL−1) (508).) Thus, every key Ki is based on (e.g., equal to or derived using) the message key KMESSAGE.
The process of decryption is illustrated in FIG. 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∥E1∥EL∥H), where “∥” 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 FIG. 2, with the root being KSTART=KROOT and the PATH=Z, and then hashes the result to yield h(KROOT,Z). At step 620, 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 FIG. 2, with KSTART=KROOT and PATH=h(N) and sets a counter i to be 1.
FIG. 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 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 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 FIG. 2, with functions f0 ( ) . . . , 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 in software (e.g., by the CPU).
For example, FIG. 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 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. Nonvolatile 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 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). 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 Apr. 6, 2006) and the AEGIS design from MIT (described in AEGIS: Architecture for Tamper-evident and Tamper-resistant Processing, Proceedings of the 17th Annual International Conference on Supercomputing, pages 160-171, 2003).
exchanging the validator between the first device and the second device as part of a challenge-response protocol in order to authenticate the first device.
2. A method as in claim 1, wherein the first device comprises a printer cartridge and the second device comprises a printer.
3. A method as in claim 1, wherein a first part of the plurality of parts determines a first leg of the path through the key tree and a second part of the plurality of parts determines a second leg of the path through the key tree, and wherein the first leg of the path is associated with a first entropy distribution operation and the second leg of the path is associated with a second entropy distribution operation.
verifying at the second device that the first device is authentic when the validator matches the expected response.
deriving the expected validator from an additional secret value at the second device using the path through the key tree, wherein the path is based on the message.
verifying at the first device that the second device is authentic when the second validator matches an expected value.
exchange the validator between the first device and the second device as part of a challenge-response protocol in order to authenticate the first device.
verify that the first device is authentic responsive to determining that the validator matches the expected response.
derive the expected validator from an additional secret value at the second device using the path through the key tree.
10. The system of claim 7, wherein the first device comprises a printer cartridge and the second device comprises a printer.
11. The system of claim 7, wherein a first part of the plurality of parts determines a first leg of the path through the key tree and a second part of the plurality of parts determines a second leg of the path through the key tree, and wherein the first leg of the path is associated with a first entropy distribution operation and the second leg of the path is associated with a second entropy distribution operation.
verify that the second device is authentic responsive to determining that the first validator matches the second validator.
13. The system of claim 12, wherein a first part of the plurality of parts determines a first leg of the path through the key tree and a second part of the plurality of parts determines a second leg of the path through the key tree, and wherein the first leg of the path is associated with a first entropy distribution operation and the second leg of the path is associated with a second entropy distribution operation.
14. The system of claim 12, wherein the first device comprises a printer and the second device comprises a printer cartridge.
Advanced Access Content System (AACS), Introduction and Common Cryptographic Elements, Revision 09.1 (Feb. 17, 2006), available at http://www.aacsla.com/specifications/specs091/AACS_Spec_Common_0.91.pdf. 82 Pages.
CN Office Action dated Apr. 22, 2015 in CN Application No. 201080060319.3, includes English Translation. 10 pages.
CN Reaponse dated Sep. 7, 2015 in CN Application No. 201080060319.3. 13 pages (no translation).
CN Response dated Dec. 18, 2014 in CN Application No. 201080060319.3. 4 pages (no translation).
CN Response dated Jan. 16, 2014 in TW Application No. 099142160. 4 pages (no translation).
Dziembowski et al., "Leakage-Resilient Cryptography in the Standard Model," FOCS, pp. 293-302, IEEE Computer Society, May 28, 2008, 13 pages.
EP Response filed on Jun. 10, 2016 with EP Appln. No. 10835139.6 in Response to the Extended Search Report dated Dec. 4, 2015 and the Communication Pursuant to Rules 70(2) and 70a(2) EPC dated Dec. 22, 2015, 32 Pages.
EP Response to Communication dated Jul. 31, 2012, dated Jan. 14, 2013 in EP Application No. 10835139.6, Includes New Claims (highlighted and clear copies). 24 pages.
EP-Extended European Search Report dated Dec. 4, 2015 re EP Appln. No. 10835139.6. 10 Pages.
EP—Extended European Search Report dated Dec. 4, 2015 re EP Appln. No. 10835139.6. 10 Pages.
Faust et al., "Leakage-Resilient Signatures," TCC, vol. 5978 of Lecture Notes in Computer Science, pp. 343-360, 2010. 21 pages.
Hu, Lingxuan et al., "Secure Aggregation for Wireless Networks", Applications and the Internet Workshops, 2003. Proceedings 2003 Symposium. pp. 384-391, Jan. 27-31, 2003, 8 Pages.
IL Memorandum of Amendment dated Apr. 17, 2013 in IL Application No. 219906, Includes Amended Pages (clear and Marked copies), 21 pages.
IL Response and IDS with IL Appln. No. 219,906 filed on Mar. 29, 2016 in Response to Official Action dated Dec. 10, 2015. 31 Pages. (With Translation).
JP Argument, Amendment and Reference Citation dated Oct. 20, 2016 for JP Appln. No. 2012-7014536 in Response to the Notice of Grounds of Rejection dated Aug. 30, 2016. 125 Pages. (Without Translation).
JP Decision of Rejection dated Nov. 28, 2013 in JP Application No. 2012-542196, Includes English Translation. 9 pages.
JP Office Action dated Mar. 27, 2014 (Request for Appeal and Amendment) in JP Application No. 2012-542196. 8 pages (no translation).
JP Response dated Nov. 6, 2013 in JP Application No. 2012-542196, 9 pages (no translation).
Katz, Jonathan (2004) , "Binary Tree Encryption: Constructions and Applications", In; Lim JI., Lee DH. (eds) Information Security and Cryptology-ICISC 2003. ICISC 2003. Lecture Notes in Computer Science, vol. 2971, Springer, Berlin, Heldelberg. 11 Pages.
Katz, Jonathan (2004) , "Binary Tree Encryption: Constructions and Applications", In; Lim JI., Lee DH. (eds) Information Security and Cryptology—ICISC 2003. ICISC 2003. Lecture Notes in Computer Science, vol. 2971, Springer, Berlin, Heldelberg. 11 Pages.
Kocher et al., "Differential Power Analysis," Advances in Cryptology-Crypto 99 Proceedings, Lecture Notes in Computer Science, vol. 1666, Srpinger-Verlag, 1999, pp. 388-397, 10 pages.
Kocher et al., "Differential Power Analysis," Advances in Cryptology—Crypto 99 Proceedings, Lecture Notes in Computer Science, vol. 1666, Srpinger-Verlag, 1999, pp. 388-397, 10 pages.
Kocher, Paul re U.S. Appl. No. 12/958,570, filed Dec. 2, 2010 re Information Disclosure Statement dated Nov. 4, 2011, 3 Pages.
KR Office Action dated Sep. 5, 2016 Re: KR Appln. No. 2012-7014536, 13 Pages. (With Translation).
Lorentz Center, "Workshop on Provable Security Against Physical Attacks," Feb. 15-19, 2010, found at http://www.lorentzcenter.nl/lc/web/2010/383/presentations/index.php3?wsid=383&type=presentations. 1 page.
McEvoy et al., "All or NothingTransforms as a Countermeasure to Differential Side-Channel Analysis," Cryptology ePrint Archive, Report 2009/185, http://eprint.iacr.org/2009/185 18 pages.
Menezes et al., "Efficient Implementation," Handbook of Applied Cryptography, CRC Press, Chapter 14, pp. 591-634, 1996, 44 pages.
Menezes et al., "Handbook of Applied Cryptography," Chapters 1, 5, and 7, CRC Press, Boca Raton, Florida, 1997, 130 pages.
Menezes et al., "Handbook of Applied Cryptography," CRC Press, 1996, pp. 285-298, 312-319,452-462, 475, and 515-524, found at http://www.cacr.math.uwaterloo.ca/hac/ on Jun. 22, 2011, 45 pages.
Menezes et al., "Handbook of Applied Cryptography," pp. 71, 586, 636-637, CRC PRess, Boca Raton, Florida, 1997, 6 pages.
Office Action dated Dec. 10, 2015, re Application No. 219,906. 12 Pages. (With Translation).
PCT International Preliminary Report on Patentability dated Jun. 14, 2012 in International Application No. PCT/US2010/058768, 12 pages.
Petit et al., "A Block Cipher Based PRNG Secure Against Side-Channel Key Recovery," Proceedings of ASIACCS 2008, pp. 56-65, Tokyo, Japan, Mar. 2008, 22 pages.
Pietrzak, K., "A Leakage-Resilient Mode of Operation," Eurocrypt 2009, Lecture Notes in Computer Science, vol. 5479, pp. 462-482, Cologne, Germany, Apr. 2009, 20 pages.
Pietrzak, K., "Provable Security for Physical Cryptography," Invited Talk, Proceedings of WEWORC 2009, Graz, Autria, Jul. 2009. 17 pages.
Pietrzak, K., "Provable Security for Physical Cryptography," Invited Talk, Slides, Proceedings of WEWORC 2009, Graz, Austria, Jul. 2009. 126 pages.
Standaert et al., "Leakage Resilient Cryptography in Practice," Cryptology ePrint Archive, Report 2009/341, 2009, found at http://eprint.iacr.org/2009/341.pdf. 37 pages.
Su, Chien-Chung et al., "The New Intrusion Prevention and Detection Approaches for Clustering-Based Sensor Networks", Wireless Communications and Networking Conference, IEEE New Orleans, LA, USA, pp. 1927-1932, Mar. 13-17, 2005. 6 pages.
TW Office Action dated Jul. 16, 2013 in TW Application No. 99142160, Includes English Translation. 12 pages.

References: V. 
 V. 
 Application No. 201080060319
 Application No. 201080060319
 Application No. 201080060319
 Application No. 099142160
 Application No. 10835139
 Application No. 219906
 Application No. 2012
 Application No. 2012
 Application No. 2012
 Application No. 219
 Application No. 99142160