WO2024158947A1

WO2024158947A1 - Integrity tree architecture for data authentication

Info

Publication number: WO2024158947A1
Application number: PCT/US2024/012829
Authority: WO
Inventors: Ajay Kapoor; Scott C. Best; Cezar Rodolfo WEDIG REINBRECHT
Original assignee: Cryptography Research Inc
Current assignee: Cryptography Research Inc
Priority date: 2023-01-25
Filing date: 2024-01-24
Publication date: 2024-08-02
Anticipated expiration: 2025-07-25

Abstract

Technologies for providing an integrity tree architecture that reduces the number of memory accesses and verification operations needed to perform a read operation. One inline memory encryption (IME) engine performs operations that include receiving a read command for data stored at a data block. The operations further include obtaining a first authentication tag associated with the data block, a first counter value used to generate the first authentication tag; a root counter value, and an intermediate tag. The operations further include generating a second authentication tag based on the intermediate tag, the first counter value, the root counter value, and the data from the data block, and responsive to determining that a value of the first authentication tag matches a value of the second authentication tag, sending, to the host system, the data stored at the data block.

Description

INTEGRITY TREE ARCHITECTURE FOR DATA AUTHENTICATION

BACKGROUND

[001] Modern computer systems generally include one or more memory devices, such as those located on a memory module. The memory module may include, for example, one or more random access memory (RAM) devices which are typically dynamic random-access memory (DRAM) devices. A memory device can include memory banks made up of memory cells that a memory controller or memory client accesses through a command interface and a data interface within the memory device. The memory module can be a persistent memory module with one or more non-volatile memory (NVM) devices.

[002] Data authentication is becoming a key requirement for memory. In some systems, data authentication is achieved by splitting the memory into different sectors, where each sector is authenticated by an authentication tag. Due to memory being limited and expensive, the authentication tags can be stored and verified using an integrity tree scheme.

[003] In some systems, a threat to data authentication in memory devices is known as replay attack. In an example, previously authenticated data is reused at a different time to mislead the computer system into a specific state or to execute a specific task. As a result, some systems use a timestamp-based authentication, where time is authenticated in addition to the host and the data. This timestamp can be referred to as a “counter.”

BRIEF DESCRIPTION OF THE DRAWINGS

[004] The present disclosure is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings.

[005] FIG. 1 is a block diagram of an inline memory encryption engine with integrity logic for protecting the integrity of authentication tags, in accordance with implementations of the present disclosure.

[006] FIG. 2 is a block diagram illustrating generating an authentication tag, in accordance with implementations of the present disclosure.

[007] FIG. 3 is a block diagram illustrating an example integrity storage architecture, in accordance with implementations of the present disclosure.

[008] FIGS 4A-B are diagrams illustrating generating an authentication tag to use for a verification process, in accordance with implementations of the present disclosure. [009] FIG. 5 is a block diagram illustrating a diagram of an example two-level integrity tree.

[0010] FIG. 6 is a flow diagram of a method of performing write and update operations, in accordance with implementations of the present disclosure.

[0011] FIG. 7 is a flow diagram of a method of performing read and verify operations, in accordance with implementations of the present disclosure.

DETAILED DESCRIPTION

[0012] The following description sets forth numerous specific details, such as examples of specific systems, components, methods, and so forth, in order to provide a good understanding of several implementations of the present disclosure. It will be apparent to one skilled in the art, however, that at least some implementations of the present disclosure may be practiced without these specific details. In other instances, well- known components or methods are not described in detail or presented in simple block diagram format to avoid obscuring the present disclosure unnecessarily. Thus, the specific details set forth are merely exemplary. Particular implementations may vary from these exemplary details and still be contemplated to be within the scope of the present disclosure.

[0013] Data authentication is becoming a key requirement for memory protection, such as for inline memory encryption (IME). Data authentication can be achieved by splitting memory into different sectors, where each sector is authenticated by an authentication tag. One authentication algorithm is the Galois Message Authentication Code (GMAC) algorithm that uses a hashing function, called the GHASH function, to generate an authentication tag. The authentication tags can protect data residing in memory against malicious modification (e.g., if a single bit of protected data is modified while the data was in memory, the tag calculated during the next “read” of that data will no longer match the tag that was written when the data was stored). To generate each authentication tag, the GMAC algorithm can use, as input, user data (e.g., encrypted data referred to as cyphertext data) and a cryptographic nonce value (hereafter “nonce value”). A nonce value can be an arbitrary value used just once in a cryptographic communication or operation. In some implementations, the nonce value can be a concatenation of one or more of an initialization vector (IV), the memory address referencing the location of the user data, counter, etc. The IV can refer to an arbitrary input used to prevent the repetition of a sequence of text in data encryption. The counter can be any function that produces a sequence that does not repeat for a relatively long time. For example, the counter can be an increment-by-one counter, where the counter be an initial value (e.g., 0) that is incremented by a value of 1 in response to each write operation performed on the corresponding sector of the memory device.

[0014] Counters can be used to prevent a replay attack(s), which is a form of hardware attack in which previously valid and authenticated user data (as well as the authentication tag associated with the user data) in the memory is maliciously or fraudulently copied and/or moved to a different location in the memory, at different instants of time. A malicious party can mislead the system to re-run a task or change system status to obtain some benefit (e.g., access to sensitive information). In particular, the counter can be used to establish the freshness of data by verifying that the memory module contains only the most recent written data. It is difficult to protect a memory system against these attacks, as every memory “write” requires a counter update. In some solutions with “freshness” protection, there can be some optimization implemented between the total memory dedicated towards counter storage (which ideally is the fewest possible, to minimize “counter overhead”) and the number of accesses required to obtain the counter value for given user-data (also ideally the fewest possible, to minimize “access latency”).

[0015] In some systems, to achieve this optimization and protect authentication tag integrity, the tags (including nonce values, which may be combined with counter values) can be stored based on an integrity tree scheme, such as, for example, a Bonsai Merkle Tree (BMT). An integrity tree can be a data structure that splits a memory space into M equal size data blocks. Leaf nodes on the integrity tree are represented by the lowest level of the tree. Each tree level (can be referred to as “branches”) of a hierarchy can be created by recursively applying an authentication algorithm over pre-sized groups of the data blocks until the procedure yields a single node called the root of the tree (hereafter “root”). For example, each node of a binary tree can hold a hash digest of two or more respective children, and the lowest leaves of the tree can hold digests of the protected (e.g., encrypted) data blocks. The root can reflect the current state of the entire memory space. In some systems, the root can be stored in tamper-resistant memory (e.g., on-chip memory). The number of checks required to verify the integrity of a leaf node can depend on the number of iterations of the authentication algorithm, which can correspond to the number of tree levels. [0016] To protect data at each tree level, a set of nonce values (which may be combined with counter values) corresponding to a respective set of authentication tags can be concatenated (e.g., multiplied, added together, joined together into a new string, etc.) and input into the GMAC algorithm, along with another nonce value, to generate an authentication tag on a higher level. The nonce value of the higher-level authentication tag can be stored in the next level of the authentication tree (along with a respective authentication tag) by concatenating said nonce value along with other nonce values of that level, and so forth.

[0017] FIG. 5 illustrates a block diagram illustrating an example two-level integrity tree. As shown, each data unit 0-3 (512-518) includes a data block (block 0 - block 3) and a respective authentication tag (tag0-tag3). Each authentication tag can be used to authenticate the respective data block during read operations by generating a recreated authentication tag using stored nonce value data and comparing the recreated authentication tag to the stored authentication tag. Each authentication tag can be generated by performing a hashing function (e.g., a GHASH function) on the respective data block and a nonce value. The nonce values (nOO, nOl, n02, and n03) used to generate each authentication tag can be stored on the first level of an integrity tree (e.g., level 0). In particular, at level 0, the data unit LOO can include nonce values nOO, nOl, n02, n03, and the corresponding authentication tag (tagOO) that is computed over nOO, nOl, n02, n03 and a new nonce value (e.g., nonce value N10). Nonce value nlO can be stored as part of data unit L10 at the next level of the integrity tree (e.g., level 1). In the example shown, level 1 is the root of the integrity tree, and the data unit L10 (532) is stored on tamper resistance memory 530. Tamper resistance memory 530, which has limited data, can be used to perform read operations by recreating the authentication tag associated with a desired data block and comparing the recreated authentication tag to the stored authentication tag.

[0018] In some systems, performing a read operation on a data block requires multiple memory accesses and verification operations that include reading data from the data block (e.g., data block dataO) and verifying that the data on the data block was not modified from its value since the last time the data was written and the integrity tree was updated. In particular, performing the read operation includes accessing the data units data unit 0 (512), LOO (522), and L10 (532), and extracting dataO, tagO, nOO and nlO from the data units. Nonce value nlO is stored on the tamper resistance memory and can be trusted. Nonce values (nOO, nOl, n02, n03) can be verified (together, as one entity) by applying the GMAC algorithm over nonce values nOO, nOl, n02, n03 and nlO, and comparing the obtained output to tagOO. This can verify nonce value nOO, that is, determine that nOO has not been changed since it was programmed and the integrity tree updated. Data block 0 can be verified by applying the GMAC algorithm over data block 0 and nonce value nOO, and comparing the obtained output to tagO.

[0019] However, the integrity tree of certain systems can include multiple levels (e.g., branches) between the data level and the root. Each level adds additional memory accesses and verification operations to verify the stored data, which creates delay (e.g., latency) and additional memory access bandwidth before the user data in memory can be reliably authenticated. For example, in a three-branch integrity tree (e.g., a root level, branch level 0, 1, and 2, and a data level), six memory accesses to the memory device and five verification operations are required to read and verify the data stored on a data block. In particular, the memory device would access the data block, the corresponding tag, the corresponding nonce value, and the integrity data (stored nonce values and respective authentication tags) stored on levels 0, 1, and 2. The memory device would then verify the integrity data stored on level 2 using the root nonce value, verify the integrity data stored on level 1 using the level 2 nonce value, verify the integrity data stored on level 0 using the level 1 nonce value, verify the corresponding nonce value using the level 0 nonce value, verify the corresponding authentication tag using the corresponding nonce value, and then authenticate the data block using the authentication tag. This results in relatively longer latency, more memory accesses, move verification operations, power consumption, and the like.

[0020] Aspects of the present disclosure and implementations address these problems and others by providing an integrity tree architecture that reduces the number of memory accesses and verification operations needed to perform a read operation. Aspects of the present disclosure and implementations can generate a new authentication for verifying a stored authentication tag using a single verification operation. In some implementations, responsive to receiving a read command for data stored at a data block, processing logic can perform a set of memory access operations and retrieve the data stored on the data block, the corresponding authentication tag corresponding to the data block (block authentication tag), and the nonce value data corresponding to the authentication tag. In some implementations, the nonce value data can be a counter value of the nonce value used to generate the authentication tag. The nonce value data can be stored at an integrity tree architecture. As such, the processing logic can obtain, from the memory device, the set of corresponding nonce values along each branch of the integrity tree and the corresponding root nonce value from the tamper resistance memory. Rather than verify each nonce value individually, the processing logic can concatenate, into a single integrity value, the root nonce value, each branch nonce value, and the data block. The processing logic can then apply an authentication algorithm (e.g., a GMAC algorithm) over the integrity value to obtain an output value. The output value can be compared, by the processing logic, to the stored block authentication to authenticate the data block. [0021] Aspects of the present disclosure and implementations can reduce the number of memory access operations required to verify an authentication tag. In some implementations, the processing logic can generate an intermediate tag reflecting the combined (e.g., concatenated) values from two or more branches of an integrity tree. In particular, for each authentication tag protecting a set of nonce values (e.g., the authentication tag which may include a nonce value combine with a counter value) that are used to generate authentication tags for data protection, the processing logic can obtain the corresponding nonce value values from each branch of an integrity tree structure. The processing logic can then concatenate the obtained nonce value values and apply a hashing algorithm over the concatenated nonce value values to generate the intermediate tag. The intermediate tag can be stored on the same data unit as the nonce value authentication tag. During a read operation performed on a data block, the processing logic generates an integrity value by obtaining and concatenating the root nonce value, the intermediate tag, the nonce value used to generate the block authentication tag, and the data stored on the block. The processing logic can then apply an authentication algorithm over the concatenated value to obtain an output value. The output value can be compared, by the processing logic, to the stored block authentication tag. Since the intermediate tag includes nonce value data from two from a least one branch of the integrity tree, the processing logic, thus performs at least one less memory access during the verification process, thus reducing latency.

[0022] In some implementations, the integrity tree structure can be modified to store the intermediate tag on the same data unit as the respective nonce value authentication tag. In some implementations, the integrity tree structure can be configured to reduce the memory size of the nonce values stored in each data unit. For example, in some implementations, a 512-bit data unit can store eight 56-bit nonce values and one corresponding 64-bit nonce value authentication tag. To accommodate the intermediate tag, the integrity tree structure can be configured to store a 512-bit data unit that includes eight 48-bit nonce values, one corresponding 64-bit nonce value authentication tag, and one corresponding 64-bit intermediate tag.

[0023] Aspects of the present disclosure and implementations can save time and power by performing a single verification operation rather than multiple verification operations to verify an authentication tag. Aspects of the present disclosure and implementations can optimize storage usage, allowing data units to store intermediate tags in addition to a set of nonce values and an authentication tag. Aspects of the present disclosure and implementations can improve system memory life by reducing unnecessary accesses.

[0024] Aspects of the present disclosure and implementations can achieve a performance improvement, including a reduction in the number of computations, bandwidth savings, and a reduction in latency, by storing intermediate tags and performing fewer memory access and verification operations during a read operation. By storing and using the intermediate tags, there is no need to access certain nonce values stored on the branches of an integrity tree structure. By concatenating the data block and the corresponding nonce values along an integrity tree, there is no need to perform verification operations on each nonce value. Aspects of the present disclosure and implementations can provide a self-contained local solution without impacting the overall data flow in the system.

[0025] FIG. 1 is a block diagram of an inline memory encryption engine (IME) 100 with integrity logic for protecting the integrity of authentication tags, according to some implementations. The IME engine 100 provides encryption, decryption, and authentication for memory read and write requests between a host processor via a hostside interface and its attached memory via a memory-side interface. The IME engine 100 can be instantiated on a host system (e.g., System on Chip (SoC) or Field Programmable Gate Array (FPGA)) between the processor logic and a memory controller. The IME engine 100 can be a high-throughput, low-latency security solution. The IME engine 100 can be implemented in hardware, software, firmware, or any combination thereof.

[0026] The IME engine 100 can receive plaintext data 102 over the host-side interface, encrypt the plaintext data 102 into ciphertext data, generate an authentication tag, generate integrity data, and provide an output 104 to memory over the memory-side interface. The output 104 includes ciphertext data, the authentication tag, and the integrity data. The integrity data can be configured to verify the nonce value data or a portion of the nonce value data (e.g., a counter value) which was used to generate the authenti cation tag related to a segment of ciphertext data. The IME engine 100 can receive ciphertext data, the authentication tag, and the integrity data from the memory controller over the memory-side interface, verify the authentication tag related to the data, verify the nonce value data used to generate the authentication tag, decrypt the data, and provide the decrypted data over the host-side interface. The IME engine 100 can implement an encryption and authentication algorithm, such as the AES-GCM algorithm. The AES-GCM algorithm can use AES-256, AES-128, SM4-XTS, etc. for encryption and GMAC for authentication. The GMAC algorithm internally uses the GHASH functions to generate the authentication tag.

[0027] In some implementations, the IME engine 100 includes an encryption engine 106 and an authentication engine 108. The encryption engine 106 can perform encryption and decryption operations. The authentication engine 108 can include tag creation component 112 to generate authentication tags and integrity data during a write operation, and tag validation component 114 to validate the authentication tags using the integrity data during a read operation. In some implementations, the IME engine 100 includes additional logic and SRAMs 110 coupled to the encryption engine 106 and the authentication engine 108. The additional logic and SRAMs 110 can be used to perform other operations and store information in connection with or provide information for the encryption, authentication, and integrity operations. In some implementations, the additional logic and SRAMs 110 can include a mechanism to generate, store, and/or update on-chip root anchors, refresh counters, provide key management, address generation for different tree levels corresponding to incoming address requests, provide authentication tag validation, etc.

[0028] During a write operation, the encryption engine 106 (also referred to herein as encryption logic) can receive the plaintext data 102 as segments (or portions) and encrypt the segments into segments (or portions) of ciphertext data. The encryption engine 106 can use AES-256 for the encryption. The ciphertext data can then be input into the authentication engine 108 (also referred to as authentication logic). The authentication engine 108 can compute the ciphertext data to generate an authentication tag. The authentication engine 108, via, for example, tag creation component 112, can use GMAC for authentication, including the GHASH function, to generate the authentication tag. The authentication engine 108 can further generate integrity data used to verify, during subsequent read operations of the corresponding data block(s), the counter values used to generate the authentication tags. [0029] During a read operation, the encryption engine 106 can receive segments of ciphertext data and decrypt the segments into segments of plaintext data. The authentication engine 108, via, for example, tag validation component 114, can use the integrity data to validate the authentication tag.

[0030] To generate an authentication tag, the authentication engine 108 can input, into one or more algorithms (e.g., the GMAC algorithm), the user data (e.g., the cyphertext data and/or plaintext data), and a cryptographic nonce value (nonce value). Each nonce value can be an arbitrary value that can be used just once in a cryptographic communication or operation. In some implementations, the nonce value can be a concatenation of one or more of an initialization vector (IV), the memory address referencing the location of the user data, and/or a counter value. The nonce value can be generated by the additional logic and SRAMS 110, by the authentication engine, 108, or by any other component of IME engine 100.

[0031] The IV can refer to an arbitrary input used to prevent the repetition of a sequence of text in data encryption. The IV can be one or more of a random value, a pseudorandom value, a unique value, a non-repeating value, etc.

[0032] Counter 111 can be any function that produces a sequence (e.g., counter value) that does not repeat for a relatively long period. In some implementations, counter 111 can increment the counter value by one, where the counter value is an initial value (e.g., 0) that is incremented by a value of 1 in response to an event, such as a write operation. For example, the counter can be incremented responsive to each write operation performed to store data of a particular granularity (e.g., a cache line of 512 bits). The counter can be a component of the additional logic and SRAMS 110.

[0033] As illustrated in FIG. 1, the generation of the authentication tag is performed in connection with an authentication algorithm that uses a hashing function to compute the authentication tag. In other implementations, the generation of the authentication tag is performed in connection with another operation, such as an encryption operation. In some implementations, the authentication algorithm is the GMAC algorithm, and the hash function is the GHASH function. Alternatively, other authentication algorithms and/or hash functions can be used.

[0034] FIG. 2 is a block diagram illustrating generating an authentication tag, in accordance with implementations of the present disclosure. Ciphertext data 210 illustrates eight data blocks (e.g., BL0-BL7) of encrypted data. In some implementations, each block can reflect a cache line (e.g., 512 bits) or any other granularity of data. Ciphertext data 210 can be obtained from encryption engine 106. Each data block can be input into authentication engine 108, along with a nonce value, to generate a respective authentication tag (e.g., authentication tags 220; tag0-tag7). For example, BL0 212 and nonce value 216 can be input into authentication engine 108 to generate tagO 222. In some implementations, nonce value 216 can be a concatenation of an IV value, the memory address of the ciphertext data (e.g., the memory address of BL0 212), and a counter value.

[0035] Authentication engine 108 can further generate integrity data that can be used to verify the counter values used to generate the authentication tags, during subsequent read operations of the corresponding data block(s). In some implementations, the integrity data can be structured as an integrity tree. Each leaf node of the integrity tree can reflect a data unit and include a set of counter values, an authentication tag, and/or an intermediate tag. It is noted that although counters are used by way of example, nonce value-related data can be stored by the integrity tree structure. Each branch of the integrity tree can include a set of counter values used to generate authentication tags in a lower level (e.g., a lower branch or the leaf nodes), a corresponding authentication tag, and/or a corresponding intermediate tag. The root of the integrity tree structure can include a set of counter values corresponding to the authentication tags of the highest branch of the integrity tree structure. The authentication tags and the intermediate tags can be generated using one or more algorithms (e.g., a hashing algorithm such as the GMAC algorithm, a concatenation operation, etc.). The intermediate tag can be a value obtained by performing a hashing function or a concatenation operation over the corresponding counters stored at one or more branches of the integrity tree structure. In some implementations, the correlations between data blocks, authentication tags, nonce values (e.g., counters), and intermediate tags can be stored in a data structure, such as, for example, a metadata table.

[0036] In some implementations, in response to each write operation performed, authentication engine 108 updates the counter values along each level of the integrity tree structure that is related to the programmed data block. This will be explained in greater detail below.

[0037] FIG. 3 is a block diagram illustrating an example integrity storage architecture 300, in accordance with implementations of the present disclosure. Architecture 300 can include root level 302, branch level 304A-C, and leaf level 306. It is noted that architecture 300 has three branch levels by way of illustrative example, and that any number of or no branch levels can be used. Each level shown in architecture 300 can reflect a data unit. In some implementations, the size of each data unit can be 512 bits. In some implementations, the size of each authentication tag can be sixty -four bits (64 bits), the size of each intermediate tag can be 64 bits, and the size of each counter can be 48 bits. The root nodes associated with root level 302 can be stored within on-chip tamperresistant memory (e.g., a trusted Field Programmable Gate Array (FPGA), System on Chip (SoC), etc.) instantiated on a host system such that the root nodes may be protected from modification by an attacker. Nodes associated with level 304 A through level 304C and leaf level 306 can be stored within off-chip memory (e.g., a volatile or non-volatile memory device).

[0038] Leaf level 306 includes a set of counters 222 (e.g., ctrO-7), an intermediate tag 224, and an authentication tag 220 (e.g., tag05). Each counter in the set of counter ctrO-7 can reflect a counter value used to generate an authentication tag for a respective data block. By way of illustrative example, referring to FIG. 2, ctrO can reflect the counter value used to generate TagO, Ctrl can reflect the counter value used to generate Tagl, and so forth.

[0039] Tag05 can be generated to provide integrity protection for counters ctrO-7. In an example, counters ctrO-7 can be concatenated and input, along with a nonce value, into a GMAC algorithm to generate Tag05. The counter value used in the nonce value can be stored, as C05, in the next level of the integrity storage architecture 300 (e.g., branch level 304C). Each remaining counter (e.g., C00-C04, C06, and C07) stored at branch level 204C can be counter values used to generate other authentication tags stored at leaf level 306.

[0040] Tagl 5 can be generated to provide integrity protection for counters C00-C07. In an example, counters C00-C07 can be concatenated and input, along with a nonce value, into a GMAC algorithm to generate Tagl 5. The counter value used in the nonce value can be stored, as C15, in the next level of the integrity storage architecture 300 (e.g., branch level 304B). Each remaining counter (e.g., C10-C14, C16, and C17) stored at branch level 304B can be counter values used to generate other authentication tags stored at branch level 304C.

[0041] Tag20 can be generated to provide integrity protection for counters C10-C17. In an example, counters C10-C17 can be concatenated and input, along with a nonce value, into a GMAC algorithm to generate Tag20. The counter value used in the nonce value can be stored, as C20, in the next level of the integrity storage architecture 300 (e.g., branch level 304A). Each remaining counter (e.g., C21-C27) stored at branch level 304A can be counter values used to generate other authentication tags stored at branch level 304B.

[0042] Tag34 can be generated to provide integrity protection for counters C20-C27. In an example, counters C20-C27 can be concatenated and input, along with a nonce value, into a GMAC algorithm to generate Tag34. The counter value used in the nonce value can be stored, as C34, in the next level of the integrity storage architecture 300 (e.g., root level 302). Each remaining counter (e.g., C30-C33 and C35-C37) stored on root level 302 can be counter values used to generate other authentication tags stored at branch level 304A. Since root level 302 is tamper resistant, in some implementations, counters C30-37 are not provided integrity protection via an authentication tag. Accordingly, Tag05, counters ctrO-7 and Hintr05 are linked to counter C34 via branch levels 304A-C. [0043] Responsive to a write operation on a data block, each respective counter value can be updated by the integrity logic of authentication engine 108. For example, responsive to receiving a program command, counter 111 can be incremented by a predetermined value (e.g., by a value of 1). A block authentication tag can then be generated using the counter value and the user data reflected by the program command. The user data and the block authentication tag can then be programmed to a specific memory address. Counter 111 can then be incremented again, and integrity logic can generate a nonce value authentication tag using the counter value related to the block authentication tag, and the updated counter value. The nonce value authentication tag and block counter value can be programmed to the lead level (e.g., leaf level 306). The counter value can again be updated to program the counter value and the nonce value authentication tag at the next branch of the integrity tree structure, and so forth.

[0044] Intermediate tag 324 can be a value reflecting the verification of the respective upper levels (excluding the root level 302) of integrity storage architecture 300. In particular, each intermediate state can be a value reflecting the output obtained from performing a hashing algorithm or a concatenation process over the counter values of the respective upper level, excluding the root level 202. For example, the intermediate tag Hintr05 can be reflective of the value generated by concatenating or hashing counters C20, Cl 5, and C05. In one implementation, integrity logic can obtain the values for counter C20, Cl 5, and C05, generate a concatenate value by concatenating (e.g., multiplying, adding, etc.) the values for counter C20, Cl 5, and C05, and apply a hashing algorithm (e.g., a GMAC algorithm) over the concatenated value to generate intermediate tag HintrO5. In another implementation, processing logic can obtain the values for counter C20, Cl 5, and C05, apply a hashing algorithm over each of the counter values, and then generate intermediate tag Hintr05 by concatenating the values obtained from the hashing algorithm for counter C20, Cl 5, and C05. In some implementations, intermediate tag Hintr05 can be stored on the same data unit as Tag05. [0045] Intermediate state Hintrl5 can be reflective of the value generated by performing a verification operation of counters C20 and C15. Intermediate state Hintr20 can be reflective of the value generated by performing a verification operation of counter C20.

[0046] Using the intermediate tags enables the processing logic of the IME engine 100 to perform fewer read operations during verification operations, thus reducing latency. In some implementations, Hintr34 is shown for symmetric reasons of the layout and can be replaced by all zeros. In some implementations, just the concatenated value of the higher branch counter can be stored as the intermediate tags (e.g., without applying a hashing algorithm over the concatenated value).

[0047] In some implementations, the counter can be updated in a hierarchical manner. For example, with each write operation, the counter at the leaf level 306 is updated (e.g., counter, ctrO). Further, the corresponding authentication tag is updated using one or more of the intermediate tag Hintr05, the root counter C34, and/or the updated leaf level counter (e.g., ctrO). Since the counters of the branches (e.g., branch level 304A-C) are a concatenated value expressed by Hint05, they may remain updated.

[0048] In some implementations, a counter at the leaf level can experience a counter overflow. A counter overflow occurs when the counter value reaches a maximum allowable value reflected by its bit-size (e.g., 48-bit). In response to a counter overflow, the integrity logic can increment the corresponding counter value at the next level (e.g., at branch level 304C). For example, the integrity logic can update counter C05. In addition, the integrity logic can update the corresponding authentication tag (e.g., Tag 15) and the intermediate tags of the child branches (e.g., Hintr05). This process can be performed at each level in response to a counter overflow. For example, responsive to a counter overflow occurring at counter C05, the integrity logic can update counter Cl 5, authentication tag Tag20, and intermediate tags Hintrl5 and Hintr05. In some implementations, this overflow protection structure enables the counter to be reduced in size (e.g., to 24-bit, to 32-bits, etc.). Furthermore, it is noted that when the counter values are not overflow, the branches of the integrity tree structure are not accessed since verification operations can be performed using the root counter and the lead level intermediate tag.

[0049] FIGS 4A-B are diagrams illustrating generating an authentication tag to use for a verification process, in accordance with implementations of the present disclosure. FIG. 4A shows a process of generating an authentication tag (e.g., Tag 0) without an intermediate tag. In particular, processing logic can obtain counter C34, counter C20, counter Cl 5, counter C05, counter ctrO, and block BLO. Processing logic can then concatenate the values of counter C34, counter C20, counter Cl 5, counter C05, counter ctrO, and block BLO to generate a concatenated value. The processing logic can then apply a hashing algorithm (e.g., a GMAC algorithm) over the concatenated value to generate tag 0. The processing logic can then compare the generated tag 0 to the stored tag 0. Responsive to determining that the value of the generate tag 0 matches the value of the stored tag 0, the processing logic can determine that the data stored on the block (block BLO) is authentic.

[0050] FIG. 4B shows a process of generating an authentication tag (e.g., Tag 0) using an intermediate tag. In particular, processing logic can obtain counter C34, intermediate tag Hintr05, counter ctrO, and block BLO. Processing logic can then concatenate the values of counter C34, intermediate tag Hintr05, counter ctrO, and block BLO to generate a concatenated value. The processing logic can then apply a hashing algorithm (e.g., a GMAC algorithm) over the concatenated value to generate tag 0. The processing logic can then compare the generated tag 0 to the stored tag 0. Responsive to determining that the value of the generated tag 0 matches the value of the stored tag 0, the processing logic can determine that the data stored on the block is authentic. Accordingly, by using the intermediate tag, the integrity logic can traverse the branches of the integrity tree from a root node of the root level 302 directly to a respective leaf node of leaf level 306, thus using fewer read operations than the process discussed in FIG. 4A.

[0051] FIG. 6 is a flow diagram of a method 600 of performing write and update operations, in accordance with implementations of the present disclosure. The method 600 may be performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions run on a processing device to perform hardware simulation), or a combination thereof. In one implementation, the IME engine 100 of FIG. 1 performs the method 600. In one implementation, the authentication engine 108 (via tag validation component 114) of FIG. 1 performs the method 600. Method 600 will discuss receiving a write command to update the data at a specific address. In some instances, method 600 will reference the storage structure and integrity tree structure of FIGS. 2 and 3.

[0052] Referring to FIG. 6, the method 600 begins at block 602, with the processing logic receiving a write command (e.g., a program command) from, for example, a host system. In some implementations, the write command can reference a memory address (e.g., a destination block) to where to program the data from the write command.

[0053] At block 604, the processing logic verifies the data stored on the leaf node associated with the destination block. For example, using block BL0 as an illustrative example, the processing logic can use one or more of the tag05, intermediate tag Hint05, and counter C34 to verify the counter values stored on the respective data unit. In particular, the processing logic can verify the counter value associated with the stored data (e.g., ctrO) by validating tag05. To validate tag05, the processing logic can read from the location storingTag05, ctr, Hintr05 reading, obtain the current on-chip root anchor (e.g., C34) and perform a verification process. Responsive to a valid verification, the processing logic can increment the counter value to generate a new IV/nonce for the destination block.

[0054] At block 606, the processing logic increments the counter value associated with the destination block. For example, the processing logic can update ctrO to reflect a current value of the counter.

[0055] At block 608, the processing logic programs the data to the destination block. For example, the processing logic can encrypt the plaintext data to ciphertext data and store the ciphertext data in the destination location referenced by a memory address. In is noted that in some implementations, the counter value can be incremented (block 606) before, after, or in parallel with programming the data (block 608). For example, in implementations using a GCM algorithm, the counter value can be incremented prior to the encryption of the data. In implementations using XTS + Ghash, the counter value can be incremented before, after, or in parallel with the encryption and/or programming of the ciphertext.

[0056] At block 610, the processing logic updates the authentication tag, tag05, using the intermediate tag (e.g., Hintr05) and the root counter (e.g., C34) for the destination block (e.g., block BL0). For example, the processing logic can increment the root counter value. The processing logic can then generate a new version of the authentication tag by using the current counter value and the new root counter value. The processing logic then stores the new authentication tag and new counter value at their corresponding locations. In some implementations, in response to detecting a counter overflow, the processing logic can update the corresponding counter at the next branch, and update the child intermediate tags.

[0057] At block 612, the processing logic updates the remaining corresponding authentication tags of the branches using the root counter value. In some implementations, the processing logic updates one or more intermediate tag of the integrity tree architecture based on the new counter value.

[0058] FIG. 7 is a flow diagram of a method 700 of performing read and verify operations, in accordance with implementations of the present disclosure. The method 700 may be performed by processing logic that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions run on a processing device to perform hardware simulation), or a combination thereof. In one implementation, the IME engine 100 of FIG. 1 performs the method 700. In one implementation, the authentication engine 108 (via tag creation component 112) of FIG. 1 performs the method 700. Method 700 will discuss receiving a write command to update the data at a specific address. In some instances, method 700 will reference the storage structure and integrity tree structure of FIGS. 2 and 3.

[0059] At block 702, the processing logic receives, from a host system, a read command. The read command can specify an address of a data block. In an illustrative example, the data block can be block BL0.

[0060] At block 704, the processing logic obtains the authentication tag associated with the data block (block authentication tag). For example, the block authentication tag can be authentication tag tagO.

[0061] At block 706, the processing logic obtains the counter value used to generate the block authentication tag and the intermediate tag related to the counter value. For example, the processing logic can obtain counter ctrO and intermediate tag Hintr05. In some implementations, the intermediate tag and the counter value are stored on the same data unit, and require a single read operation to obtain.

[0062] At block 708, the processing logic obtains a root counter related to counter ctrO. For example, the processing logic can obtain counter C34.

[0063] At operation 710, the processing logic generates a verification authentication tag based on the intermediate tag, the block tag counter value, the root counter value, and the data from the data block. In some implementations, the processing logic first generates a concatenated value based on the intermediate tag, the block tag counter value, the root counter value, and the data from the data block. The processing logic then applies an authentication algorithm that uses a hashing function on the concatenated value to generate the second authentication tag. In at least one implementation, the authentication algorithm is the GMAC algorithm, and the hashing function is the GHASH function. Alternatively, other authentication algorithms and other hashing functions can be used. [0064] At operation 712, the processing logic determines whether the value of the stored authentication tag matches the value of the verification authentication tag. In response to the values matching, the processing logic sends, to the host system, the data stored at the data block. In response to the values failing to match, the processing logic can send, to the host system, an error message indicative of possible data corruption.

[0065] It is to be understood that the above description is intended to be illustrative and not restrictive. Many other implementations will be apparent to those of skill in the art upon reading and understanding the above description. Therefore, the disclosure scope should be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.

[0066] In the above description, numerous details are set forth. It will be apparent, however, to one skilled in the art that the aspects of the present disclosure may be practiced without these specific details. In some instances, well-known structures and devices are shown in block diagram form rather than in detail to avoid obscuring the present disclosure.

[0067] Some portions of the detailed descriptions above are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self- consistent sequence of steps leading to the desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

[0068] However, it should be borne in mind that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “receiving,” “determining,” “selecting,” “storing,” “setting,” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system’s registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

[0069] The present disclosure also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer-readable storage medium, such as, but not limited to, any type of disk, including floppy disks, optical disks, CD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, or any type of media suitable for storing electronic instructions, each coupled to a computer system bus.

[0070] In some implementations, aspects of the present disclosure can be implemented in Double Data Rate Synchronous Dynamic Random-Access Memory (DDR SDRAM), solid-state drives (SSDs), or any other type of non-volatile storage memory. In some implementations, aspects of the present disclosure can be implemented in off-chip storage topologies, such as, for example, computer express link (CXL) DDR, and other off-chip storage modules.

[0071] The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatuses to perform the required method steps. The required structure for a variety of these systems will appear as set forth in the description. In addition, aspects of the present disclosure are not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the present disclosure as described herein.

[0072] Aspects of the present disclosure may be provided as a computer program product, or software, that may include a machine-readable medium having stored thereon instructions, which may be used to program a computer system (or other electronic devices) to perform a process according to the present disclosure. A machine-readable medium includes any procedure for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable (e.g., computer-readable) medium includes a machine (e.g., a computer) readable storage medium (e.g., read-only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices, etc.).

Claims

CLAIMS What is claimed is:

1. A method comprising: receiving, by a processor, from a host system, a read command for data stored at a data block; obtaining a first authentication tag associated with the data block; obtaining a first counter value used to generate the first authentication tag; obtaining a root counter value associated with the first counter value; obtaining an intermediate tag based on a second counter value and a third counter value stored on two respective levels of an integrity tree structure, wherein the second counter value and the third counter value form a link between the first counter value and the root counter value on the integrity tree structure; generating a second authentication tag based on the intermediate tag, the first counter value, the root counter value, and the data from the data block; and responsive to determining that a value of the first authentication tag matches a value of the second authentication tag, sending, to the host system, the data stored at the data block.

2. The method of claim 1, wherein the size of each intermediate tag is sixty-four bits.

3. The method of claim 1, wherein the intermediate tag comprises a concatenated value of the second counter value and the third counter value.

4. The method of claim 3, wherein the intermediate tag comprises a value obtained from applying an authentication algorithm that uses a hashing function on the concatenated value.

5. The method of claim 4, wherein the authentication algorithm is the Galois Message Authentication Code (GMAC) algorithm, and the hash function is the GHASH function.

6. The method of claim 1, wherein the intermediate tag and the first counter value are stored in a same data unit on a memory device.

7. The method of claim 1, further comprising: generating a concatenated value based on the intermediate tag, the first counter value, the root counter value, and the data from the data block; and applying an authentication algorithm that uses a hashing function on the concatenated value to generate the second authentication tag.

8. The method of claim 1, further comprising: responsive to determining that the first counter experienced a counter overflow, updating a corresponding counter at an upper level of the integrity tree structure; updating an authentication tag associated with the counter at the upper level; and updating the intermediate tag.

9. An inline memory encryption (IME) engine having logic to perform operations comprising: receiving, from a host system, a read command for data stored at a data block; obtaining a first authentication tag associated with the data block; obtaining a first counter value used to generate the first authentication tag; obtaining a root counter value associated with the first counter value; obtaining an intermediate tag based on a second counter value and a third counter value stored on two respective levels of an integrity tree structure, wherein the second counter value and the third counter value form a link between the first counter value and the root counter value on the integrity tree structure; generating a second authentication tag based on the intermediate tag, the first counter value, the root counter value, and the data from the data block; and responsive to determining that a value of the first authentication tag matches a value of the second authentication tag, sending, to the host system, the data stored at the data block.

10. The IME engine of claim 9, wherein the size of each intermediate tag is sixty-four bits.

11. The IME engine of claim 9, wherein the intermediate tag comprises a concatenated value of the second counter value and the third counter value.

12. The IME engine of claim 11, wherein the intermediate tag comprises a value obtained from applying an authentication algorithm that uses a hashing function on the concatenated value.

13. The IME engine of claim 12, wherein the authentication algorithm is the Galois Message Authentication Code (GMAC) algorithm, and the hash function is the GHASH function.

14. The IME engine of claim 9, wherein the intermediate tag and the first counter value are stored in a same data unit on a memory device.

15. The IME engine of claim 9, wherein the operations further comprise: generating a concatenated value based on the intermediate tag, the first counter value, the root counter value, and the data from the data block; and applying an authentication algorithm that uses a hashing function on the concatenated value to generate the second authentication tag.

16. The IME engine of claim 9, wherein the operations further comprise: responsive to determining that the first counter experienced a counter overflow, updating a corresponding counter at an upper level of the integrity tree structure; updating an authentication tag associated with the counter at the upper level; and updating the intermediate tag.

17. A non-transitory machine-readable storage medium storing executable instructions which, when executed by a processing device, cause the processing device to: receive, from a host system, a read command for data stored at a data block obtain a first authentication tag associated with the data block; obtain a first counter value used to generate the first authentication tag; obtain a root counter value associated with the first counter value; obtain an intermediate tag based on a second counter value and a third counter value stored on two respective levels of an integrity tree structure, wherein the second counter value and the third counter value form a link between the first counter value and the root counter value on the integrity tree structure; generate a second authentication tag based on the intermediate tag, the first counter value, the root counter value, and the data from the data block; and responsive to determining that a value of the first authentication tag matches a value of the second authentication tag, send, to the host system, the data stored at the data block

18. The non-transitory machine-readable storage medium of claim 17, wherein the intermediate tag comprises a concatenated value of the second counter value and the third counter value.

19. The non-transitory machine-readable storage medium of claim 17, wherein the intermediate tag comprises a value obtained from applying an authentication algorithm that uses a hashing function on the concatenated value.

20. The non-transitory machine-readable storage medium of claim 17, further comprising instructions that cause the processing device to: generate a concatenated value based on the intermediate tag, the first counter value, the root counter value, and the data from the data block; and apply an authentication algorithm that uses a hashing function on the concatenated value to generate the second authentication tag .