Cache attacks on subkey calculation of Blowfish

Abstract

Cache attacks pose a serious security threat to cryptographic implementations in processor architectures. In this paper, we first propose cache attacks against Blowfish, which can break the protection of key-dependent S-box. This attack targets at the subkey calculation of Blowfish, and fully exploits features of the subkey calculation to construct a leakage equation group about the key. Without any knowledge of plaintext and ciphertext, the attacker only needs to obtain the cache leakage once to recover a variable-length key in minute-level time. More than that, we establish a leakage model for cache attack situations to evaluate the exhausting space of the intermediate value of block ciphers, and estimate the time complexity of cache attacks. In our experiments, we perform Flush + Reload and Prime + Probe attacks and recover the random key of Blowfish in OpenSSL 1.1.1h in 4 minutes. Furthermore, we have applied our attacks to existing systems, such as JavaScript-blowfish and Bcrypt. Our attack on JavaScript-blowfish can recover any plaintext input by the user. As for Bcrypt, our attack can recover the hash values stored in the database, thereby allowing attackers to impersonate the user’s identity.

Keywords

Cache attack Blowfish subkey calculation Flush + Reload Prime + Probe

1. Introduction

In the big data era, the cloud environment emerged as a means to quickly process massive amounts of data and reduce the cost of hardware facilities. The cloud has an open platform and resource sharing, which provide strong technical support for building big data services. However, it is also vulnerable to the security threat of micro-architecture side-channel attacks. Cloud management programs share physical hardware resources among concurrent virtual machines (VMs) to reduce computing overhead and improve efficiency. From the perspective of security, researchers have developed a set of technologies, such as hypervisor-OS privilege hierarchy and security extensions, to provide virtual memory isolation between VMs and processes. Although virtualization aims to strictly isolate and access the exclusive resources of the core, virtual memory is mapped to shared physical memory, which leads to shared resource attacks. An attacker can obtain the knowledge of shared resource contention by monitoring the execution time of the victim’s process, and then, they can infer the victim’s secret information.

Cache attack is one of the most widely used attack methods in micro-architecture side-channel attacks. In the past two decades, cache attacks have posed a huge security threat to cryptographic implementations. By observing the time difference of the victim’s memory access, the cache attacker learns whether the victim has accessed the target address and then obtains the intermediate value of ciphers and infers the key through further analysis.

1.1. Cache attack on fixed S-boxes

In block ciphers, an S-box is the only nonlinear structure, and its security determines the security of the whole cipher. The nonlinearity of an S-box indicates that it is usually implemented by a lookup table. Unfortunately, the lookup table of non-lightweight block ciphers needs to be stored in multiple cache lines. Therefore, an attacker can directly learn some bits of the input or output of an S-box by observing whether the target address is accessed and then recovering the key based on multiple cache leakage. Researchers have proposed cache attacks against block ciphers such as AES [3,10,13,19], DES [25], SM4 [17], ARIA [2], Camellia [20], and MISTY1 [7]. These attacks have the following commonalities:

The S-box is public and fixed;

The first round S-box input is related to the key and the plaintext, while the last round S-box output is related to the key and the ciphertext, and the first or last round is the target of cache attack;

The attacker performs a chosen-plaintext or chosen-ciphertext attack and observe multiple cache leakage of encryption and using exclusion to recover the key.

1.2. Cache attack on key-dependent S-boxes

[9] first proposed a cache attack against the North Korean cipher Pilsung. Both the substitution and the permutation steps in Pilsung depend on the key and neither of these are known to the attacker. However, the approach exploits the limited dependency of the first-round S-boxes on the second-round key, that is, the S-box used for the n-th byte in the first round solely depends on the corresponding byte of the second-round key. Their attack requires 19,472 oracle queries to fully recover the key.

Similarly to Pilsung, Blowfish has a key-dependent S-box, and it is generated through the entire encryption. Thus, it is difficult for an attacker to establish a link between the cache leakage and the key, let alone recover the key. Research has shown that Blowfish has a cache leakage but has not proposed a complete attack against Blowfish [15]. In our work, we found a clever way to bypass the key-dependent S-box, which is to perform cache attacks on the subkey calculation of Blowfish. Blowfish uses a fixed public S-box in subkey calculation, and the calculation process is only related to the key. This means that even if the attacker can monitor the victim’s multiple encryption processes, the leakage information will not increase. How to use limited leaked information to recover the key becomes a problem that we must solve.

1.3. Security and applications of Blowfish

Researchers generally believe that Blowfish has the advantages of both efficiency and security. [14] compared DES, 3DES, AES, Blowfish, Twofish, and Threefish. The results showed that Blowfish had the highest security level and fastest encryption speed among these ciphers and that it was difficult to form an effective attack against Blowfish, as shown in Table 1. [11] conducted an in-depth analysis of AES, DES, 3DES, RSA, and Blowfish in the Internet of Things (IoT) from the aspects of time complexity, size, encryption, and decryption speed. The results showed that Blowfish had better performance in the encrypted communication between two edge devices and that there were no known security vulnerabilities. Therefore, Blowfish is more suitable as a candidate algorithm for the standard encryption algorithm for IoT devices.

Blowfish is one of the most popular ciphers in the personal encryption field and is suitable for a wide range of applications, including bulk encryption, random bit generation, packet encryption, password hashing and management, mobile processors, email, file or disk encryption, data backup and Secure Shell. Besides, Blowfish is used by many popular products, such as CryptoDisk, PasswordWallet, Access Manager, Symantec NetBackup and SplashID. Many social media platforms and e-commerce websites also use Blowfish to protect user data. Moreover, Blowfish is included in many common open-source cryptographic libraries, such as OpenSSL, Crypto++, and mbedTLS.

Table 1
Comparison of various ciphers on the basis of different parameters

Algorithm Development Key length (bit) Rounds Block size (bit) Attacks found

3DES IBM in 1978 128 48 64 Related key attack

AES Vincent Rijmen 128 10, 12, 14 128 Key recovery attack, side channel attack

Blowfish Bruce Schneier Variable 16 64 No attack found to be successful

Twofish Bruce Schneier 256 16 128 Related key attack

Threefish Bruce Schneier 256, 512 80 256, 512, 1024 Related-key boomerang attack

Algorithm	Development	Key length (bit)	Rounds	Block size (bit)	Attacks found
3DES	IBM in 1978	128	48	64	Related key attack
AES	Vincent Rijmen	128	10, 12, 14	128	Key recovery attack, side channel attack
Blowfish	Bruce Schneier	Variable	16	64	No attack found to be successful
Twofish	Bruce Schneier	256	16	128	Related key attack
Threefish	Bruce Schneier	256, 512	80	256, 512, 1024	Related-key boomerang attack

1.4. Work of this paper

We used the fixed values and the cache leakage of the subkey calculation to construct the equation group. According to whether the equation group has a solution, we can exclude most of the wrong key guesses. After that, we will receive a few solutions solved by different key guesses, one of which is solved by the correct key. We can recover the key in accordance with periodicity, that is, if the solution solved by the correct key XOR with the initial P-array, the result would be periodic; otherwise, it would be not.

To evaluate the time complexity of our attack, we established a leakage model suitable for the cache attack situations, which provides a theoretical basis for the time complexity estimation of the cache attack. The leakage model constructs the probability space for the input and output pairs of the nonlinear structure of ciphers and expresses the leakage as a specific event set in the probability space. By calculating the expectation of the basic event number, the attacker can learn the exhausting space size of the intermediate value in the average sense. The leakage model can also be used to estimate the time complexity of cache attacks against block ciphers other than Blowfish.

Aiming at the implementation of Blowfish in OpenSSL 1.1.1h, we performed Flush + Reload and Prime + Probe attack to recover the key in minute-level time, and the result verifies the effectiveness of our attack. Moreover, our attack fully exploits features of the subkey calculationdoes and not rely on knowledge of plaintext and ciphertext. Generally, we make the following contributions in this paper:

We performed the first cache attack on the implementation of Blowfish with a key-dependent S-box. The attacker does not need any knowledage of plaintext and ciphertext, only needs to obtain the cache leakage once to recover a variable-length key. We showed that in the case of Blowfish, key-dependent conversion did not provide inherent protection against cache attacks (Section 3).

We established a leakage model for cache attack situations to reasonably evaluate the cache attack time complexity against block ciphers, not only Blowfish (Section 4).

We showed how to recover the key of the Blowfish implementation in OpenSSL 1.1.1h via cache attacks, and we completed the attack in 4 minutes (Section 5).

We have extended our attack to existing systems, such as JavaScript-blowfish and Bcrypt. In JavaScript-blowfish case, the attacker can obtain any plaintext input by the user. As for Bcrypt, the attacker can recover the hash values stored in the database, enabling him to impersonate the user’s identity (Section 6).

2. Background

2.1. Cache attacks

Multilevel caches are located between memory and CPU and are used to store data and instructions used recently to improve access efficiency. The cache that is closer to the core accesses data more quickly. Taking the x86 processor as an example, cache hierarchy ensures that each core has its own L1 and L2 caches and that the LLC cache is divided into partitions according to the number of cores. These partitions are connected by a ring bus, which ensures that each core can access a complete LLC. The cache hierarchy is shown in Fig. 1.

Fig. 1.

Cache hierarchy.

According to the locality principle of data access, the storage units accessed by the CPU tend to be clustered in a smaller continuous area, and the cache can effectively avoid high latency. The CPU first looks for data in the cache and produces two results:

Cache hit. If the CPU finds the requested data in the cache, it is considered a cache hit.

Cache loss. If the CPU does not find the requested data in the cache, the data must be retrieved through the system bus and copied to the cache.

So, cache hits are two orders of magnitude faster than cache misses.

Flush + Reload: Flush + Reload [27] uses the clflush instruction to clear the target address from caches and then reloads the target address after the victim accesses it. If the reload time is short(ablout 30 ns), the target address is already in the cache, which indicates that the victim has accessed the target address; otherwise, the attacker reloads the target address for a long time(over 300 ns). The time difference leaks the victim’s access information. The steps are shown in Fig. 2:

Flush: The attacker uses the clflush instruction to refresh the cache;

Wait: Wait for the victim to access the target address;

Reload: The attacker reloads the target address and timing.

Fig. 2.

Flush + Reload attack.

Flush + Reload is fine-grained and highly efficient, but it relies on the clflush instruction. Thus, when the system disables the clflush instruction, the attacker must use other methods to clear the cache.

Prime + Probe: The main feature of Prime + Probe [8] is that the attacker accesses their memory to learn the cache leakage of the victim. Specifically, an attacker selects a set of memory addresses (called ‘eviction sets’) that map to the same cache line as the target address and primes them into the cache by accessing the eviction sets. In the Probe phase, the attacker again accesses the eviction sets and timing. The steps are shown in Fig. 3:

Prime: The attacker accesses the eviction sets;

Wait: Wait for the victim to access the target address;

Probe: The attacker again accesses the eviction sets and timing.

Fig. 3.

Prime + Probe attack.

If the probe time is long (over 300 ns), it indicates that the eviction set has been evicted to memory from the cache. This means that the victim has recently accessed the target address. If the access time is short (about 30 ns), it implies that the eviction set is still in the cache. This means that the victim has not accessed the target address during the waiting period. The advantage of the Prime + Probe attack is that the attacker only needs to access their memory, which makes the Prime + Probe more widely applicable to L1, L2, and LLC caches.

Cache attack on an S-box: Block cipher implementations often use lookup tables to complete substitution. The lookup table of non-lightweight block ciphers must be stored in multiple cache lines, which leads to leakage. Let the length of input of $S_{a}$ be a bits, and one item of $S_{a}$ needs $2^{a}$ bytes of memory. Then, if the size of cache line is $2^{k}$ byte, $S_{a}$ needs $2^{a + b}$ bytes of memory and $2^{a + b - k}$ cache lines of storage. If an attacker knows the memory address of $S_{a}$ and uses a cache attack when the programs of ciphers run, the attacker can learn the highest $a + b - k$ bits of the S-box input. According to the characteristics of cipher implementation, the attacker can recover the intermediate value of ciphers by exhausting unknown bits or observing multiple leakages and then trying to recover the key.

2.2. Blowfish

Blowfish, proposed by [23], is a generalized Feistel structure block cipher based on 64-bit blocks and a variable key length from 32 bits to 448 bits. Blowfish first executes a subkey calculation before encryption, as follows:

The P-array is initialized first, followed by the four S-boxes with the decimal part of π. Then, the P-array is XORed with the key by 8 bytes, and the result is denoted as $P_{i}$ , $1 ⩽ i ⩽ 18$ . The security of the key is equivalent to the security of the $P_{i}$ , $1 ⩽ i ⩽ 18$ .

The all-zero string is encrypted with the Blowfish using the subkeys described in step (1), and the result is denoted as ${P_{1}}^{'}$ and $P_{2}$ . $P_{1}$ and $P_{2}$ are replaced by the encrypted ${P_{1}}^{'}$ and ${P_{2}}^{'}$ . At this time, the P-array consists of ${P_{1}}^{'}$ , ${P_{2}}^{'}$ and $P_{i}$ , $3 ⩽ i ⩽ 18$ .

${P_{i}}^{'}$ and $P_{i + 1}^{'}$ are encrypted using the Blowfish with the modified subkeys, and the result is denoted as $P_{i + 2}^{'}$ and $P_{i + 3}^{'}$ . $P_{i + 2}$ and $P_{i + 3}$ are replaced by the encrypted $P_{i + 2}^{'}$ and $P_{i + 3}^{'}$ , $i = 1, 3, \dots, 15$ . At this time, the P-array consists of ${P_{i}}^{'}$ , $1 ⩽ i ⩽ 18$ , and is denoted as ${P_{i}}^{'}$ .

${P_{17}}^{'}$ and ${P_{18}}^{'}$ , m, are encrypted using the subkeys described in step (3), and the result is denoted as ${S_{1}}^{'}$ and ${S_{2}}^{'}$ . $S_{1}$ and $S_{2}$ are replaced by the encrypted ${S_{1}}^{'}$ and ${S_{2}}^{'}$ .

The process is continued until all entries of four S-boxes are replaced in order with the output of the continuously changing Blowfish.

Encryption of Blowfish: The plaintext is divided into two parts: $L_{0}$ and $R_{0}$ . F is the round function. The encryption of the i-th round, shown in Fig. 4, is $L_{i} = R_{i - 1}$ ; $R_{i} = L_{i - 1} \oplus F (R_{i - 1}, P_{i - 1})$ . Encryption and . Function F of Blowfish is shown in Fig. 5

Fig. 4.

Encryption of Blowfish.

Fig. 5.

Function F of Blowfish.

2.3. Threat model

Our attack follows an identical threat model as most current cache side channel attacks [2,3,7,9,10,13,17,19,20,25]. We assume that the adversary is a normal user in the target system without root privileges and shares the same hardware platform as the victim. The adversary is able to execute non-privileged code, but cannot control the scheduling of the attacking process or the victim. Our assumption is a typical and practical assumption in cloud computing systems.

While the adversary cannot directly monitor the victim’s memory accesses, he can detect the shared cache state to determine if certain cache lines have been accessed by the victim’s program. This threat model covers the majority of cache side channel attacks like PRIME + PROBE [8] and FLUSH + RELOAD [27]. Existing works [4,6] commonly refer to the attackers in our threat model as “trace-based attackers” since they are able to probe the cache state after the execution of each program statement in the victim program.

3. Cache attack against Blowfish

This section assumes that the attacker has obtained an accurate cache leakage of the subkey calculation. How to obtain accurate cache leakage is described in Section 5. Our attack exploits two features of the subkey calculation of Blowfish:

In step (3) of the subkey calculation, the input of the first round is the fixed value 0 and the input of the second round is the fixed value $F (0)$ ;

The key recurrently XORs the P-array by 8 bytes.

An attacker can use feature (1) and the cache leakage to construct an equation group for the key. According to whether the equation group has a solution, most of the wrong key guesses can be excluded. Then, the attacker uses feature (2) to XOR the solution sequence output from the leakage equation group with the initial P-box and recovers the key based on periodicity. Specifically, the result calculated by the correct key is periodic; otherwise, it will be not periodic.

3.1. Leakage of the S-box and function F

According to Section 2.2, the round function F consists of four S-boxes. Let the input of F be $(L, P)$ , where L is the plaintext, and P is the subkey. Let $L \oplus P = X_{1} ‖ X_{2} ‖ X_{3} ‖ X_{4}$ , $X_{i}, 1 ⩽ i ⩽ 4$ , and all $X_{i}$ are 8 bits. Then, $F (L, P) = ((S (X_{1}) + S (X_{2})) \oplus S (X_{3})) + S (X_{4})$ .

The input of the S-box is 8 bits, and the output is 32 bits; so, every S-box requires $2^{8} \times 32 b = 1024 B$ storage space. If the size of the cache line is 64 bytes, the S-box is stored in 16 cache lines. Under the condition of acquiring the S-box’s storage address, the attacker can infer the 4 bits via cache attacks; so, the $4 \times 4$ bits of $L \oplus P$ are leaked when the function F is called.

3.2. Constructing the leakage equation group

Because the P-array and S-box used in the encryption of Blowfish are unknown to the attacker, while the initial P-array and S-box used in subkey calculation of Blowfish are public, this section takes the subkey calculation of Blowfish as the target of cache attacks. Blowfish sets the length of the key from 32 bits to 448 bits; so, an attacker can recover the key by recovering $P_{i}$ , $1 ⩽ i ⩽ 14$ .

Step (1) of the subkey calculation does not replace the initial S-box. Step (2) encrypts the 64-bit all-zero data using the initial S-box and P-array generated in step (1), and the result is denoted as ${P_{1}}^{'}$ and ${P_{2}}^{'}$ . $P_{1}$ and $P_{2}$ are replaced by the encrypted ${P_{1}}^{'}$ and ${P_{2}}^{'}$ . This procedure calls the round function F 16 times, as shown in Fig. 6.

Fig. 6.

Step (2) of subkey calculation.

Fig. 7.

Step (3) of subkey calculation.

Let $X_{i}, 1 ⩽ i ⩽ 4$ be the input of the i-round function F of step (2); then, we have $\begin{array}{c} (1) & X_{1} = P_{1}, \\ (2) & X_{2} = F (X_{1}) \oplus P_{2}, \\ \dots \\ (16) & X_{16} = F (X_{15}) \oplus X_{14} \oplus P_{16} . \end{array}$

Performing cache attacks for the function F, the attacker can learn the $4 \times 4$ bits of $X_{i}$ , $1 ⩽ i ⩽ 16$ . $P_{i}$ in Eqs (1)–(16) is unknown to the attacker. To eliminate $P_{i}$ , the attacker should consider step (3) of the subkey calculation. At the beginning of step (3), the P-array consists of ${P_{1}}^{'}$ , ${P_{2}}^{'}$ , and $P_{i}, 3 ⩽ i ⩽ 18$ , and there are no changes in the initial S-box. Step (3) encrypts ${P_{1}}^{'}$ and ${P_{2}}^{'}$ , first, and the results of the encryption are ${P_{3}}^{'}$ and ${P_{4}}^{'}$ , as shown in Fig. 7.

Note that the input of the first round of the function F is ${P_{1}}^{'} \oplus {P_{1}}^{'} = 0$ , and the input of the second round is $F (0) \oplus {P_{2}}^{'} \oplus {P_{2}}^{'} = F (0)$ . The attacker can calculate $F (0)$ and $F (F (0))$ because of the public initial S-box.

Let $Y_{i}, 1 ⩽ i ⩽ 16$ be the input of the i-round function F; then, we have $\begin{array}{c} (17) & Y_{1} = 0, \\ (18) & Y_{2} = F (0), \\ (19) & Y_{3} = F (Y_{2}) \oplus Y_{1} \oplus P_{3}, \\ \dots \\ (32) & Y_{16} = F (Y_{15}) \oplus Y_{14} \oplus Y_{16} . \end{array}$

To eliminate $P_{i}$ , we should use Eqs (1)–(16) to XOR Eqs (17)–(32); then, we have $\begin{array}{c} (33) & X_{3} \oplus Y_{3} = F (Y_{2}) \oplus Y_{1} \oplus F (X_{2}) \oplus X_{1}, \\ \dots \\ (46) & X_{16} \oplus Y_{16} = F (Y_{15}) \oplus Y_{14} \oplus F (X_{15}) \oplus X_{14} . \end{array}$

In Eq. (33), $4 \times 4$ bits of $X_{1}$ , $X_{2}$ , $X_{3}$ , and $Y_{3}$ are known to the attacker, while $Y_{1}$ and $Y_{2}$ are all known. Let $\begin{matrix} (47) & Z_{2} = F (Y_{2}) \oplus X_{1} \oplus Y_{1} \oplus X_{3} \oplus Y_{3} . \end{matrix}$ Then, $Z_{2} = F (X_{2})$ is called the leakage equation. The $4 \times 4$ bits of $Z_{2}$ are known. The attacker can recover $X_{2}$ by traversing the unknown 16 bits of $X_{2}$ and determining whether $F (X_{2})$ is consistent with the known bits of $Z_{2}$ . The solution of the leakage equation $Z_{2} = F (X_{2})$ is not necessarily unique. We further evaluate the number of solutions of the leakage equation in Section 4.

Then, the attacker exhausts the unknown $4 \times 4$ bits of $X_{1} = P_{1}$ and calculates $P_{2}$ by $P_{2} = F (P_{1}) \oplus X_{2}$ . When $X_{1}$ , $X_{2}$ , $Y_{1}$ , $Y_{2}$ , and $P_{1}$ , $P_{2}$ are determined, equation $\begin{matrix} (48) & X_{i} \oplus Y_{i} = F (Y_{i - 1}) \oplus Y_{i - 2} \oplus F (X_{i - 1}) \oplus X_{i - 2}, 4 ⩽ i ⩽ 16, \end{matrix}$ can be expressed as $\begin{matrix} (49) & \begin{aligned} X_{i - 2} \oplus Y_{i - 2} \oplus X_{i} \oplus Y_{i} = F (F (X_{i - 2}) \oplus X_{i - 3} \oplus P_{i - 1}) \oplus F (F (Y_{i - 2}) \oplus Y_{i - 3} \oplus P_{i - 1}), \\ 4 ⩽ i ⩽ 16. \end{aligned} \end{matrix}$ Let $\begin{matrix} (50) & Z_{i} = X_{i - 2} \oplus Y_{i - 2} \oplus X_{i} \oplus Y_{i} . \end{matrix}$ Then, the $4 \times 4$ bits of $Z_{i}$ can be calculated by the $4 \times 4$ bits of $X_{i - 2}$ , $Y_{i - 2}$ , $X_{i}$ , $Y_{i}$ ; then, we have $\begin{matrix} (51) & Z_{i} = F (c_{i 1} \oplus P_{i - 1}) \oplus F (c_{i 2} \oplus P_{i - 1}), \end{matrix}$ where $c_{i 1} = F (X_{i - 2}) \oplus X_{i - 3}$ , $c_{i 2} = F (Y_{i - 2}) \oplus Y_{i - 3}$ , and the $4 \times 4$ bits of $c_{i 1}$ , $c_{i 2}$ are known.

Because $P_{i - 1} = X_{i - 1} \oplus c_{i 1} = Y_{i - 1} \oplus c_{i 2}$ , the $4 \times 4$ bits of $P_{i - 1}$ can be calculated by $X_{i - 1}$ , $c_{i 1}$ , $Y_{i - 1}$ , $c_{i 2}$ . The attacker can recover $P_{i - 1}$ by traversing the unknown 16 bits of $P_{i - 1}$ and determining whether $F (c_{i 1} \oplus P_{i - 1}) \oplus F (c_{i 2} \oplus P_{i - 1})$ is consistent with the known bits of $Z_{i}$ . Then, according to $\begin{array}{c} (52) & X_{i} = F (X_{i - 1}) \oplus X_{i - 2} \oplus P_{i}, \\ (53) & Y_{i} = F (Y_{i - 1}) \oplus Y_{i - 2} \oplus P_{i}, \end{array}$

$X_{i - 1}$ , $Y_{i - 1}$ can be calculated. Similarly, the attacker can calculate $P_{i}$ by the leakage equation and $X_{i - 1}$ , $Y_{i - 1}$ . Equations (33)–(46) are called the leakage equation group. According to the leakage equation group, the attacker can obtain $P_{1}$ – $P_{15}$ . Because the solution of the leakage equation is not necessarily unique, the attacker may obtain multiple $P_{1}$ – $P_{15}$ . Section 3.3 discusses how to recover the key from multiple $P_{1}$ – $P_{15}$ . The process of constructing the leakage equation group and solving $P_{i}$ , $3 ⩽ i ⩽ 15$ , is shown in Fig. 8.

Fig. 8.

Constructing the leakage equation group and solving $P_{i}$ , $3 ⩽ i ⩽ 15$ .

3.3. Recovering the key

Exclude wrong solutions. There may be multiple solutions that satisfy the leakage equation; so, the attacker faces the problem of how to confirm the key in multiple $P_{1}$ – $P_{15}$ .

If $P_{1}$ – $P_{15}$ , $i \in [1, 15]$ are correct, then the next leakage equation is $\begin{matrix} (54) & Z_{i + 2} = F (c_{i + 2, 1} \oplus P_{i + 1}) \oplus F (c_{i + 2, 2} \oplus P_{i + 1}), \end{matrix}$ which must have one solution at least. According to the equivalence of the inverse negative proposition, as long as the leakage Eq. (54) has no solution, at least one of $P_{1}$ – $P_{15}$ , $i \in [1, 15]$ is wrong.

According to this conclusion, the attacker can establish the relationship among $P_{1}$ – $P_{15}$ , by constructing a solution tree of the leakage equation group. When a leakage equation has no solution, it goes back to the previous solution, as shown in Fig. 9, where the j-th guess of $P_{i}$ is denoted by $P_{i}^{(j)}, 1 ⩽ i ⩽ 15$ , $j ⩾ 1$ . The final output satisfies all the leakage equations. If the output is more than one, the attacker can use periodicity to recover the key.

Fig. 9.

Theoretical model of constructing the leakage equation solution tree.

Recovering the key by periodicity. The attacker must determine the key from all the solutions. At this point, the attacker can exploit the feature (2) of Blowfish, mentioned in Section 3, that is, the key recurrently XORs the initial P-array to generate $P_{1}$ – $P_{15}$ . This can be discussed in two cases:

Case 1: The length of the key is between 32 and 240 bits. Because the total length of $P_{1}$ – $P_{15}$ is 480 bits, the key is looped at least twice at step(1) of the subkey calculation of Blowfish. According to this, we make $P_{1}$ – $P_{15}$ XOR with initial P-array, the result calculated by the correct key will be periodic; otherwise, it will be random from someone byte, as shown in Fig. 10.

Fig. 10.

Recovering short key by periodicity.

Fig. 11.

Recovering long key by periodicity.

Case 2: The length of the key is between 240 and 448 bits. Owing to the limitations of Blowfish, the length of the key entered by the user is at most 448 $(= 14 \times 32)$ bits. This means that the result of the XOR between $P_{15}$ and the initial P-array must be a part of the key. Therefore, comparing the 417–448 bits of the sequence with the 1–416 bits, if there is exactly the same segment, the sequence is calculated by the correct solution. Otherwise, it is calculated by the wrong solution. We can approximately regard the sequence calculated by the wrong solution as random, and then, the probability of false positive is about $1 / 2^{32}$ , which is negligible. The process of recovering the long key is shown in Fig. 11.

3.4. Attack summary

Obtaining an accurate cache leakage, the attacker can recover any 32–448 bit variable key of Blowfish by constructing a leakage equation group, solving round keys $P_{1}$ – $P_{15}$ , and judging the periodicity of the XOR between $P_{1}$ – $P_{15}$ and the initial P-array. The steps of cache attack against Blowfish are as follows:

The attacker obtains the cache leakage of the subkey calculation via a cache attack;

The attacker constructs the leakage equation group according to the cache leakage and fixed value of the subkey calculation, including 14 leakage equations;

The attacker uses the first leakage equation to calculate $X_{2}$ , exhausts the unknown $4 \times 4$ bits of $P_{1}$ , and then calculates $P_{2}$ ;

The attacker uses the 2–14 leakage equations to determine $P_{i}$ , $3 ⩽ i ⩽ 15$ , sequentially, outputting the solution of the leakage equation group, which may not be unique;

The attacker recovers the key by periodicity.

Our attack does not rely on knowledge of plaintext and ciphertext. An attacker only needs to obtain the cache leakage during the subkey calculation to recover the key, which is very practical.

4. Cache attack leakage model for S-box

In the cache resource-sharing environment, the attacker can obtain some bits of input or output of an S-box through a cache attack. According to this feature, this section proposes a leakage model for cache attacks, which provides a theoretical basis for estimating the time complexity of cache attacks. This section uses the leakage model to evaluate the time complexity of the cache attack proposed in Section 3.

4.1. Probability description of leakage model

After obtaining some bits of input or output of each round S-box by cache attack, the attacker still faces a problem to recover the key:

How does the attacker estimate the time complexity of the attack and evaluate whether the cache attack is feasible for limited computing resources?

To evaluate the time complexity of cache attacks, this section proposes a leakage model. Suppose that the attacker exploits the cache attack to obtain the S-box input of t bits and the output of r bits. In the block cipher, an S-box is a bijective function. Consider that the event A is input X, output $Y = S (X)$ satisfies the known input t bits and output r bits in the probability space, and random variable N is the number of basic events in A. The expectation of N represents the exhaustive space size of the S-box input in the average sense. According to this, the attacker can further calculate the exhaustive space size and time complexity of the entire attack. Let $K^{'}$ be the exhaustive space of X (or Y) after a cache leakage. The leakage model is shown in Fig. 12.

Fig. 12.

Leakage model.

Let $G F^{n} (2)$ be an n-dimensional vector space over the finite field $G F (2) = {0, 1}$ . Sample space $Ω = {(x, y) | x = (x_{1}, x_{2}, \dots, x_{n}) \in G F^{n} (2), y = F (x)}$ . The S-box with n bits of input and output is regarded as the bijective function F, that is, $\begin{matrix} (55) & F : \{\begin{array}{l} G F^{n} (2) \to G F^{n} (2), \\ (x_{1}, x_{2}, \dots, x_{n}) \mapsto (y_{1}, y_{2}, \dots, y_{n}) . \end{array} \end{matrix}$

Let the σ-algebra of all subsets of Ω be $F$ , and P be a probability measure. Then, $(Ω, F, P)$ is a probability space following the properties below:

Property 1.

The sample space Ω contains $2^{n}$ basic events. For any $a = (a_{1}, a_{2}, \dots, a_{n}) \in G F^{n} (2)$ , we have $P (x = a) = 1 / 2^{n}$ , $P (y = a) = 1 / 2^{n}$ .

Property 2.

If $b = (b_{q_{1}}, b_{q_{2}}, \dots, b_{q_{r}}) \in G F^{r} (2)$ , $r ⩽ n$ , the probability of the event ${(x, y) | y = b}$ is $P (y = b) = P (y_{q_{1}} = b_{q_{1}}, y_{q_{2}} = b_{q_{2}}, \dots, y_{q_{r}} = b_{q_{r}}) = 2^{n - r} / 2^{n} = 1 / 2^{r}$ .

Property 3.

Let $P (x = a | y = b)$ be the conditional probability of event ${(x, y) | x = a}$ occurring, based on the occurrence of event ${(x, y) | y = b}$ . Then, for all $a = (a_{s_{1}}, a_{s_{2}}, \dots, a_{s_{t}} \in G F^{t} (2))$ , satisfy the following: $\begin{matrix} (56) & \sum_{a_{s_{1}}, a_{s_{2}}, \dots, a_{s_{t}} = (0, 0, \dots, 0)}^{(1, 1, \dots, 1)} P (x = a | y = b) = 1 \end{matrix}$

According to properties (1), (2), and (3), we have Proposition 1.

Proposition 1.

Given $b = (b_{q_{1}}, b_{q_{2}}, \dots, b_{q_{r}}) \in G F^{r} (2)$ , the random variable $ξ_{t}$ defines the sample space to a positive integer set. $ξ_{t}$ represents the number of basic events in the event ${(x, y) | x = a, y = b}$ , where $a = (a_{s_{1}}, a_{s_{2}}, \dots, a_{s_{t}} \in G F^{t} (2))$ . Then, $E (ξ_{t}) ⩽ 2^{n - r - t}$ .

Proof.

For $a = (a_{s_{1}}, a_{s_{2}}, \dots, a_{s_{t}} \in G F^{t} (2))$ , denote $k = \sum_{i = 1}^{t} s_{i} \cdot 2^{i}$ , $0 ⩽ k ⩽ 2^{t} - 1$ . Let $a_{k} = (a_{s_{1}}, a_{s_{2}}), \dots, a_{s_{t}}$ , $x = (x_{s_{1}}, x_{s_{2}}, \dots, x_{s_{t}})$ , $y = (y_{q_{1}}, y_{q_{2}}, \dots, y_{q_{r}})$ , $b = (b_{q_{1}}, b_{q_{2}}, \dots, b_{q_{r}})$ , and $N_{k}$ is the number of basic events in ${(x, y) | x = a_{k}, y = b}$ ; that is, $N_{k} = | {(x, y) | x = a_{k}, y = b} | = 2^{n} \cdot P (y = b) \cdot P (x = a | y = b)$ ; so, we have $\begin{aligned} E (ξ_{t}) & = \sum_{k = 0}^{2^{t} - 1} N_{k} \cdot P (ξ_{t} = N_{k}) ⩽ \sum_{k = 0}^{2^{t} - 1} N_{k} \cdot P (x = a_{k}) \\ = \sum_{a_{s_{1}}, a_{s_{2}}, \dots, a_{s_{t}} = (0, 0, \dots, 0)}^{(1, 1, \dots, 1)} \frac{2^{n} \cdot P (x = a | y = b)}{2^{r} \cdot 2^{t}} \\ = 2^{n - r - t} \cdot \sum_{a_{s_{1}}, a_{s_{2}}, \dots, a_{s_{t}} = (0, 0, \dots, 0)}^{(1, 1, \dots, 1)} P (x = a | y = b) \\ = 2^{n - r - t} . \end{aligned}$ □

According to Proposition 1, when the attacker knows the r bits of output and t bits of input, the expectation of the input number satisfies $E (ξ_{t}) ⩽ 2^{n - r - t}$ , that is, in the average sense, the number of $(x, y)$ that meets the known leakage condition is at most $2^{n - r - t}$ .

Proposition 1 gives the upper bound of the solution number of the leakage model in the average sense. The attacker exhausts the unknown bits of the input x and determines whether the output $y = F (x)$ satisfies the known r bits. If so, the $(x, y)$ will be recorded. In the average sense, the attacker can obtain at most $2^{n - r - t}$ input and output pairs $(x, y)$ corresponding to the exhaustive space of the intermediate value x (or y) of the ciphers. It is convenient for the attacker to evaluate the time complexity of the attack.

According to Section 3, the function F of Blowfish consists of four known initial S-boxes. Through a cache attack and by constructing the leakage equation group, the attacker can obtain the $4 \times 4$ bits of the function F input and output. According to Proposition 1, the number of $(x, y)$ that meets the known leakage condition is at most 1 in the average sense.

4.2. Time complexity estimation of cache attack against Blowfish

According to the conclusions in Sections 3 and 4.1, the time complexity estimation for the cache attack against Blowfish consists of the following parts:

Let the time complexity of steps (1) and (2) of the attack be $O (n)$ , and the time complexity of step (5) be $O (m)$ , where n and m are constants. n is determined by the experimental scenario, while m is determined by the number of leakage equation solutions.

In step (3), the attacker must first exhaust the unknown $4 \times 4$ bits of $P_{1}$ . $X_{1}$ , $X_{2}$ , $Y_{1}$ , $Y_{2}$ , and $P_{2}$ are calculated by $P_{1}$ . So, the time complexity of step (3) is $O (2^{16})$ .

In step (4), the attacker calculates $P_{i}$ by $X_{i - 1}$ , $X_{i - 2}$ , $Y_{i - 1}$ , $Y_{i - 2}$ , $P_{i - 1}$ , $P_{i - 2}$ . It must exhaust the unknown $4 \times 4$ bits of $P_{i}$ and judge whether $P_{i}$ satisfies the leakage equations. According to Section 4.1, the solution number of the leakage equation is at most one in the average sense. So, the time complexity of step (4) is estimated to be $O (13 \cdot 2^{16}) \approx O (2^{20})$ .

The overall time complexity of the attack is estimated to be $O (2^{36}) + O (n) + O (m)$ , where $O (n)$ and $O (m)$ can be negligible.

Therefore, attackers do not need a lot of computing resources to perform cache attacks against Blowfish. It is entirely possible to complete the attack on a personal laptop.

4.3. Application in other block ciphers

In cache sharing environment, attackers always choose S-box of block ciphers as the attack target. Block cipher implementations often use lookup tables to complete S-box. The lookup table of non-lightweight block ciphers must be stored in multiple cache lines, which leads to leakage. If the size of cache line is 64 bytes and an attacker has got cache leakage, the estimation for the S-box input exhausting space of various block ciphers is shown in Table 2.

Table 2
Comparison of various block ciphers on the estimation of S-box input exhausting space with a cache leakage

Algorithm Structure Target Input size (bit) Output size (bit) Storage size (B) Cacheline occupation Leakage size (bit) Estimation space

AES SPN S-box 8 8 256 4 2 $2^{4}$

AIRA SPN S-box 8 8 256 4 2 $2^{4}$

Pilsung SPN S-box 8 8 256 4 2 $2^{4}$

SM4 Feistel S-box 8 8 256 4 2 $2^{4}$

Camellia Feistel S-box 8 8 256 4 2 $2^{4}$

MISTY1 Recursive S7 7 7 128 2 1 $2^{5}$

MISTY1 Recursive S9 9 9 1024 16 4 2

Blowfish Feistel Four S-boxes 8 32 1024 16 4 1

Algorithm	Structure	Target	Input size (bit)	Output size (bit)	Storage size (B)	Cacheline occupation	Leakage size (bit)	Estimation space
AES	SPN	S-box	8	8	256	4	2	$2^{4}$
AIRA	SPN	S-box	8	8	256	4	2	$2^{4}$
Pilsung	SPN	S-box	8	8	256	4	2	$2^{4}$
SM4	Feistel	S-box	8	8	256	4	2	$2^{4}$
Camellia	Feistel	S-box	8	8	256	4	2	$2^{4}$
MISTY1	Recursive	S7	7	7	128	2	1	$2^{5}$
MISTY1	Recursive	S9	9	9	1024	16	4	2
Blowfish	Feistel	Four S-boxes	8	32	1024	16	4	1

According to the estimation for the S-box input exhausting space, attackers can evaluate whether their computing resources are sufficient to support cache attacks against the specific cipher. If not, the attacker must obtain more cache leakage of encryption to reduce the exhausting space of S-box input. The more leakages an attacker needs, the weaker the attack scenario will be.

5. Experimental results

The experiments in this section were conducted in Intel(R)Core(TM)i5-8265U CPU with 64-byte cache line and targeted the implementation of Blowfish in OpenSSL 1.1.1h. According to Section 2.1, Blowfish’s S-box is stored in 16 cache lines. We randomly generated a 32-bit key and 448-bit key for the experiment.

First, we entered the OpenSSL folder and found the libcrypto.so and then found the storage location of bf_init in libcrypto.so. According to Section 3.2, the input of the function F appeared as 0 and $F (0)$ during the subkey calculation, which enabled the attacker to locate the cache leakage. If there was cache leakage of 0 and $F (0)$ , it indicated the beginning of step (3) of the subkey calculation. The cache leakage of the 16 rounds before and 14 rounds after was the focus of the attacker.

We used Flush + Reload and Prime + Probe to obtain the cache leakage. The Flush + Reload attack first used the clflush instruction to clear the S-box of Blowfish out of cache. After waiting for the victim to access, we reloaded the 16 cache lines’ memory addresses sequentially and timing. If the reload time was short(about 30 ns), the victim had accessed the cache line. The Prime + Probe attack first constructed an eviction set for the S-box. Then, we accessed the eviction set and primed it into the cache. After waiting for the victim to access, we probed the eviction set and time again. If the probe time was long (over 300 ns), the victim had accessed the cache line during the wait. To avoid the error of cache attacks, we calculated the access delay by measuring and averaging multiple times. The access delay of the subkey calculation of the Blowfish is shown in Figs 13 and 14. $F_{i, j}$ represents the j-th round of the i-th encryption. The lighter the color, the shorter the access delay. The darker the color, the longer the access delay.

Fig. 13.

Flush + Reload attack obtained the cache leakage of the subkey calculation. The unit of delay is milliseconds. The test key is ‘0x54454b49’.

Fig. 14.

Prime + Probe attack obtained the cache leakage of subkey calculation. The unit of delay is milliseconds. The test key is ‘0x54454b49’.

According to the cache leakage of the subkey calculation, the attacker could obtain the $4 \times 4$ bits of the function F input during each round of encryption, as shown in Table 3.

Table 3

Intermediate value of subkey calculation of Blowfish via cache attacks, ‘u’ means unknown for the attacker

Intermediate value	Leakage	Intermediate value	Leakage
$X_{1}$	7u7u3udu	$Y_{1}$	00000000
$X_{2}$	fu2u5u3u	$Y_{2}$	2fcff51e
$X_{3}$	7u8ubu4u	$Y_{3}$	2ucu5u0u
$X_{4}$	6ueu3u0u	$Y_{4}$	1u2u2u2u
$X_{5}$	9u3u9uFu	$Y_{5}$	4udu5uEu
$X_{6}$	cuducu4u	$Y_{6}$	du9u0u3u
$X_{7}$	6u5u6u7u	$Y_{7}$	au5ufueu
$X_{8}$	4ucu9u5u	$Y_{8}$	4u6ucuau
$X_{9}$	7ueueu2u	$Y_{9}$	8u3ucufu
$X_{10}$	5u9u3u0u	$Y_{10}$	3ueu2u9u
$X_{11}$	9ubu9u7u	$Y_{11}$	bu4u6ubu
$X_{12}$	3u0u2udu	$Y_{12}$	1u2ueu8u
$X_{13}$	fu5u4ubu	$Y_{13}$	2u0u0u0u
$X_{14}$	0u2u7u5u	$Y_{14}$	du0u1u1u
$X_{15}$	du4ueu3u	$Y_{15}$	eu1u7ufu
$X_{16}$	5udu8udu	$Y_{16}$	bu5u3udu

$4 \times 4$ bits of $X_{1}$ , $X_{2}$ , $X_{3}$ , and $Y_{3}$ and 32 bits of $Y_{1}$ and $Y_{2}$ were known to the attacker. According to $X_{3} \oplus Y_{3} = F (Y_{2}) \oplus Y_{1} \oplus F (X_{2}) \oplus X_{1}$ , let $Z_{2} = F (Y_{2}) \oplus X_{1} \oplus Y_{1} \oplus X_{3} \oplus Y_{3}$ . The attacker could recover $X_{2}$ by traversing the unknown 16 bits of $X_{2}$ and determining whether $F (X_{2})$ was consistent with the known bits of $Z_{2}$ . The $X_{2}$ was ‘0xf92d5630’ in this experiment. Then, the attacker exhausted the unknown $4 \times 4$ bits of $X_{1} = P_{1}$ and calculated $P_{2}$ by $P_{2} = F (P_{1}) \oplus X_{2}$ .

When $X_{1}$ , $X_{2}$ , $Y_{1}$ , $Y_{2}$ , and $P_{1}$ , $P_{2}$ were determined, the attacker could establish the relationship of $P_{i}$ , $1 ⩽ i ⩽ 15$ by constructing a solution tree of the leakage equation group. When a leakage equation had no solution, it goes back to the previous solution. In this experiment, the detailed process of constructing the leakage equation solution tree is shown in the Appendix. The outputs satisfied all the leakage equations, as shown in Table 4.

Table 4

Solutions of the leakage equation group of the 32-bit key ‘0x54454b49’. The six solutions have the same $P_{1}$ – $P_{10}$ but different $P_{11}$ – $P_{15}$

$P_{1}$ – $P_{5}$	0x707a39dc,cee65187,564ade65,46292701,f75d7367
$P_{6}$ – $P_{10}$	0x70cb7483,05c65bfc1,b80b3fdd,0e6d78b2,7d83473c
$P_{11}$	0xf7053689	0xfb0d328a
$P_{12}$	0x03a8bcf1	0x67bd4729
$P_{13}$	0x7c2a7960	0x92f665ee			0x99f86ce4
$P_{14}$	0xdfd609af	0xad13dbfa		0xa21fd5f8	0x9c351d8c	0x9d371584
$P_{15}$	0x6bc186e1	0x2f03e3d4	0x1d08ebd1	0x1d08ebd1	0x26affbce	0x6bc186e1

In order to prove the universality of the attack method, we randomly generated a 448-bit key ‘0x28bbc561bab3d6d9be0309c73dcf1783cc0c8daa97fa4e048895a556fc354aaa35fa7215c17613d158457f6bdbb81eae7617dcc46c7c0090b’. The process of obtaining cache leakages and constructing leakage equation group was the same as above. The detailed process of constructing the leakage equation solution tree was shown in the Appendix. The outputs satisfied all the leakage equations, as shown in Table 5.

Table 5

Solutions of the leakage equation group of the 448-bit key. The five solutions have the same $P_{1}$ – $P_{10}$ but different $P_{11}$ – $P_{15}$ .*

$P_{1}$ – $P_{5}$	0x0c84afe9,3f10de0a,ad1a83e9,3ebf64c7,68c1e28b
$P_{6}$ – $P_{10}$	0x563bd198,8174aff7,2f1ac62a,1a8f00ba,2fb12e62,3a039072
$P_{12}$	0x8f68e68b		0x8c69ea81
$P_{13}$	0xa1d1e5f1		0x7d50e11e
$P_{14}$	0x0ebc59d3		0xa0e6a431	0xadecab37
$P_{15}$	0x1f3119d2	0x173f10d4	0xcc62a5ca	0x03cfda48	0x08c2da40

After obtaining all the solutions of the leakage equation group, we XORed $P_{1}$ – $P_{15}$ with the initial P-array to obtain a set of sequences. According to Section 3.3, if $P_{1}$ – $P_{15}$ were correct, the key sequence generated by $P_{1}$ – $P_{15}$ would be periodic. Therefore, when the key sequence was periodic, it was considered to be the cycle of the key. Otherwise, the next leakage equation solution would be verified. This is shown in Figs 15 and 16.

Fig. 15.

Recovering the random 32-bit key.

Fig. 16.

Recovering the random 448-bit key.

Fig. 17.

Blowfish encryption in ECB or CBC mode.

Finally, the attacker could recover the variable key of Blowfish in 4 minutes, regardless of the length of the key.

6. Extension

We attempted to extend our attack to applications that use Blowfish as the underlying encryption algorithm. To do this, we found more than 1,000 applications on GitHub which use Blowfish and selected two representative ones, JavaScript-blowfish and Bcrypt, to perform our attack.

6.1. JavaScript-blowfish

JavaScript-blowfish (https://github.com/agorlov/javascript-blowfish) is a browser application developed by Alexandr Gorlov in 2017, which can run well in various browsers. JavaScript-blowfish uses Blowfish in ECB or CBC mode to encrypt user-inputted text or binary data, as shown in Fig. 17.

After the user inputs the key, JavaScript-blowfish performs the subkey calculation of Blowfish. Since JavaScript-blowfish statically stores S-box, it is easy for the attacker to find its memory address, which is the target for cache attacks. Then, the attacker performs Flush + Reload or Prime + Probe attack to obtain cache leakage during the subkey calculation. Afterwards, the attacker utilizes the method in Section 3 to construct the equation group by the fixed values and cache leakage of subkey calculation and can recover the key from the solution space by periodicity.

For the ECB mode of Blowfish, it is easy to recover the plaintext if the attacker recovers the key. Firstly, the ciphertext is divided into 64-byte blocks, and for each 64-bit ${ciphertext}_{i}$ , performing Blowfish decryption can recover ${plaintext}_{i}$ . For the CBC mode of Blowfish, again, the ciphertext is divided into 64-byte blocks, denoted as ${ciphertext}_{1}$ , ${ciphertext}_{2}$ , …, ${ciphertext}_{n}$ . First, the attacker performs Blowfish decryption on the last 64 bytes ${ciphertext}_{n}$ , and the result XOR with ${ciphertext}_{n - 1}$ to recover ${plaintext}_{n}$ . Repeating this process, the attacker can gradually recover ${plaintext}_{n}$ , ${plaintext}_{n - 1}$ , …, ${plaintext}_{2}$ . However, since we do not know the value of the initialization vector (IV), we cannot currently recover ${plaintext}_{1}$ . From the perspective of cryptography, the IV should be a random number, and each encryption should use a different IV. However, in practical applications, developers may sometimes set the IV to a fixed value for efficiency or convenience. In the JavaScript-blowfish case, we found that the developer has set the IV at line 136, and it is a fixed value of ‘abc12345’. With the IV, ${ciphertext}_{1}$ , and the key, we can calculate ${plaintext}_{1}$ , as shown in Fig. 18.

Fig. 18.

Blowfish decryption in ECB or CBC mode.

Overall, in our threat model, our attack can recover the key of JavaScript-blowfish and any message input by users.

6.2. BCrypt

Bcrypt (https://github.com/bcrypt-ruby/bcrypt-ruby) is a password hashing function based on Blowfish. It is widely used for storing passwords and performing authentication. Bcrypt is the default password hashing algorithm for OpenBSD and other systems, including some Linux distributions such as SUSE Linux. Bcrypt can be applied in various scenarios that require storing passwords or performing authentication, such as:

User Registration: When a user registers, his password needs to be hashed before being stored in the database.

User Login: When a user logs in, his inputted password is compared with the hashed value stored in the database to determine if the password is correct.

Password Reset: When a user forgets their password, Bcrypt can generate a new hashed value for resetting the password.

While MD5, SHA series, and other hash algorithms can also be used for password encryption, they have a common disadvantage, in that the same input generates a constant hash value. This creates opportunities for brute force attacks or Rainbow Table attacks. However, Bcrypt has an important feature: each generated hash value is different. This is because Bcrypt enhances password security by using a random ‘salt’ and iteration count ‘cost’ during the hash calculation process.

Salt: In order to prevent rainbow table attacks, Bcrypt generates a random salt value. The salt value is concatenated with the password before hashing. It consists of 22 printable characters and its purpose is to produce different hash results for the same password under different salt values, thereby increasing the difficulty of password cracking.

Cost: Bcrypt performs multiple iterations of hashing on the password and salt. The number of iterations is determined by the cost value. A higher cost value corresponds to more iterations, which increases the difficulty of password cracking. It is generally recommended to set the cost value to 12, which provides a balance between security and performance.

Bcrypt can be represented as: output = bcrypt(cost, salt, key). The “cost” is the number of iterations, the “salt” is a random value, and the “key” is the password. For attacks, we only focus on the subkey calculation of Bcrypt. Bcrypt utilizes the Blowfish at its core for encryption. Therefore, after the user inputs the key, the subkey calculation is performed as follows:

Initialize the P-array and S-box with the key and perform the subkey calculation of Blowfish, resulting in $P^{'}$ and $S^{'}$ ;

Initialize $P^{'}$ and $S^{'}$ with the salt, and perform the subkey calculation again, resulting in $P^{″}$ and $S^{″}$ .

In our threat model, when a user registers, logs in, or resets his password, Bcrypt will generate a hash value. At the same time, the attacker monitors the memory addresses of the S-box and performs Flush + Reload or Prime + Probe attack to obtain cache leakage. Based on the calculation process of Bcrypt, we divide our attack into two steps:

Performing the attack described in Section 3 on step (1) of Bcrypt to recover the key.

Using the key to computing $P^{'}$ and $S^{'}$ and performing the attack described in Section 3 on step (2) of Bcrypt to recover the salt.

At this stage, the only unknown parameter for the attacker is the cost, and he knows that the larger the cost value, the more iterations performs, resulting in a longer execution time of Bcrypt. Therefore, the attacker can utilize a simple timing attack to recover the cost value. We execute Bcrypt 1,000 times with different cost values and calculate the average. The relationship between the cost value and the execution time of Bcrypt is shown in Fig. 19.

Fig. 19.

Linear relationship between cost value and execution time of Bcrypt.

Therefore, in our threat model, an attacker can utilize cache attacks and timing attacks to obtain all the private parameters of Bcrypt—cost, salt and key, and subsequently calculate the output of Bcrypt, which is stored in the database. This means that the attacker has completely impersonated the user’s identity.

6.3. Other applications

We have studied other applications on GitHub, including Puff-Android, erlang-bcrypt, PHP-Blowfish, python-blowfish, Browsers-Blowfish, PyElliptic, ElnurBlowfishPasswordEncoderBundle, blowfish-csharp, etc. These applications all require a large memory space of 1 KB to store the S-boxes. Therefore, in our threat model, these applications are severely vulnerable to cache attacks. The key of underlying Blowfish is easily recovered by attackers, resulting in serious information leakage.

7. Discussion

7.1. Comparison of cache attack methods

We compare several cache attacks against ciphers. Due to the construction of leakage model and the full use of leakage, our attack does not need any knowledge about plaintext or ciphertext, and only needs a set of accurate cache leakage to recover the key of Blowfish, as shown in Table 6.

Table 6
Comparison of cache attacks against various ciphers

Target cipher S-box Development Cache attack method Knowledge Number of encyption to recover the key

AES Fixed [3] Timing measurement Plaintext $2^{14.6}$

[13] Prime + Probe Ciphertext 150,000

[10] Flush + Reload None 100

ARIA Fixed [2] Flush + Reload Ciphertext 20

SM4 Fixed [17] Flush + Reload Plaintext 5000

MISTY1 Fixed [7] Flush + Reload None 10

Pilsung Key-dependent [9] Prime + Probe Plaintext 19,472

Blowfish Key-dependent This paper Flush + Reload and Prime + Probe None 1

Target cipher	S-box	Development	Cache attack method	Knowledge	Number of encyption to recover the key
AES	Fixed	[3]	Timing measurement	Plaintext	$2^{14.6}$
[13]	Prime + Probe	Ciphertext	150,000
[10]	Flush + Reload	None	100
ARIA	Fixed	[2]	Flush + Reload	Ciphertext	20
SM4	Fixed	[17]	Flush + Reload	Plaintext	5000
MISTY1	Fixed	[7]	Flush + Reload	None	10
Pilsung	Key-dependent	[9]	Prime + Probe	Plaintext	19,472
Blowfish	Key-dependent	This paper	Flush + Reload and Prime + Probe	None	1

7.2. Countermeasures

We have summarized countermeasures against cache attacks, categorized into hardware-level and software-level countermeasures.

Hardware-level countermeasures: One approach is to partition shared resources to prevent processes from interfering with each other. The simplest method is to divide the cache into multiple partitions per way and allocate them exclusively to different processes, such as static partitioned cache [12] and dynamic partitioned cache [5].

Another approach is resource randomization. Random permutation cache [26] maintains dynamic and random memory to cache mapping tables for each process to ensure that the accessed set is unpredictable. For example, the CEASER cache [21] proposed by Moinuddin encrypts and remaps the addresses of memory rows, effectively reducing the probability of conflicts caused by cache misses. Later, Moinuddin designed an improved version called CEASER-S [22], which partitions the cache into multiple sets and adopts random placement among these sets, further increasing the uncertainty of memory-to-cache mappings.

The hardware countermeasures have limitations in terms of applicability. For efficiency or other reasons, main CPU manufacturers such as Intel and ARM do not excessively use countermeasures proposed by academia. Even if these measures are implemented, they may still face challenges from improved cache attacks. For instance, a probabilistic cache attack method [24] was proposed in the literature (citation needed), which targeted randomized cache structures and breached the protection offered by CEASER-S.

Software-level countermeasures: One approach is to use shift and XOR operations instead of lookup tables for S-box. For example, [1] introduces improvements to AES using this method. Another approach involves using masking schemes to conceal the side channel leakage of critical information. For instance, many masking schemes of AES has been proposed [13,18].

Unfortunately, software-level countermeasures need to be specifically designed for each algorithm. Unlike AES, which has received significant attention, neither of the aforementioned software countermeasures has been tailored for the Blowfish. Our investigation on GitHub indicates that most applications implementing Blowfish still rely on large lookup tables, making them vulnerable to serious security threats posed by cache attacks.

8. Conclusions

The results of this study indicate that in the case of Blowfish, key-dependent P-array and S-box do not provide internal protection against side-channel attacks. The attacker does not need any knowledge about plaintext or ciphertext and only needs a set of accurate cache leakage to recover the key. This result indicates that Blowfish is seriously threatened by cache attacks in a resource-sharing scenario, such as the cloud. Our work indicates that, within our threat model, Blowfish faces significant threats from cache attacks. Therefore, we do not recommend using Blowfish in resource-sharing scenarios, such as cloud platforms.

Footnotes

Acknowledgment

This paper is supported by Henan Key Laboratory of Network Cryptography Technology (No. LNCT2020-A03) and National Engineering Laboratory for Big Data Distribution and Exchange Technologies.

Constructing the leakage equation solution tree

The experimental random 32-bit key is ‘0x54454b49’ (Fig. 20) and the random 448-bit key is ‘0x28bbc561bab3d6d9be0309c73dcf1783cc0c8daa97fa4e048895a556fc354aaa35fa7215c17613d158457f6bdbb81eae7617dcc46c7c0090b’ (Fig. 21). The attacker uses the cache leakage of subkey calculation to construct the leakage equation solution tree. When a leakage equation has no solution, it goes back to the previous equation solution. The output solutions of the tree satisfy all leakage equations. The blue line represents the correct path.

References

Adomnicai and

Peyrin, Fixslicing AES-like ciphers: New bitsliced AES speed records on ARM-Cortex M and RISC-V, Cryptology ePrint Archive 11 (2020), 1–23.

Bae,

Hwang and

Ha, Flush + Reload cache side-channel attack on block cipher ARIA, J Korea Inst Inf Secur Cryptol 6 (2020), 1207–1216.

Bonneau and

Mironov, Cache-collision timing attacks against AES, in: International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2006), Springer, Berlin, Heidelberg, 2006, pp. 201–215. doi:10.1007/11894063_16.

Brotzman,

Liu,

Zhang,

Tan and

Kandemir, CaSym: Cache aware symbolic execution for side channel detection and mitigation, in: 2019 IEEE Symposium on Security and Privacy (SP 2019), San Francisco, 19–23 May, USENIX Association, 2019, pp. 505–521. doi:10.1109/SP.2019.00022.

Domnitser,

Jaleel,

Loew,

Abu-Ghazaleh and

Ponomarev, Non-monopolizable caches: Low-complexity mitigation of cache side channel attacks, ACM Transactions on Architecture and Code Optimization (TACO) 4 (2012), 1–21.

Doychev,

Köpf,

Mauborgne and

Reineke, Cacheaudit: A tool for the static analysis of cache side channels, Transactions on information and system security (TISSEC) 1 (2015), 1–32.

Fan,

Wang and

Wang, Cache attack on recursive structure of MISTY1, in: 2022 IEEE 6th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC’22), Beijing, China, 3–5 Oct, IEEE, 2022, pp. 31–43. doi:10.1109/IAEAC54830.2022.9929896.

Fox and

J.W.

De Fockert, Negative priming depends on prime-probe similarity: Evidence for episodic retrieval, Psychon Bull Rev 5 (1998), 107–113. doi:10.3758/BF03209464.

Genkin,

Poussier,

R.Q.

Sim,

Yarom and

Zhao, Cache vs. key-dependency: Side channeling an implementation of Pilsung, in: International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2020), Springer, Beijing, China, 2020, pp. 231–255.

10.

Gullasch,

Bangerter and

Krenn, Cache games – bringing access-based cache attacks on AES to practice, in: 2011 IEEE Symposium on Security and Privacy (SP 2020), Oakland, USA, 22–25 May, IEEE, 2011, pp. 490–505. doi:10.1109/SP.2011.22.

11.

M.K.

Hasan,

Shafiq,

Islam,

Pandey,

Y.A.

Baker El-Ebiary,

N.S.

Nafi et al., Lightweight cryptographic algorithms for guessing attack protection in complex Internet of Things applications, Complexity 1 (2021), 1–13.

12.

He and

Lee, How secure is your cache against side-channel attacks? in: The 50th Annual IEEE/ACM International Symposium, New York, 14–18 Oct, IEEE, 2017, pp. 341–353.

13.

Irazoqui,

Eisenbarth and

Sunar, S$A: A shared cache attack that works across cores and defies VM sandboxing – and its application to AES, in: 2015 IEEE Symposium on Security and Privacy (SP 2015), San Jose, USA, 17–21 May, IEEE, 2015, pp. 591–604. doi:10.1109/SP.2015.42.

14.

S.W.

Jang, Comparative analysis of AES, Blowfish, Twofish and Threefish encryption algorithms, Anal Appl Math 10 (2017), 5–24.

15.

Kelsey,

Schneier,

Wagner and

Hall, Side channel cryptanalysis of product ciphers, J Comput Secur 8 (2000), 141–158. doi:10.3233/JCS-2000-82-304.

16.

Liu,

Yarom,

Ge,

Heiser and

R.B.

Lee, Last-level cache side-channel attacks are practical, in: 2015 IEEE Symposium on Security and Privacy (SP 2015), San Jose, USA, 17–21 May, IEEE, 2015, pp. 605–622. doi:10.1109/SP.2015.43.

17.

Lou,

Zhang,

Xu,

Liang,

Zhao,

Guo et al., Enhanced differential cache attacks on SM4 with algebraic analysis and error-tolerance, in: Information Security and Cryptology, Springer, Cham, Switzerland, 2020, pp. 480–496. doi:10.1007/978-3-030-42921-8_29.

18.

Ming,

Zhou,

Li and

Zhang, A secure and highly efficient first-order masking scheme for AES linear operations, Cybersecurity 4 (2021), 1–15. doi:10.1186/s42400-021-00099-1.

19.

Neve and

J.P.

Seifert, Advances on Access-Driven Cache Attacks on AES. Selected Areas in Cryptography, Springer, Berlin, 2007, pp. 147–162.

20.

Poddar,

Datta and

Rebeiro, A Cache Trace Attack on CAMELLIA. Security Aspects in Information Technology, Springer, Berlin, 2011, pp. 144–156.

21.

M.K.

Qureshi, CEASER: Mitigating conflict-based cache attacks via encrypted-address and remapping, in: 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), Fukuoka, 20–24 Oct, IEEE, 2018, pp. 775–787. doi:10.1109/MICRO.2018.00068.

22.

M.K.

Qureshi, New attacks and defense for encrypted-address cache, in: 2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA), Phoenix, 22–26 June, IEEE, 2019, pp. 360–371.

23.

Schneier, Description of a new variable-length key, 64-bit block cipher (Blowfish), in: Fast Software Encryption, Springer, Berlin, 1994, pp. 191–204.

24.

Song,

Li,

Xue,

Li,

Wang and

Liu, Randomized last-level caches are still vulnerable to cache side-channel attacks! But we can fix it, in: 2021 IEEE Symposium on Security and Privacy (SP 2021), San Francisco, 19–23 May, IEEE, 2021, pp. 955–969. doi:10.1109/SP40001.2021.00050.

25.

Tsunoo,

Saito,

Suzaki,

Shigeri and

Miyauchi, Cryptanalysis of DES Implemented on Computers with Cache. International Workshop on Cryptographic Hardware and Embedded Systems (CHES 2003), Springer, Berlin, 2003, pp. 62–76.

26.

Werner,

Unterluggauer,

Giner,

Schwarz,

Gruss and

Mangard, in: Proceedings of 28th USENIX Conference on Security Symposium (SEC’19), Santa Clara, 14–16 Aug, USENIX Association, 2019, pp. 675–692.

27.

Yarom and

Falkner, FLUSH + RELOAD: A high resolution, low noise, L3 cache side-channel attack, in: 23th USENIX Conference on Security Symposium (SEC’14), San Diego, 20–22 Aug, USENIX Association, 2014, pp. 719–732.