MEAS: memory encryption and authentication secure against side-channel attacks

In this paper, we solve the problem of protecting data in memory against physical attackers in possession of a running device. More concretely, we solve the stringent problem of DPA attacks on memory encryption and authentication without additional memory overhead over conventional schemes.

We approach the topic with a detailed analysis of the security of fresh re-keying [33, 39] as a promising mechanism to prevent DPA on memory encryption. While re-keying completely thwarts DPA on the cryptographic key, our major result here is that re-keying provides merely first-order DPA security for the memory content itself. In particular, we show that the read–modify–write access patterns inevitably occurring in encrypted memory allow for profiled, higher-order DPA attacks that leak constant plaintext data when re-keying is applied to memory encryption.

Second, we build on our analysis and present Meas—the first Memory Encryption and Authentication Scheme secure against DPA attacks. The scheme is suitable for all kinds of memory including random access memory (RAM) and non-volatile memory (NVM). By making use of synergies between fresh re-keying and authentication trees [18, 27, 40], Meas simultaneously offers security against first-order DPA and random access to all memory blocks. In more detail, Meas uses separate keys for each memory block that are stored in a tree structure and changed on every write access in order to strictly limit the use of each key to the encryption of two different plaintexts at most. For higher-order DPA security, Meas performs data masking by splitting the plaintext values into shares and storing the encrypted shares in memory. This allows to flexibly extend DPA protection to higher orders in trade for additional memory. For all DPA protection levels, Meas does not require DPA-protected implementations of the cryptographic primitives, making Meas suitable for common off-the-shelf (COTS) systems equipped with unprotected cryptographic accelerators. However, Meas is also an ideal choice for constructing a DPA-secure system from scratch as engineers do not have to cope with complex DPA protection mechanisms within the cipher implementation.

Third, we give two lightweight Meas instances suitable for RAM that encrypt and authenticate the tree nodes with strictly bounded data complexity per key. Meas-v1 uses the PRINCE cipher and derives a fresh key for each encryption block using the sponge Ascon. Meas-v2 provides faster tree traversal by using the same key for the encryption of several, but a sufficiently small number of, e.g., 4 or 8, blocks using the tweakable cipher QARMA.

Finally, we implement both Meas instances on the Xilinx XC7Z020 System on Chip (SoC) Field Programmable Gate Array (FPGA) to practically evaluate the performance of RAM encryption and authentication with Meas.¹ We show that Meas provides protection against the very powerful DPA attacks, and still features the same performance and memory overhead as state-of-the-art memory authentication schemes which completely lack side-channel protection. In particular, we show that a 4-ary, first-order DPA-secure instance of Meas-v2 is a highly suitable choice for encrypting and authenticating RAM in practice. Contrary to that, protecting cryptographic implementations against DPA to make use of state-of-the-art schemes would result in massive overheads making memory encryption and authentication infeasible.

This work is organized as follows. In Sect. 2, we first state our threat model and requirements, and we then discuss the state of the art on memory encryption and authentication. The state of the art on side-channel attacks and countermeasures is content of Sect. 3. We analyze the re-keying countermeasure in terms of memory encryption in Sect. 4 and use the results to present our first-order DPA-secure Meas in Sect. 5. Section 6 then presents data masking to achieve higher-order DPA security in Meas. We give two lightweight instances of Meas suitable for RAM in Sect. 7 and detail their implementation in Sect. 8. An evaluation of Meas is done in Sect. 9, and we finally conclude in Sect. 10.

While reading can give an attacker access to confidential data stored inside the memory, modification breaks memory authenticity in several ways [17]: In spoofing attacks, an attacker simply replaces an existing memory block with arbitrary data, in splicing attacks, the data at address A is replaced with the data at address B, and in replay attacks, the data at a given address is replaced with an older version of the data at the same address.

Our leaking chip model extends the non-leaking chip model by considering passive side-channel attacks. It assumes that the microchip performing all relevant computations leaks information on the processed data via side channels, e.g., power and electromagnetic emanation (EM). Physical attackers can observe this leakage and perform side-channel attacks.

Hence, cryptographic schemes protecting the confidentiality and authenticity of off-chip memory in the leaking chip model have to fulfill three main requirements.In addition, fast random access to all memory blocks, high throughput (fast bulk encryption), and low memory overhead are desired.

Memory encryption schemes usually split the memory address space into blocks of predefined size, e.g., sector size, page size, or cache line size. Each of these blocks is then encrypted independently using a suitable encryption scheme. The partitioning of the address space into memory blocks aims to provide fast random access on block level and fast bulk encryption within the instantiated encryption scheme. Hereby, the chosen block size strongly affects possible trade-offs w.r.t. metadata overhead, access granularity, and speed.

So far, several memory encryption schemes have been proposed in the non-leaking chip model and are being used nowadays, e.g., the tweakable encryption modes XEX [47] and XTS [30], CBC with ESSIV [20], and counter mode encryption [48, 54].

For example, a keyed Message Authentication Code (MAC) using the block address information can protect against spoofing and splicing attacks. However, it still allows for replay attacks. In order to protect against replay attacks, authenticity information must be stored in a trusted environment, e.g., in secure on-chip memory, that an attacker cannot modify. Authentication trees minimize this demand for secure on-chip storage, namely only the tree’s root is stored in secure memory, while the remaining tree nodes can be stored in public memory. Such trees therefore protect against spoofing, splicing, and replay attacks. Authentication trees over m memory blocks with arity a have logarithmic height \(l=\log _a(m)\). Three prominent examples of authentication trees are Merkle trees [40], Parallelizable Authentication Trees [27] (PAT), and Tamper Evident Counter [18] (TEC) trees. We give a detailed description of them in Appendix A.

In SPA attacks, the adversary tries to learn the secret value processed inside a device from observing side channels during a single processing of the secret value to be revealed, e.g., the adversary tries to learn the encryption key from a power trace observed during a single encryption. However, the adversary is allowed to observe the same encryption multiple times to reduce measurement noise. Clearly, an implementation that cannot keep a key secret for a single encryption is worthless. Therefore, bounded side-channel leakage for a single encryption and thus security against SPA attacks is a precondition for any implementation.

Quite naturally, the amount of information learned about a secret value from a side channel increases with the number of different inputs processed under the respective secret. This is exploited in DPA attacks, which use the observation of several different processings of a secret value in a device to learn its value, e.g., the adversary tries to learn the secret key from power traces observed during the encryption/decryption of multiple (public) input values.

One important property of DPA attacks is their order. The order d of a DPA [34, 41] is defined as the number of d different internal values in the executed algorithm that are used in the attack. The attack complexity of DPA grows exponentially with its order [12].

Independently of whether SPA or DPA is performed, side-channel attacks can make use of profiling. Profiling of a side-channel, e.g., the power consumption, means to construct templates [13] that classify the side-channel information of a target device with respect to a certain value processed inside the device. In the actual attack, the templates are matched with the side-channel trace to gain some information on the value processed inside the device. The information learned from template matching can then be exploited in either SPA or DPA manner. Note, however, that conducting profiled attacks requires much more effort than performing non-profiled attacks. Further note that in many applications it is impossible to perform the required profiling step at all.

The effectiveness of DPA attacks has caused a lot of effort to be put into the development of countermeasures to prevent DPA. Two basic approaches to counteract DPA have evolved, namely (1) to protect the cryptographic implementation using mechanisms like masking, and (2) the frequent re-keying of unprotected cryptographic primitives.

Up until now, the principle of re-keying was applied only to communicating parties aiming for confidential transmission. Hereby, constructions following Fig. 1 prevent DPA, but require the initialization with a fresh key and thus secure key synchronization between the communicating parties. A common approach to this synchronization is to derive a fresh key from a shared master secret k and a public, random nonce n [21, 39, 53]. However, this approach shifts the DPA problem to the key derivation, which thus needs DPA protection through mechanisms like masking.

The encryption and authentication of data stored in memory gives different conditions for the instantiation of re-keying-based schemes. In particular, encrypting data in memory means that encryption and decryption are performed by the same party, i.e., a single device encrypts data, writes it to the memory, and later reads and decrypts the data. Therefore, key synchronization becomes unnecessary and the cryptographic scheme can be re-keyed using random numbers without the need for any cryptographic primitive or function being implemented with DPA countermeasures.

The typical target of DPA attacks is the key being used as key recovery fully breaks a cryptographic scheme. Re-keying-based schemes thus thwart such attacks and make DPA on the key infeasible. However, the actual goal of encryption is to ensure data confidentiality. Therefore, protecting the key against DPA is a useful measure, but as our analysis shows, the application of re-keying to memory encryption can yet result in a loss of memory confidentiality.

The main observation that leads to this conclusion is read–modify–write operations that inevitably occur in any encrypted memory. These take place whenever the write granularity is smaller than the encryption granularity. For example, when a single byte is written to a memory that is encrypted using an 128-bit block cipher, the respective 128-bit encryption block has to be loaded from memory, decrypted and modified according to the byte-wise write access, and then be encrypted again and written back to the memory. In this case, 120 bits of the respective block remain the same. The same phenomenon is observed in encryption schemes that cover multiple encryption blocks \(p_0,p_1,p_2,\ldots \) . Here as well, one plaintext block, e.g., \(p_0\), might be changing, while others, e.g., \(p_1\), remain constant.

If now re-keying is applied to memory encryption, the constant plaintext parts within read–modify–write operations will be encrypted several times using different keys. This causes constant, secret plaintext parts to be mixed with varying keys. This situation is quite similar to the original DPA setting, where a constant, secret key is mixed with varying plaintexts. For stream ciphers, attackers can easily exploit this mixing operation—the XOR of varying pad and constant plaintexts—in a first-order DPA. Namely, attackers can model the power consumption of the varying pad for each plaintext hypothesis using the observed ciphertexts. Matching the power model with the side-channel observations eventually reveals the constant plaintext. For block ciphers, a first-order DPA does not work, but a profiled, second-order DPA that is similar to unknown plaintext template attacks [28] can be applied to learn constant plaintexts. While we emphasize that there are also other second-order techniques, e.g. [14, 35], that can be employed in this setting, we consecutively focus on adapting unknown plaintext template attacks to extract constant plaintexts from re-keyed block ciphers.

The construction of Meas is designed to be secure according to the leaking chip model. Therefore, Meas requires an SPA-secure block encryption scheme ENC and an SPA-secure authenticated encryption scheme AE. Both ENC and AE have to fulfill the common security properties for (authenticated) encryption schemes and must be based on block encryption such as in [56]. However, Sect. 7 will detail concrete instances for both ENC and AE. Apart from that, any other operations within Meas, such as loading keys, must be SPA-secure. In addition, a secure random number generator is needed for generating keys.

An example of the tree construction proposed for Meas is depicted in Fig. 2. For the sake of simplicity, this example as well as the following description assumes the use of a binary tree, i.e., arity \(a = 2\). However, instantiating the tree with higher arity is easily possible.

The structure of Meas is as follows. The data in memory is split into m plaintext blocks \(p_i\). Each of these \(p_i\) is encrypted and authenticated to a ciphertext-tag pair \((c_i, t_i)\) using the authenticated encryption scheme AE with data encryption key \(dek_{i}\):The encryption scheme ENC then encrypts the data encryption keys \(dek_i\) to the ciphertexts \(c_{l-1,i}\) using key encryption keys \(kek_{l-1,i}\). The operator || denotes concatenation.Recursively applying ENC in a similar way to the key encryption keys finally leads to the desired tree.While all ciphertexts and tags are stored in public, untrusted memory, the root key \(kek_{0,0}\) is stored on the leaking chip.

The design of Meas protects data authenticity with respect to spoofing, splicing, and replay attacks using both the authentic root key and the AE scheme. In particular, spoofing and splicing attacks on the leaf nodes are directly detected by the AE scheme since different keys are used for each block. Moreover, the AE scheme indirectly also protects the inner tree nodes for properly chosen schemes AE and ENC. In such case, any tampering with the ciphertext of an intermediate node will lead to a random but wrong key to be decrypted. This tampering will thus propagate down to the leaf node to give an erroneous, random data encryption key and finally an authentication error.

We discuss the side-channel security using three types of attackers with increasing capabilities. The first type solely uses passive attacks and tries to exploit the side-channel leakage during operation. The second type additionally induces authenticity errors by tampering with the memory and strives for exploiting error handling behavior. The third type further tries to gain an advantage by restarting, i.e., power cycling, the whole system at arbitrary points in time.

The basic idea to provide higher-order DPA security is to add a masking scheme (cf. Sect. 3.4.1) to Meas. However, unlike the masking of specific cryptographic implementations, the proposed data masking scheme operates with unprotected primitives. Therefore, the plaintext data in each tree node of Meas is first masked, and then the masked plaintext and the masks are encrypted separately and both stored in memory. On decryption, both the masked plaintexts and the masks are decrypted and the masks applied to obtain the original plaintext value.

The masking scheme requires new masks to be chosen whenever the key of a tree node is changed. This is the case on every write access to a specific node. As a result, the data being encrypted is randomized. This prevents that constant data is encrypted under different keys. Moreover, it requires adversaries trying to learn a constant plaintext using profiled attacks such as described in Sect. 4 to additionally extract information on every single mask from the side-channel. Therefore, the order of the attack increases accordingly.

The following masking approach can be applied accordingly to both the intermediate nodes, which use an encryption scheme ENC, and the leaf nodes, which use an authenticated encryption scheme AE. However, for simplicity we only consider the encryption of an arbitrary tree node using an encryption scheme ENC.

When encrypting a tree node in Meas, the node’s plaintext p is split into \(b+1\) blocks \(p_0,\ldots ,p_b\) according to the size of the underlying encryption primitive, i.e., 128 bits in case of AES. In order to protect this node against d-th order DPA, \(d-1\) random and secret masks \(m_0,\ldots ,m_{d-2}\) have to be generated. These masks are then applied to each plaintext block \(p_i\) to give random values \(r_i\):In the actual encryption, both the masks \(m_0,\ldots ,m_{d-2}\) and the random values \(r_0,\ldots ,r_b\) are processed and the respective ciphertext c is stored in memory:Whenever the node has to be read, the ciphertext is decrypted to give \(m_0||\ldots ||m_{d-2}||r_0||\ldots ||r_b\). To obtain the plaintext blocks \(p_i\), the masking is reverted by again xor-ing all masks \(m_0,\ldots ,m_{d-2}\) to each block \(r_i\).

The re-keying of the (authenticated) encryption scheme guarantees that adversaries are not capable of building suitable DPA power models from the observation of ciphertexts and thus prevents DPA against the key completely.

To prevent the loss of plaintext confidentiality from the profiled, second-order attacks outlined in Sect. 4, the proposed masking scheme randomizes the plaintext input using \(d-1\) random, secret masks. As a result, the scheme requires adversaries to combine side-channel information from \((d+1)\) different values to recover the plaintext, i.e., to perform a \((d+1)\)-th order DPA. In particular, such DPA requires to learn side-channel information on the varying key, an intermediate value in the cipher, and the \(d-1\) masks. On the other hand, the masking scheme requires to additionally encrypt \(d-1\) masks in each tree node. However, for a properly chosen encryption scheme ENC, these encryption operations cannot be exploited in a DPA, because both the masks and the keys are random and always changed simultaneously on every write access to the respective tree node.

Unfortunately, using the same masks for multiple encryption blocks within a tree node can yet give side-channel leakages with an order below \(d+1\). For illustration, we consider a single mask \(m_0\), i.e., \(d=2\). In this case, attackers could exploit the combination of \(m_0\) with \(b+1\) different plaintext blocks within a tree node to learn the mask \(m_0\) in a second-order side-channel attack with unknown input and output. Once \(m_0\) is known, \(m_0\) can be used to learn a constant plaintext block \(p_i\) in the same tree node using another second-order attack.

However, such lower-order attacks are impractical for Meas for two main reasons. First, in order to perform a lower-order attack on a constant \(p_i\), an attacker must initially learn all the masks \(m_0,m'_0,m''_0,\ldots \) as they are changed upon re-keying. Second, the number of different operations with a certain mask \(m_0\) is bounded by the number of \(b+1\) plaintext blocks in each tree node. For example, a 4-ary instance of Meas might reuse the same mask four times, which will typically not suffice to recover the mask. Consequently, the data complexity for each mask is limited in the same way as it is limited for each key within Meas, making lower-order attacks to learn the masks practically infeasible. Contrary to that, the number of different keys used for a constant plaintext block \(p_i\) is potentially unlimited.

The data complexity for each mask depends on the number of plaintext blocks in a tree node that share the respective mask. This number of plaintext blocks depends on the tree arity a for intermediate nodes, and on the data block size \(s_b\) for data leaf nodes. Hence, both the data block size and the tree arity must be chosen to give a data complexity per mask that suits the device’s leakage behavior. Hereby, note that learning the masks involves at least a second-order attack setting with unknown input and output, which usually allows for higher data complexities than for keys that encrypt/decrypt known plaintexts or ciphertexts.

Besides, we also emphasize that profiled DPA attacks such as in Sect. 4—which are counteracted by the proposed masking scheme—are quite hard to conduct on state-of-the-art systems. For example, while the unknown plaintext template attack in [28] was performed against software implementations on 8-bit and 32-bit microcontrollers, a profiled DPA will take significantly more effort on hardware implementations embedded in a complex system-on-chip. Moreover, the attack complexity also rises rapidly with the attack order. As a result, small protection orders will already be sufficient for Meas in practice. However, a detailed analysis of the side-channel leakage of a device implementing Meas is indispensable for a proper choice of the protection order.

The definite choice of the implemented protection order allows for various trade-offs influenced by several parameters: the cost for storing the masks, the concrete leakage behavior of the device, and the risk. Hereby, the leakage behavior and the cost for storing the masks are closely coupled.

A DPA is more likely to be successful on a device the more side-channel leakage the device gives. Therefore, a higher protection order is needed the more the device leaks, which leads to higher storage costs for masks. Alternatively, the leakage of the device might be reduced by hiding countermeasures [38] in the implementation, such as shuffling. However, such countermeasures can only be built into newly designed devices. Nevertheless, besides the actual strength of a potential attacker, the actual leakage behavior of the device forms the basis for the choice of the protection order and thus memory cost.

Besides, the choice of the protection order is also strongly influenced by the concrete risk of an attack. In more detail, a trade-off between the protection order and the risk is possible. Namely, the higher the risk of an attack to a specific block, the better should be the protection of the respective block, i.e., the higher should be the protection order. Concretely in Meas, the tree nodes stored in levels closer to the root are a more interesting target for an attacker since revealing the keys stored in these nodes would allow to decrypt large parts of the memory. Therefore, tree nodes closer to the root are at higher risk and thus need a higher protection order. However, the number of nodes in one tree level decreases the closer the respective level is to the root. As a result, increasing the protection order for tree nodes at higher risk has only little memory overhead in Meas and thus is an inexpensive improvement of security against higher-order DPA.

Our instance Meas-v1 is intended for RAM encryption and authentication and constructs ENC and AE by combining two different primitives: a lightweight block cipher E for encryption, and an r-round permutation \(f^r\) for sponge-based key derivation and authentication. While ENC uses the sponge merely for key stream generation, the sponge duplex construction [9] is used in AE to also absorb the computed ciphertext and to compute the tag. Algorithm 1 gives the description of the respective algorithms. Their schematic is illustrated in Figs. 3 and 4, respectively. Since Meas applies (authenticated) encryption to message blocks of fixed, well-defined length, we describe ENC and AE without a padding rule and assume the messages to be a multiple of the b-bit block size of E. Note that for optimization, AE absorbs the ciphertexts \(c_i\) with some delay. This allows to compute the permutation \(f^{r_2}\) and the encryption E in parallel.

We use PRINCE [11] as the block cipher E and the Ascon permutation [16] with \(r_1=8\) and \(r_2=6\) rounds for the sponge. PRINCE uses a key of \(s_{key}=128\) bits to process blocks of \(b=64\) bits and the Ascon state S is sized \(s_{state}=320\) bits. These parameters allow to implement both ENC and AE with adequate throughput and low latency in hardware. The size of the tag \(s_{tag}\) can be chosen according to the desired security level, e.g., \(s_{tag}=64\) or 128 bits.

For this purpose, we construct ENC using a tweakable block cipher. This allows to efficiently encrypt/decrypt parts of a tree node similar to ECB, but provides better security in terms of ciphertext distinguishability. Given a tweakable block cipher \(E(k;\tau ;p)\) that encrypts a b-bit plaintext p with the key k and tweak \(\tau \), a tree node comprising u plaintext blocks \(p_0,\ldots ,p_{u-1}\) is thus encrypted by simply computing \(E(k; addr(p_i); p_i)\) for \(i=0,\ldots ,u-1\), where the tweak \(\tau \) is set to be the address of the respective \(p_i\) in memory. This is summarized in Algorithm 2.

On the other hand, we keep the design of AE in Meas-v2 the same as in Meas-v1. However, to avoid the implementation of another cipher for the use in AE, we recommend using the same tweakable cipher \(E(k; \tau ; p)\) in AE as well and set the tweak \(\tau \) in AE to either the block address or a constant. As the tweakable block cipher \(E(k; \tau ; p)\), we use the lightweight design QARMA-64 [4] with the parameter \(r=6\).

In terms of DPA, the mentioned approach increases the number of different inputs processed using a single key according to the number of plaintext blocks u in a tree node. However, for many practical implementations DPA will remain infeasible also for, e.g., 4 or 8, different encryptions using the same key. This assumption facilitates the efficient and secure implementation of Meas-v2 for, e.g., binary and 4-ary trees.

For the implementation, we chose a ZedBoard featuring the Xilinx Zynq XC7Z020 SoC and 512 MB DDR3 RAM. This SoC consists of two parts: (1) a processing system (PS) comprising a dual-core ARM Cortex-A9 processor as well as several peripherals, and (2) a Xilinx Artix-7 programmable logic (PL). The PS is connected to the PL via 32-bit advanced extensible interfaces (AXI). The PL has access to the RAM via 64-bit AXI.

For memory encryption and authentication, we designed an encryption pipeline capable of Meas that is placed in the PL. As shown in Fig. 5, the software running on the ARM core is configured such that the processor accesses the main memory via the PL, where all accesses are transparently encrypted and authenticated using Meas.

The implementation of Meas requires to place all the tree nodes as well as their metadata somewhere in the RAM. For this purpose, and as shown in Fig. 6, the physical memory is partitioned into two parts. In the first part, all data (leaf) nodes of Meas are placed. These also contain their respective authenticity tags. The consecutive, second part contains all intermediate tree nodes storing the keys.

In order to provide the functionality of Meas transparently to the CPU, a translation of the CPU’s memory requests to the encrypted physical memory is required. Without consideration of tree node fetches, Fig. 7 illustrates this CPU address translation. The CPU memory request is split according to the block size of the data (leaf) nodes. The Meas implementation then issues independent requests to each of these data leaf nodes. Hereby, the size of the authentication tags is taken into account, which causes both an address shift and additional tags to be fetched.

However, the tree construction requires to also load several keys to decrypt a certain data (leaf) node. These key load operations are handled the same way as the requests to the data leaf nodes themselves. In particular, the Meas implementation issues, translates, and processes the respective key load requests to intermediate tree nodes transparently without further CPU interaction and follows an address translation similar to data leaf nodes.

The pipeline architecture of our Meas implementation is visualized in Fig. 8. Its design results from the typical data flow in encrypted memory accesses. In particular, all requests run through a series of modules performing different actions. Hereby, the single modules interact by using a simple handshake mechanism. The width w of the respective data stream can be set to either 64 or 128 bits.

Our implementation communicates with CPU and memory via five different AXI4 interfaces: (1) the CPU address port, (2) the CPU read port, (3) the CPU write port, (4) the memory read port, and (5) the memory write port. Read requests use the modules shaded in light gray. Write requests are implemented as read–modify–write operations and additionally use the modules depicted in dark gray. Dashed lines mark modules needed to process or optimize key-related requests to intermediate tree nodes.

Comparing the contestants in Table 1 regarding security properties shows that only Meas and TEC trees provide both confidentiality and authenticity in the form of spoofing, splicing and replay protection. DPA security, on the other hand, is only featured by Meas and Merkle trees. However, Merkle trees do not provide confidentiality and their DPA security can be considered a side effect. Namely, the hash functions used in Merkle trees simply do not use any secret material, i.e., keys or plaintexts, which is the common target in DPA attacks.

A more performance oriented feature, on which previous tree constructions typically improved on, is the ability to compute the cryptographic operations involved in read and write operations in parallel. Having this property is nice in theory, but is in practice not the deciding factor to gain performance. To make use of a scheme’s parallelism, multiple parallel implementations of the cryptographic primitives as well as multi-port memory, to read and write various nodes in parallel, are required. Since these resources are typically not available, a common, alternative approach to improve performance is the excessive use of caches.

In Meas, due to the key encapsulation approach used to achieve its DPA security, parallelizing the computations within the encryption scheme is not possible. However, this is not necessarily a problem preventing the adoption of Meas in practice since on-chip computation is very fast compared to off-chip memory accesses. Additionally, like for all authentication trees, caches for intermediate nodes are a very effective and important measure to reduce the average latency. In summary, the performance of any authentication tree (and Meas) is mainly determined by the tree height, which depends on both the tree arity and the number of blocks in the authenticated memory, and the cache size. As a result, given a concrete implementation of the cryptographic primitive, the actual runtime performance of all authentication trees is expected to be quite similar, which is also emphasized by the implementation results following in Sect. 9.6.

Table 1 further contains the memory overhead formulas that have been derived for each scheme. These formulas take into account the tree arity a, and the sizes for data blocks \(s_b\), nonces \(s_{nonce}\), hashes \(s_{hash}\), tags \(s_{tag}\), and keys \(s_{key}\). The overhead formulas neglect the influence of the actual number of data blocks m given that it vanishes with rising node counts. The overheads therefore have to be considered as an upper bound which gets tight with \(m \rightarrow \infty \). This approach gives exact and comparable results that are independent of the actual implementation and that are realistic for any memory with more than 128 data blocks.

The different parameters involved may make the overhead comparison seem difficult at first glance. However, it gets quite simple when actual instantiations are considered. Instantiating the trees for a fixed security level with \(s_{nonce} = s_{tag} = s_{key}\) and \(s_{hash} = 2 \cdot s_{tag}\), for example, shows that Merkle trees, PATs, and TEC trees have identical overhead. The overhead of Meas, on the other hand, is even lower, especially with small arity. This is due to the fact that in Meas only leaf nodes are directly authenticated. On the other hand, PATs and TEC trees directly protect the authenticity of every tree node.

The memory overhead of Meas, PATs, Merkle trees, and TEC trees is also visualized in Fig. 9 for different block sizes. For practical instantiations, the block size will be chosen according to the system architecture, namely page size, sector size, or cache line size. Both the sectors of modern disks and memory pages in state-of-the-art systems are sized 4096 bytes \((=32768\) bits). Such large block size is out of scope of Fig. 9 as it has negligible memory overhead in any case. Besides, the memory overhead for a block size of 4096 bits (sector size in older hard disks) is also very low, e.g., 7.3% for 4-ary Meas. However, the memory overhead of Meas for block sizes fitting nowadays cache architectures is also practical given the security features it provides. While today’s typical cache line size is 512 bits, modern CPUs often come with features such as Adjacent Cache Line Prefetch [31], which effectively double the cache line fetches from memory to 1024 bits. In a 4-ary Meas, for example, such block size results in decent 29.2% memory overhead.

Note that these relatively small overheads—quite similar to existing authentication techniques—in combination with additional and exclusive DPA protection are the main advantage of Meas. Using existing memory encryption and authentication schemes with DPA-protected implementations, on the other hand, would result in overheads of a factor of four to a few hundred [6, 10, 42, 45] and thus be far more expensive, eventually rendering memory encryption and authentication in many applications impractical.

The memory overhead of Meas with higher-order DPA protection additionally depends on the protection order d and the size of the masks \(s_{mask}\). This size \(s_{mask}\) typically equals the block size of the cryptographic primitive \(s_{state}\). A generalized version of the limit of the memory overhead as the number of memory blocks approaches infinity is:In addition to the memory overhead without masking, Fig. 9 shows the memory overhead with masking for a 4-ary tree and 128-bit security, i.e., the keys, the tags, and the masks are sized 128 bits. It shows that masking adds multiplicatively to the memory overhead for all block sizes. However, for larger block sizes, the memory overhead of Meas becomes negligible regardless of the protection order. Note that the protection order stated for Meas in Fig. 9 applies to all nodes in Meas. If, however, and as explained in Sect. 6.4, different protection orders are used for nodes at different risk, the depicted plots mark the border cases for the actual memory overhead. For example, if low-level tree nodes do not use masking (i.e., having first-order DPA security) and first-order masking is applied to all other nodes (i.e., having second-order DPA security), the actual memory overhead is lower- and upper-bounded by the plot with first- and second-order protection, respectively.

An evaluation of the memory overhead of Meas over different protection orders and arity is depicted for 1024-bit blocks and 128-bit security in Fig. 10. Hereby, it turns out that the memory overhead is strongly influenced by the tree’s arity leading to two main observations. First, a higher arity clearly lowers the memory overhead, but for an arity higher than eight, the reduction resulting from another increase of the arity becomes quite small. Second, the memory overhead rises linearly with the protection order, but the increase is stronger the lower the tree’s arity is. This is due to the masks for randomization of the plaintext being chosen and stored for each tree node. As a result, higher arity leads to more plaintext blocks sharing such masks in one tree node and thus lower memory overhead due to the masking.

Meas consumes a considerable amount of randomness. In particular, fresh random keys and masks must be chosen for all nodes on the path from the root to the leaf whenever a write operation is performed. For Meas with protection order d, this sums up to \((s_{key} + (d-1)\cdot s_{mask}) \cdot (l+1)\) random bits needed on each write operation, where l is the tree height. Implementations of Merkle trees, PATs and TEC trees without consideration of side channels, however, do not require any random value if all nonces are chosen as counters. Yet, cipher implementations that protect PATs and TEC trees against side-channel attacks rely on significant amounts of randomness too. Namely, implementations with protection order d split their state into \((d+1)\) shares. This demands for at least \(d \cdot s_{state}\) random bits per cipher invocation that get necessary for all accessed nodes on both reads and writes. Contrary to that, Meas does not require randomness during read accesses.

We extensively evaluated the performance of our Meas implementation from Sect. 8. In particular, we ran both Meas-v1 and Meas-v2 on the Digilent ZedBoard using different tree arities. As a state-of-the-art reference, we further implemented and ran a variant of TEC trees with different arities based on the same architecture as given in Fig. 8. These TEC trees use Ascon  [16] for authenticated encryption. For all our evaluations, we used an unprotected implementation of Ascon that computes three permutation rounds per cycle.

The evaluations for TEC trees were done with 64-bit counters (nonces) and 64-bit tags, which is a common instance for TEC trees in RAM [25]. For our evaluations of Meas, we used a side-channel protection order \(d=1\) and 128-bit keys. Besides, we operated Meas with 128-bit tags as 64-bit tags only gave negligibly better results. Another relevant evaluation parameter is the data block size \(s_b\). A suitable choice for \(s_b\) typically is the processor’s cache line size. While the cache of the ARM Cortex-A9 processor on the ZedBoard’s Xilinx XC7Z020 SoC features 256-bit cache lines, we configured the cache to always fetch 512-bits from memory by enabling the double line fill feature [3]. For this reason, both Meas and the TEC tree use a data block size of \(s_b=512\) bits. To speed up our designs, we made use of 1024 root keys (or root nonces for TEC trees) and a cache with 1024 slots to store keys (or nonces, respectively).

All our implementations use the 32-bit GP0 AXI interface to the CPU and the 64-bit HP0 AXI interface to the memory. As a result, a natural choice for the width w of the internal data stream that connects the various modules in Fig. 8 is 64 bits. For the TEC tree implementation, we hence set \(w=64\) bits. On the other hand, Meas operates heavily on 128-bit keys, which could make a 128-bit internal stream more efficient. For this reason, we evaluated the performance impact of the internal data stream width by running both Meas-v1 and Meas-v2 with both \(w=64\) and \(w=128\) bit internal stream width.

In our evaluations, we booted Linux (Xilinx Linux kernel 4.4, tag 2016.2) [59] in encrypted and authenticated memory, and measured the memory performance using a set of benchmarks. In particular, we executed tinymembench 0.3 [51] and LMBENCH 3.0-a9 [52] for determining the memory bandwidth and latency, respectively. We performed these benchmarks for 256 MB of encrypted and authenticated memory provided to the ARM CPU and an FPGA clock frequency of 50 MHz. Note that at 50 Mhz, the 32-bit GP0 interface bounds the achievable memory bandwidth with 200 MB/s.