Towards the optimal performance of integrating Warm and Delay against remote cache timing side channels on block ciphers

Abstract

Cache timing side channels allow a remote attacker to disclose the cryptographic keys, by repeatedly invoking the encryption/decryption functions and measuring the execution time. Warm and Delay are two algorithm-independent and implementation-transparent countermeasures against remote cache-based timing side channels for block ciphers. They destroy the relationship between the execution time and the cache misses/hits which are determined by the secret key, but bring remarkable performance overhead. In this paper, we investigate the performance of cryptographic functions protected by Warm and Delay, and attempt to find the best strategy to integrate these two countermeasures with the optimal performance while effectively eliminate remote cache timing side channels for block ciphers implementations with lookup tables. To the best of our knowledge, this work is the first to systematically analyze the performance of integrating Warm and Delay against cache side channels.We derive the optimal scheme to integrate Warm and Delay, and apply it to AES. It is proven that the integration scheme achieves the optimal performance with the least extra operations on commodity systems. Finally, we implement it on Linux with Intel CPUs. Experimental results confirm that, (a) the execution time does not leak information on cache access, (b) the scheme outperforms other integration strategies of Warm and Delay, and (c) the implementation works without any privileged operations on the computer.

Keywords

Cache side channel optimal performance timing side channel block cipher AES

1. Introduction

In practical implementations of cryptographic algorithms, the cryptographic keys could be leaked through side channels on timing [2,3,8,9,14,34,37,46,50,57,58], electromagnetic fields [29], power [10,49], ground electric potential [30] or acoustic emanations [31], even when the algorithm is semantically secure. Among these vulnerabilities, timing side-channel attacks are launched without any special probe devices. In particular, remote timing side channels allow attackers, who have no system privilege or physical access to the computer, to discover the keys by repeatedly invoking the encryption/decryption functions and measuring the execution time [9,14,17,18,46].

One type of remote timing side channels, called remote cache timing side channels in this paper, exploits the time differences of data-cache hits and misses. Such cache timing side channels are widely found in the implementations of block ciphers [4,7,9,53,58]. In the implementations, table lookup is the primary time-consuming operation in encryption/decryption. The overall execution time is influenced by the number of cache misses/hits in table lookup. Therefore, from the execution time, attackers are able to infer the inputs of table lookup operations which are determined by the secret keys (and the known plaintext/ciphertext). Generally, for a block cipher, encryption and decryption are symmetric computations with same basic operations. So we only emphasize on encryption in the rest of the paper, but all discussions and conclusions are applicable to decryption.

Compared with other side channels, such as power, electromagnetic fields, ground electric potential and acoustic emanations, cache-based timing side-channel attacks do not require special equipments or extra physical access to the victim system. Moreover, such remote attacks only require the least privilege to (remotely) invoke the encryption functions, while other active cache side-channel attacks involve operations by a malicious task that shares caches with the victim cryptographic engine [34,52,61,63].

Various methods are proposed against cache timing side-channel attacks for block ciphers, destroying the relationship between the secret keys and the execution time. The intuitive design is to perform encryption, a) with the lookup tables completely inside or outside caches, or b) in a constant period of time, regardless of cache utilization. Warm and Delay are two typical algorithm-independent and implementation-transparent mechanisms to eliminate cache timing side channels [15,50,62]. Warm fills cache lines by reading constant tables before the encryption operations, and Delay inserts padding instructions after encryption.1

¹
Another choice is to perform encryption without caches, which is inefficient. In fact, a typical Delay strategy is to extend the encryption operation in constant time, equal to the execution time without caches.

With Warm or Delay, the execution time measured by attackers becomes irrelevant to the cache misses/hits during encryption.

These two common mechanisms prevent cache-based timing attacks at different phases, but they introduce extra operations and significantly degrade the performance. In this paper, we investigate the performance of symmetric cryptographic functions that adopt Warm and Delay to defend against remote cache timing side channel attacks, and attempt to find the optimal strategy to integrate these two mechanisms to achieve the optimized performance. The following principles are analyzed and discussed in the integration:

Each encryption is protected by Warm and/or Delay, so that the measured time reflects either the best case (i.e., all table entries are cached by Warm), or the worst case (i.e., it is delayed to the execution time without any caches). Otherwise, the cache timing side channel attacks may still be launched.

In order to optimize the performance, Warm is preferred to Delay; i.e., finish encryption operations as many as possible, with all table entries in caches. Only when the effect of Warm is broken by system activities, such as interrupts and task scheduling, i.e., the information on the secret key may be leaked, the execution time is delayed to the worst case.

When Delay is performed, Warm is done as a part of inserted padding instructions for the next encryption. So, the cost of Warm is masked by padding instructions, and the performance is further improved.

The integrated scheme does not require any privileged operation on computer systems. The conditions to perform Warm and Delay, are defined as regular timing. Reading constant tables, inserting padding instructions, and timing are commonly supported in computer systems without special privileges. The scheme is independent of algorithms and transparent to implementations. It does not depend on any special design or feature of block ciphers, and it is applicable to different implementations.

We apply the integrated Warm+Delay scheme to protect AES, and analyze the conditions that produce the optimal performance. It is proven that, the integrated scheme with appropriate parameters, achieves the optimal performance with the least extra operations on commodity systems; that is, without any unnecessary table lookup operations or padding instructions. The optimal performance of Warm+Delay with different key sizes (128, 192, and 256 bits) and different implementations (2 KB, 4 KB, 4.25 KB, and 5 KB lookup tables), is also investigated. For example, the protected AES-128 implementation with a 2 KB lookup table [24] achieves the optimal performance, if the ratio of the extra execution time caused by Delay to the extra time by Warm, is less than a certain threshold. These conditions hold in commodity computers, which is confirmed by our experiments. The conditions of the optimal performance for other AES implementations of different key sizes are not identical but also hold in commodity systems.

To the best of our knowledge, this is the first to systematically analyze the optimal performance of integrating Warm and Delay against remote cache timing side channels in commodity systems. Our contributions are as follows:

We investigate the overheads of Warm and Delay, and derive the scheme to integrate these countermeasures with the optimal performance while effectively eliminate remote cache side channels for block ciphers.

We implement the optimal integration scheme on Linux with Intel CPUs for AES-128, and experimentally confirm that it (a) eliminates cache timing side channels, (b) outperforms other different integration strategies, and (c) works without any privileged operation on the system.

The remainder of this paper is organized as follows. Section 2 presents the background and related works. Section 3 discusses the Warm+Delay scheme and analyzes its security. Section 4 proves the optimal integration scheme, which is verified in Section 5. Section 6 contains extended discussions. Section 7 draws the conclusions.

2. Background and related works

2.1. AES and block cipher implementation

AES is a block cipher with 128-bit blocks, and the key is 128, 192 or 256 in bits. AES encryption (or decryption) consists of several rounds of transformations and the number depends on the key length. Each round consists of SubBytes, ShiftRows, MixColumns and AddRoundKey on the 128-bit state.2

²
The last round of AES encryption performs only SubBytes, ShiftRows and AddRoundKey.

The transformations except AddRoundKey, are implemented as lookup operations on constant tables [24], and AddRoundKey consists of bitwise-XOR on the state.

The straightforward AES implementation needs four 1 KB tables in all rounds, $T_{0}$ , $T_{1}$ , $T_{2}$ and $T_{3}$ , where $S (x)$ is the result of an AES S-box lookup for the input x. $\begin{matrix} \{\begin{matrix} T_{0} [x] = (2 \cdot S (x), S (x), S (x), 3 \cdot S (x)) \\ T_{1} [x] = (3 \cdot S (x), 2 \cdot S (x), S (x), S (x)) \\ T_{2} [x] = (S (x), 3 \cdot S (x), 2 \cdot S (x), S (x)) \\ T_{3} [x] = (S (x), S (x), 3 \cdot S (x), 2 \cdot S (x)) \end{matrix} \end{matrix}$

Four tables are encoded into a 2 KB lookup table in the compact implementation, $T [x] = (2 \cdot S (x), S (x), S (x), 3 \cdot S (x), 2 \cdot S (x), S (x), S (x), 3 \cdot S (x))$ . Note that, $T_{0} [x]$ , $T_{1} [x]$ , $T_{2} [x]$ and $T_{3} [x]$ are included in $T [x]$ .

Implementations of other block ciphers, usually consist of table lookup operations and basic computations without data-dependent branches in the execution path, such as 3DES, Blowfish [54], CAST-128 [5] in OpenSSH-7.4p1 [47].

2.2. Cache side channels

Caches, a small amount of high-speed memory cells located between CPU cores and RAM, are designed to temporarily store the data recently accessed by CPU cores, avoiding accessing the slow RAM chips. When the CPU core attempts to access a data block, the operation takes place in caches if the data have been cached (i.e., cache hit); otherwise, the data block is firstly read from RAM into caches (i.e., cache miss) and then the operation is performed in caches.

Cache timing side-channel attacks exploit the fact that accessing cached data is about two orders of magnitude faster than those in RAM, to recover the keys based on the execution time. Typically, it takes 3 to 4 cycles for a read operation in L1D caches, while an operation in RAM takes tens or hundreds of cycles [27].

Cache side-channel attacks on cryptographic engines are roughly divided into three categories: trace-driven, time-driven and access-driven attacks. The trace-driven attackers probe the variation of electromagnetic fields or power, to capture the profile of cache activities and deduce cache hits and misses [2]. In time-driven attacks, the adversary passively measures the execution time to disclose the secret keys. In these two categories of attacks, the cache states are changed by the victim cryptographic engine (and the system activities), while an access-driven attacker actively manipulates the cache states by running a malicious process that shares caches with the victim.

2.2.1. Time-driven side channel

Two typical remote cache timing side channel attacks on block cipher implementations are outlined as follows.

Bernstein’s attack. It statically analyzes the relation between the overall execution time and lookup table indexes [9]. The attacker firstly obtains the AES execution time for each possible value of $p_{i} \oplus k_{i}$ (where $p_{i}$ and $k_{i}$ are the ith byte of the plaintext and key, respectively) on a duplicated server whose hardware and software configurations are the same as the victim server. It finds the value of $p_{i} \oplus k_{i}$ corresponding to the maximal average AES execution time. Then for the ith byte of the unknown key (denoted as $k_{i}^{'}$ ) on the victim server, it collects a large number of encryption times for different known plaintexts, and obtains $p_{i}^{'}$ corresponding to the maximal average AES execution time. The maximal time shall result from the same index in the two phases, so the attacker infers $k_{i}^{'} = p_{i}^{'} \oplus (p_{i} \oplus k_{i})$ .

Internal collision attack. This attack exploits the fact that less time is needed for accessing the lookup table entries in the same cache line. Each 64-byte cache line has 16 4-byte entries, and in the first round of AES [14], the inputs of lookup table $T_{i}$ are $p_{i + 4 j} \oplus k_{i + 4 j}$ where $0 ⩽ i, j ⩽ 3$ . When any two inputs of $T_{i}$ access the lookup table entries in a same cache line (i.e., the high 4 bits of $p_{i + 4 j} \oplus k_{i + 4 j} \oplus p_{i + 4 j^{'}} \oplus k_{i + 4 j^{'}}$ is zero), it results in less execution time. The attacker measures the execution time for all possible $p_{i + 4 j} \oplus p_{i + 4 j^{'}}$ ( $0 ⩽ j, j^{'} ⩽ 3$ ). The least time at the value $p_{i + 4 j} \oplus p_{i + 4 j^{'}} = δ$ means that $k_{i + 4 j} \oplus k_{i + 4 j^{'}}$ has the same high 4 bits as δ. Thus, the information of key bytes is leaked. This attack is extended to the second and last rounds of AES [4] to fully extract the secret key. It also works for DES and 3DES [58].

2.2.2. Access-driven cache side channel

When the caches are shared by the attacker and the victim, the attacker could actively control the cache states and monitor the cache access by the victim process. Then, the keys are derived from the access patterns.

There are two categories of active cache side channels: synchronous and asynchronous [50]. In a synchronous attack, the attacker first sets the cache states, triggers the encryption, and monitors the memory access by detecting the change of cache states after the encryption. While in an asynchronous attack, the attacker sets the cache states and detects the changes by the victim process running concurrently. The synchronous attack monitors the cache state once per encryption, while the asynchronous one does it for several times per encryption with higher performance.

In synchronous Evict+Time attacks [50,57], the attacker sets the cache states as follows: triggering the encryption to load data into caches and explicitly evicting some from caches, which will be monitored. Then, the attacker triggers the encryption again, and records the time to infer whether the monitored addresses are accessed or not.

Prime+Probe [44,57] is launched in both scenarios. The attacker sets the cache states by filling one cache set with its own data, called Prime. Then, it accesses these data and measures the access time, to determine whether the monitored cache set is used by the encryption after the Prime phase, called Probe. Different cache sets are monitored one by one in synchronous attacks, or the access pattern of a cache set is detected in an asynchronous attack.

Flush+Reload [61] is another asynchronous threat that exploits shared memory. The attack process first flushes the shared memory data out of caches, and then measures the access time of some addresses in the shared memory to find whether they are accessed by the concurrent encryption or not (called Reload). Flush+Flush [32] and Prime+Abort [26] work in the asynchronous mode and exploit different methods to observe the cache access patterns. Flush+Flush is a variant of Flush+Reload, which monitors the cache state by flushing some addresses in the shared memory instead of reading them. Prime+Abort accesses the Prime data within Intel TSX, and then if some of them is accessed by the victim during the encryption, an abort occurs. So the attacker studies the cache access pattern through the abort events.

2.3. Defense against cache timing side channels

Countermeasures against the remote cache timing attacks have been proposed at different levels, and some of them also are effective against the active attacks.

Eliminating the difference of execution time. The straightforward method is to perform encryption without caches, by disabling caches [51], exploiting the no-fill cache mode [50,56] or loading lookup tables into registers [50]. But all of them result in very low performance. Bitsliced implementations [35,39,50] of AES without lookup tables, effectively defend against the cache timing attacks. However, they are specific to AES, and the performance is even lower.

AES-NI is a set of hardware instructions for AES, free of timing side channels. It is available only on Intel CPUs, and Intel provides the hardware support only for AES.

Loading lookup tables into caches before encryption [50,51,58], or using a compact table [34,50], eliminates cache misses remarkably, but not completely. There are still time differences exploitable to disclose the keys.

Confusing the cache access. Delay (or inserting padding instructions) after encryption, confuses the cache access leaked through the execution time. Random delay [50,51] or delay for the constant time of encryption [6,21,28,62], at the user-space or system level [20,22,64], were proposed. Instruction-based task scheduling [21,55,59] also confuses the cache access. These methods are algorithm-independent and effectively defend against the timing side-channel attacks, but result in a large performance overhead.

[51] suggests to access extra data arrays, while the permutation of lookup tables and caches is proposed in [13]. Rescheduling the instructions achieves the same goal, and is enforced at different levels [23,51]. The masking technique is used to the cache attack-resistant algorithm implementations [12,50]. The combination of blinding and delay is designed [40] to confuse the cache access against the cache timing side channels. These algorithm-dependent designs are not implementation-transparent, and also suffer from the performance problem to some extent.

Breaking the precision of timing confuses a local attacker’s observations [41,45,51], but it does not work against a remote attacker with its own timer.

Limiting the cache sharing. Cache partition prevents the interference of active cache side-channel attackers. Cache coloring partitions the caches at the operating system (OS) level [21]. STEALTHMEM [36] allows each VM to load the sensitive data into its own locked cache lines. Partition-locked caches are designed [38,60] to prevent the cache interference. Although they defend against the cache attacks, the usage of caches is significantly degraded and then such designs are rarely deployed on commodity systems.

CATalyst [43] and Cloak [25] employ CPU hardware features to limit the cache sharing. CATalyst [43] adopts Intel Cache Allocation Technology (CAT), a way-based cache-partitioning mechanism, to divide the caches into two partitions: non-secure one and secure one. The secure applications store sensitive data and codes in the secure cache partition which will never be evicted, against active cache side-channel attack. Cloak [25] uses hardware transactional memory (HTM) to provide non-shared caches for sensitive data and codes; that is, the sensitive codes and data are executed and accessed in HTM-backed transactions which will abort when attackers attempt to probe their cache access-patterns.

Integrated methods. Different methods are integrated to defend against the cache timing attacks. The scheme [16] integrates compact lookup tables, table permutation (or randomization), and cache line preloading, so that cache misses occur as little as possible while the relationship between the secret keys and the cache misses/hits is secret-independent. Dynamic instruction padding, isolated cache resources, and lazily-cleaned cache states are integrated against cache side-channel attacks [15]. These schemes are not implementation-transparent, or require special system privileges.

3. Eliminating remote cache timing side channels by integrating Warm and Delay

This section first introduces the threat model and the objectives. Then we describe the Warm+Delay scheme, and analyze its effectiveness. It provides a foundation for the analysis of performance optimization in next sections.

3.1. Threat model

We consider the remote cache timing side-channel attacks on block ciphers which are implemented with lookup tables. The cryptographic algorithms and their implementation details are publicly known, but the keys are kept secret, which are the attack targets. The table-based implementations are very efficient and widely adopted by popular cryptographic engines, e.g., AES in OpenSSL and mbed TLS[42], 3DES and Blowfish [54] in GPG and SSH. In such implementations, no branches exist, and no operation except the table lookup operation results in the cache-based execution time variation.

This threat model is adapted in most of the typical scenarios of remote cache timing side-channel attacks. The remote attackers know the software/hardware configurations of the target system, including the OS, the cache hierarchy, etc. However, the running states of the system are unknown to the attackers, due to non-deterministic interrupts, task scheduling and other system activities. The attackers are able to invoke the encryption function arbitrarily – they could continuously invoke the function so that all lookup table entries are cached, or stop using the function for a long time so that all entries are highly likely to be evicted from caches. They are able to measure the overall execution time for each execution of the block cipher.

In the following analysis in Section 3 and Section 4, we first assume that the execution time variation is only caused by the cache hits/misses of lookup table entries, by ignoring the variation caused by the system architecture issues. Then, in Section 5.1, we demonstrate the mitigations to prevent the attacks exploiting the tiny time variation caused by these issues (e.g., cache replacement policy and cache structure) [9,19].

The cache timing side-channels by active attackers are out of the scope of this paper. That is, the attackers cannot run privileged or unprivileged processes on the target system to modify or probe the cache state. The attackers do not have physical access to the hardware, either.

3.2. Objective

This work aims to provide an in-depth investigation of the performance of integrating Warm and Delay against the remote cache timing side-channel attacks for block ciphers. As the baseline, the defense shall satisfy the following conditions:

Algorithm-independent. It is generally applicable to block ciphers implemented with lookup tables (so that they are vulnerable to cache timing attacks).

Implementation-transparent. It does not require modification to the source code of the encryption functions.

Unprivileged. It requires no privileged operations. It works well in user space or kernel space, to protect the computations in user mode and kernel mode.

More importantly, the objectives of our research are elaborated as follows:

We attempt to develop the first quantitative model to formally analyze the performance of block cipher implementations that integrate Warm and Delay to defend against the cache timing side-channel attacks.

Follow the model, we examine the strategies of integrating Warm and Delay, and present the theoretical boundaries for the optimal performance while ensuring security.

In the optimal strategy, the parameters are configurable. By configuring appropriate parameters, the optimal performance is achieved for different block-cipher implementations and computing platforms.

3.3. The Warm+Delay scheme

There are two basic common countermeasures against remote cache timing side channels [9,19,34,50]: a) Warm, load the lookup tables into caches before encryption; and b) Delay, insert padding instructions after encryption. They work complementarily and each has its own advantages: Warm improves the performance, but cannot completely ensure security by itself because the effect may be broken by system activities; Delay completely eliminates the timing side channels, but significantly degrades the performance.

A naive integration scheme is to perform both Warm and Delay operation every time the protected encryption function is invoked. It introduces too many unnecessary extra operations and the performance is seriously degraded, although the security is ensured. In order to achieve the optimal performance, we perform Delay as the last line of defense, only when the effect of Warm is broken and the execution time may leak information on the secret key i.e., is not equal to the expected execution time with all table entries cached (detailed in Section 4.2); similarly, Warm is performed only when some entries are not in caches (detailed in Section 4.3). As the scheme does not involve privileged operations, the conditions of Warm and Delay are defined as regular timing.

When we consider that the cryptographic function is invoked continuously for large amounts of data, the time of each Warm may vary and this variation reflects the cache state after the previous encryption. We could evict all tables from caches before Warm to eliminate this variation, but it brings another extra overhead. Fortunately, we find that, the conditions to perform Warm and Delay are related. That is, when the execution time is greater than the expected time with all table entries cached (i.e., the execution time when no cache miss occurs), Delay is necessary to mitigate the risk and Warm is also necessary for the next encryption because some table entries are probably uncached. So, Warm is performed as a part of inserted instructions by Delay, if it is needed. This design further improves the performance, and the variation of Warm is also masked.

The Warm+Delay scheme is described in Algorithm 1. There are two parameters, $T_{n m}$ and $T_{m m}$ . $T_{n m}$ is the time period for one encryption operation, in the case that no cache misses occur during the execution, or all table entries are in caches. $T_{m m}$ is defined as the time period with the maximal number of cache misses, i.e., the worst execution time in the case that none of table entries is cached before the encryption. Given an implementation of block ciphers, $T_{n m}$ and $T_{m m}$ are fixed values on a specific computing platform.

Algorithm 1

The Warm+Delay scheme

In addition to Encrypt, three operations are introduced in this scheme: a) Warm, access lookup tables as constant data, b) Delay, insert padding instructions, and c) GetTime, return the current time as the conditions of Warm and Delay. These operations are algorithms-independent and implementation-transparent, except that the memory addresses of lookup tables are needed in Warm. All these operations are supported in commodity computer systems without special privileges, either in user mode or kernel mode. We do not query the status of any cache line to find whether a table entry is in caches or not, which are generally unavailable on common computing platforms.

In general, ProtectedEncrypt are invoked continuously to process large amounts of data, where the performance matters. Warm takes effect in the next execution of encryption. Therefore, if ProtectedEncrypt has been idle for a long time, we suggest an additional “initial” invocation of Warm before the loop of ProtectedEncrypt. Note that, even if this initial Warm is not performed, the security is still ensured by Delay afterward and the performance impact is negligible if the loop is long enough.

3.4. Security analysis

The timing side channels result from the relation between the measured execution time and the data processed; that is, different data processed (i.e., keys and plaintexts/ciphertexts) determines the lookup table access, resulting in different measured time as some table entries are in caches and others are not. We ensure that the measured time does not leak any exploitable information about the status of lookup tables in caches, and then destroy the relationship between the execution time and the data processed in encryption.

The execution time of Encrypt falls into three intervals, $(0, T_{n m}]$ , $(T_{n m}, T_{m m})$ and $[T_{m m}, + \infty)$ . We make the following treatments according to Algorithm 1:

Case 1: The execution time of Encrypt is in $(0, T_{n m}]$ . It means that this execution is done when all table entries are cached. No cache miss occurs and no information is leaked. Thus, Delay is not performed in this case.

Case 2: The execution time is in $(T_{n m}, T_{m m})$ . It will be delayed to $T_{m m}$ , the execution time as all accessed table entries are uncached before encryption.

Case 3: The execution time is in $[T_{m m}, + \infty)$ . It results from task scheduling, interrupts or other system activities. As explained in Section 3.1, the running states are random and unknown to the remote attackers, so the execution time is unexploitable. In this case, Delay is not performed, either.

When applying the Warm+Delay scheme, as shown in Algorithm 1, the remote attackers are (assumed to be) able to measure each execution time of ProtectedEncrypt, but not internal Encrypt. So the measured time, i.e., the execution time of ProtectedEncrypt, falls into two intervals, $(0, T_{n m}]$ and $[T_{m m}, + \infty)$ .

The values of $T_{n m}$ and $T_{m m}$ are irrelevant to the data processed, and determined by the implementation and computing platform. When the measured time is in $(0, T_{n m}]$ , it means that all lookup tables are in caches. When the time is greater than $T_{m m}$ , it is caused by random system activities and/or the Delay operations which destroy the relationship between the time and the data processed. Although the execution time of Warm may leak the cache states after the previous encryption, it is only a part of the measured time and masked by the system activities or Delay operations. So the cache timing side-channel attacks do not work under the integration scheme in Algorithm 1.

In the following, we further explain that the integration scheme successfully prevents typical remote cache timing side-channel attacks in the literature. For Bernstein’s attack [9], although the attacker obtains the maximal AES execution time for each $p_{i} \oplus k_{i}$ on the duplicated server, the measured time of the victim server reflects only system activities of the victim server. Because random and unknown system activities are involved in the measured AES execution time, the maximal time is not determined by the lookup table index; that is, it does not hold that $k_{i}^{'} \oplus p_{i}^{'} = p_{i} \oplus k_{i}$ .

To launch an internal collision attack [4,14], the attackers need to determine the least execution time for all possible $p_{i + 4 j} \oplus p_{i + 4 j^{'}}$ ( $0 ⩽ i, j, j^{'} ⩽ 3$ ) and exploit the high 4 bits of $p_{i + 4 j} \oplus p_{i + 4 j^{'}}$ to disclose the high 4 bits of $k_{i + 4 j} \oplus k_{i + 4 j^{'}}$ . When protected by the Warm+Delay scheme, the execution time measured by attackers is irrelative to the inputs of the lookup table and the time variation is caused by random and unknown system activities. So the least time does not mean an internal collision, that is, $p_{i} \oplus k_{i} = p_{j} \oplus k_{j}$ does not hold. Therefore, the attackers cannot extract useful information about the keys.

4. Towards the optimal performance of the Warm+Delay scheme

In this section, we apply the Warm+Delay scheme in Algorithm 1 to AES, which is applied to other block ciphers as described in Section 4.5. We first discuss the factors for the integration scheme to produce the optimized long-term performance. Then we present the conditions for the Delay operations to get the optimal performance. Meanwhile we use a statistical model to examine the Warm operations. Finally, we propose a strategy for the Warm+Delay scheme, and quantitatively prove that the optimal performance is achieved through our strategy. We list the major symbols of the analysis in Table 1.

Table 1
Symbols in the performance analysis

Symbol Description

$T_{n m}$ The encryption execution time when no cache miss occurs.

$T_{m m}$ The encryption execution time with the maximal number of cache misses.

$T_{c l}$ The time cost to load a cache line of data from RAM to L1D caches.

$B_{n l} (N)$ The benefit of not loading data into N cache lines in a Warm operation.

$D_{n l} (N)$ The expected overhead (or padding by Delay) due to not loading N cache lines in a Warm operation.

$P_{\bar{a}} (N)$ The probability that N certain cache lines are not accessed after R rounds of AES encryption.

$T_{d}$ The extra time cost introduced by D elay operation. $T_{d} = T_{m m} - T_{n m}$ .

$T_{w}$ The extra time cost introduced by W arm operation.

$S_{c}$ The state that all entries of the lookup table are in caches.

$S_{\bar{c}, a}$ The state that some entries are uncached, and at least one of them is accessed during encryption.

$S_{\bar{c}, \bar{a}}$ The state that some entries are uncached, but none of them is accessed during encryption.

$Π_{c}$ The probability that the system is in $S_{c}$ , in the stationary distribution.

$Π_{\bar{c}, \bar{a}}$ The probability that the system is in $S_{\bar{c}, \bar{a}}$ , in the stationary distribution.

$Π_{\bar{c}, a}$ The probability that the system is in $S_{\bar{c}, a}$ in the stationary distribution.

Symbol	Description
$T_{n m}$	The encryption execution time when no cache miss occurs.
$T_{m m}$	The encryption execution time with the maximal number of cache misses.
$T_{c l}$	The time cost to load a cache line of data from RAM to L1D caches.
$B_{n l} (N)$	The benefit of not loading data into N cache lines in a Warm operation.
$D_{n l} (N)$	The expected overhead (or padding by Delay) due to not loading N cache lines in a Warm operation.
$P_{\bar{a}} (N)$	The probability that N certain cache lines are not accessed after R rounds of AES encryption.
$T_{d}$	The extra time cost introduced by D elay operation. $T_{d} = T_{m m} - T_{n m}$ .
$T_{w}$	The extra time cost introduced by W arm operation.
$S_{c}$	The state that all entries of the lookup table are in caches.
$S_{\bar{c}, a}$	The state that some entries are uncached, and at least one of them is accessed during encryption.
$S_{\bar{c}, \bar{a}}$	The state that some entries are uncached, but none of them is accessed during encryption.
$Π_{c}$	The probability that the system is in $S_{c}$ , in the stationary distribution.
$Π_{\bar{c}, \bar{a}}$	The probability that the system is in $S_{\bar{c}, \bar{a}}$ , in the stationary distribution.
$Π_{\bar{c}, a}$	The probability that the system is in $S_{\bar{c}, a}$ in the stationary distribution.

4.1. Overview

In the Warm+Delay scheme, the extra operations are introduced by Warm, Delay and GetTime. Because the cost of GetTime is static and always necessary, the additional overhead is determined by Warm and Delay. Therefore, to achieve the optimal performance, we shall discuss the following questions:

Of Warm and Delay, which is the preferred operation?

What is the best strategy for the Delay operations that will produce the optimal performance in the long term? The strategy includes two aspects: (2.A) When shall Delay be imposed? and (2.B) What is the optimal delay to be imposed?

What is the best strategy for the Warm operations? It also includes two aspects: (3.A) When shall Warm be imposed? and (3.B) What is the optimal amount of lookup table entries to be accessed in Warm?

When attempting to answer these questions, we focus on the optimization of the long-term performance. That is, our objective is to optimize the overall performance of encrypting large amounts of data, instead of the performance of encrypting one block (i.e., short-term performance).

The first question is relatively easy to answer. The Warm operation, which loads lookup tables into caches, will speed up the following encryption. Meanwhile, the Delay operation, which inserts padding instructions to eliminate timing side channels, increases the overhead. Therefore, intuitively, the Warm operation is preferred over Delay.

In our analysis (as in other implementations), an instruction loop imposes Delay which accesses no memory, so the cache state is not changed by Delay. The Delay operation only changes the execution time of the current encryption, while it will not affect the following executions. So the answers to Question (2) are: (2.A) We should only impose Delay when it is required for security purposes (i.e., to impose the minimal number of Delay operations); and (2.B) The length of the imposed delay should be just enough to ensure security, but not more than that (i.e., to impose the minimal padding in each Delay operation).

Meanwhile, the Warm operation not only changes the execution time of the current encryption, but also has a lasting effect on the next one(s). Intuitively, loading less data during one Warm operation introduces a smaller overhead for the current encryption; however, it may result in more Delay and Warm operations in the future. In this case, optimized short-term performance may cause worse long-term performance, which is not desirable. Therefore, to answer Question (3), we need to build a quantitative model for the impacts of a partial/full Warm on future encryption. And it is the main challenge of this work.

In the next, we first examine the optimal conditions for Delay. We prove that, it provides the optimal performance while ensuring security if delaying to $T_{m m}$ in Delay and performing Delay only when the encryption time is in $(T_{n m}, T_{m m})$ . Then we investigate the Warm operation for AES-128 with 2 KB lookup tables [48]. We prove that it is statistically the most efficient to load all lookup table entries in Warm and perform it if a cache miss occurs during the previous encryption. Finally, we extend the conclusions to different key lengths of AES and different implementations, and show that, the conlusions are applicable to these typical key lengths and implementations. That is, the derived Warm+Delay scheme achieves the optimal performance for various AES implementations with lookup tables.

4.2. The optimal conditions for Delay

Theorem 1.
To effectively eliminate the cache timing side channels, in the Delay operation delaying to $T_{m m}$ imposes the minimal delay.
Proof.
From the attacker’s perspective, $T_{n m}$ , $T_{m m}$ and any value greater than $T_{m m}$ are three types of measured time that are unexploitable; i.e., the measured time does not reflect the cache misses/hits of certain lookup table entries.

If we delay the execution time to any value greater than $T_{m m}$ , though the security is guaranteed, the overhead is greater than that delays to $T_{m m}$ . On the other hand, if we delay the time to any value less than $T_{m m}$ , a little information about the cache access leaks. Meanwhile, if we delay it to a random/pseudorandom value, which may be greater or less than $T_{m m}$ , the attackers could exclude all results greater than $T_{m m}$ and the other results are still exploitable. Such methods reduce the attack accuracy, but do not eliminate the timing side channels completely. Therefore, delaying to $T_{m m}$ imposes the minimal overhead while effectively eliminates the cache timing side channels. □
Theorem 2.
Performing the Delay operation if and only if the execution time of encryption is in $(T_{n m}, T_{m m})$ , results in the least number of Delay operations.
Proof.
As described above, if the encryption execution time is equal to or less than $T_{n m}$ , no cache miss occurs, and if the time is equal to $T_{m m}$ or greater, it is unexploitable. In these cases, the execution time is independent of keys and plaintexts/ciphertexts, so Delay is unnecessary.

When the execution time is in $(T_{n m}, T_{m m})$ , it may result from cache misses due to the access of the uncached table entries or system activities (but the overhead is less than $T_{m m} - T_{n m}$ ). We cannot distinguish the exact reasons without special privileges. However, the attackers may eliminate the effect of system activities by repeatedly invoking the encryption function using the same input. Therefore, Delay is necessary in this case. □

It is easy to verify that, the Delay operation in the scheme in Algorithm 1 satisfies Theorems 1 and 2.
4.3. The optimal conditions for Warm

We apply the Warm+Delay scheme to AES-128 with a 2 KB lookup table [48], as described in Section 2.1. We first determine the amount of data to be loaded in Warm for the optimal performance. Then, in order to explore the best conditions of performing the Warm operation, we use Markov Chain to model different Warm strategies and compare their performance. We show that, the best conditions of performing the Warm operation (i.e. with the optimal performance) hold in commodity computer systems.

4.3.1. The amount of data loaded in Warm

A Warm operation loads the lookup tables into caches. It takes less time if only a part of the table is loaded, but it may introduce extra Delay operations if the unloaded entries are accessed. The benefit of not loading N cache lines of data in the Warm operation is denoted as $B_{n l} (N)$ , while the expected overhead due to not loading N cache lines is denoted as $D_{n l} (N)$ . So the amount of data to be loaded in Warm is determined by comparing $B_{n l} (N)$ with $D_{n l} (N)$ .

We denote the size of a cache line as C, and the time cost to load a cache line of data from RAM to L1D caches as $T_{c l}$ . We have the following theorem for an AES implementation of R rounds with an L-byte lookup table ( $L ≫ C$ ).

Theorem 3.
If $B_{n l} (N) < D_{n l} (N)$ for any $0 < N ⩽ \frac{L}{C}$ , loading all entries of the lookup table into caches in the Warm operation provides better performance than loading any part of entries, where $B_{n l} (N) = N T_{c l}$ and $D_{n l} (N) = (1 - {(1 - \frac{N C}{L})}^{16 R}) (T_{m m} - T_{n m})$ .
Proof.
Not loading N cache lines of table entries saves the execution time of Warm, while the potential cost is the longer execution of encryption and the extra execution of Delay. Since $L ≫ C$ , we needs $\frac{L}{C}$ cache lines to hold the lookup table. In each round of AES encryption, the lookup table is accessed for 16 times. We assume that, in each round, the input of SubBytes is random and then each table entry is accessed uniformly. Hence, the probability that N certain cache lines are not accessed after R rounds of AES encryption, denoted as $P_{\bar{a}} (N)$ , is $P_{\bar{a}} (N) = {(1 - \frac{N C}{L})}^{16 R}$ .

If a table entry is uncached but accessed during encryption, the execution time is greater than $T_{n m}$ and Delay is performed. Therefore, if N cache lines of table entries are not in caches, the probability of extra Delay is: $\begin{matrix} (1) & P_{d} (N) = 1 - P_{\bar{a}} (N) = 1 - {(1 - \frac{N C}{L})}^{16 R} \end{matrix}$

Table 2
Benefit and expected cost of not loading N cache lines of table entries (in CPU cycles)

N 1 2 3 5 10 15 20 25 30 31 32

$B_{n l} (N)$ 54.55 109.10 163.65 272.75 545.50 818.25 1091.00 1386.25 1636.50 1691.05 1745.60

$D_{n l} (N)$ 2463.58 2478.92 2478.99 2479.00 2479.00 2479.00 2479.00 2479.00 2479.00 2479.00 2479.00

The execution time shall be delayed to $T_{m m}$ according to Theorem 1, while it is $T_{n m}$ if all entries are in caches. So, $\begin{array}{rcl} (2) & D_{n l} (N) = (1 - {(1 - \frac{N C}{L})}^{16 R}) (T_{m m} - T_{n m}) \end{array}$

The time cost to load a cache line of data is $T_{c l}$ , so $B_{n l} (N) = N T_{c l}$ . Therefore, we conclude that (a) if $B_{n l} (N) < D_{n l} (N)$ for any $\frac{L}{C} ⩾ N > 0$ , loading all entries of the lookup table into caches in the Warm operation provides better performance; and (b) if there exists N satisfying that $B_{n l} (N) > D_{n l} (N)$ , not loading N cache lines of table entries does better. □
Example 1.
For the AES-128 implementation with a 2 KB lookup table, loading all entries of the lookup table into caches in the Warm operation provides better performance than loading any part of entries.

We finished the experiments on a Lenovo ThinkCentre M8400t PC with an Intel Core i7-2600 CPU and 2 GB RAM. $T_{m m}$ , $T_{n m}$ , and $T_{c l}$ are 2834.00, 355.00, and 54.55 CPU cycles, respectively (see Section 5.1 for details). Table 2 shows $B_{n l} (N)$ and $D_{n l} (N)$ , when $R = 10$ , $L = 2$ KB, and $C = 64$ B. The cost of not loading N ( $32 ⩾ N > 0$ ) cache lines of the lookup table is always much greater than the benefit. Thus, according to Theorem 3, loading all entries in Warm produces better performance.

On commodity systems, the cache is enough for all entries of the lookup tables. For example, AES is implemented with the lookup tables of 2 KB, 4 KB, 4.25 KB or 5 KB, and the lookup tables of DES/3DES are 2 KB. Meanwhile, the typical L1D cache is 32 KB or 64 KB for Intel CPUs, and 16 KB or 32 KB for ARM CPUs.

Moreover, in our Warm+Delay scheme, Warm is performed as a part of the Delay operation, as shown in Algorithm 1. So the cost of Warm is further reduced, ensuring that loading all entries of the lookup table in Warm is better.
4.3.2. State transitions of different Warm strategies

N	1	2	3	5	10	15	20	25	30	31	32
$B_{n l} (N)$	54.55	109.10	163.65	272.75	545.50	818.25	1091.00	1386.25	1636.50	1691.05	1745.60
$D_{n l} (N)$	2463.58	2478.92	2478.99	2479.00	2479.00	2479.00	2479.00	2479.00	2479.00	2479.00	2479.00

We use Markov Chain to analyze the states of the lookup table in caches during the continuous invocations of AES encryption. Then the extra costs are calculated based on the probability of each state in the stationary distributions, to determine the optimal Warm strategy. There are three states after one AES execution (i.e. Encrypt in Algorithm 1):

$S_{c}$ : all entries of the lookup table are in caches;

$S_{\bar{c}, a}$ : some entries are uncached, and at least one of them is accessed during the AES encryption;

$S_{\bar{c}, \bar{a}}$ : some entries are uncached, but none of them is accessed during the AES encryption.

S_{\bar{c}, a}

and

S_{\bar{c}, \bar{a}}

represent the states where one or more cache lines of table entries are uncached or evicted from caches.

The state is estimated after each execution of AES encryption. The transition among three states is triggered by three events:

Warm: Performing Warm to load all table entries into caches, and the probability is $P_{w}$ .

Eviction: Some table entries may be evicted from caches when task scheduling, interrupts or other system activities occur during the execution. The probability that such an event occurs is denoted as $P_{e}$ .

Access-Uncached: For one AES execution, some entries are uncached before encryption and some of them are accessed during encryption, and the probability is denoted as $P_{a}$ . Actually, $P_{a}$ is the same as $P_{d}$ in Theorem 3; i.e., Access-Uncached results in Delay.

Without loss of generality, we assume that during one state transition, each of the events occurs once at most.3

³
Even if some occurs more than once actually, they can be viewed as one event with the strengthened impact on the state transition.

We assume that, during one state transition, Warm occurs before Eviction if both of them occur. It is reasonable, because an Eviction event occurring before Warm has no effect on the state of the lookup table, and then can be ignored. Since the state is observed immediately after the AES execution, Access-Uncached occurs in the last during one state transition (if occurs). In the following analysis, we firstly ignore the partial-warm effect of Access-Uncached in the analysis of the different strategies, and in Section 4.3.4 we show that this effect does not influence our conclusions.

We consider three strategies:

Conditional Warm: performing Warm when some cache misses occur during the previous encryption execution, as done in the Warm+Delay scheme;

Less Warm: performing Warm with a probability $P_{w}^{⊖} \in [0, 1)$ when cache misses occur during the previous encryption execution;

More Warm: performing Warm when some cache misses occur during the previous encryption execution, and also performing with a probability $P_{w}^{\oplus} \in (0, 1]$ in other conditions.

Markov Chain is used to simulate the state transition. The state of the lookup table denoted as $X_{n}$ , takes values in the state space ${S_{c}, S_{\bar{c}, a}, S_{\bar{c}, \bar{a}}}$ . If it is in the state i, the probability that it will be in the state j after one step is denoted as $P_{j | i} = P {X_{n + 1} = j | X_{n} = i}$ , where $i, j \in {S_{c}, S_{\bar{c}, a}, S_{\bar{c}, \bar{a}}}$ . Also, $P_{a | i}$ and $P_{e | i}$ represent the probabilities that Access-Uncached and Eviction occur in the state i, respectively, where $i \in {S_{c}, S_{\bar{c}, a}, S_{\bar{c}, \bar{a}}}$ . Besides, we use ⊖ and ⊕ to distinguish the symbols of less and more Warm as the superscripts, respectively.

Next, the stationary distributions for the three different strategies are analyzed as follow.

Fig. 1.

The Markov state transition probability diagram.

Conditional Warm. The state transition of conditional Warm is shown in Figure 1a. In the state $S_{c}$ , Warm is not performed. If Eviction does not occur, Access-Uncached does not occur and the state remains, i.e., $P_{S_{c} | S_{c}} = 1 - P_{e | S_{c}}$ . When Eviction occurs, some table entries are evicted from caches. Then if these evicted entries are accessed during the AES execution, it turns to $S_{\bar{c}, a}$ and $P_{S_{\bar{c}, a} | S_{c}} = P_{e | S_{c}} P_{a | S_{c}}$ ; otherwise, it turns to $S_{\bar{c}, \bar{a}}$ and $P_{S_{\bar{c}, \bar{a}} | S_{c}} = P_{e | S_{c}} (1 - P_{a | S_{c}})$ .

In the state $S_{\bar{c}, a}$ , Warm is performed to load all entries into caches, and then the state transition is similar to that in $S_{c}$ . If Eviction does not occur, it turns to $S_{c}$ and $P_{S_{c} | S_{\bar{c}, a}} = 1 - P_{e | S_{c}}$ . When Eviction occurs, and if the evicted entries are accessed during encryption, the state remains the same and $P_{S_{\bar{c}, a} | S_{\bar{c}, a}} = P_{e | S_{c}} P_{a | S_{c}}$ ; otherwise, it turns to $S_{\bar{c}, \bar{a}}$ and $P_{S_{\bar{c}, \bar{a}} | S_{\bar{c}, a}} = P_{e | S_{c}} (1 - P_{a | S_{c}})$ .

In the state $S_{\bar{c}, \bar{a}}$ , Warm is not performed because cache misses do not occur. Whether Eviction occurs or not, some table entries are not in caches. If these uncached entries are accessed during encryption, it turns to $S_{\bar{c}, a}$ : (a) if Eviction occurs also, the probability is $P_{e | S_{\bar{c}, \bar{a}}} P_{a | S_{\bar{c}, \bar{a}}}$ ; and (b) if not, the probability is $(1 - P_{e | S_{\bar{c}, \bar{a}}}) P_{a | S_{c}}$ . Thus, $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} = P_{e | S_{\bar{c}, \bar{a}}} P_{a | S_{\bar{c}, \bar{a}}} + (1 - P_{e | S_{\bar{c}, \bar{a}}}) P_{a | S_{c}}$ . If the uncached entries are not accessed, the state remains and $P_{S_{\bar{c}, \bar{a}} | S_{\bar{c}, \bar{a}}} = 1 - P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}$ .

We use $Π_{c}$ , $Π_{\bar{c}, \bar{a}}$ , $Π_{\bar{c}, a}$ to represent the stationary distribution of three states and the following equations hold: $\begin{matrix} (3) & \{\begin{matrix} Π_{c} = \frac{P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} (1 - P_{e | S_{c}})}{P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} + P_{e | S_{c}} (1 - P_{a | S_{c}})} \\ Π_{\bar{c}, \bar{a}} = \frac{P_{e | S_{c}} (1 - P_{a | S_{c}})}{P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} + P_{e | S_{c}} (1 - P_{a | S_{c}})} \\ Π_{\bar{c}, a} = \frac{P_{e | S_{c}} P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}}{P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} + P_{e | S_{c}} (1 - P_{a | S_{c}})} \end{matrix} \end{matrix}$

Less Warm. The state transition of less Warm is in Figure 1b. In the state $S_{c}$ , Warm is not performed. So the transition probability is the same as that in conditional Warm.

In the state $S_{\bar{c}, a}$ , Warm is performed with the probability $P_{w}^{⊖}$ . The state turns to $S_{c}$ if Warm is performed and Eviction does not occur, so $P_{S_{c} | S_{\bar{c}, a}}^{⊖} = P_{w}^{⊖} P_{S_{c} | S_{\bar{c}, a}} = P_{w}^{⊖} (1 - P_{e | S_{c}})$ . The state remains if the uncached entries are accessed during the AES execution, whether Warm is performed or not. Thus, $P_{S_{\bar{c}, a} | S_{\bar{c}, a}}^{⊖} = (1 - P_{w}^{⊖}) P_{S_{\bar{c}, a} | S_{\bar{c}, a}^{\bar{w}}}^{⊖} + P_{w}^{⊖} P_{e | S_{c}} P_{a | S_{c}}$ , where $P_{S_{\bar{c}, a} | S_{\bar{c}, a}^{\bar{w}}}^{⊖} = P_{e | S_{\bar{c}, a}}^{⊖} P_{a | S_{\bar{c}, a}}^{⊖} + (1 - P_{e | S_{\bar{c}, a}}^{⊖}) P_{a | S_{c}}$ is the probability of the state transition from $S_{\bar{c}, a}$ to $S_{\bar{c}, a}$ when Warm is not performed. The state turns to $S_{\bar{c}, \bar{a}}$ if the uncached entries are not accessed, and the probability is $P_{S_{\bar{c}, \bar{a}} | S_{\bar{c}, a}}^{⊖} = (1 - P_{w}^{⊖}) (1 - P_{S_{\bar{c}, a} | S_{\bar{c}, a}^{\bar{w}}}^{⊖}) + P_{w}^{⊖} P_{e | S_{c}} (1 - P_{a | S_{c}})$ .

In the state $S_{\bar{c}, \bar{a}}$ , Warm is not performed. Whether Eviction occurs or not, some entries are not in caches. So if these uncached entries are accessed during the AES execution, it turns to $S_{\bar{c}, a}$ , and the transition probability is $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}^{⊖} = P_{e | S_{\bar{c}, \bar{a}}}^{⊖} P_{a | S_{\bar{c}, \bar{a}}}^{⊖} + (1 - P_{e | S_{\bar{c}, \bar{a}}}^{⊖}) P_{a | S_{c}}$ . Otherwise, the state remains and $P_{S_{\bar{c}, \bar{a}} | S_{\bar{c}, \bar{a}}}^{⊖} = 1 - P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}^{⊖}$ .

The stationary distribution of three states satisfies with the following equations: $\begin{matrix} (4) & \{\begin{matrix} Π_{c}^{⊖} = \frac{(1 - P_{e | S_{c}}) P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}^{⊖} P_{w}^{⊖}}{D_{L}} \\ Π_{\bar{c}, \bar{a}}^{⊖} = \frac{P_{e | S_{c}} (1 - P_{S_{\bar{c}, a} | S_{\bar{c}, a}^{\bar{w}}}^{⊖})}{D_{L}} + \frac{P_{e | S_{c}} (P_{S_{\bar{c}, a} | S_{\bar{c}, a}^{\bar{w}}}^{⊖} - P_{a | S_{c}}) P_{w}^{⊖}}{D_{L}} \\ Π_{\bar{c}, a}^{⊖} = \frac{P_{e | S_{c}} P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}^{⊖}}{D_{L}} \end{matrix} \end{matrix}$ where $\begin{array}{l} D_{L} & = P_{e | S_{c}} (1 + P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}^{⊖} - P_{S_{\bar{c}, a} | S_{\bar{c}, a}^{\bar{w}}}^{⊖}) + (1 - P_{e | S_{c}}) P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}^{⊖} P_{w}^{⊖} + (P_{S_{\bar{c}, a} | S_{\bar{c}, a}^{\bar{w}}}^{⊖} - P_{a | S_{c}}) P_{e | S_{c}} P_{w}^{⊖} . \end{array}$

More Warm. The state transition diagram of more Warm is shown in Figure 1c. In the state $S_{c}$ , Warm is performed with the probability $P_{w}^{\oplus}$ but has no effect. In the state $S_{\bar{c}, a}$ , Warm is performed to load all table entries into caches. The two situations are the same with the states of conditional Warm and also the transition probabilities.

In the state $S_{\bar{c}, \bar{a}}$ , Warm is performed with the probability $P_{w}^{\oplus}$ . If Warm is performed, all entries are in caches and the state transition is the same as in the state $S_{c}$ . The state turns to $S_{c}$ with the probability $P_{S_{c} | S_{\bar{c}, \bar{a}}}^{\oplus} = P_{w}^{\oplus} P_{S_{c} | S_{c}} = P_{w}^{\oplus} (1 - P_{e | S_{c}})$ . If Warm is not performed, whether Eviction occurs or not, some entries are not in caches. So if these uncached entries are accessed during encryption, it turns to $S_{\bar{c}, a}$ , and $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}^{\oplus} = P_{w}^{\oplus} P_{e | S_{c}} P_{a | S_{c}} + (1 - P_{w}^{\oplus}) P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}^{\bar{w}}}^{\oplus}$ , where $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}^{\bar{w}}}^{\oplus}$ is the probability of the state transition from $S_{\bar{c}, \bar{a}}$ to $S_{\bar{c}, a}$ when Warm is not performed. Otherwise, the state remains and $P_{S_{\bar{c}, \bar{a}} | S_{\bar{c}, \bar{a}}}^{\oplus} = P_{w}^{\oplus} P_{e | S_{c}} (1 - P_{a | S_{c}}) + (1 - P_{w}^{\oplus}) (1 - P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}^{\bar{w}}}^{\oplus})$ .

The stationary distribution of three states satisfies with the following equations: $\begin{matrix} (5) & \{\begin{matrix} Π_{c}^{\oplus} = \frac{(1 - P_{e | S_{c}}) (P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}^{\bar{w}}}^{\oplus} (1 - P_{w}^{\oplus}) + P_{w}^{\oplus})}{D_{M}} \\ Π_{\bar{c}, \bar{a}}^{\oplus} = \frac{P_{e | S_{c}} (1 - P_{a | S_{c}})}{D_{M}} \\ Π_{\bar{c}, a}^{\oplus} = \frac{P_{e | S_{c}} P_{a | S_{c}} P_{w}^{\oplus}}{D_{M}} + \frac{P_{e | S_{c}} P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}^{\bar{w}}}^{\oplus} (1 - P_{w}^{\oplus})}{D_{M}} \end{matrix} \end{matrix}$ where $\begin{array}{l} D_{M} & = P_{e | S_{c}} + P_{w}^{\oplus} + P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}^{\bar{w}}}^{\oplus} (1 - P_{w}^{\oplus}) - P_{e | S_{c}} (P_{w}^{\oplus} + P_{a | S_{c}} - P_{a | S_{c}} P_{w}^{\oplus}) . \end{array}$

4.3.3. The best strategy to perform Warm operation

We compare the performance of conditional Warm with the less Warm and more Warm strategies. Then, we investigate the relationship between conditional Warm and an arbitrary strategy. Finally, we estimate whether the conditions for conditional Warm to achieve the optimal performance are satisfied in commodity systems.

We denote the extra time cost introduced by Delay and Warm as $T_{d}$ and $T_{w}$ , respectively. $T_{d} = T_{m m} - T_{n m}$ is constant, while $T_{w}$ varies because the number of loaded cache lines changes if different Warm strategies are adopted.

Theorem 4.
The conditional Warm strategy provides better performance than the less Warm strategy.
Proof.
The expected extra time costs introduced by less Warm and conditional Warm are denoted as $E (T^{⊖})$ and $E (T)$ , respectively. Delay is needed in $S_{\bar{c}, a}$ , so the extra time introduced by Warm is masked in the Delay operation. In $S_{c}$ and $S_{\bar{c}, \bar{a}}$ , Warm and Delay are not needed for these two strategies. The difference between the extra time introduced by less Warm and conditional Warm is: $\begin{matrix} (6) & E (T^{⊖}) - E (T) = Π_{\bar{c}, a}^{⊖} T_{d} - Π_{\bar{c}, a} T_{d} \end{matrix}$

We find that $E (T^{⊖}) - E (T) > 0$ for any $P_{w}^{⊖} \in (0, 1)$ , and the detailed calculation is in Appendix A.1. So the extra time introduced by less Warm is always greater than conditional Warm, and conditional Warm is better. □

Next, we compare conditional Warm with more Warm. We use $T_{w}^{min}$ to denote the minimum of $T_{w}$ as the number of cached table entries varies, which is the time of Warm when all table entries have been in caches before Warm. The following symbols are defined: $G = T_{d} / T_{w}$ , $M = T_{w}^{min} / T_{d}$ , $\begin{array}{l} D_{F} = P_{e | S_{c}} (P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} - P_{e | S_{c}} P_{a | S_{c}}) (P_{a | S_{c}} - 1) + M (1 - P_{e | S_{c}}) P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} (P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} + P_{e | S_{c}} (1 - P_{a | S_{c}})), \\ F_{G} = \frac{P_{e | S_{c}} (P_{a | S_{c}} - 1) (P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} + P_{e | S_{c}} (1 - P_{a | S_{c}}))}{D_{F}}, \end{array}$ and $F_{G}^{min}$ is the minimal value of $F_{G}$ as $P_{e | S_{c}}$ , $P_{a | S_{c}}$ and $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}$ vary. Theorem 5.
The conditional Warm strategy provides better performance than more Warm , if the following condition holds: (1) $D_{F} ⩾ 0$ , or (2) $D_{F} < 0$ and $G < F_{G}^{min}$ .
Proof.
We compare $E (T)$ and $E (T^{\oplus})$ as in Theorem 4, where $E (T^{\oplus})$ is the expected extra time costs of more Warm. Delay is needed in $S_{\bar{c}, a}$ , so the extra time introduced by Warm is masked in Delay for these two strategies. In $S_{c}$ and $S_{\bar{c}, \bar{a}}$ , Warm and Delay are not needed for conditional Warm, but for the more Warm strategy, Warm is performed with $P_{w}^{\oplus}$ . The extra time is $T_{w}^{min}$ in $S_{c}$ as all table entries are cached, and is $T_{w}$ in $S_{\bar{c}, \bar{a}}$ . Thus, $\begin{array}{l} (7) & E (T^{\oplus}) - E (T) = Π_{\bar{c}, a}^{\oplus} T_{d} + Π_{c}^{\oplus} P_{w}^{\oplus} T_{w}^{min} + Π_{\bar{c}, \bar{a}}^{\oplus} P_{w}^{\oplus} T_{w} - Π_{\bar{c}, a} T_{d} \end{array}$

It is drawn that, $E (T^{\oplus}) ⩾ E (T)$ , if (1) $D_{F} ⩾ 0$ , or (2) $D_{F} < 0$ and $G < F_{G}^{min}$ . The details are in Appendix A.2. □
Theorem 6.
Conditional Warm that performs Warm if some cache miss occurs during the previous encryption, results in the least extra time cost of Warm and Delay , if the following condition holds: (1) $D_{F} ⩾ 0$ , or (2) $D_{F} < 0$ and $G < F_{G}^{min}$ .
Proof.
Firstly, consider an unusual strategy that performs Warm with a probability $P_{w}^{⊙} \in [0, 1]$ only if cache misses do not occur during the previous encryption, while not Warm if any cache miss occurs. It is called unusual Warm, and the state transition is shown in Figure 1d. It is proved that the conditional Warm strategy produces better performance than unusual Warm, following the same steps in Theorem 4.

Any Warm strategy W is generally described with $P_{1}$ and $P_{2}$ : performs Warm with a probability $P_{1} \in [0, 1]$ when a cache miss occurs during the previous encryption, and with a probability $P_{2} \in [0, 1]$ in other states. Therefore, W is viewed as a combination of less Warm with a percentage $x_{1}$ , more Warm with $x_{2}$ and unusual Warm with $x_{3}$ , where: $\begin{matrix} (8) & \{\begin{matrix} x_{1} + x_{2} + x_{3} = 1 \\ x_{2} P_{w}^{\oplus} + x_{3} P_{w}^{⊙} = P_{2} \\ x_{1} P_{w}^{⊖} + x_{2} = P_{1} . \end{matrix} \end{matrix}$

It has been proved that conditional Warm always produces better performance than less Warm and unusual Warm. So conditional Warm performs better than any warm strategy, if it does better than more Warm, i.e., (1) $D_{F} ⩾ 0$ , or (2) $D_{F} < 0$ and $G < F_{G}^{min}$ . □
Example 2.
For the AES-128 implementation with a 2 KB lookup table, performing Warm when cache misses occur during the previous encryption, results in the least extra time cost of Delay and Warm.

First of all, $P_{a | S_{c}}$ is greater than 0.994 based on Equation (1), and the range of $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}$ is $[0.994, 1]$ . We measured $T_{d}$ and $T_{w}$ in the Lenovo ThinkCentre M8400t PC. $T_{d}$ is 2479.00 CPU cycles, $T_{w}^{min}$ is 88.00 cycles when accessing the lookup tables in the L1D cache, and the maximum of $T_{w}$ is 1745.60 CPU cycles when all the lookup entries are not cached. Thus, $M = 0.0355$ and the rang of G is $[1.42, 28.17]$ .

On this platform, the range of $D_{F}$ is $[- 0.000036, 0.0355]$ . When $D_{F} ⩾ 0$ , conditional Warm is the best according to Theorem 6. When $D_{F} < 0$ , $F_{G}$ is a monotone increasing function of $P_{a | S_{c}}$ , so $F_{G}$ reaches the minimum when $P_{a | S_{c}} = 0.994$ . At this point, $P_{e | S_{c}}$ and $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}$ satisfy: $\begin{matrix} (9) & \{\begin{matrix} P_{e | S_{c}} = \frac{0.994 M (1 - P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}}) + \sqrt{Δ}}{0.006 (1 - 0.006 M)} \\ P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} = \frac{0.07746 P_{e | S_{c}}}{\sqrt{M (1 - P_{e | S_{c}})}} - 0.006 P_{e | S_{c}} \\ If P_{e | S_{c}} ⩾ 1, P_{e | S_{c}} = 1 and P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} = 1 \\ If P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} ⩾ 1, P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} = 1, \end{matrix} \end{matrix}$ where $\begin{array}{l} Δ = 0.988 M^{2} - 1.976 M^{2} P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} + (0.006 M + 0.988 M^{2}) {(P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}})}^{2} . \end{array}$

We find that when $P_{e | S_{c}} = 1$ , $P_{S_{\bar{c}, a} | S_{\bar{c}, \bar{a}}} = 1$ and $P_{a | S_{c}} = 0.994$ , $F_{G}$ reaches the minimum and $F_{G}^{min}$ is 167.67. So G is much less than $F_{G}^{min}$ when $D_{F} < 0$ .

Finally, according to Theorem 6, performing Warm when cache misses occur during the previous encryption, results in the least extra time of Delay and Warm.

4.3.4. Remarks

In the above analysis, we ignore some effects on caches by encryption execution, task scheduling and interrupts, and these effects are discussed as below. We also summarize the relation between the measured time and the cache states.

One encryption execution is a partial Warm operation. When the system is in the state $S_{\bar{c}, a}$ , one encryption execution is a partial warm operation because table entries are accessed during the encryption and cache misses will load the corresponding entries into caches.

Therefore, when the system is in $S_{\bar{c}, a}$ , conditional Warm performs Warm with probability 1, while a general strategy actually performs Warm with a probability $P_{1}^{'}$ greater than $P_{1}$ in Theorem 6, due to the partial warm by the encryption execution. Although $P_{1}^{'}$ is different from $P_{1}$ , the condition that leads to $E (T^{\oplus}) > E (T)$ does not change. So conditional Warm still produces better performance.

If task scheduling or interrupts occur during the encryption, Warm is performed always. In this case, the time of Encrypt is greater than $T_{m m}$ (i.e., $t 2 - t 1 > T_{m m}$ ), Warm will be triggered in the conditional Warm strategy. When task scheduling or interrupts occur, we assume that N cache lines of the lookup table are evicted from caches. Hence, the extra overhead of Warm to load the lookup table is $W_{n l} (N) = N T_{c l} + (32 - N) T_{\bar{c l}}$ , where $T_{\bar{c l}}$ and $T_{c l}$ denote the time for accessing one cache line from caches and RAM, respectively. If we do not perform Warm, the next AES may need to access some part(s) of the lookup table from RAM instead of caches, which will trigger Delay. The expected overhead is $D_{n l} (N)$ (see Equation (2)).

Table 3 shows the results on the Lenovo ThinkCentre M8400t PC, and performing Warm achieves better performance when $N > 0$ . If $N = 0$ (i.e., no table entry is evicted from caches), Warm is not needed while $t 2 - t 1 > T_{m m}$ . However, we cannot find whether the table entry is evicted or not, unless more privileged operations are supported. So we have to perform Warm and it introduces a little extra overhead (i.e., access each cache line of data that are in caches) in this special case.

Table 3
The introduced time by performing warmup operation or not (in CPU cycles)

N 1 2 3 5 10 15 20 25 30 31 32

$D_{n l} (N)$ 2463.58 2478.92 2478.99 2479.00 2479.00 2479.00 2479.00 2479.00 2479.00 2479.00 2479.00

$W_{n l} (N)$ 139.80 191.60 243.40 347.00 606.00 865.00 1124.00 1383.00 1642.00 1693.80 1745.60

N	1	2	3	5	10	15	20	25	30	31	32
$D_{n l} (N)$	2463.58	2478.92	2478.99	2479.00	2479.00	2479.00	2479.00	2479.00	2479.00	2479.00	2479.00
$W_{n l} (N)$	139.80	191.60	243.40	347.00	606.00	865.00	1124.00	1383.00	1642.00	1693.80	1745.60

If task scheduling is triggered but the encryption execution is not suspended and resumed immediately, Warm is still performed. Because the task is not switched, the time cost of scheduling is less than $T_{d}$ . That is, $T_{n m} < t 2 - t 1 ⩽ T_{m m}$ . In this case, Warm is unnecessary for no other task is executed and the lookup table is not evicted. However, Warm is still a better choice, as we cannot find whether a table entry is in caches or not, and the introduced overhead is concealed by Delay.

The execution time does not exactly reflect the cache state. In the above, we prove that, Warm when not all lookup entries are in caches, results the least extra time. However, in the Warm+Delay scheme, Warm is performed according to the previous execution time, as it is technically unable to observe the cache states. The relationship between the cache state and execution time is as follows:

$t 2 - t 1 ⩽ T_{n m}$ , the system is in $S_{c}$ or $S_{\bar{c}, \bar{a}}$ , no Warm is needed according to Theorem 6.

$t 2 - t 1 > T_{m m}$ , it is in $S_{c}$ , $S_{\bar{c}, a}$ or $S_{\bar{c}, \bar{a}}$ , Warm is needed according to Theorem 3.

$T_{n m} < t 2 - t 1 ⩽ T_{m m}$ , it is in $S_{c}$ or $S_{\bar{c}, a}$ , Warm is better according to the previous analysis.

Therefore, performing Warm according to the previous execution time is reasonable to obtain the best performance.

4.4. Different key lengths and implementations

For other key lengths with different numbers of rounds and implementations with different sizes of tables, Theorems 1, 2, 3, 4, 5, and 6 still hold, but we need to re-calculate the equations (for example, in Theorem 3, $T_{c l}$ is the maximum of $T_{w}$ divided by the number of cache lines in the table). After the re-calculation, we will find whether the Warm+Delay scheme provides the optimal performance or not.

$T_{w}$ , $T_{m m}$ , and $T_{n m}$ will be measured on the platform. $P_{d} (N)$ in Theorems 3 (i.e., the probability that some cache lines of table entries not in caches are accessed, or called $P_{a}$ in Section 4.3.2), depends on the structure of lookup tables. We list the calculation of $P_{a}$ in Appendix B. Other variables and equations will be calculated, following the same steps as in the theorems.

4.5. Different algorithms

For other block cipher implementations with lookup tables, Theorems 1, 2, 3, 4, 5, and 6 still hold. We still use $S_{c}$ , $S_{\bar{c}, a}$ and $S_{\bar{c}, \bar{a}}$ to denote three states of the lookup table in caches during the continuous encryption/decryption. However, as described in Section 4.4, we need to re-calculate the parameters in Theorems 3, 4, 5, and 6 for different numbers of rounds and lookup table access in each execution of encryption/decryption, and various size of lookup tables, by using the parameters of cache line, $P_{d} (N)$ , $T_{w}$ , $T_{m m}$ , and $T_{n m}$ on each target platform, to find whether the Warm+Delay scheme is optimal.

5. Performance evaluation

We evaluate the scheme on a Lenovo ThinkCentre M8400t PC with an Intel Core i7-2600 CPU and 2 GB RAM. The CPU has 4 cores and each core has a 32 KB L1 data cache, and the operating system is Linux v3.6.2 (32-bit).

5.1. Implementation

We apply Warm+Delay to AES-128 implemented with a 2 KB lookup table, directly borrowed from OpenSSL-1.0.2c [48]. As we attempt to optimize the performance, efficient Warm, GetTime, and Delay are finished as follows.

Warm. It loads all entries of the lookup table into the L1D cache by accessing one byte of each block of 64 bytes (i.e., the size of one cache line). In order to ensure these operations are not obsoleted due to the compiler optimization, the variables are declared with the keyword volatile.

However, even when all table entries are in L1D caches, the execution time of encryption still has variations and these variations could be exploited to launched side-channel attackers [9,19]. The variations result from two types of time differences within L1D caches. One is the cache bank conflict. The L1D cache is divided physically into several banks. Each core has its own L1D cache and the banks are not across the L1D cache. Different banks can be concurrently accessed, but one bank only serves one request at a time. So, multiple access operations to the same cache bank are slower than those to different banks. Because the L1D cache is unshared and the L1D cache is not accessed by other cores, we disable Hyper-Threading of the system to ensure the protected process itself not to produce concurrent access to L1D caches with cache bank conflicts. In all the following experiments, Hyper-Threading is disabled.

The other cause is the read-write conflict that the load from L1D caches takes slightly more time if it involves the same set of cache lines as a recent store. Figure 2a shows the distribution of the AES execution time for $2^{30}$ random plaintexts when such a conflict occurs. We avoid the read-write conflict by switching the stack [33]. The aligned consecutive lookup table distributes in 32 cache sets due to the cache mapping rule while the total number of cache sets is 64 on our platform. We declare a 2 KB global array as the stack, with which we easily control the address. The beginning address of the array is made next to the lookup table module 4096, and this makes the intermediate variables of AES execution use the remaining cache sets. Finally, the distribution of AES encryption time is shown in Figure 2b.

Fig. 2.

The distribution of AES encryption time with a 2 KB lookup table in L1D caches.

Fig. 3.

The relation between the delayed time and the number of instruction loops.

GetTime. We adopt the instruction RDTSCP to implement GetTime, to obtain the current time in high precision (clock cycles) with low cost. RDTSCP is a serializing call which prevents the CPU from reordering it. We finished the following to achieve the high accuracy: (1) as the time stamp counters (TSC) on each core are not guaranteed to be synchronized, we install the patch [x86: unify/rewrite SMP TSC sync code] to synchronize the TSCs; (2) the clock cycle changes due to the energy-saving option, so we disable this option in BIOS to ensure the clock cycle be constant.

The cost of RDTSCP is 36 cycles which is much greater than the comparison operation and cannot be ignored. We perform GetTime only if $t 2 - t 1 < T_{m m}$ , instead of every time after Warm (Line 7 in Algorithm 1).

Delay. The system functions such as nanosleep() and usleep(), do not satisfy the resolution requirement, and they switch the process state to TASK_INTERRUPTIBLE, which may cause the lookup tables to be evicted from caches. On the contrary, we implement Delay by executing the xor instruction repeatedly as follows, achieving a high resolution without modifying the cache state.

We measure the time for different loop numbers of the xor instruction, by invoking it for $10^{6}$ times with different loop numbers (from 0 to 950 and the step is 50), as shown in Figure 3. The relation between the time delayed and the loop number (n) is calculated through the least squares method. The result is $T_{delay} = 2.9886 n + 15.68$ , and the coefficient of determination is 0.99996. The implementation of Delay() is provided in Listing 1. No table is used in this implementation, to reduce the use of caches.

Listing 1.

The implementation of Delay().

Fig. 4.

The distribution of AES execution time, with one cache line of data uncached.

The fixed parameters ( $T_{n m}$ and $T_{m m}$ ) are set properly as follows. First of all, the implementation of block ciphers is not subject to timing side-channel attacks based on instruction caches [1], because there is no branches in the execution path. However, the instructions of block ciphers may be evicted from the caches due to system activities, which causes instruction cache misses and increases the execution time. As the effect of instruction caches on the execution time is almost indistinguishable from that of data caches, we measure $T_{n m}$ when all instructions are cached, and $T_{m m}$ as the execution time when all instructions are not in instruction caches (and all table entries are not in data caches). Otherwise, the measured time might leak some information about data cache access. Also, when determining the value of $T_{n m}$ and $T_{m m}$ , we need to take the impact of architecture into consideration.

$T_{n m}$ . $T_{n m}$ is greater than the minimal AES execution time when no cache miss occurs, which avoids unnecessary Warm() and Delay() operations; and less than the execution time when only one cache miss occurs. The minimal AES execution time, is measured as the average time of $2^{30}$ AES execution with all table entries in the L1D cache, and it is 331 cycles in our environment.

Figure 4 shows the distribution of AES execution time for $2^{30}$ plaintexts, when all table entries except one block of 64 bytes (i.e., one cache line) are in L1D caches. Note that, this uncached entry may be unnecessary in an execution of AES encryption (i.e., the results of less than 420 CPU cycles in Figure 4). The stack switch makes the AES execution time much more concentrated, which helps the measurement of $T_{n m}$ to be more accurate, as shown in Figure 2. In order to avoid the influence of possible fluctuations around $T_{n m}$ and exclude the impact of the system architecture (e.g., read-write conflicts of the memory other than the lookup tables), we choose $T_{n m}$ as large as possible. Finally, we choose 355 cycles as $T_{n m}$ , to ensure that all table entries are in L1D caches and no fluctuation occurs around it.

$T_{m m}$ . $T_{m m}$ is the maximal encryption execution time when all table entries are out of caches. Before measuring it, we flush both the data and instructions out of L1/2/3 caches. We repeat the measurement for 10000 times, and calculate the average value of the 100 greatest measurements as $T_{m m}$ . The result is 2834 CPU cycles.

5.2. Performance evaluation

This section shows that, with the Warm+Delay scheme, the distribution of AES execution time are separated into two parts: less than $T_{n m}$ and greater than $T_{m m}$ , which meets our expectation. Then, we evaluate the performance in different aspects. We compare it with different Warm strategies to show that the integration scheme has the best performance among the different strategies integrating Warm and Delay. We measure the performance of several different timing side-channel defenses. It is shown that Warm+Delay produces better performance than other software-based methods, either running as an encryption service or integrated in an Apache HTTPS server.

The distribution of the encryption execution time with Warm+Delay. We measure the AES execution time implemented with the Warm+Delay scheme, and compare it with the unprotected version, for $2^{30}$ random plaintexts.

Figure 5 shows the distributions of the AES execution time for two implementations, which will be observed by attackers. With Warm+Delay, almost all results are in the range of (0, $T_{n m} + 2 T_{GetTime}$ ] and [ $T_{m m} + 2 T_{GetTime}$ , $+ \infty$ ), where $T_{GetTime}$ is the cost of RDTSCP, because GetTime is called at least twice (Lines 2 and 4 in Algorithm 1). A small set appears around the position of 1750 cycles due to task scheduling, which are unexploitable constant results. In this case, the average execution time of Warm+Delay is less than 1.29 times of the unprotected implementation.

Fig. 5.

The distribution of the observed AES execution time with different plaintexts.

Performance of different Warm strategies. We compare conditional Warm with other strategies that are configured with different $P_{1}$ and $P_{2}$ : perform Warm with $P_{1} \in [0, 1]$ when a cache miss occurs during the previous encryption, and with $P_{2} \in [0, 1]$ in other states. They are compared in different scenarios: low workload, high CPU workload and high memory workload.

With low workload, no other task except the evaluated AES implementation runs. We use the SysBench benchmark to simulate the CPU and memory workloads. We run SysBench in its CPU mode, which launches 16 threads to issue 10K requests to search the primes up to 300K, to produce the CPU workload. For the memory workload, we adopt SysBench with 16 threads in its memory mode, which reads or writes 1 KB blocks each time to access total 3 GB data on one CPU core. The evaluated AES implementation and the concurrent workload run on the same CPU core. The interval of task OS scheduling is set as $1 ms$ and $4 ms$ , respectively. In each case, we perform AES encryption with $2^{30}$ random plaintexts.

Figure 6 shows that, in any case, conditional Warm is the best, and the strategy with $P_{1} = 0.5$ and $P_{2} = 1$ is the worst.

Fig. 6.

AES execution performance of different Warm strategies.

Comparison with other defenses. Warm+Delay is compared with other timing side-channel defenses: AES-NI, compact table [48] and bit-sliced implementation [11]. Each method encrypts random plaintexts for $2^{30}$ times.

Figure 7 shows that, hardware AES-NI has the best performance, and the Warm+Delay scheme is the best among all software implementations.

Fig. 7.

Performance of different defense methods.

Performance when integrated in HTTPS servers. We applied each solution to protect the AES implementation in OpenSSL, which serves as the cryptographic engine in an Apache HTTPS server. Apache serves several web pages of different sizes with TLSv1.2. The TLS cipher suit is ECDHE-RSA-AES128-SHA256. The client runs on another computer in 1 Gbps LAN with the server. ApacheBench issues 10K requests with various request sizes, and we measure the HTTPS server throughput.

The HTTPS throughput is shown in Fig. 8. When the unprotected AES is used, the throughput is 27.2 requests per second for 1 MB data. With Warm+Delay, the throughput is 23.5 requests per second for 1 MB data. Warm+Delay scheme has a little influence on the performance. As the requested data increase, the performance influence caused by the Warm+Delay scheme increases gradually. Meanwhile, in Fig. 8, Warm+Delay is better than other countermeasures except hardware AES-NI.

Fig. 8.

Performance of different defense methods in apache HTTPS servers.

6. Discussions

6.1. Timing variations with fully-cached lookup tables

In the evaluation, we use the AES implementation with a 2 KB lookup table. The L1D cache of 32 KB, is typically divided into 64 cache sets and each set has 8 cache lines. The 2 KB lookup table occupies exactly one cache line in each of 32 cache sets. So we declare a 2 KB array using the other 32 cache sets as the stack, the address of which does not intersect with the lookup table module 4096.

However, when a larger lookup table is used, all cache sets will be occupied by default due to the continuity of lookup tables in memory. In these cases, to avoid the read-write conflict of cache sets between the look table and the stack, we shall reserve the lookup table within 32 cache sets. It will be achieved by discontinuous table entries. For example, when using 4 KB lookup tables ( $T_{0}$ , $T_{1}$ , $T_{2}$ , $T_{3}$ ), we allocate $T_{2} / T_{3}$ in the same memory address as $T_{0} / T_{1}$ module 4096, so that they occupy the same cache sets. Then the 4 KB lookup tables occupy only 32 cache sets and the 2 KB stack occupies the other 32 cache sets. This method works for 4.25 KB or 5 KB lookup tables.

6.2. Other cache-based timing side channels

The Warm+Delay scheme is effective against remote cache timing side channels, and it also prevents synchronous access-driven attacks such as Evict+Time [50]. The synchronous access-driven attackers do not observe the cache states during the encryption execution but only monitor the cache state once per encryption, while the access pattern is masked by Warm+Delay.

The Warm+Delay scheme fails to prevent the trace-driven attacks and the asynchronous attacks. For the trace-driven attacks, as Warm+Delay scheme only uses Warm to load all the lookup table entries before/after the encryption, the attackers who have the privilege to probe the cache state, infer the cryptographic key based on the cache access pattern obtained during the encryption execution. For the asynchronous attacks, in addition to probe the cache state, the attackers have the privilege to modify the cache states, which makes Warm+Delay ineffective.

7. Conclusion

This work investigates the integration of Delay and Warm, against remote cache-based timing side channels with the optimal performance (or with the least extra operations), for block cipher implementations with lookup tables. We theoretically derive the optimization strategy to integrate Delay and Warm, and apply it to AES. We implement the derived integration scheme on Linux for AES-128 with a 2 KB lookup table. Experimental results confirm that, (a) the execution time does not leak information about cache access during encryption, (b) the scheme achieves the optimal performance, outperforming other different integration strategies, and (c) the implementation works without any privileged operations on the system.

Footnotes

Acknowledgments

This work was partially supported by National Natural Science Foundation of China (No. 61772518) and the Information Construction Project of the 13th Five-year Plan of Chinese Academy of Sciences (XXH13505). We would like to thank the associate editor and the reviewers for the insightful comments.

Proofs of Theorems 4 and 5

We present the proof details of Theorems 4 and 5. In the following calculation, all probabilities are in $[0, 1]$ . $E (T^{⊖})$ , $E (T)$ and $E (T^{\oplus})$ are the expected extra time costs introduced by less Warm, conditional Warm and more Warm, respectively.

P a for different AES key lengthes and implementations

The size of a cache line is C bytes. $P_{a}$ represents the probability that some of the N cache line size of lookup tables not in caches are accessed. When the AES implementation uses 4.25 KB lookup tables, $P_{a}$ for AES-128, AES-192 and AES-256 is as follows: $\begin{array}{l} P_{a}^{[128]} = 1 - \frac{1}{(\binom{4352 / C}{N})} \sum_{x_{4} = x_{4 b}}^{x_{4 e}} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} f (x_{4}) \prod_{i = 0}^{3} g (x_{i}, 36), \\ P_{a}^{[192]} = 1 - \frac{1}{(\binom{4352 / C}{N})} \sum_{x_{4} = x_{4 b}}^{x_{4 e}} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} f (x_{4}) \prod_{i = 0}^{3} g (x_{i}, 44), \\ P_{a}^{[256]} = 1 - \frac{1}{(\binom{4352 / C}{N})} \sum_{x_{4} = x_{4 b}}^{x_{4 e}} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} f (x_{4}) \prod_{i = 0}^{3} g (x_{i}, 52), \end{array}$ where $\begin{array}{l} f (x) = (\binom{256 / C}{x}) {(1 - \frac{x C}{256})}^{16} \\ g (x, y) = (\binom{1024 / C}{x}) {(1 - \frac{x C}{1024})}^{y} \\ x_{0} + x_{1} + x_{2} + x_{3} + x_{4} = N \\ x_{4 b} = max (0, N - 4096 / C) \\ x_{4 e} = min (256 / C, N) \\ x_{0 b} = max (0, N - x_{4} - 3072 / C) \\ x_{0 e} = min (1024 / C, N - x_{4}) \\ x_{1 b} = max (0, N - x_{4} - x_{0} - 2048 / C) \\ x_{1 e} = min (1024 / C, N - x_{4} - x_{0}) \\ x_{2 b} = max (0, N - x_{4} - x_{0} - x_{1} - 1024 / C) \\ x_{2 e} = min (1024 / C, N - x_{4} - x_{0} - x_{1}) \end{array}$

When the AES implementation uses 5 KB lookup tables, $P_{a}$ for AES-128, AES-192 and AES-256 is as follows: $\begin{array}{l} P_{a}^{[128]} = 1 - \frac{1}{(\binom{5120 / C}{N})} \sum_{x_{4} = x_{4 b}}^{x_{4 e}} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} f (x_{4}, 16) \prod_{i = 0}^{3} f (x_{i}, 36), \\ P_{a}^{[192]} = 1 - \frac{1}{(\binom{5120 / C}{N})} \sum_{x_{4} = x_{4 b}}^{x_{4 e}} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} f (x_{4}, 16) \prod_{i = 0}^{3} f (x_{i}, 44), \\ P_{a}^{[256]} = 1 - \frac{1}{(\binom{5120 / C}{N})} \sum_{x_{4} = x_{4 b}}^{x_{4 e}} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} f (x_{4}, 16) \prod_{i = 0}^{3} f (x_{i}, 52), \end{array}$ where $\begin{array}{l} f (x, y) = (\binom{1024 / C}{x}) {(1 - \frac{x C}{1024})}^{y} \\ x_{0} + x_{1} + x_{2} + x_{3} + x_{4} = N \\ x_{4 b} = max (0, N - 4096 / C) \\ x_{4 e} = min (1024 / C, N) \\ x_{0 b} = max (0, N - x_{4} - 3072 / C) \\ x_{0 e} = min (1024 / C, N - x_{4}) \\ x_{1 b} = max (0, N - x_{4} - x_{0} - 2048 / C) \\ x_{1 e} = min (1024 / C, N - x_{4} - x_{0}) \\ x_{2 b} = max (0, N - x_{4} - x_{0} - x_{1} - 1024 / C) \\ x_{2 e} = min (1024 / C, N - x_{4} - x_{0} - x_{1}) \end{array}$

When the AES implementation uses 4 KB lookup tables, $P_{a}$ for AES-128, AES-192 and AES-256 is as follows: $\begin{array}{l} P_{a}^{[128]} = 1 - \frac{1}{(\binom{4096 / C}{N})} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} \prod_{i = 0}^{3} f (x_{i}, 40), \\ P_{a}^{[192]} = 1 - \frac{1}{(\binom{4096 / C}{N})} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} \prod_{i = 0}^{3} f (x_{i}, 48), \\ P_{a}^{[256]} = 1 - \frac{1}{(\binom{4096 / C}{N})} \sum_{x_{0} = x_{0 b}}^{x_{0 e}} \sum_{x_{1} = x_{1 b}}^{x_{1 e}} \sum_{x_{2} = x_{2 b}}^{x_{2 e}} \prod_{i = 0}^{3} f (x_{i}, 56), \end{array}$ where $\begin{array}{l} f (x, y) = (\binom{1024 / C}{x}) {(1 - \frac{x C}{1024})}^{y} \\ x_{0} + x_{1} + x_{2} + x_{3} = N \\ x_{0 b} = max (0, N - 3072 / C) \\ x_{0 e} = min (1024 / C, N) \\ x_{1 b} = max (0, N - x_{0} - 2048 / C) \\ x_{1 e} = min (1024 / C, N - x_{0}) \\ x_{2 b} = max (0, N - x_{0} - x_{1} - 1024 / C) \\ x_{2 e} = min (1024 / C, N - x_{0} - x_{1}) \end{array}$

When the AES implementation uses 2 KB lookup table, $P_{a}$ for AES-128, AES-192 and AES-256 is as follows: $\begin{array}{l} P_{a}^{[128]} = 1 - {(1 - \frac{N C}{2048})}^{160}, \\ P_{a}^{[192]} = 1 - {(1 - \frac{N C}{2048})}^{192}, \\ P_{a}^{[256]} = 1 - {(1 - \frac{N C}{2048})}^{224} . \end{array}$

References

Acıiçmez, Yet another MicroArchitectural attack: Exploiting I-cache, in: ACM Workshop on Computer Security Architecture, 2007.

Acıiçmez and

Ç.K.

Koç, Trace-driven cache attacks on AES, in: ICICS, 2006.

Acıiçmez,

Schindler and

Ç.K.

Koç, Improving Brumley and Boneh timing attack on unprotected SSL implementations, in: ACM CCS, 2005.

Acıiçmez,

Schindler and

Ç.K.

Koç, Cache based remote timing attack on the AES, in: CT-RSA, 2007.

Adams, IETF RFC 2144: The CAST-128 Encryption Algorithm, 1997.

Askarov,

Zhang and

A.C.

Myers, Predictive black-box mitigation of timing channels, in: ACM CCS, 2010.

A.C.

Atici,

Yilmaz and

Savas, Remote cache-timing attack without learning phase, IACR Cryptology ePrint Archive (2016).

Gras,

Razavi,

Bos and

Giuffrida, Translation leak-aside buffer: Defeating cache side-channel protections with TLB attacks, in: USENIX Security, 2018.

D.J.

Bernstein, Cache-Timing Attacks on AES, 2005, http://cr.yp.to/antiforgery/cachetiming-20050414.pdf.

10.

Bertoni,

Zaccaria,

Breveglieri,

Monchiero and

Palermo, AES power attack based on induced cache miss and countermeasure, in: ITCC, 2005.

11.

bitcoin-core/ctaes: Simple constant-time AES implementation, Simple constant-time AES implementation, https://github.com/bitcoin-core/ctaes/.

12.

Blömer,

Guajardo and

Krummel, Provably secure masking of AES, in: SAC, 2004.

13.

Blömer and

Krummel, Analysis of countermeasures against access driven cache attacks on AES, in: SAC, 2007.

14.

Bonneau and

Mironov, Cache-collision timing attacks against AES, in: CHES, 2006.

15.

B.A.

Braun,

Jana and

Boneh, Robust and efficient elimination of cache and timing side channels, 2015, arXiv:1506.00189.

16.

Brickell,

Graunke,

Neve and

J.-P.

Seifert, Software mitigations to hedge AES against cache-based software side channel vulnerabilities, IACR Cryptology ePrint Archive (2006).

17.

B.B.

Brumley and

Tuveri, Remote timing attacks are still practical, in: ESORICS, 2011.

18.

Brumley and

Boneh, Remote timing attacks are practical, Computer Networks 48(5) (2005). doi:10.1016/j.comnet.2005.01.010.

19.

Canteaut,

Lauradoux and

Seznec, Understanding cache attacks, PhD thesis, INRIA, 2006.

20.

J.V.

Cleemput,

Coppens and

De Sutter, Compiler mitigations for time attacks on modern ×86 processors, TACO (2012).

21.

Cock,

Ge,

Murray and

Heiser, The last mile: An empirical study of some timing channels on seL4, in: ACM CCS, 2014.

22.

Coppens,

Verbauwhede,

K.D.

Bosschere and

B.D.

Sutter, Practical mitigations for timing-based side-channel attacks on modern X86 processors, in: IEEE S&P, 2009.

23.

Crane,

Homescu,

Brunthaler,

Larsen and

Franz, Thwarting cache side-channel attacks through dynamic software diversity, in: NDSS, 2015.

24.

Daemen and

Rijmen, The Design of Rijndael: AES – the Advanced Encryption Standard, Springer Science & Business Media, 2013.

25.

Gruss,

Lettner,

Schuster,

Ohrimenko,

Haller and

Costa, Strong and efficient cache side-channel protection using hardware transactional memory, in: USENIX Security, 2017.

26.

Disselkoen,

Kohlbrenner,

Porter and

Tullsen, Prime+ Abort: A timer-free high-precision L 3 cache attack using Intel TSX, in: USENIX Security, 2017.

27.

Drepper, What every programmer should know about memory, Technical Report, Red Hat, 2007.

28.

Ferdinand, Worst case execution time prediction by static program analysis, in: IPDPS, 2004.

29.

Genkin,

Pachmanov,

Pipman and

Tromer, Stealing keys from PCs by radio: Cheap electromagnetic attacks on windowed exponentiation, in: CHES, 2015.

30.

Genkin,

Pipman and

Tromer, Get your hands off my laptop: Physical side-channel key-extraction attacks on PCs, in: CHES, 2014.

31.

Genkin,

Shamir and

Tromer, RSA key extraction via low-bandwidth acoustic cryptanalysis, in: CRYPTO, 2014.

32.

Gruss,

Maurice,

Wagner and

Mangard, Flush+ Flush: A fast and stealthy cache attack, in: DIMVA, 2016.

33.

Guan,

Lin,

Luo and

Jing, Copker: Computing with private keys without RAM, in: NDSS, 2014.

34.

Gullasch,

Bangerter and

Krenn, Cache games: Bringing access-based cache attacks on AES to practice, in: IEEE S&P, 2011.

35.

Käsper and

Schwabe, Faster and timing-attack resistant AES-GCM, in: CHES, 2009.

36.

Kim,

Peinado and

Mainar-Ruiz, STEALTHMEM: System-level protection against cache-based side channel attacks in the cloud, in: USENIX Security, 2012.

37.

P.C.

Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, in: CRYPTO, 1996.

38.

Kong,

Acıiçmez,

J.P.

Seifert and

Zhou, Hardware-software integrated approaches to defend against software cache-based side channel attacks, in: HPCA, 2009.

39.

Könighofer, A fast and cache-timing resistant implementation of the AES, in: CT-RSA, 2008.

40.

Kopf and

Durmuth, A provably secure and efficient countermeasure against timing attacks, in: CSF, 2009.

41.

Li,

Gao and

M.K.

Reiter, Mitigating access-driven timing channels in clouds using StopWatch, in: DSN, 2013.

42.

SSL Library mbed TLS/PolarSSL, https://tls.mbed.org/.

43.

Liu,

Ge,

Yarom,

Mckeen,

Rozas,

Heiser and

R.B.

Lee, CATalyst: Defeating last-level cache side channel attacks in cloud computing, in: HPCA, 2016.

44.

Liu,

Yarom,

Ge,

Heiser and

R.B.

Lee, Last-level cache side-channel attacks are practical, in: IEEE S&P, 2015.

45.

Martin,

Demme and

Sethumadhavan, TimeWarp: Rethinking timekeeping and performance monitoring mechanisms to mitigate side-channel attacks, in: ISCA, 2012.

46.

Neve,

J.P.

Seifert and

Wang, A refined look at Bernstein’s AES side-channel analysis, in: ACM AsiaCCS, 2006.

47.

OpenSSH, http://www.openssh.com/.

48.

OpenSSL: Cryptography and SSL/TLS Toolkit, https://www.openssl.org/.

49.

Oren and

Shamir, How not to protect PCs from power analysis, in: Rump Session, CRYPTO, 2006.

50.

D.A.

Osvik,

Shamir and

Tromer, Cache attacks and countermeasures: The case of AES, in: CT-RSA, 2006.

51.

Page, Defending against cache-based side-channel attacks, Information Security Technical Report, 2003.

52.

Ristenpart,

Tromer,

Shacham and

Savage, Hey, you, get off of my cloud: Exploring information leakage in third-party compute clouds, in: ACM CCS, 2009.

53.

Saraswat,

Feldman,

D.F.

Kune and

Das, Remote cache-timing attacks against AES, in: CS2 Workshop, 2014.

54.

Schneier, Description of a new variable-length key, 64-bit block cipher (Blowfish), in: FSE, 1993.

55.

Stefan,

Buiras,

E.Z.

Yang,

Levy,

Terei,

Russo and

Mazières, Eliminating cache-based timing attacks with instruction-based scheduling, in: ESORICS, 2013.

56.

Y.H.

Taha,

S.M.

Abdulh,

N.A.

Sadalla and

Elshoush, Cache-timing attack against AES crypto system – countermeasures review, 2014.

57.

Tromer,

D.A.

Osvik and

Shamir, Efficient cache attacks on AES, and countermeasures, Journal of Cryptology (2010).

58.

Tsunoo,

Saito,

Suzaki,

Shigeri and

Miyauchi, Cryptanalysis of DES implemented on computers with cache, in: CHES, 2003.

59.

Varadarajan,

Ristenpart and

M.M.

Swift, Scheduler-based defenses against cross-VM side-channels, in: USENIX Security, 2014.

60.

Wang and

R.B.

Lee, New cache designs for thwarting software cache-based side channel attacks, in: ISCA, 2007.

61.

Yarom and

Falkner, Flush+Reload: A high resolution, low noise, L 3 cache side-channel attack, in: USENIX Security, 2014.

62.

Zhang,

Askarov and

A.C.

Myers, Predictive mitigation of timing channels in interactive systems, in: ACM CCS, 2011.

63.

Zhang,

Juels,

M.K.

Reiter and

Ristenpart, Cross-VM side channels and their use to extract private keys, in: ACM CCS, 2012.

64.

Zhang and

M.K.

Reiter, Düppel: Retrofitting commodity operating systems to mitigate cache side channels in the cloud, in: ACM CCS, 2013.

Towards the optimal performance of integrating Warm and Delay against remote cache timing side channels on block ciphers

Abstract

Keywords

1. Introduction

1 Another choice is to perform encryption without caches, which is inefficient. In fact, a typical Delay strategy is to extend the encryption operation in constant time, equal to the execution time without caches.

2.1. AES and block cipher implementation

2 The last round of AES encryption performs only SubBytes, ShiftRows and AddRoundKey.

2.2.1. Time-driven side channel

2.2.2. Access-driven cache side channel

2.3. Defense against cache timing side channels

3. Eliminating remote cache timing side channels by integrating Warm and Delay

3.1. Threat model

3.2. Objective

3.3. The Warm+Delay scheme

4. Towards the optimal performance of the Warm+Delay scheme

4.2. The optimal conditions for Delay

4.3.1. The amount of data loaded in Warm

3 Even if some occurs more than once actually, they can be viewed as one event with the strengthened impact on the state transition.

4.5. Different algorithms

5. Performance evaluation

5.1. Implementation

6.1. Timing variations with fully-cached lookup tables

6.2. Other cache-based timing side channels

7. Conclusion

Footnotes

Acknowledgments

Proofs of Theorems 4 and 5

P a for different AES key lengthes and implementations

References

¹
Another choice is to perform encryption without caches, which is inefficient. In fact, a typical Delay strategy is to extend the encryption operation in constant time, equal to the execution time without caches.

²
The last round of AES encryption performs only SubBytes, ShiftRows and AddRoundKey.

³
Even if some occurs more than once actually, they can be viewed as one event with the strengthened impact on the state transition.