2111.08404v1

## Practical Timing Side Channel Attacks on Memory Compression Martin Schwarzl Graz University of Technology martin.schwarzl@iaik.tugraz.at Pietro Borrello Sapienza University of Rome borrello@diag.uniroma1.it Michael Schwarz CISPA Helmholtz Center for Information Security michael.schwarz@cispa.saarland Abstract -Compression algorithms are widely used as they save memory without losing data. However, elimination of redundant symbols and sequences in data leads to a compression side channel. So far, compression attacks have only focused on the compression-ratio side channel, i.e. , the size of compressed data, and largely targeted HTTP traffic and website content. In this paper, we present the first memory compression attacks exploiting timing side channels in compression algorithms, targeting a broad set of applications using compression. Our work systematically analyzes different compression algorithms and demonstrates timing leakage in each. We present Comprezzor, an evolutionary fuzzer which finds memory layouts that lead to amplified latency differences for decompression and therefore enable remote attacks. We demonstrate a remote covert channel exploiting small local timing differences transmitting on average 643 . 25bit ♥ h over 14 hops over the internet. We also demonstrate memory compression attacks that can leak secrets bytewise as well as in dictionary attacks in three different case studies. First, we show that an attacker can disclose secrets co-located and compressed with attacker data in PHP applications using Memcached. Second, we present an attack that leaks database records from PostgreSQL, managed by a Python-Flask application, over the internet. Third, we demonstrate an attack that leaks secrets from transparently compressed pages with ZRAM, the memory compression module in Linux. We conclude that memory-compression attacks are a practical threat. ## I. INTRODUCTION Data compression plays a vital role for performance and efficiency. For example, compression leads to smaller data footprints, allowing more data to be stored in memory. Memory accesses are typically faster than retrieving data from slower mediums such as hard disks or solid-state disks. As a result, both Microsoft [63] and Apple [3] rely on memory compression in their operating systems (OSs) to better utilize memory. Similarly, memory compression is also used in databases [46] or keyvalue stores [45]. Compression can also increase performance when storing or transferring data on slow mediums. Hence, data compression is also widely used for HTTP traffic [41], [15] and file-system compression [6]. While compression has many advantages, it is problematic in scenarios where sensitive data is compressed [49], [20], [4], [58], [57], [32]. Attacks such as CRIME [49], BREACH [20], Gururaj Saileshwar Georgia Tech Graz University of Technology gururaj.s@gatech.edu Hanna M¨ uller Graz University of Technology h.mueller@student.tugraz.at Daniel Gruss Graz University of Technology daniel.gruss@iaik.tugraz.at TIME [4], or HEIST [58], exploit the combination of encryption and compression in TLS-encrypted HTTP traffic. Karaskostas et al. [32] extended BREACH to commonly used ciphers, such as AES. These attacks demonstrated that an attacker could learn secrets when they are compressed together with attacker-controlled input. However, all these attacks focused on web traffic and only exploited differences in the compressed size of data. The size of compressed data is either accessed directly [49], e.g., in a man-in-the-middle (MITM) attack or indirectly by observing the impact of the compressed size on the transmission time [4]. Although attacks exploiting the compression ratio were first described by Kelsey et al. [33] in 2002, most attacks thus far have focused on compressed web traffic. Surprisingly, security implications of compression in other settings, such as virtual memory and file systems, have not been studied thoroughly. Also, compression fundamentally provides a reduction in size of data at the expense of additional time required for compression and decompression. However, so far, only the result of the compression, i.e. , the compressed size, has been exploited to leak data but not the time consumed by the process of compression or decompression itself. In this paper, we demonstrate that the decompression time also leaks information about the compressed data. Instead of focussing on the final compressed data, we measure the time it takes to decompress data. Hence, we do not need to observe the transport of the compressed data. Decompression timing can be measured in several scenarios, e.g., a simple read access to the data can suffice for compressed virtual memory or file systems. Moreover, decompression timings can be observed remotely, even when the compressed data never leaves the victim system. We systematically analyzed six compression algorithms, including widely-used algorithms such as DEFLATE (in zlib), PGLZ (in PostgreSQL), and zstd (by Facebook). We observe that the decompression time not only correlates with the entropy of the uncompressed data, but also with various other aspects, such as the relative position or alignment of compressible data. In general, these timing differences arise due to the design of the compression algorithm and its implementation. To explore these parameters in an automated fashion, we introduce Comprezzor, an evolutional fuzzer. In line with previous attacks on compression, Comprezzor assumes that parts of the compressed data are controlled by an attacker. Based on this assumption and a target secret, Comprezzor searches for a memory layout that maximizes the timing differences for decompression timing attacks. As a result, Comprezzor discovers a memory layout for compression algorithms which leads to decompression timing attacks with high-latency differences up to three orders of magnitude higher than manually discovered layouts. Based on the results of Comprezzor, we present three case studies demonstrating that these timing differences can be exploited in realistic scenarios to leak sensitive data. We demonstrate that these timing differences can be exploited even in remote attacks on an in-memory database system without executing code on the victim machine and without observing the victim's network traffic. Hence, our case studies show that compressing sensitive data poses a security risk in any scenario using compression and not just for web traffic. In the first case study, we build a remote covert channel which works across 14 hops on the internet, abusing the memory compression of Memcached, an in-memory object caching system. By measuring the execution time of a public PHP API of an application using Memcached, we can covertly transfer data between two computers at an average transmission rate of 643 . 25 bit ♥ h with an error rate of only 0 . 93 % . In a similar setup, we also demonstrate the capability of leaking a secret bytewise co-located with data compressed by a PHP application into Memcached, in 31 . 95 min ( n 20 , σ 8 . 48% ) over the internet. Using a dictionary with 100 guesses, we leak a 6 B -secret in 14 . 99 min . In the second case study, we exploit the transparent database compression of PostgreSQL. Our exploit leaks database records from an inaccessible database table of a remote web app. We show that as long as an attacker can co-locate data with a secret, it is possible for the attacker to influence and observe decompression times when accessing the data, thus, leaking secret data. Such a scenario might arise if structured data, i.e. , JSON documents, are stored with attack-controlled fields into a single cell. Using an attack that leaks a secret bytewise, we leak a 6 B -secret in 7 . 85 min . Our dictionary attack runs in 8 . 28 min on average over the internet for 100 guesses. In the third case study, we exploit ZRAM, the memory compression module in Linux. We demonstrate that even if the application itself or the file system does not compress data, the OS's memory compression can transparently introduce timing side channels. We demonstrate that a dictionary attack with 100 guesses on ZRAM decompression can leak a 6 B -secret co-located with attacker data in a page within 2 . 25 min on average. Our fuzzer shows that most if not all compression algorithms are susceptible to timing side channels when observing the decompression of data. With our case studies, we demonstrate that data leakage is not only a concern for data in transit but also for data at rest. With this work, we seek to highlight the importance of evaluating the trade-off between compressing data, and leaking side-channel information about the compressed data, for any system adopting compression. Contributions. The main contributions of this work are: Fig. 1: DEFLATE algorithm has two parts: LZ77 part to compress sequences and a Huffman part to compress symbols. <details> <summary>Image 1 Details</summary>  ### Visual Description ## Diagram Type: Data Compression Process ### Overview The diagram illustrates the process of data compression and decompression using two different algorithms: LZ77 and Huffman coding. The process involves encoding, decoding, and the application of deflate and inflate operations. ### Components/Axes - **Data**: The original data to be compressed. - **LZ77 Encoding**: A lossless data compression algorithm that replaces repeated sequences of data with references to a previous occurrence. - **Huffman Encoding**: A variable-length prefix code that assigns shorter codes to more frequent symbols and longer codes to less frequent symbols. - **Deflate**: A lossless data compression algorithm that uses LZ77 encoding and Huffman coding to compress data. - **Inflate**: A lossless data decompression algorithm that uses the same compression techniques to decompress data. ### Detailed Analysis or ### Content Details - **LZ77 Encoding**: The data is divided into windows, and the algorithm searches for repeated sequences within these windows. If a repeated sequence is found, it is replaced with a reference to the previous occurrence. - **Huffman Encoding**: The algorithm assigns shorter codes to more frequent symbols and longer codes to less frequent symbols. This is done by creating a Huffman tree where the frequency of each symbol is used to determine the length of its code. - **Deflate**: The data is first encoded using LZ77 and then Huffman coding. The compressed data is then stored in a compressed format. - **Inflate**: The compressed data is decompressed using the same compression techniques. The data is first decompressed using Huffman decoding and then LZ77 decoding to retrieve the original data. ### Key Observations - **LZ77 and Huffman Encoding**: Both algorithms are used to compress data, but they work differently. LZ77 replaces repeated sequences, while Huffman encoding assigns shorter codes to more frequent symbols. - **Deflate and Inflate**: These operations are used to compress and decompress data, respectively. Deflate uses both LZ77 and Huffman coding, while Inflate uses the same compression techniques to decompress data. ### Interpretation The diagram demonstrates the process of data compression and decompression using two different algorithms. The use of LZ77 and Huffman coding allows for efficient compression of data, while the deflate and inflate operations ensure that the data can be decompressed accurately. The diagram also highlights the importance of using compression algorithms that are suitable for the type of data being compressed. </details> - 1) We present a systematic analysis of timing leakage for several lossless data-compression algorithms. - 2) We demonstrate an evolutional fuzzer to automatically search for memory layouts causing large timing differences for timing side channels on memory compression. - 3) We show a remote covert channel exploiting the in-memory compression of PHP-Memcached. - 4) We demonstrate that compression-based timing side channels can be introduced by compression in applications, databases, or the system's memory compression. - 5) We leak secrets from Memcached, PostgreSQL, and ZRAM within minutes. Outline. In Section II, we provide background. In Section III, we present attack model and building blocks. In Section IV, we systematically analyze compression algorithms. In Section V, we present Comprezzor. In Section VI, we demonstrate local and remote attacks exploiting decompression timing. We discuss mitigations in Section VII and conclude in Section VIII. We responsibly disclosed our findings to the developers and will open-source our fuzzing tool and attacks on Github. ## II. BACKGROUND AND RELATED WORK In this section, we provide background on data compression algorithms, prior side-channel attacks on data compression, and the use of fuzzing to discover side channels. ## A. Data Compression Algorithms Lossless compression reduces the size of data without losing information. One of the most popular algorithms is the DEFLATE compression algorithm, which is used in gzip (zlib). The DEFLATE compression algorithm [12] consists of two main parts, LZ77 and Huffman encoding and decoding, as shown in Figure 1. The Lempel-Ziv (LZ77) part scans for the longest repeating sequence within a sliding window and replaces repeated sequences with a reference to the first occurrence [8]. This reference stores distance and length of the occurrence. The Huffman -coding part tries to reduce the redundancy of symbols. When compressing data, DEFLATE first performs LZ77 encoding and Huffman encoding [8]. When decompressing data (inflate), they are performed in reverse order. The algorithm provides different compression levels to optimize for compression speed or compression ratio. The smallest possible sequence has a length of 3 B [12]. Other algorithms provide different design points for compressibility and speed. Zstd, designed by Facebook [10] for modern CPUs, improves both compression ratio and speed, and is used for compression in file systems (e.g., btrfs, squashfs) and databases (e.g., AWS Redshift, RocksDB). LZ4 and LZO are other algorithms used in file systems, which are optimized for compression and decompression speed. LZ4, in particular, gains its performance by using a sequence compression stage (LZ77) without the symbol encoding stage (Huffman) like in DEFLATE. FastLZ, similar to LZ4, is a fast compression algorithm implementing LZ77. PGLZ is a fast LZ-family compression algorithm used in PostgreSQL for varying-length data in the database [46]. ## B. Prior Data Compression Attacks In 2002, Kelsey [33] first showed that any compression algorithm is susceptible to information leakage based on the compression-ratio side channel. Duong and Rizzo [49] applied this idea to steal web cookies with the CRIME attack by exploiting TLS compression. In the CRIME attack, the attacker adds additional sequences in the HTTP request, which act as guesses for possible cookies values, and observes the request packet length, i.e. , the compression ratio of the HTTP header injected by the browser. If the guess is correct, the LZ77-part in gzip compresses the sequence, making the compression ratio higher, thus allowing the secret to be discovered. To perform CRIME, the attacker needs to be able to spy on the packet length, and the secret needs to have a known prefix such as sessionid= or cookie= . To mitigate CRIME, TLS-level compression was disabled for requests [4], [20]. The BREACH attack [20] revived the CRIME attack by attacking HTTP responses instead of requests and leaking secrets in the HTTP responses such as cross-site-request-forgery tokens. The TIME attack [4] uses the time of a response as a proxy for the compression ratio, as it can be measured even via JavaScript. To reliably amplify the signal, the attacker chooses the size of the payload such that additional bytes, due to changes in compressibility, cross a boundary and cause significantly higher delays in the round-trip time (RTT). TIME exploits the compression ratio to amplify timing differences via TCP windows and does not exploit timing differences in the underlying compression algorithm itself. A malicious site can perform a TIME attack on their visitors to break same-origin policy or leak data from sites that reflect user input in the response, such as a search engine [4]. Vanhoef and Van Goethem [58] showed with HEIST that HTTP/2 features can also be used to determine the size of crossorigin responses and to exploit BREACH using the information. Van Goethem et al. [57] similarly showed that compression can be exploited to determine the exact size of any resource in browsers. Karaskostas and Zindros[32] presented Rupture, extending BREACH attacks to web apps using block ciphers such as AES. Tsai et al. [55] demonstrated cache timing attacks on compressed caches, which can leak a secret key in under 10 ms . Common Theme. All of the prior attacks primarily exploit the compression-ratio side channel. However, the time taken by the underlying compression algorithm for compression or decompression is not analyzed or exploited as side channels. Additionally, these attacks largely target the HTTP traffic and website content, and do not focus on the broader applications Fig. 2: Overview of a memory compression attack exploiting a timing side channel. <details> <summary>Image 2 Details</summary>  ### Visual Description ## Diagram Type: Flowchart ### Overview The image is a flowchart that illustrates the process of data transmission and processing between an attacker and a victim in a cybersecurity context. The flowchart is divided into five steps, each represented by a numbered box and an arrow indicating the direction of data flow. ### Components/Axes - **Victim's RAM/Disk Page**: This is the starting point of the flowchart, where the victim's computer memory and disk are located. - **Attacker**: This is the entity that initiates the data transmission process. - **Victim**: This is the entity that receives the data and processes it. - **Secret Data**: This is the data that is being transmitted and processed by the victim. - **Attacker Data**: This is the data that is being transmitted and processed by the attacker. - **Compress Data**: This is the step where the secret data is compressed along with the attacker data. - **Decompress Data**: This is the step where the data is decompressed to reveal the secret data. - **Send Data**: This is the step where the compressed data is sent to the victim's application/server. - **Request Data**: This is the step where the victim requests the data from the attacker. - **Calculate Round-Trip Time (RTT)**: This is the step where the RTT is calculated to measure the time taken for data transmission. ### Detailed Analysis or ### Content Details - **Step 1**: The attacker sends data to the victim's application/server. - **Step 2**: The attacker compresses the secret data along with the attacker data. - **Step 3**: The victim requests the data from the attacker. - **Step 4**: The attacker decompresses the data to reveal the secret data. - **Step 5**: The RTT is calculated to measure the time taken for data transmission. ### Key Observations - The flowchart shows that the attacker is able to transmit secret data to the victim's application/server. - The attacker is also able to compress the secret data along with the attacker data, making it difficult for the victim to detect the presence of the secret data. - The flowchart also shows that the attacker is able to calculate the RTT, which can be used to measure the time taken for data transmission. ### Interpretation The flowchart demonstrates the process of data transmission and processing between an attacker and a victim in a cybersecurity context. The attacker is able to transmit secret data to the victim's application/server, compress it along with the attacker data, and calculate the RTT to measure the time taken for data transmission. This flowchart highlights the importance of data encryption and compression in protecting sensitive information from unauthorized access. </details> of compression such as memory-compression, databases, file systems, and others, that we target in this paper. ## C. Fuzzing to Discover Side Channels Historically, fuzzing has been used to discover bugs in applications [64], [16]. Typically, it involves feedback based on novelty search, executing inputs, and collecting ones that cover new program paths in the hope of triggering bugs. Other fuzzing proposals use genetic algorithms to direct input generation towards interesting paths [48], [54]. Recently fuzzing has also been used to discover side channels both in software and in the microarchitecture [59], [21], [40], [18]. ct-fuzz [27] used fuzzing to discover timing side channels in cryptographic implementations. Nilizadeh et al. [42] used differential fuzzing to detect compression-ratio side channels that enable the CRIME attack. In this work, we build on these and use fuzzing to discover timing channels in compression algorithms. ## III. HIGH-LEVEL OVERVIEW In this section, we discuss the high-level overview of memory compression attacks and the attack model. ## A. Attack Model & Attack Overview Most prior attacks discussed in Section II-B focused on the compression ratio side channel. Even the TIME attack and its variants by Vanhoef and Van Goethem et al. [58], [57] only exploited timing differences due to the TCP protocol. None of these exploited or analyzed timing differences due to the compression algorithm itself, which is the focus of our attack. We assume that the attacker can co-locate arbitrary data with secret data. This co-location can be given, e.g., via a memory storage API like Memcached or a shared database between the attacker and the victim. Once the attacker data is compressed with the secret, the attacker only needs to measure the latency of a subsequent access to its data. Furthermore, we assume no software vulnerabilities i.e. , memory corruption vulnerabilities in the application it self. Figure 2 illustrates an overview of a memory compression attack in five steps. The victim application can be a web server with a database or software cache, or a filesystem that compresses stored files. First , the attacker sends its data to be stored to the victim's application. Second , the victim application compresses the attacker-controlled data, together with some co-located secret data, and stores the compressed data. The attacker-controlled data contains a partial guess of the co-located victim's data SECRET or, in the case where a prefix is known, prefix=SECRET . The guess can be performed bytewise to reduce the guessing entropy. If the partial guess is correct, i.e. , SECR , the compressed data not only has a higher compression ratio, but it also influences the decompression time. Third , after the compression happened, the attacker requests the content of the stored data again and takes a timestamp. Fourth , the victim application decompresses the input data and responds with the requested data. Fifth , the attacker takes another timestamp when the application responds and computes the RTT as the difference between the two timestamps. Based on the RTT, which depends on the decompression latency of the algorithm, the attacker infers whether the guess was correct or not and thus infers the secret data. Thus, the attack relies on the timing differences of the compression algorithm itself, which we characterize next. ## IV. SYSTEMATIC STUDY: COMPRESSION ALGORITHMS In this section, we provide a systematic analysis of timing leakage in compression algorithms. We choose six popular compression algorithms (zlib, zstd, LZ4, LZO, PGLZ, and FastLZ), and evaluate the compression and decompression times based on the entropy of the input data. Zlib (which implements the DEFLATE algorithm) is the most popular as a standard for compressing files and is used in gzip. Zstd is Facebook's alternative to Zlib. PGLZ is used in the popular relational database management system PostgreSQL. LZ4, FastLZ, and LZO were built to increase compression speeds. For each of the algorithms, we observe timing differences in the range of hundreds to thousands of nanoseconds based on the content of the input data ( 4 kB -page). ## A. Experimental Setup We conducted the experiments on an Intel i7-6700K (Ubuntu 20.04, kernel 5.4.0) with a fixed frequency of 4 GHz . We evaluate the latency of each compression algorithm with three different input values, each 4 kB in size. The first input is the same byte repeated 4096 times, which should be fully compressible . The second input is partly compressible and a hybrid of two other inputs: half random bytes and half compressible repeated bytes. The third input consists of random bytes which are theoretically incompressible . With these, we show that compression algorithms can have different timings dependent on the compressibility of the input. ## B. Timing Differences for Different Inputs For each algorithm and input, we measure the decompression and compression time over 100 000 repetitions and compute the mean values and standard deviations. Decompression. Table I lists the decompression latencies for all evaluated compression algorithms. Depending on the entropy of the input data, there is considerable variation in the decompression time. All algorithms incur a higher latency for decompressing a fully compressible page compared to an incompressible page, leading to a timing difference of few hundred to few thousand nanoseconds for different TABLE I: Different compression algorithms yield distinguishable timing differences when decompressing content with a different entropy ( n 100000 ). | Algorithm | Fully Compressible (ns) | Partially Compressible (ns) | Incompressible (ns) | |-------------|---------------------------------|----------------------------------|---------------------------------| | FastLZ | 7257 . 88 ( 0 . 23% ) | 4264 . 56 ( 2 . 27% ) | 1155 . 57 ( 0 . 92% ) | | LZ4 | 605 . 79 ( 1 . 02% ) | 218 . 68 ( 1 . 76% ) | 107 . 90 ( 2 . 49% ) | | LZO | 2115 . 65 ( 2 . 05% ) | 1220 . 07 ( 3 . 64% ) | 309 . 44 ( 6 . 27% ) | | PGLZ | 813 . 75 ( 0 . 71% ) | 5340 . 47 ( 0 . 38% ) | - | | zlib | 7016 . 02 ( 0 . 33% ) | 13212 . 53 ( 0 . 35% ) | 1640 . 09 ( 1 . 51% ) | | zstd | 941 . 05 ( 0 . 94% ) | 772 . 55 ( 0 . 77% ) | 370 . 59 ( 2 . 87% ) | algorithms. This is because, for incompressible data, algorithms can augment the raw data with additional metadata to identify such cases and perform simple memory copy operations to 'decompress' the data, as is the case for zlib where the decompression for an incompressible page is 5375 . 93 ns faster than a fully compressible page. For decompression of partially compressible pages, some algorithms (FastLZ, LZ4, LZO, zstd) have lower latency than fully compressible pages, while others (zlib and PGLZ) have a higher latency than fully compressible pages. This shows the existence of even algorithm-specific variations in timings. PGLZ does not create compressible memory in the case of an incompressible input, and hence we do not measure its latency for this input. Compression. For compression, we observed a trend in the other direction (Table IV in Appendix A lists compression latencies for different algorithms). For a fully compressible page, there are also latencies between the three different inputs, which are clearly distinguishable in the order of multiple hundreds to thousands of nanoseconds. Thus, timing side channels from compression might also be used to exploit compression of attacker-controlled memory co-located with secret memory. However, attacks using the compression side channel might be harder to perform in practice as the compression of data might be performed in a separate task (in the background), and the latency might not be easily observable for a user. Hence, our work focuses on attacks exploiting the decompression timing side channel. Handling of Corner Cases. For incompressible pages, the 'compressed' data can be larger than the original size with the additional compression metadata. Additionally, it is slower to access after compression than raw uncompressed data. Hence, this corner-case with incompressible data may be handled in an implementation-specific manner, which can itself lead to additional side channels. For example, a threshold for the compression ratio can decide when a page is stored in a raw format or in a compressed state, like in MemcachedPHP [45]. Alternatively, PGLZ, the algorithm used in PostgreSQL database, which computes the maximum acceptable output size for input by checking the input size and the strategy compression rate, could simply fail to compress inputs in such corner cases. In Section VI, we show how real-world applications like Memcached, PostgreSQL, and ZRAM deal with such corner cases and demonstrate attacks on each of them. ## C. Leaking secrets via timing side channel Thus far, we analyzed timing differences for decompressing different inputs, which in itself is not a security issue. In this section, we demonstrate Decomp+Time to leak secrets from compressed pages using these timing differences. We focus on sequence compression, i.e. , LZ77 in DEFLATE. 1) Building Blocks for Decomp+Time: Decomp+Time consists of three building blocks: sequence compression that we use to modulate the compressibility of an input, colocation of attacker data and secrets, and timing variation for decompression depending on the change in compressibility of the input. Sequence compression: Sequence compression i.e. , LZ77 tries to reduce the redundancy of repeated sequences in an input by replacing each occurrence with a pointer to the first occurrence. This results in a higher compression ratio if redundant sequences are present in the input and a lower ratio if no such sequences are present. This compressibility side channel can leak information about the compressed data. Co-location of attacker data and secrets: If the attacker can control a part of data that is compressed with a secret, as described in Figure 2, then the attacker can place a guess about the secret and place it co-located with the secret to exploit sequence compression. If the compression ratio increases, the attacker can infer if the guess matches the secret or not. While the CRIME attack [49] previously used a similar set up and observed the compressed size of HTTP requests to steal secrets like HTTP cookies, we target a more general attack and do not require observability of compressed sizes. Timing Variation in Decompression: We infer the change in compressibility via its influence on decompression timing. We observe that even sequence compression can cause variation in the decompression timing based on compressibility of inputs (for all algorithms in Section IV-B). If the sequence compression reduces redundant symbols in the input and increases the compression ratio, we observe faster decompression due to fewer symbols. Otherwise, with a lower compression ratio and more number of symbols, decompression is slower. Hence, the attacker can infer the compressibility changes for different guesses by observing differences in decompression time due to sequence compression. For a correct guess, the guess and the secret are compressed together and the decompression time is faster due to fewer symbols. Otherwise, it is slower for incorrect guesses with more symbols. 2) Launching the Decomp+Time: Using the building blocks described above, we setup the attack with an artificial victim program that has a 6 B -secret string ( SECRET ) embedded in a 4 kB -page. The page also contains attacker-controlled data that is compressed together with the secret, like the scenario shown in Figure 2. The attacker can update its own data in place, allowing it to make multiple guesses. The attacker can also read this data, which triggers a decompression of the page and allows the attacker to measure the decompression time. A correct guess that matches with the secret results in faster decompression. We perform the attack on the zlib library (1.2.11) and use 8 different guesses, including the correct guess. For each guess, a single string is placed 512 B away from the secret value; other data in the page is initialized with dummy values (repeated number sequence from 0 to 16). To measure the execution time, we use the rdtsc instruction. Fig. 3: Decompression time with Decomp+Time for a dictionary attack. There is a clear threshold (line) separating the correct from wrong secrets. <details> <summary>Image 3 Details</summary>  ### Visual Description ## Line Chart: Timing Measurements ### Overview The line chart displays timing measurements in milliseconds (ms) for various tasks labeled as "FOOBAR," "SECRET," "PYTHON," "123456," "COOKIE," "SOMEDA," "ADMIN," and "NOPENO." The x-axis represents the tasks, while the y-axis shows the timing in milliseconds. ### Components/Axes - **X-axis**: Labeled "Guess," it lists the tasks. - **Y-axis**: Labeled "Timing [ms]," it measures the timing in milliseconds. - **Legend**: There is no legend visible in the image. - **Data Points**: Blue dots represent the timing measurements for each task. ### Detailed Analysis or ### Content Details - **FOOBAR**: The timing measurement is approximately 4,000 ms. - **SECRET**: The timing measurement is approximately 3,950 ms. - **PYTHON**: The timing measurement is approximately 4,000 ms. - **123456**: The timing measurement is approximately 4,000 ms. - **COOKIE**: The timing measurement is approximately 4,000 ms. - **SOMEDA**: The timing measurement is approximately 4,000 ms. - **ADMIN**: The timing measurement is approximately 4,000 ms. - **NOPENO**: The timing measurement is approximately 3,950 ms. ### Key Observations - All tasks except "SECRET" and "NOPENO" have a timing measurement close to 4,000 ms. - "SECRET" and "NOPENO" have timing measurements close to 3,950 ms. ### Interpretation The data suggests that most tasks have a consistent timing of around 4,000 ms, with "SECRET" and "NOPENO" being slightly slower. This could indicate that these tasks are more resource-intensive or have a higher overhead compared to the others. The close timing measurements for most tasks suggest that they are relatively similar in performance. </details> Fig. 4: Leaking the secret sixth offset character-wise. Still, the correct guess is distinguishable from the wrong guesses. A clear threshold can be used to separate the correct guess from the incorrect guesses. <details> <summary>Image 4 Details</summary>  ### Visual Description ## Line Chart: Guessing Times ### Overview The line chart displays the timing measurements in nanoseconds (ns) for various guesses labeled as "SECRES" and "SECRET". The x-axis represents the guesses, while the y-axis shows the timing in nanoseconds. ### Components/Axes - **X-Axis**: Labeled "Guess" with values from "SECRES" to "SECRET". - **Y-Axis**: Labeled "Timing [ns]" with values ranging from 3,520 to 3,560. - **Legend**: Located at the top right, indicating the color coding for "SECRES" (blue) and "SECRET" (red). - **Data Points**: Blue dots represent "SECRES" guesses, and a single red dot represents the "SECRET" guess. ### Detailed Analysis or ### Content Details - The "SECRES" guesses have a consistent timing around 3,540 ns. - The "SECRET" guess is significantly lower at approximately 3,520 ns. - There is a clear trend where the "SECRET" guess consistently has a lower timing than the "SECRES" guesses. ### Key Observations - The "SECRET" guess is consistently lower than the "SECRES" guesses. - There is a noticeable difference in timing between the two guesses. ### Interpretation The data suggests that the "SECRET" guess is faster than the "SECRES" guesses. This could indicate that the "SECRET" guess is more efficient or accurate in the context of the measurement being taken. The consistent lower timing of the "SECRET" guess implies that it may be a more reliable or optimized method for the task at hand. </details> Evaluation. Our evaluation was performed on an Intel i76700K (Ubuntu 20.04, kernel 5.4.0) with a fixed frequency of 4 GHz . To get stable results, we repeat the decompression step with each guess 10 000 times and repeat the entire attack 100 times. For each guess, we take the minimum timing difference per guess and choose the global minimum timing difference to determine the correct guess. Figure 3 illustrates the minimum decompression times. With zlib, we observe that the correct guess is faster on average by 71 . 5 ns ( n 100 , σ 27 . 91% ) compared to the second-fastest guess. Our attack correctly guessed the secret in all 100 repetitions of the attack. While we used a 6 B secret, our experiment also works for smaller secrets down to a length of 4 B . We also observe the attack is faster if the secret has a known prefix with a length of 3 B or more. Bytewise leakage. If the attacker manages to guess or know the first three bytes of the secret, the subsequent bytes can even be leaked bytewise using our attack. Both CRIME and BREACH, assume a known prefix such as cookie= . Similar to CRIME and BREACH [49], [20], [32], we try to perform a bytewise attack by modifying our simple layout. We use the first 5 characters of SECRET as a prefix "SECRE" and guess the last byte with 7 different guesses. On average the latency is 28 . 37 ns ( n 100 , σ 65 . 78% ), between the secret and second fastest guess. Figure 4 illustrates the minimum decompression times for the different guesses. However, we observe an error rate of 8 % for this experiment, which might be caused by the Huffmann-decoding part in DEFLATE. While techniques like the Two-Tries method [49], [20], [32] have been proposed to overcome the effects of Huffmancoding in DEFLATE to improve the fidelity of byte-wise attacks exploiting compression ratio, we seek to explore whether bytewise leakage can be reliably performed via the timing only by amplying the timing differences. 3) Challenge Of Amplifying Timing: While the decompression timing side channels can be directly used in attacks as demonstrated, the timing differences are still quite small for practical exploits on real-world applications. For example, the timing differences we observed for the correct guess are in tens of nanoseconds, while most practical use-cases of compression such as in a Memcached server accessed over the network, or PostgreSQL database accessed from a filesystem could have access latencies of milliseconds. Amplification. To enable memory compression attacks via the network or on data stored in file systems, we need to amplify the timing difference between correct and incorrect guesses. However, it is impractical to manually identify inputs that could amplify the timing differences, as each compression algorithm has a different implementation that is often highly optimized. Moreover, various input parameters could influence the timing of decompression, such as frequency of sequences, alignments of the secret and attack-controlled data, size of the input, entropy of the input, and different compression levels provided by algorithms. As an additional factor, the underlying hardware microarchitecture might also have undesirable influences. Therefore, to automate this process in a systematic manner, we develop an evolutionary fuzzer, Comprezzor, to find input corner cases that amplify the timing difference between correct and incorrect guesses for different compression algorithms. ## V. EVOLUTIONARY COMPRESSION-TIME FUZZER Compression algorithms are highly optimized, complex and even though most of them are open-source, their internals are only partially documented. Hence, we introduce Comprezzor, an evolutionary fuzzer to discover attacker-controlled inputs for compression algorithms that maximize differences in decompression times for certain guesses enabling both bytewise leakage and dictionary attacks. Comprezzor empowers genetic algorithms to amplify decompression side channels. It treats the decompression process of a compression algorithm as an opaque box and mutates inputs to the compression while trying to maximize the output, i.e. , timing differences for decompression with different guesses. The mutation process in Comprezzor focuses on not only the entropy of the data, but also the memory layout and alignment that end up triggering optimizations and slow paths in the implementation that are not easily detectable manually. While previous approaches used fuzzing to detect timing side channels [42], [27], Comprezzor can dramatically amplify timing differences by being specialized for compression algorithms by varying parameters like the input size, layout, and entropy that affect the decompression time. The inputs discovered by Comprezzor can amplify timing differences to such an extent that they are even observable remotely. ## A. Design of Comprezzor In this section, we describe the key components of our fuzzer: Input Generation, Fitness Function, Input Mutation and Input Evolution. Input Generation. Comprezzor generates memory layouts for Decomp+Time by maximizing the timing differences on decompression of the correct guess compared to incorrect ones. Comprezzor creates layouts with sizes in the range of 1 kB to 64 kB . It uses a helper program that takes the memory layout configuration as input, builds the requested memory layout for each guess, compresses them using the target compression algorithm, and reports the observed timing differences in the decompression times among the guesses. A memory layout configuration is composed of a file to start from, the offset of the secret in the file, the offset of guesses, how often the guesses are repeated in the layout, the compression level ( i.e. , between 1 and 9 for zlib), and a modulus for entropy reduction that reduces the range of the random values. The fuzzer can be used in cases where a prefix is known and unknown. Fitness Function. The evolutionary algorithm of Comprezzor starts from a random population of candidate layouts (samples) and takes as feedback the difference in time between decompression of the generated memory containing the correct guess and the incorrect ones. Comprezzor uses the timing difference between the correct guess and the second-fastest guess as the fitness score for a candidate. The fitness function is evaluated using a helper program performing an attack on the same setup as in Section IV-A. The program performs 100 iterations per guess and reports the minimum decompression time per guess to reduce the impact of noise. This minimum decompression time is the output of the fitness function for Comprezzor. Input Mutation. Comprezzor is able to amplify timing differences thanks to its set of mutations over the samples space specifically designed for data compression algorithms. Data compression algorithms leverage input patterns and entropy to shrink the input into a compressed form. For performance reasons, their ability to search for patterns in the input is limited by different internal parameters, like lookback windows, lookahead buffers, and history table sizes [46], [8]. We designed the mutations that affect the sample generation process to focus on input characteristics that directly impact compression algorithm strategies and limitations towards corner cases. Comprezzor mutations randomize the entropy and size of the samples that are generated. This has an effect on the overall compressibility of sequences and literals in the sample [8]. Moreover, the mutator varies the number of repeated guesses and their position in the resulting sample stressing the capability of the compression algorithm to find redundant sequences over different parts of the input. This affects the sequence compression and can lead to corner cases, i.e. , where subsequent blocks to be compressed are directly marked as incompressible, as we will later show for zlib in Section V-B. All of these factors together contribute to Comprezzor's ability to amplify timing differences. Input Evolution. Comprezzor follows an evolutionary approach to generate better inputs that maximize timing differences. It generates and mutates candidate layout configurations for the attack. Each configuration is forwarded to the helper program that builds the requested layout, inserts the candidate guess, compresses the memory, and returns the decompression time. Algorithm 1 shows the pseudocode of the evolutionary algorithm used by Comprezzor. ``` ``` Algorithm 1: Comprezzor evolutionary pseudo-code TABLE II: Timing differences between correct and incorrect guesses found by Comprezzor and the corresponding runtime. | Algorithm | Max difference for correct guess (ns) | Runtime (h) | |-------------|-----------------------------------------|---------------| | PGLZ | 109233 | 2.09 | | zlib | 71514.8 | 2.46 | | zstd | 4239.25 | 1.73 | | LZ4 | 2530.5 | 1.64 | Comprezzor iterates through different generations, with each sample having a probability of survival to the new generation that depends on its fitness score, where the fitness score is the time difference between the correct guess and the nearest incorrect one. Comprezzor discards all the samples where the correct guess is not the fastest or slowest. A retention factor decides the percentage of samples selected to survive among the best ones in the old generation ( 5 % by default). The population for each new generation is initialized with the samples that survived the selection process and enhanced by random mutations of such samples, tuning evolution towards local optimal solutions. By default, 70 % of the new population is generated by mutating the best samples from the previous generation. However, to avoid trapping the fuzzer in locally optimal solutions, a percentage of completely random new samples is injected in each new generation. Comprezzor runs until the maximum number of generations is evaluated, and the best candidate layouts found are returned. ## B. Results: Fuzzing Compression Algorithms Evaluation. Our test system has an Intel i7-6700K (Ubuntu 20.04, kernel 5.4.0) with a fixed frequency of 4 GHz . We run Comprezzor on four compression algorithms: zlib (1.2.11), Facebook's Zstd (1.5.0), LZ4 (v1.9.3), and PGLZ in PostgreSQL (v12.7). Comprezzor can support new algorithms by just adding compression and decompression functions. We run Comprezzor with 50 epochs and a population of 1000 samples per epoch. We set the retention factor to 5 % , selecting the best 50 samples in each generation of 1000 samples. We randomly mutate the selected samples to generate 70 % of the children and add 25 % of completely randomly generated layouts in the new generation. The runtime of Comprezzor to finish all 50 epochs was for zlib, 2 . 46 h , for zstd, 1 . 73 h , for LZ4, 1 . 64 h , and for PGLZ, 2 . 09 h . Table II lists the maximum timing differences found for Decomp+Time on the four compression algorithms, all of which use sequence compression like LZ77. Particularly, for zlib and PGLZ, the fuzzer discovers cases with timing differences of the scale of microseconds between correct and incorrect guesses, that is, orders of magnitude higher than the manually discovered differences in Section IV. Since zlib is one of the more popular algorithms, we analyze its high latency difference in more detail below. Zlib. Using Comprezzor, we found a corner case in zlib where all incorrect guesses lead to a slow code path, and the correct guess leads to a significantly faster execution time. We ran Comprezzor with a known prefix i.e. , cookie. We observe a high timing difference of 71 514 . 75 ns between correct and incorrect guesses, which is 3 orders of magnitude higher compared to the latency difference found manually in Section IV-C. This memory layout also leads to similarly high timing differences across all compression levels of zlib. To rule out micro-architectural effects, we re-run the experiment on different systems equipped with an Intel i5-8250U, AMD Ryzen Threadripper 1920X, and Intel Xeon Silver 4208, and observe similar timing differences. On further analysis, we observe that the corner case identified by the fuzzer is due to incompressible data. The initial data in the page, from a uniform distribution, is primarily incompressible. For such incompressible blocks, DEFLATE algorithm can store them as raw data blocks, also called stored blocks [12]. Such blocks have fast decompression times as only a single memcpy operation is needed on decompression instead of the actual DEFLATE process. In this particular corner case, the fuzzer discovered the correct guess results in such an incompressible stored block which is faster, while an incorrect guess results in a partly compressible input which is slower, as we describe below. Correct Guess. On a compression for the case where the guess matches the secret, the entire guess string, i.e. , cookie=SECRET , is compressed with the secret string. All subsequent data in the input is incompressible and treated as a stored block and decompressed with a single memcpy operation, which is fast without any Huffman or LZ77 decoding. Incorrect Guess. On a compression for the case where the guess does not match the secret, only the prefix of the guess, i.e. , cookie= , is compressed with the prefix of the secret, while another longer sequence i.e. , cookie=FOOBAR leads to forming a new block. On a decompression, this block must now undergo the Huffman decoding (and LZ77), which results in several table lookups, memory accesses, and higher latency. Thus, the timing differences for the correct and incorrect guesses are amplified by the layout that Comprezzor discovered. We provide more details about this layout in Figure 14 in the Appendix C and also provide listings of the debug trace from zlib for the decompression with the correct and incorrect guesses, to illustrate the root-cause of the amplified timing differences with this layout. Takeaway: We showed that it is possible to amplify timing differences for decompression timing attacks. With Comprezzor, we presented an approach to automatically find high timing differences in compression algorithms. The high latencies can be used for stable remote attacks. <details> <summary>Image 5 Details</summary>  ### Visual Description ## Diagram Type: Key-Value Store ### Overview The diagram illustrates the process of data transmission between a sender and a receiver, involving a key-value store for data compression and decompression. ### Components/Axes - **Sender**: A component that sends data. - **Receiver**: A component that receives data. - **Key-Value Store**: A central component that stores and retrieves data. - **Compress/Decompress**: A process that compresses data for transmission and decompresses it upon receipt. - **Store/Update**: The action of storing or updating data in the key-value store. - **Fetch data**: The action of retrieving data from the key-value store. ### Detailed Analysis or ### Content Details The sender sends data to the key-value store, which compresses the data using a compress/decompress process. The compressed data is then sent to the receiver, where it is decompressed and fetched from the key-value store. The receiver then processes the data. ### Key Observations - The key-value store acts as a central hub for data storage and retrieval. - The compress/decompress process is essential for efficient data transmission over networks. - The store/update and fetch data actions are critical for maintaining and accessing the data in the key-value store. ### Interpretation The diagram demonstrates the concept of data compression and decompression in a key-value store architecture. It highlights the importance of a central storage component and the need for efficient data transmission processes. The key-value store allows for quick access and retrieval of data, while the compress/decompress process ensures that data can be transmitted over networks without significant loss of information. The store/update and fetch data actions ensure that the data in the key-value store is up-to-date and accessible when needed. </details> Fig. 5: Covert communication via a key-value store using memory compression. <details> <summary>Image 6 Details</summary>  ### Visual Description ## Heatmap: Response Time Distribution ### Overview The heatmap illustrates the distribution of response times in nanoseconds (ns) for two different conditions: lower entropy and higher entropy. The x-axis represents the response time in nanoseconds, while the y-axis represents the amount of data points. ### Components/Axes - **X-Axis**: Response time [ns] - **Y-Axis**: Amount - **Legend**: - Lower entropy (0x42*4096) - Higher entropy ### Detailed Analysis or ### Content Details The heatmap shows two distinct peaks, one for lower entropy and one for higher entropy. The lower entropy peak is located around 0.7 ns, with a value of approximately 600 data points. The higher entropy peak is located around 1.1 ns, with a value of approximately 400 data points. ### Key Observations - The lower entropy condition has a higher peak, indicating a higher frequency of response times around 0.7 ns. - The higher entropy condition has a lower peak, indicating a lower frequency of response times around 1.1 ns. - There is a noticeable difference in the distribution between the two conditions, suggesting that the response time is more consistent in the lower entropy condition. ### Interpretation The data suggests that the response time is more consistent in the lower entropy condition, with a higher frequency of response times around 0.7 ns. This could indicate that the lower entropy condition is more efficient or that the system is better optimized for lower entropy conditions. The higher entropy condition, on the other hand, has a lower frequency of response times around 1.1 ns, which could indicate that the system is less efficient or that the system is not as well optimized for higher entropy conditions. Overall, the data suggests that the lower entropy condition is more efficient than the higher entropy condition. </details> Fig. 6: Timing when decompressing a single zlib-compressed 4 kB page with a high-entropy in comparison to a page with a low-entropy. ## VI. CASE STUDIES In this section, we present three case studies showing the security impacts of the timing side channel. In Section VI-A, we present a local covert channel that allows hidden communication via the latency decompression. Furthermore, we present a remote covert channel that exploits the decompression of memory objects in a PHP application using Memcached. We demonstrate Decomp+Time on a PHP application that compresses secret data together with attacker-data to leak the secret bytewise. In Section VI-D, we leak inaccessible values from a database, exploiting the internal compression of PostgreSQL. In Section VI-E, we show that OS-based memory compression also has timing side channels that can leak secrets. ## A. Covert channel To evaluate the transmission capacity of memorycompression attacks, we evaluate the transmission rate for a covert channel, where the attacker controls both the sending and receiving end. First, we evaluate a cross-core covert channel that relies on shared memory. This is in line with state-of-theart work to measure the maximum capacity of the memory compression side channel [24], [35], [37], [62], [23], [25]. The maximum capacity poses a leakage rate limit for other attacks that use memory compression as a side channel. Our local covert channel achieves a capacity of 448 bit ♥ s ( n 100 , σ 0 . 001% ). Setup. Figure 5 illustrates the covert communication between a sender and receiver via shared memory. We create a simple key-value store that communicates via UNIX sockets. The store takes input from a client and stores it on a 4 kB -aligned page. The sender inserts a key and value into the first page to communicate with the server. The receiver inserts a small key and value as well, which should be placed on the same 4 kB . If the 4 kB -page is fully written, the key-value store compresses the whole page. Compressing full 4 kB -page separately also occurs on filesystems like BTRFS [6]. Sender and receiver agree on a time frame to send and read content. The basic idea is to communicate via the observation on zlib that memory with low entropy, e.g., 4096 times the same value, requires more time when decompressing compared to pages with a higher entropy, e.g., repeating sequence number from 0 to 255 . Figure 6 shows the histogram of latency when decompression is triggered for both cases for the key-value on an Intel i7-6700K running at 4 GHz . On average, we observe a timing difference of 3566 . 22 ns ( 14 264 . 88 cycles, n 100000 ). These two timing differences are easy to distinguish and enable covert communication. Transmission. We evaluate our cross-core covert channel by generating and sending random content from /dev/urandom through the memory compression timing side channel. The sender transmits a '1'-bit by performing a store with the page that has a higher entropy 4095 B in the key-value store. Conversely, to transmit a '0'-bit, the sender compresses a lowentropy 4 kB page. To trigger the compression, the receiver also stores a key-value pair in the page, wheres as 1 B fills the remaining page. The key-value store will now compress the full 4 kB -page, as it is fully used. The receiver performs a fetch request from the key-value store, which triggers a decompression of the 4 kB -page. To distinguish bits, the receiver measures the mean RTT of the fetch request. Evaluation. Our test machine is equipped with an Intel Core i7-6700K (Ubuntu 20.04, kernel 5.4.0), and all cores are running on a fixed CPU frequency of 4 GHz . We repeat the transmission 50 times and send per run 640 B . To reduce the error rate, the receiver fetches the receiver-controlled data 50 times and compares the average response time against the threshold. Our cross-core covert channel achieves an average transmission rate of 448 bit ♥ s ( n 100 , σ 0 . 007% ) with an error rate of 0 . 082 % ( n 100 , σ 2 . 85% ). This capacity of the unoptimized covert channel is comparable to other stateof-the-art microarchitectural cross-core covert channels that do not rely on shared memory [60], [36], [14], [44], [37], [53], [47], [59]. ## B. Remote Covert Channel We extend the scope of our covert channel to a remote covert channel. In the remote scenario, we rely on Memcached on a web server for memory compression and decompression. Memcached. Memcached is a widely used caching system for web sites [38]. Memcached is a simple key-value store that internally uses a slab allocator. A slab is a fixed unit of contiguous physical memory, which is typically assigned to a certain slab class which is typically a 1 MB region [29]. Certain programming languages such as PHP or Python offer the option to compress memory before it is stored in Memcached [45], [5]. For PHP, memory compression is enabled per default if Memcached is used [45]. PHP-Memcached has a threshold that decides at which size data is compressed, with the default value at 2000 B . Furthermore, PHP-Memcached computes the compression ratio to a compression factor and decides whether it stores the data compressed or uncompressed in Memcached. The default value for the compression factor is 1 . 3 , i.e. , 23 % of the space needs to be saved from the original data size to store it compressed [45]. Fig. 7: Distribution of HTTP response times for zlibdecompressed pages stored in Memcached on memory compression encoding a '1' and a '0'-bit. <details> <summary>Image 7 Details</summary>  ### Visual Description ## Heatmap: Response Time Distribution ### Overview The heatmap illustrates the distribution of response times for two different conditions, labeled as 0 and 1. The x-axis represents the response time in nanoseconds (ns), while the y-axis represents the amount of data processed. ### Components/Axes - **X-axis**: Response time [ns] - **Y-axis**: Amount - **Legend**: - Red line: Condition 0 - Blue line: Condition 1 ### Detailed Analysis or ### Content Details - **Condition 0**: The response time for Condition 0 is relatively low, with a peak around 0.6 ns and a slight increase to 0.8 ns. The amount of data processed is low, with a peak around 200,000 and a slight decrease to 100,000. - **Condition 1**: The response time for Condition 1 is higher, with a peak around 1.2 ns and a slight increase to 1.4 ns. The amount of data processed is higher, with a peak around 400,000 and a slight decrease to 300,000. ### Key Observations - **Condition 1** generally has higher response times compared to Condition 0. - **Condition 1** also processes more data than Condition 0. - There is a slight trend of increasing response time with increasing data amount for both conditions. ### Interpretation The heatmap suggests that Condition 1 has a higher response time and processes more data compared to Condition 0. This could indicate that Condition 1 is more computationally intensive or has a higher latency. The slight increase in response time with increasing data amount for both conditions suggests that the system's performance may be limited by the amount of data being processed. </details> Bypassing the Compression Factor. While the compression factor already introduces a timing side channel, we focus on scenarios where data is always compressed. This is later useful for leakage on co-located data. Intuitively, it should suffice to prepend highly-compressible data to enforce compression. However, we found that only prepending and adopting the offsets for secret repetitions, as for zlib, also influenced the corner case we found and the large timing difference. We integrate prepending of compressible pages to Comprezzor and also add the compression factor constraint to automatically discover inputs that fulfills the constraint and leads to large latencies between a correct and incorrect guess. Transmission. We use the page found by Comprezzor which triggers a significantly lower decompression time to encode a '1'-bit. Conversely, for a '0'-bit, we choose content that triggers a significantly higher decompression time. The sender places a key-value pair for each bit index at once into PHPMemcached. The receiver sends GET requests to the resource, causing decompression of the data that contains the sender content. The timing difference of the decompression is reflected in the RTT of the HTTP request. Hence, we measure the timing difference between the HTTP request being sent and the first response packet received. Evaluation. Our sender and receiver are equipped with an Intel i7-6700K (Ubuntu 20.04, kernel 5.4.0) and connected to the internet with a 10 Gb/s connection. For the web server, we use a dedicated server in the Equinix [13] cloud, 14 hops away from our network (over 1000 km physical distance) with a 10 Gbit ♥ s connection. The victim server is equipped with an Intel Xeon E3-1240 v5 (Ubuntu 20.04, kernel 5.4.0). Our server runs a PHP (version 7.4) website, which allows storing and retrieving data, backed by Memcached. We installed Memcached 1.5.22, the default version on Ubuntu 20.04. The PHP website is hosted on Nginx 1.18.0 with PHP-FPM. We perform a simple test where we perform 5000 HTTP requests to a PHP site that stores zlib-compressed memory in Memcached. Figure 7 illustrates the timing difference between a '0'-bit and a '1'-bit. The timing difference between the mean values for a '0'- and '1'-bit is 61 622 . 042 ns . Figure 7 shows that the two distributions overlap to a certain extent. We call this overlap the critical section . We implement an early-stopping mechanism for bits in the covert channel that clearly belong into one of the two regions below or above the critical section. After 25 requests, we start to classify the RTT per bit. Fig. 8: Distribution of the response time for the correct guess (S) and the incorrect guesses (0-9, A-R, T-Z) for the first byte leaked in the byte-wise leakage of the secret from PHPMemcached. Similar trends are observed for subsequent bytes leaked as shown in Appendix D. <details> <summary>Image 8 Details</summary>  ### Visual Description ## Heatmap: Byte 0 ### Overview The heatmap displays the timing measurements in nanoseconds (ns) for different cookies at byte 0. The x-axis represents the cookies, and the y-axis represents the timing measurements. ### Components/Axes - **X-axis**: Labeled with different cookies (cookie=0, cookie=5, cookie=9, cookie=A, cookie=M, cookie=S, cookie=Z). - **Y-axis**: Labeled with timing measurements in nanoseconds (ns). - **Legend**: Located at the top right corner, indicating the color coding for the cookies. - **Title**: "Byte 0" at the top center of the heatmap. ### Detailed Analysis or ### Content Details The heatmap shows a range of timing measurements for each cookie. The timing measurements vary, with some cookies having higher values than others. The legend indicates that the colors represent different cookies, with red representing cookie=S and blue representing the rest. ### Key Observations - **Cookie=S**: Has a significantly higher timing measurement compared to the other cookies. - **Cookie=Z**: Has a lower timing measurement compared to the other cookies. - **Trend**: There is no clear trend in the timing measurements across the cookies. ### Interpretation The heatmap suggests that the timing measurements for different cookies at byte 0 vary significantly. The cookie=S has a much higher timing measurement, which could indicate that it takes longer to process or access this cookie compared to the other cookies. The cookie=Z has a lower timing measurement, which could indicate that it is faster to process or access this cookie. The other cookies have similar timing measurements, suggesting that they are processed or accessed at a similar rate. </details> At most, we perform 200 HTTP requests per bit. If there are still unclassified bits, we compare the amount of requests classified as '0'-bit and those classified as '1'-bit and decide on the side with more elements. We transmit a series of different messages of 8 B over the internet. Our simple remote covert channel achieves an average transmission rate of 643 . 25 bit ♥ h ( n 20 , σ 6 . 66% ) at an average error rate of 0 . 93 % . Our covert channel outperforms the one by Schwarz et al. [52] and Gruss [22],although our attack works with HTTP instead of the more lightweight UDP sockets. Other remote timing attacks usually do not evaluate their capacity with a remote covert channel [65], [30], [2], [51], [1], [2], [56]. ## C. Remote Attack on PHP-Memcached Using our building blocks to perform Decomp+Time and the remote covert channel, we perform a remote attack on PHP-Memcached to leak secret data from a server over the internet. We assume a memory layout where secret memory is co-located to attacker-controlled memory, and the overall memory region is compressed. Attack Setup. We use the same PHP-API as in Section VI-B that allows storing and retrieving data. We run the attack using the same server setup as used for the remote covert channel attacking a dedicated server in the Equinix [13] cloud 14 hops away from our network. We define a 6 B long secret ( SECRET ) with a 7 B long prefix ( cookie= ) and prepend it to the stored data of users. PHP-Memcached will compress the data before storing it in Memcached and decompress it when accessing it again. For each guess, the PHP application stores the uploaded data to a certain location in Memcached. On each data fetch, the PHP application decompresses the secret data together with the co-located attacker-controlled data and then responds onlythe attacker-controlled data. The attacker measures the RTT per guess and distinguishes the timing differences between the guesses. In the case of zlib, the guess with the fastest response time is the correct guess. We demonstrate a byte-wise leakage of an arbitrary secret and also a dictionary attack with a dictionary size of 100 guesses. Evaluation. For the byte-wise attack, we assume each byte of the secret is from 'A-Z,0-9' (36 different options). For each of the 6 bytes to be leaked, we generate a separate memory layout using Comprezzor that maximizes the latency between the guesses. We repeat the experiment 20 times. On average, our attack leaks the entire 6 B secret string in 31 . 95 min ( n Fig. 9: Distribution of the response time for the correct guess (SECRET) and the 99 other incorrect guesses in dictionary attack on PHP-Memcached. Note that we only label SECRET and 6 out of 99 incorrect guesses on the X-axis for brevity. <details> <summary>Image 9 Details</summary>  ### Visual Description ## Heatmap: Timing Analysis ### Overview The heatmap displays the timing measurements for various cryptographic algorithms. The x-axis represents different algorithms, while the y-axis shows the timing in nanoseconds (ns). ### Components/Axes - **X-axis**: Algorithms (03eBxD, 8kX92B, IEMle7, SECRET, dDFqk3, m4GWKM, 2XioC) - **Y-axis**: Timing in nanoseconds (ns) - **Color Scale**: Blue to red, indicating increasing timing ### Detailed Analysis or ### Content Details The heatmap shows a range of timing values for each algorithm. The majority of the points are clustered around the 1 ns mark, indicating that most algorithms have a similar timing performance. However, there are some outliers, such as the SECRET algorithm, which has a significantly higher timing value. ### Key Observations - The majority of algorithms have a similar timing performance. - The SECRET algorithm has a significantly higher timing value compared to others. - There are no clear trends or patterns in the data. ### Interpretation The heatmap suggests that the timing performance of the algorithms is relatively consistent. However, the SECRET algorithm has a significantly higher timing value, which could indicate a potential security vulnerability or a performance issue. Further analysis would be needed to determine the cause of this discrepancy. </details> 20 , σ 8 . 48% ). Since the latencies between a correct and incorrect guess are in the microseconds range, we do not observe false positives with our approach. Figure 8 shows the median response time for each guess in the first iteration (leaking the first byte) as a representative example. It can be seen that the response time for the correct guess ( S ) for the first byte is significantly faster than the incorrect guesses. We observe similar results for the remaining bytes ( E,C,R,E,T ). Dictionary attack. While bytewise leakage is the more generic and practical approach for decompression timing attacks, there might be use cases where also a dictionary attack is applicable. For instance, if the attacker would try the top n most common usernames or passwords, which are publicly available. Another use case for dictionary attacks could be to profile if certain images are forbidden in a database used for digital rights management. We perform a dictionary attack over the network using randomly generated 100 guesses, including the correct guess. We repeat the experiment 20 times. For each run, we re-generate the guesses and randomly shuffle the order of the guesses per request iteration to not create a potential bias. On average, our attack leaks the secret string in 14 . 99 min ( n 20 , σ 16 . 27% ). To classify the correct guess, we use the same early stopping technique as was used for the covert channel. Since the timing difference is in the microseconds range, we do not observe false positives with our approach. Figure 9 illustrates the median of the response times for each guess from one iteration. Figure 15 (in Appendix D) shows the latencies for all leaked bytes. It can be clearly seen that the response time for the correct guess ( SECRET ) is significantly faster. Takeaway: We show that a PHP application using Memcached to cache blobs hosted on Nginx enables covert communication with a transmission rate of 643 . 25 bit ♥ h . If secret data is stored together with attacker-controlled data, we demonstrate a remote memory-compression attack on Memcached leaking a 6 B -secret bytewise in 31 . 95 min . We further demonstrated that the attack can also be used for dictionary attacks. ## D. Leaking Data from Compressed Database In this section, we show that an attacker can also exploit compression in databases to leak inaccessible information, i.e. , from the internal database compression of PostgreSQL. PostgreSQL Data Compression. PostgreSQL is a widespread open-source relational database system using the SQL standard. PostgreSQL maintains tuples saved on disk using a fixed page size of commonly 8 kB , storing larger fields compressed and possibly split into multiple pages. By default, variable-length fields that may produce large values, e.g., TEXT fields, are stored compressed. PostgreSQL's transparent compression is known as TOAST (The OversizedAttribute Storage Technique) and uses a fast LZ-family compression, PGLZ [46]. By default, data in a cell is actually stored compressed if such a form saves at least 25 % of the uncompressed size to avoid wasting decompression time if it is not worth it. Indeed, data stored uncompressed is accessed faster than data stored compressed since the decompression algorithm is not executed. Moreover, the decompression time depends on the compressibility of the underlying data. A potential attack scenario for structured text in a cell is where JSON documents are stored and compressed within a single cell, and the attacker controls a specific field within the document. While our focus is restricted to cell-level compression, note that compressed columnar storage [9], [39], [7], a non-default extension available in PostgreSQL, may also be vulnerable to decompression timing attacks. Attack Setup. To assess the feasibility of an attack, we use a local database server and access two differently compressed rows with a Python wrapper using the psycopg2 library. The first row contains 8192 characters of highly compressible data, while the second one 8192 characters of random incompressible data. Both rows are stored in a table as TEXT data and accessed 1000 times. The median for the number of clock cycles required to access the compressible row is 249 031 , while for the uncompressed one is 221 000 , which makes the two accesses distinguishable. On our 4 GHz CPUs, this is a timing difference of 7007 . 75 ns . We use Comprezzor to amplify these timing differences and demonstrate a bytewise leakage of a secret and also a dictionary attack. Leaking First Byte. For the bytewise leeakage of the secret, we first create a memory layout to leak the first byte using Comprezzor against a standalone version of PostgreSQL's compression library, using a similar setup as the previous Memcached attack. A key difference in the use of Comprezzor with PostgreSQL is that the helper program measuring the decompression time returns a time of 0 when the input is not compressed, i.e. , the data compressed with PGLZ does not save at least 25 % of the original size. Comprezzor found a layout that sits exactly at the corner case where a correct guess in the secret results in a compressed size that saves 25 % of the original size. Hence, a correct guess is saved compressed, while for any wrong guess, the threshold is not met, and the data is saved uncompressed. This is because the correct guess characters match the secret bytes and result in a higher compression rate. Leaking Subsequent Bytes with Secret Shifting. We observed that one good layout is enough and can be reused for bytewise leakage in PGLZ. The prefix can be shifted by one character to the left by a single character, i.e. , from 'cookie=S' to 'ookie=SE', to accommodate an additional byte for the guess. This shifting allows bytewise leakage with the same memory layout. Note, that the same approach did not work Fig. 10: Distribution of the response time for the first-byte guesses in the remote PostgreSQL attack leaking a secret bytewise, with the correct guess (S) and incorrect guesses (0-9, A-R, T-Z). Similar trends are observed for subsequent bytes leaked as shown in Appendix D. <details> <summary>Image 10 Details</summary>  ### Visual Description ## Heatmap: Byte 0 ### Overview The heatmap displays the timing measurements in nanoseconds (ns) for different cookies (cookie=0 to cookie=Z) at Byte 0. The x-axis represents the cookies, and the y-axis represents the timing in nanoseconds. ### Components/Axes - **X-axis**: Labeled "cookie=0" to "cookie=Z" with values 0, 5, 9, A, H, M, S, and Z. - **Y-axis**: Labeled "Timing (ns)" with a scale from 1.2 to 1.35. - **Legend**: Located at the bottom right, indicating the color coding for the cookies. - **Title**: "Byte 0" at the top center. ### Detailed Analysis or ### Content Details The heatmap shows a distribution of timing measurements across different cookies. The majority of the data points are clustered around the 1.2 ns mark, with some points slightly above and below this value. The red dot stands out, indicating a significantly higher timing measurement compared to the other data points. ### Key Observations - The majority of the data points are close to 1.2 ns. - There is a notable outlier at the red dot, which is significantly higher than the rest. - The distribution appears to be relatively even, with no single cookie having a drastically higher or lower timing measurement. ### Interpretation The heatmap suggests that the timing measurements for most cookies at Byte 0 are relatively consistent, with most falling within a narrow range of 1.2 ns. The outlier at the red dot indicates a potential issue or anomaly in the timing measurement for that specific cookie. This could be due to a variety of factors, such as a hardware malfunction, a software bug, or an unusual data point. Further investigation would be needed to determine the cause of this outlier and to understand its implications for the overall system performance. </details> Fig. 11: Distribution of the response time in the remote PostgreSQL dictionary attack, for the correct guess (SECRET) and the 99 other incorrect guesses (we only label 4 out of 99 incorrect guesses and SECRET on the X-axis for brevity). <details> <summary>Image 11 Details</summary>  ### Visual Description ## Heatmap: Timing Analysis ### Overview The heatmap displays the timing data for various guesses, with the x-axis representing different guesses and the y-axis representing the timing in nanoseconds (ns). The color intensity indicates the magnitude of the timing difference. ### Components/Axes - **X-axis**: Labeled "Guess" with values ranging from "02OdDt" to "youFg0". - **Y-axis**: Labeled "Timing [ns]" with values ranging from 1.2 to 1.35. - **Legend**: Located at the top right corner, indicating the color coding for different guesses. - **Data Points**: Blue dots representing the timing data for each guess. ### Detailed Analysis or ### Content Details The heatmap shows a distribution of timing data with most points clustered around the 1.2 ns mark. There is a single red dot at approximately 1.35 ns, indicating a significant outlier. The color intensity varies, with darker shades representing higher timing differences. ### Key Observations - The majority of guesses have a timing difference of around 1.2 ns. - There is a notable outlier at 1.35 ns. - The distribution is relatively even, with no single guess dominating the timing data. ### Interpretation The heatmap suggests that most guesses have a timing difference of around 1.2 ns, which could indicate a consistent performance or a standard deviation in the timing data. The outlier at 1.35 ns could be due to a specific event or condition that caused a significant delay. The even distribution of data points suggests that the timing differences are relatively consistent across the guesses. </details> on DEFLATE. We leave it as future work, to mount such a shifting approach to other compression algorithms. Evaluation. We perform a remote decompression timing attack against a Flask [17] web server that uses a PostgreSQL database to store user-provided data. We used the same Equinix cloudserver setup as used for the Memcached remote attack (cf. Section VI-C). The server runs Python 3.8.5 with Flask version 2.0.1 and PostgreSQL version 12.7. We define a 6 B long-secret with a 7 B prefix that the server colocates with attacker-provided data in a cell of the database through POST requests. The secret is never shown to the user. Using the layout found by Comprezzor, the entry in the database is stored compressed only when the secret matches in the provided data. A second endpoint in the server accesses the database to read the data without returning the secret to the attacker. The attack leaks bytewise over the internet by guessing again in the character set 'A-Z,0-9' ( 36 possibilities per character), including the correct one. We repeat the attack 20 times. The average time required to determine the guess with the highest latency (that the server had to decompress before returning) is 17 . 84 min ( 2 . 97 min ♥ B ) ( n 20 , σ 2 . 3% ). Figure 10 illustrates the median of the response times for a single guess in an example iteration, showing how the correct guess results in a slower response. Dictionary attack. We also performed a dictionary attack over the internet with 100 randomly generated guesses, including the correct one, and repeated the experiments 20 times. We measured the time required for the server to reply to a request in the second endpoint by observing the network packets arriving at our machine with the same setup as the remote Memcached attack, repeating each request 100 times. The average time required to brute-force all the guesses and select the guess with the highest latency (that the server had to decompress before returning) is 8 . 28 min ( n 20 , σ 0 . 003% ). Figure 11 illustrates the median of the response times for each guess in an example iteration, showing how the correct guess results in a slower response. Again, the timing difference is clearly distinguishable over 14 h ops in the internet. Takeaway: Secrets can be leaked from databases due to timing differences caused by PostgreSQL's transparent compression, if an application stores untrusted data with secrets in the same cell of a database. With a Flask appplication using a PostgreSQL database, we show that an attacker can infer when its inserted data matches the secret based on response times, which are influence by the decompression timing. Our decompression timing attack on PostgreSQL leaks a 6 B secret bytewise over the network in 17 . 84 min . ## E. Attacking OS Memory Compression In this section, we show how memory compression in modern OSs can introduce exploitable timing differences. In particular, we demonstrate a dictionary-based attack to leak secrets from compressed pages in ZRAM, the Linux implementation of memory compression. Background. Memory compression is a technique used in many modern OSs, e.g., Linux [34], Windows [28], or MacOS [11]. Similar to traditional swapping, memory compression increases the effective memory capacity of a system. When processes require more memory than available, the OS can transparently compress unused pages in DRAM to ensure they occupy a smaller footprint in DRAM rather than swapping them to disk. This frees up memory while still allowing the compressed pages to be accessed from DRAM. Compared to disk I/O, DRAM access is an order of magnitude faster, and even with the additional decompression overhead, memory compression is significantly faster than swapping. Hence, memory compression can improve the performance despite the additional CPU cycles required for compression and decompression. Such memory compression is adopted in the Linux kernel (since kernel version 3.14) in a module called ZRAM [26], which is enabled by default on Fedora [34] and Chrome OS [11]. 1) Characterizing Timing Differences in ZRAM: To understand how memory compression can be exploited, we characterize its behavior in ZRAM. On Linux systems, ZRAM appears as a DRAM-backed block device. When pages need to be swapped to free up memory, they are instead compressed and moved to ZRAM. Subsequent accesses to data in ZRAM result in a page fault, and the page is decompressed from ZRAM and copied to a regular DRAM page for use again. We show that the time to access data from a ZRAM page depends on its compressibility and thus the data values. We characterize the latency of accessing data from ZRAM pages with different entropy levels: pages that are incompressible (with random bytes), partially-compressible (random values for 2048 bytes and a fixed value repeated for the remaining TABLE III: Mean latency of accesses to ZRAM. Distinguishable timing differences exist based on data compressibility in the pages ( n 500 and 6% of samples removed as outliers with more than an order of magnitude higher latency). | Algorithm | Incompressible (ns) | Partly Compressible (ns) | Fully Compressible (ns) | |-------------|------------------------|----------------------------|---------------------------| | deflate | 1763 ( 12% ) | 12208 ( 2% ) | 1551 ( 12% ) | | 842 | 1789 ( 11% ) | 8785 ( 2% ) | 1556 ( 10% ) | | lzo | 1684 ( 9% ) | 4866 ( 4% ) | 1479 ( 12% ) | | lzo-rle | 1647 ( 9% ) | 4751 ( 4% ) | 1453 ( 12% ) | | zstd | 1857 ( 10% ) | 2612 ( 9% ) | 1674 ( 11% ) | | lz4 | 1710 ( 11% ) | 1990 ( 7% ) | 1470 ( 10% ) | | lz4hc | 1746 ( 9% ) | 2091 ( 9% ) | 1504 ( 11% ) | 2048 bytes), and fully-compressible (a fixed value in each of the 4096 bytes). We ensure a page is moved to ZRAM by accessing more memory than the memory limit allows. To ensure fast run times for the proof of concept, we allocate the process to a cgroup with a memory limit of a few megabytes. We measure the latency for accessing a 8-byte word from the page in ZRAM, and repeat this process 500 times. Table III shows the mean latency for ZRAM accesses for different ZRAM compression algorithms on an Intel i76700K (Ubuntu 20.04, kernel 5.4.0). The latency for accesses to ZRAM is much higher for partially compressible pages (with lower entropy) compared to incompressible pages (with higher entropy) for all the compression algorithms. This is because the process of moving compressed ZRAM pages to regular memory on an access requires additional calls to functions that decompress the page; on the other hand, ZRAM pages that are stored uncompressed do not require these function calls (Appendix B provides a trace of the kernel function calls on ZRAM accesses and their execution times to illustrate this difference). The largest timing difference is observed for deflate algorithm (close to 10 000 ns ) and 842 algorithm (close to 7000 ns ); moderate timing differences are observed for lzo and lzo-rle (close to 1000 ns ), and zstd (close to 750 ns ); the smallest timing difference is seen for lz4 and lz4hc (close to 250 ns ). These timing differences largely correspond with the raw decompression latency for these algorithms, some of which are measured in Table I. Accesses to a fully-compressible page in ZRAM, i.e. , a page containing the same byte repeatedly, are faster (by 200 ns ) than accesses to an incompressible page for all the compression algorithms. This is because ZRAM stores such pages with a special encoding as a single-byte (independent of the compression algorithm) that only requires reading a single byte from ZRAM on an access to such a page. 2) Leaking Secrets via ZRAM Decompression Timings: In this section, we exploit timing differences between accesses to a partially compressible and incompressible page in ZRAM (using deflate algorithm) to leak secrets. Like previous PoCs, we use Comprezzor to generate data layouts that maximize the decompression-timing difference for the correct guess, while leaking a secret byte-wise. Attack Setup. We demonstrate byte-wise leakage attack on a program with a 4KB page stored in ZRAM containing both a secret value and attacker-controlled data, as is common in many applications like databases. To determine optimal data layouts an attacker might use, we combine this program with Comprezzor. With a known secret value, Comprezzor runs the program with the attacker guessing each byte position successively. For each byte position, Comprezzor measures the decompression time for the page from ZRAM with different attacker data layouts and different attacker guesses, and the layout maximizing the timing difference when the attacker's guessed-byte matches the secret-byte is returned. In such an optimal layout, when the attacker's guess matches the secretbyte, the page entropy reduces (page is partially compressible) and ZRAM decompression takes longer; and for all other guesses, the entropy is high and ZRAM decompression is fast. We repeat this process to generate optimal data layouts for each byte position. Note that this optimal data layout only relies on the number of repetitions of the guess and the relative position of the guessed data and the secret (a property of the compression algorithm), and is applicable with any data values. Using these attacker data-layouts, we perform the byte-wise leakage of an unknown secret. At each step, the attacker makes one-byte guesses (0-9, A-Z) and then denotes the guess with the highest latency to be the 'correct' guess. It appends this value to its guess-string and then guesses the next byte-position. We repeat this attack for 100 random secret strings. Evaluation. Figure 12 shows the bytewise leakage for a secret value (cookie= SECRET ), with the decompression times for guesses of the first four bytes depicted in each of the graphs. For each byte, among guesses of (0-9,A-Z), the highest decompression time successfully leaks the secret byte value (shown in red). For example, for byte-0, the highest time is for cookie= S and similarly for byte-1, it is cookie= SE . For byte-2, we observe a false-positive, cookie= SE8 , which also has a high latency along with the correct guess cookie= SEC . But in the subsequent byte-3, with both these strings used as prefixes for the guesses, the false-positives are eliminated and cookie= SECR is obtained as the correct guess. The next two bytes are also successfully leaked to fully obtain cookie= SECRET , as shown in the Figure 17 in Appendix D. Our attack successfully completes in less than 5 minutes. Over 100 randomly generated secrets, we observe that 90% of secrets are exactly leaked successfully. In 9 out 10 remaining cases, we narrow down the secret to within four 6-byte candidates (due to false-positives) and in the last case we recover only 4 out of 6-bytes of the secret (as the false-positives grows considerably beyond this). These false-positives arise due to the data-layouts generated not being as robust as in previous PoCs. Comprezzor with ZRAM is a few orders of magnitude slower (almost 0.03x the speed) compared to iterations with raw algorithms studied in Section V-B, so it is unable to explore as large a search space as previous PoCs. This is because moving a page to ZRAM and compressing it requires accessing sufficient memory to swap the page out, which is slower than just executing the compression algorithm. But such false positives can be easily addressed by using multiple data-layouts per byte (each layout causes different false-positives), or by fuzzing for a longer duration to generate more robust data-layouts. The fuzzing speed can also be increased by implementing the ZRAM compression algorithm (a fork of zlib) inside Comprezzor, so this is not a fundamental limitation. Dictionary Attack. For completeness, we also demonstrate a dictionary attack where the secret is guessed from a range Fig. 12: Times for guesses (0-9, A-Z) for each of the first four bytes (S, E, C, R) in a 6-byte secret (cookie= SECRET ) leaked byte-wise from ZRAM. The highest times correspond to the secret-byte value (shown in red). The last two bytes (E, T) are also successfully leaked similarly and shown in Appendix D. <details> <summary>Image 12 Details</summary>  ### Visual Description ## Heatmap Analysis ### Overview The image displays a heatmap with four axes labeled Byte 0, Byte 1, Byte 2, and Byte 3. Each byte is represented by a horizontal axis, and the heatmap shows the timing values in nanoseconds (ns) for different cookie values. ### Components/Axes - **Byte 0**: The horizontal axis represents Byte 0, with values ranging from 0 to 1.5 x 10^4 ns. - **Byte 1**: The horizontal axis represents Byte 1, with values ranging from 0 to 1.5 x 10^4 ns. - **Byte 2**: The horizontal axis represents Byte 2, with values ranging from 0 to 1.5 x 10^4 ns. - **Byte 3**: The horizontal axis represents Byte 3, with values ranging from 0 to 1.5 x 10^4 ns. - **Cookies**: The vertical axis represents different cookie values, labeled from cookie=0 to cookie=SECRZ. ### Detailed Analysis or ### Content Details The heatmap shows the timing values for each byte and cookie combination. The data points are represented by blue dots, and the red dot indicates a specific value of interest. The heatmap is color-coded, with darker shades representing higher timing values. ### Key Observations - **Byte 0**: The majority of data points are clustered around the 0 ns mark, indicating that the timing values for Byte 0 are relatively low. - **Byte 1**: The data points are more spread out, with some values reaching up to 1.5 x 10^4 ns. - **Byte 2**: The data points are similar to Byte 1, with some values reaching up to 1.5 x 10^4 ns. - **Byte 3**: The data points are similar to Byte 1 and Byte 2, with some values reaching up to 1.5 x 10^4 ns. ### Interpretation The heatmap suggests that the timing values for Byte 0 are relatively low, while the timing values for Byte 1, Byte 2, and Byte 3 are higher. This could indicate that the timing values for Byte 0 are related to the cookie value, while the timing values for the other bytes are not. The red dot indicates a specific value of interest, which could be used to further investigate the relationship between the cookie value and the timing values. </details> Fig. 13: Median latency for ZRAM accesses in dictionary attack, with correct guess SECRET and 99 incorrect guesses (we only label 4 out of 99 incorrect guesses on X-axis for brevity). <details> <summary>Image 13 Details</summary>  ### Visual Description ## Heatmap: Timing Analysis ### Overview The heatmap displays the timing measurements for various guesses, represented by different colors. The x-axis lists the guesses, while the y-axis shows the timing in nanoseconds (ns). ### Components/Axes - **X-axis**: Guesses labeled as "9Q7Lwt", "1MP6Pv", "SECRET", "0NSQFp", and "e4gvLN". - **Y-axis**: Timing in nanoseconds (ns), ranging from 0 to 1.5 x 10^4 ns. - **Color Scale**: The heatmap uses a color gradient from blue to red, indicating increasing timing values. ### Detailed Analysis or ### Content Details - The guess "SECRET" has the highest timing value, approximately 1.5 x 10^4 ns, marked by a red dot. - The other guesses have significantly lower timing values, ranging from 0 to 0.5 x 10^4 ns, represented by blue dots. - The timing values for the other guesses are relatively close to each other, with "9Q7Lwt" and "1MP6Pv" having the lowest values. ### Key Observations - The guess "SECRET" is the most time-consuming, indicating it may be the slowest or most complex. - The other guesses have shorter timing values, suggesting they are faster or simpler. - There is a noticeable difference in timing between the guesses, with "SECRET" being the outlier. ### Interpretation The heatmap suggests that the guess "SECRET" is significantly slower than the others, which could imply that it is more complex or requires more computational resources. The other guesses are likely faster and simpler, which could be due to their design or implementation. The difference in timing could be due to various factors such as algorithm efficiency, hardware constraints, or the complexity of the guess itself. </details> of 100 possible guesses (dictionary), similar to previous PoCs. We assume the target page has a secret embedded the tophalf and the bottom half of the page is attacker-controlled and filled with repeated guesses from a dictionary. Figure 13 shows the median latency for attacker's data access from ZRAM (over 10 observations) for different guesses from the dictionary. The guesses consist of 99 randomly generated strings and the secret (cookie= SECRET ). We observe a high timing for decompression when the guess matches the secret as the page entropy is lowered (and the page compressed in ZRAM), thus leaking the secret; for all other guesses the decompression is fast. This dictionary attack completes in less than 10 minutes. But in general, the duration depends on the time required to force a target page into ZRAM, depending on the physical memory limit for a target process. Takeaway: We show that even if an application does not explicitly use compression, its data may still get compressed by the OS due to memory compression. Our case study of ZRAM shows that all compression algorithms in ZRAM have timing differences of 250 ns to 10 400 ns for accesses to compressed versus uncompressed pages. We also show that if secrets are co-located with attacker-controlled data in the same page and compressed with memory compression, they can be leaked in minutes. ## VII. MITIGATIONS Disabling LZ77. The most rudimentary solution is to completely disable compression or at least disable the LZ77 part. Karakostas et al. [31] showed for web pages that this adds an overhead between 91 % and 500 % . Furthermore, attacks have not been studied well enough on symbol compression to provide any security guarantees. Masking. Karakostas et al. [31] presented a generic defense technique called Context Transformation Extension (CTX). The general idea is to use context-hiding to protect secrets from being compressed with attacker-controlled data. Data is permuted on the server-side using a mask, and on the clientside, an inverse permutation is performed (JavaScript library). The overhead compared to the original algorithms decrease with the number of compressed data [31]. Randomization. Yang et al. [61] showed an approach with randomized input to mitigate compression side-channel attacks. The service would require adding an additional amount of random data to hide the size of the compressed memory. However, as the authors also show, randomization-based approaches can be defeated with at the expense of a higher execution time. Also, Karaskostas et al. [31] showed that size randomization is ineffective against memory compression attacks. It is also unclear if size randomization mitigates the timing-based side channel of the memory decompression. Keyword protection. Zieli´ nski demonstrated an implementation of DEFLATE called SafeDeflate [66]. SafeDeflate mitigates memory compression attacks by splitting the set of keywords into subsets of sensitive and non-sensitive keywords. Depending on the completeness of the sensitive keyword list, this approach can be considered as secure, but there is no guaranteed security. As Paulsen et al. [43] mention, it is easy to overlook a corner case. Furthermore, this approach leads to a loss of compression ratio of about 200 % to 400 % [31]. Taint tracking. Taint tracking tries to trace the data flow and mark input sources and their sinks. Paulsen et al. [43] use taint analysis to track the flow of secret data before feeding data into the compression algorithm. Their tool, Debreach, is about 2-5 times faster than SafeDeflate [43]. However, this approach is, so far, only compatible with PHP. Furthermore, for such an approach, the developer needs to flag the sensitive input which is being tracked. The probably best strategy in practice is to avoid sensitive data being compressed with potential attacker-controlled data. The aforementioned mitigations focus on mitigating compression ratio side channels. As the compression and decompression timings are not constant, a timing side channel is harder to mitigate, e.g., remote attacks might be mitigated by adding artificial noise or using network packet inspection to detect attacks [52]. Since the latency for a correct guess is in the region of microseconds, not many requests ( & 200 ) are required per guess to distinguish the latency. Therefore a simple DDoS detection might detect an attack but only after a certain amount of data being leaked. ## VIII. CONCLUSION In this paper, we presented a timing side channel attack on several memory compression algorithms. With Comprezzor, we developed a generic approach to amplify latencies for correct guesses when performing dictionary attack on different compression algorithms. Our remote covert channel achieves a transmission rate of 643 . 25 bit ♥ h over 14 hops in the internet. We demonstrated three cases studies on memory compression attacks. First, we showed a remote dictionary attack on a PHP application, hosted on an Nginx, storing zlibcompressed data in Memcached. We demonstrate bytewise leakage across the internet from a server located 14 hops away. Using Comprezzor, we explored high timing differences when performing a dictionary attack on PostgreSQLs PGLZ algorithm. and leveraged those to leak database records from PostgreSQL. Lastly, we also demonstrated a dictionary attack on ZRAM. ## REFERENCES - [1] Acıic ¸mez, Onur and Schindler, Werner and Koc, Cetin K. Cache based remote timing attack on the aes. In CT-RSA , 2006. - [2] Hassan Aly and Mohammed ElGayyar. Attacking aes using bernstein's attack on modern processors. In International Conference on Cryptology in Africa , 2013. - [3] Apple Insider, 2013. URL: https://appleinsider.com/articles/13/06/13/c ompressed-memory-in-os-x-109-mavericks-aims-to-free-ram-extendbattery-life. - [4] Tal Be'ery and Amichai Shulman. A Perfect CRIME? Only TIME Will Tell. Black Hat Europe , 2013. - [5] Bmemcached. bmemcached package, 2021. URL: https://python-binarymemcached.readthedocs.io/en/latest/bmemcached/. - [6] BTRFS. Compression, 2021. URL: https://btrfs.wiki.kernel.org/index. php/Compression#Why does not du report the compressed size.3F. - [7] Buckenhofer. PostgreSQL Columnar Storage, 2021. URL: https://www. buckenhofer.com/2021/01/postgresql-columnar-extension-cstore/. - [8] Euccas Chen. Understanding zlib, 2021. URL: https://www.euccas.me/ zlib/#deflate. - [9] Citus. Columnar: Distributed PostgreSQL as an extension., 2021. URL: https://github.com/citusdata/citus/blob/master/src/backend/columnar/RE ADME.md. - [10] Collett, Yann. Smaller and faster data compression with Zstandard, 2016. URL: https://engineering.fb.com/2016/08/31/core-data/smaller-andfaster-data-compression-with-zstandard/. - [11] DennyL. Enabling ZRAM in Chrome OS, 2020. URL: https://suppor t.google.com/chromebook/thread/75256850/enabeling-zram-doesn-twork-in-crosh?hl=en&msgid=75453860. - [12] P. Deutsch. Rfc1951: Deflate compressed data format specification version 1.3, 1996. - [13] Equinix, 2021. URL: https://www.packet.com/. - [14] Dmitry Evtyushkin and Dmitry Ponomarev. Covert channels through random number generator: Mechanisms, capacity estimation and mitigations. In CCS , 2016. - [15] R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee. Rfc 2616, hypertext transfer protocol - http/1.1, 1999. URL: http://www.rfc.net/rfc2616.html. - [16] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. AFL++: Combining incremental steps of fuzzing research. In USENIX Workshop on Offensive Technologies (WOOT) , August 2020. - [17] Flask. Flask, 2021. URL: https://flask.palletsprojects.com/en/2.0.x/. - [18] Anders Fogh. Covert Shotgun: automatically finding SMT covert channels, 2016. URL: https://cyber.wtf/2016/09/27/covert-shotgun/. - [19] Gailly, Jean-loup and Adler, Mark. zlib.h - interface of the 'zlib' general purpose compression library, 2020. URL: https://github.com/torvalds/li nux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/include/linux/ zlib.h. - [20] Yoel Gluck, Neal Harris, and Angelo Prado. BREACH: reviving the CRIME attack. Unpublished manuscript , 2013. - [21] Ben Gras, Cristiano Giuffrida, Michael Kurth, Herbert Bos, and Kaveh Razavi. ABSynthe: Automatic Blackbox Side-channel Synthesis on Commodity Microarchitectures. In NDSS , 2020. - [22] Daniel Gruss, Erik Kraft, Trishita Tiwari, Michael Schwarz, Ari Trachtenberg, Jason Hennessey, Alex Ionescu, and Anders Fogh. Page Cache Attacks. In CCS , 2019. - [23] Daniel Gruss, Cl´ ementine Maurice, Klaus Wagner, and Stefan Mangard. Flush+Flush: A Fast and Stealthy Cache Attack. In DIMVA , 2016. - [24] Daniel Gruss, Raphael Spreitzer, and Stefan Mangard. Cache Template Attacks: Automating Attacks on Inclusive Last-Level Caches. In USENIX Security Symposium , 2015. - [25] Berk G¨ ulmezo˘ glu, Mehmet Sinan Inci, Thomas Eisenbarth, and Berk Sunar. A Faster and More Realistic Flush+Reload Attack on AES. In COSADE , 2015. - [26] Gupta, Nitin. zram: Compressed RAM-based block devices, 2021. URL: https://www.kernel.org/doc/html/latest/admin-guide/blockdev/zram.ht ml. - [27] Shaobo He, Michael Emmi, and Gabriela Ciocarlie. ct-fuzz: Fuzzing for timing leaks. In International Conference on Software Testing, Validation and Verification (ICST) , 2020. doi:10.1109/ICST46399.2020 .00063 . - [28] Hoffman, Chris. What Is Memory Compression in Windows 10?, 2017. URL: https://www.howtogeek.com/319933/what-is-memory-compressio n-in-windows-10/. - [29] holmeshe.me. Understanding the memcached source code - slab ii, 2020. URL: https://holmeshe.me/understanding-memcached-source-code-II/. - [30] Darshana Jayasinghe, Jayani Fernando, Ranil Herath, and Roshan Ragel. Remote cache timing attack on advanced encryption standard and countermeasures. In ICIAFs , 2010. - [31] Dimitris Karakostas, Aggelos Kiayias, Eva Sarafianou, and Dionysis Zindros. Ctx: Eliminating breach with context hiding. Black Hat EU , 2016. - [32] Dimitris Karakostas and Dionysis Zindros. Practical new developments on breach. Black Hat Asia , 2016. - [33] John Kelsey. Compression and information leakage of plaintext. In Fast Software Encryption , 2002. - [34] Larabel, Michael. What Is Memory Compression in Windows 10?, 2020. URL: https://www.phoronix.com/scan.php?page=news item&px=Fedo ra-33-Swap-On-zRAM-Proposal. - [35] Moritz Lipp, Daniel Gruss, Raphael Spreitzer, Cl´ ementine Maurice, and Stefan Mangard. ARMageddon: Cache Attacks on Mobile Devices. In USENIX Security Symposium , 2016. - [36] Fangfei Liu, Yuval Yarom, Qian Ge, Gernot Heiser, and Ruby B. Lee. Last-Level Cache Side-Channel Attacks are Practical. In S&P , 2015. - [37] Cl´ ementine Maurice, Manuel Weber, Michael Schwarz, Lukas Giner, Daniel Gruss, Carlo Alberto Boano, Stefan Mangard, and Kay R¨ omer. Hello from the Other Side: SSH over Robust Cache Covert Channels in the Cloud. In NDSS , 2017. - [38] Memcached, 2020. URL: https://memcached.org/. - [39] Microsoft. concepts-hyperscale-columnar, 2021. URL: https://docs.mic rosoft.com/en-us/azure/postgresql/concepts-hyperscale-columnar. - [40] Daniel Moghimi, Moritz Lipp, Berk Sunar, and Michael Schwarz. Medusa: Microarchitectural Data Leakage via Automated Attack Synthesis. In USENIX Security Symposium , 2020. - [41] Mozilla. Compression in HTTP, 2021. URL: https://developer.mozilla. org/en-US/docs/Web/HTTP/Compression. - [42] Shirin Nilizadeh, Yannic Noller, and Corina S Pasareanu. Diffuzz: differential fuzzing for side-channel analysis. In International Conference on Software Engineering (ICSE) , 2019. - [43] Brandon Paulsen, Chungha Sung, Peter AH Peterson, and Chao Wang. Debreach: mitigating compression side channels via static analysis and transformation. In IEEE/ACM International Conference on Automated Software Engineering (ASE) . IEEE, 2019. - [44] Peter Pessl, Daniel Gruss, Cl´ ementine Maurice, Michael Schwarz, and Stefan Mangard. DRAMA: Exploiting DRAM Addressing for CrossCPU Attacks. In USENIX Security Symposium , 2016. - [45] php.net. memcached.constants.php, 2021. URL: https://www.php.net/ manual/en/memcached.constants.php. - [46] PostgreSQL. TOAST Compression, 2021. URL: https://www.postgresql .org/docs/current/storage-toast.html. - [47] Hany Ragab, Alyssa Milburn, Kaveh Razavi, Herbert Bos, and Cristiano Giuffrida. CrossTalk: Speculative Data Leaks Across Cores Are Real. In S&P , 2021. - [48] Sanjay Rawat, Vivek Jain, Ashish Kumar, Lucian Cojocar, Cristiano Giuffrida, and Herbert Bos. Vuzzer: Application-aware evolutionary fuzzing. In NDSS , 2017. - [49] Juliano Rizzo and Thai Duong. The CRIME attack. In ekoparty security conference , volume 2012, 2012. - [50] Rostedt, Steven. ftrace - Function Tracer, 2017. URL: https://www.kern el.org/doc/Documentation/trace/ftrace.txt. - [51] Vishal Saraswat, Daniel Feldman, Denis Foo Kune, and Satyajit Das. Remote cache-timing attacks against aes. In Workshop on Cryptography and Security in Computing Systems , 2014. - [52] Michael Schwarz, Martin Schwarzl, Moritz Lipp, and Daniel Gruss. NetSpectre: Read Arbitrary Memory over Network. In ESORICS , 2019. - [53] Benjamin Semal, Konstantinos Markantonakis, Keith Mayes, and Jan Kalbantner. One covert channel to rule them all: A practical approach to data exfiltration in the cloud. In IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) , 2020. - [54] Dongdong She, Kexin Pei, Dave Epstein, Junfeng Yang, Baishakhi Ray, and Suman Jana. Neuzz: Efficient fuzzing with neural program smoothing. In IEEE Symposium on Security and Privacy , 2019. doi: 10.1109/SP.2019.00052 . - [55] Po-An Tsai, Andres Sanchez, Christopher W. Fletcher, and Daniel Sanchez. Safecracker: Leaking secrets through compressed caches. In ASPLOS , 2020. - [56] Tom Van Goethem, Christina P¨ opper, Wouter Joosen, and Mathy Vanhoef. Timeless Timing Attacks: Exploiting Concurrency to Leak Secrets over Remote Connections. In USENIX Security Symposium , 2020. - [57] Tom Van Goethem, Mathy Vanhoef, Frank Piessens, and Wouter Joosen. Request and conquer: Exposing cross-origin resource size. In USENIX Security Symposium , 2016. - [58] Mathy Vanhoef and Tom Van Goethem. Heist: Http encrypted information can be stolen through tcp-windows. In Black Hat US Briefings, Location: Las Vegas, USA , 2016. - [59] Daniel Weber, Ahmad Ibrahim, Hamed Nemati, Michael Schwarz, and Christian Rossow. Osiris: Automated Discovery Of Microarchitectural Side Channels. In USENIX Security Symposium , 2021. - [60] Zhenyu Wu, Zhang Xu, and Haining Wang. Whispers in the Hyperspace: High-speed Covert Channel Attacks in the Cloud. In USENIX Security Symposium , 2012. - [61] Meng Yang and Guang Gong. Lempel-ziv compression with randomized input-output for anti-compression side-channel attacks under https/tls. In International Symposium on Foundations and Practice of Security . Springer, 2019. - [62] Yuval Yarom and Katrina Falkner. Flush+Reload: a High Resolution, Low Noise, L3 Cache Side-Channel Attack. In USENIX Security Symposium , 2014. - [63] Pavel Yosifovich, Alex Ionescu, Mark E. Russinovich, and David A. Solomon. Windows Internals Part 1 . Microsoft Press, 7 edition, 2017. - [64] Michał Zalewski. American Fuzzy Lop, 2021. URL: https://github.com /Google/AFL. - [65] Xin-jie Zhao, Tao Wang, and Yuanyuan Zheng. Cache Timing Attacks on Camellia Block Cipher. Cryptology ePrint Archive, Report 2009/354 , 2009. - [66] Michał Zielinski. Safedeflate: compression without leaking secrets. Technical report, Cryptology ePrint Archive, Report 2016/958. 2016, 2016. ## APPENDIX A TIMING DIFFERENCE FOR COMPRESSION TABLE IV: Different compression algorithms yield distinguishable timing differences when compressing content with a different entropy. ( n 100000 | Algorithm | Fully Compressible (ns) | Partially Compressible (ns) | Incompressible (ns) | |-----------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | FastLZ LZ4 LZ4 LZO PGLZ zlib zstd | 38619 . 07 ( 0 . 74% ) 606 . 82 ( 0 . 93% ) 44748 . 02 ( 0 . 15% ) 5645 . 86 ( 2 . 18% ) 44275 . 84 ( 0 . 13% ) 38479 . 53 ( 0 . 22% ) 3596 . 41 ( 0 . 42% ) | 58887 . 40 ( 0 . 50% ) 220 . 63 ( 1 . 00% ) 47731 . 08 ( 0 . 16% ) 5915 . 28 ( 2 . 78% ) 65752 . 55 ( 0 . 12% ) 80284 . 72 ( 0 . 23% ) 22288 . 14 ( 0 . 52% ) | 79384 . 89 ( 0 . 40% ) 231 . 76 ( 1 . 97% ) 47316 . 56 ( 0 . 16% ) 7928 . 21 ( 3 . 91% ) - 76973 . 82 ( 0 . 20% ) 29284 . 77 ( 0 . 34% ) | ## APPENDIX B KERNEL TRACE FOR ZRAM DECOMPRESSION To highlight the root-cause of the timing differences in ZRAM accesses, we trace the kernel functions called on accesses to ZRAM pages using the ftrace [50] utility. Listing 1 and Listing 2 show the trace of kernel functions called on an access to an incompressible and compressible page respectively in ZRAM (using deflate algorithm). The incompressible page contains random bytes, while the compressible page contains 2048 bytes of the same value and 2048 random bytes similar to the partially-compressible setting in Section VI-E1. We only show the functions which are called when the ZRAM page is swapped in to regular memory. The main difference between the two listings (colored in red) is that the functions performing decompression of the ZRAM page are only called when a compressible page is swapped-in, while these functions are skipped for the page stored uncompressed. Of these additional function calls, the main driver of the timing difference is the \_\_deflate\_decompress function in Listing 2 which consumes 12555 ns. This ties in with the characterization study in Section VI-E1 which showed the average timing difference between accesses to compressible and incompressible pages to be close to 10000 ns for ZRAM with deflate algorithm. These timings are for the deflate implementation in the Linux kernel, which is a modified version of zlib v1.1.3 [19]; hence these timings differ from the zlib timings measured in Table I for the more recent zlib v1.2.11 . Listing 1: Kernel function trace for ZRAM access to incompressible page <details> <summary>Image 14 Details</summary>  ### Visual Description ## Time(ns) Function ### Overview The image displays a table with a list of functions and their corresponding execution times in nanoseconds (ns). The table is organized in a tabular format with two columns: "Time(ns)" and "Function". ### Components/Axes - **Time(ns)**: This column lists the execution times in nanoseconds. - **Function**: This column lists the functions that are being executed. ### Detailed Analysis or Content Details The table provides a breakdown of the time taken by various functions. Each function is associated with a specific time value, indicating how long it takes to execute. The functions listed include operations related to memory management, such as swapping pages, reading and writing to files, and managing queues. ### Key Observations - **swap_readpage**: This function takes the least amount of time, suggesting it is the fastest operation in the list. - **page_swap_info**: This function takes a moderate amount of time, indicating it is a relatively slower operation compared to swap_readpage. - **_frontswap_load**: This function takes the most time, suggesting it is the slowest operation in the list. ### Interpretation The data suggests that the performance of the system is heavily influenced by the functions related to memory management. The functions that take the most time, such as _frontswap_load, indicate that these operations are critical for the system's performance. The functions that take the least time, such as swap_readpage, suggest that these operations are relatively fast and can be optimized for better performance. The interpretation also highlights the importance of optimizing these functions for better system performance. The data can be used to identify areas for improvement and to optimize the system's performance. </details> Listing 2: Kernel function trace for ZRAM access to compressible page <details> <summary>Image 15 Details</summary>  ### Visual Description ## Time (ns) Function ### Overview The image displays a table listing various functions and their corresponding execution times in nanoseconds (ns). The table is organized with two columns: "Time (ns)" and "Function". Each row represents a different function, with the time in nanoseconds listed next to it. ### Components/Axes - **Time (ns)**: This column lists the execution time in nanoseconds for each function. - **Function**: This column lists the names of the functions, which are related to data processing and compression. ### Detailed Analysis or Content Details - **swap_readpage**: This function takes approximately 61 ns to execute. - **page_frontswap_info**: This function takes approximately 123 ns to execute. - **__page_file_index**: This function takes approximately 188 ns to execute. - **bdev_read_page**: This function takes approximately 248 ns to execute. - **blk_queue_enter**: This function takes approximately 310 ns to execute. - **zram_rw_page**: This function takes approximately 379 ns to execute. - **zram_bvec_rw.isra.0**: This function takes approximately 442 ns to execute. - **generic_start_io_acct**: This function takes approximately 505 ns to execute. - **update_io_ticks**: This function takes approximately 575 ns to execute. - **part_inc_in_flight**: This function takes approximately 634 ns to execute. - **__zram_bvec_read.constprop.0**: This function takes approximately 755 ns to execute. - **__zmap_object**: This function takes approximately 838 ns to execute. - **__raw_read_lock**: This function takes approximately 1040 ns to execute. - **zcomp_stream_get**: This function takes approximately 1229 ns to execute. - **zcomp_decompress**: This function takes approximately 1306 ns to execute. - **crypto_decompress**: This function takes approximately 1373 ns to execute. - **deflate_decompress**: This function takes approximately 1433 ns to execute. - **__deflate_decompress**: This function takes approximately 1499 ns to execute. - **zcomp_stream_put**: This function takes approximately 14053 ns to execute. - **zs_unmap_object**: This function takes approximately 14117 ns to execute. - **generic_end_io_acct**: This function takes approximately 14195 ns to execute. - **update_io_ticks**: This function takes approximately 14317 ns to execute. - **jiffies_to_usecs**: This function takes approximately 14374 ns to execute. - **part_dec_in_flight**: This function takes approximately 14422 ns to execute. - **ktime_get_with_offset**: This function takes approximately 14518 ns to execute. - **page_endio**: This function takes approximately 14589 ns to execute. ### Key Observations - The function with the highest execution time is **zcomp_stream_put**, taking approximately 14053 ns. - The function with the lowest execution time is **swap_readpage**, taking approximately 61 ns. - There is a significant variation in the execution times, with some functions taking only a few nanoseconds and others taking several hundred nanoseconds. ### Interpretation The data suggests that the functions related to data compression and decompression, such as **zcomp_stream_get** and **zcomp_decompress**, are the most time-consuming. This could indicate that these functions are the most resource-intensive or that they are performing more complex operations. On the other hand, the function **swap_readpage** is the fastest, which could indicate that it is the most efficient or that it is performing a simple operation. The presence of functions related to data processing and compression suggests that the system is designed to handle large amounts of data and perform complex operations on it. The variation in execution times could be due to the complexity of the operations being performed or the efficiency of the underlying algorithms. </details> ## APPENDIX C ## LAYOUT DISCOVERED BY COMPREZZOR Figure 14 shows the layout discovered by the Comprezzor that amplifies the timing difference for decompression of the correct and incorrect guesses in Zlib dictionary attack. Listing 3 and Listing 4 show the debug trace from the Zlib code for decompression with the correct and incorrect guesses to illustrate the root cause of the timing differences. Fig. 14: Incorrect guesses with the corner-case discovered by Comprezzor lead to a dynamic Huffman block creation for the partially compressible data, that is slow to decompress. <details> <summary>Image 16 Details</summary>  ### Visual Description ## Diagram Type: Schematic Diagram ### Overview The image is a schematic diagram that illustrates the concept of data compression and decompression using Huffman coding. It compares two scenarios: a correct guess and an incorrect guess. ### Components/Axes - **New Dynamic Huffman Block**: Represented by a light brown color. - **Stored Block**: Represented by a light green color. - **Incompressible data**: Represented by a dark blue color. - **Pointer to cookie=SECRET x n**: Represented by a red color. - **Pointer to cookie=FOOBAR x n**: Represented by a light blue color. - **Incompressible data**: Represented by a dark brown color. ### Detailed Analysis or ### Content Details - **Correct guess**: The diagram shows a block of data that is compressed using Huffman coding. The data is represented by a pointer to a cookie with the value "SECRET" repeated n times. The compressed data is stored in a new dynamic Huffman block. - **Incorrect guess**: The diagram shows a block of data that is also compressed using Huffman coding, but the data is represented by a pointer to a cookie with the value "FOOBAR" repeated n times. The compressed data is stored in a stored block. ### Key Observations - The correct guess shows that the data is compressed using Huffman coding, which is an efficient compression algorithm. - The incorrect guess shows that the data is not compressed using Huffman coding, which is not an efficient compression algorithm. ### Interpretation The diagram demonstrates the importance of using an efficient compression algorithm like Huffman coding to compress data. The incorrect guess shows that using an inefficient compression algorithm like storing the data in a stored block can result in larger file sizes. The correct guess shows that using an efficient compression algorithm like Huffman coding can result in smaller file sizes. </details> Listing 3: Trace for correct guess in zlib. Here the entire guess string is compressed and the remainder is incompressible (decompressed fast as a stored block). <details> <summary>Image 17 Details</summary>  ### Visual Description ## Inflatable Data Representation ### Overview The image displays a series of data points represented in a structured format, likely a part of a larger dataset or a programming language's data structure. The data points are labeled with various identifiers and measurements, such as "length," "distance," and "literal." ### Components/Axes - **Labels**: "inflated," "length," "distance," "literal" - **Scales**: Numeric values ranging from 12 to 16484 - **Legends**: Color-coded for different data series - **Axis Markers**: Specific values like "12," "13," "14," etc. ### Detailed Analysis or ### Content Details The data points are organized in a list format, with each entry containing a label followed by a numeric value. The labels indicate the type of data, while the numeric values represent specific measurements or identifiers. The use of "literal" suggests that the data might be part of a string or a literal value in a programming context. ### Key Observations - **Notable Patterns**: The data points are evenly spaced, suggesting a regular pattern or sequence. - **Outliers**: There are no significant outliers in the data, as all values fall within the expected range. - **Trends**: The data points show a consistent increase in the numeric values, indicating a positive trend. ### Interpretation The data represents a series of measurements or identifiers that are likely used in a programming or data analysis context. The use of "literal" suggests that the data might be part of a string or a literal value in a programming language. The consistent increase in the numeric values indicates a positive trend or sequence. The color-coded legends help in distinguishing between different data series, which is useful for analysis and interpretation. </details> Listing 4: Trace for incorrect guess in zlib. Here only part of the guess string ( cookie= ) is compressed and the remainder cookie=FOOBAR is separately compressed (decompression requires a slower code block for Huffman tree decoding). <details> <summary>Image 18 Details</summary>  ### Visual Description ## Textual Data Analysis ### Overview The image contains a list of hexadecimal values, which appear to be part of a binary or low-level data structure. The values are organized in a structured format, with each line representing a different data element. ### Components/Axes - **Labels**: None - **Scales**: None - **Legends**: None - **Axis Markers**: None ### Detailed Analysis or ### Content Details The list includes a variety of hexadecimal values, each with a specific length and a label. The values are as follows: - `inflate: length 6` - `inflate: distance 16484` - `inflate: literal 'F'` - `inflate: literal 'O'` - `inflate: literal 'B'` - `inflate: literal 'A'` - `inflate: literal 'R'` - `inflate: literal 0x17` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal 0xb3` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal 'x'` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal 0x05` - `inflate: dynamic codes block (last)` - `inflate: table sizes ok` - `inflate: code lengths ok` - `inflate: codes ok` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal 0xa9` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal 0x81` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal '('` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal 0xff` - `inflate: length 13` - `inflate: distance 14` - `inflate: literal 0xa5` - `inflate: length 13` - `inflate: distance 14` ### Key Observations The data appears to be a part of an inflation algorithm, which is a process used in data compression to reduce the size of data. The values represent different parameters and states of the inflation process, such as length, distance, and literal values. The presence of the word "inflate" suggests that this data is related to the compression process. ### Interpretation The data suggests that this is a detailed log or record of the inflation process in a data compression algorithm. The various parameters and states indicate that the algorithm is processing different parts of the data, possibly at different stages of compression. The presence of the word "inflate" implies that the data is related to the compression process, which is a common technique used in data storage and transmission to reduce the size of data. The data could be used for debugging, performance analysis, or to understand the behavior of the inflation algorithm. </details> ## APPENDIX D BYTEWISE LEAKAGE Figure 15 illustrates the bytewise leakage of the secret (SECRET) for a PHP application using PHP-Memcached. Figure 16 shows the bytewise of the secret string for a Flask application that stores secret data together with attackercontrolled data into PostgreSQL. The prefix value can be shifted bytewise, which allows reusing the same memory layouts found by Comprezzor. Figure 17 shows the last two bytes leaked from a secret (SECRET) in a ZRAM page. This is a continuation of Figure 12 which showed the leakage of the first four bytes. Fig. 15: Bytewise leakage of the secret (S,E,C,R,E,T) from PHP-Memcached. In each plot, the lowest timing (shown in red) indicates the correct guess. <details> <summary>Image 19 Details</summary>  ### Visual Description ## Heatmap: Byte Analysis ### Overview The heatmap displays the timing measurements for different byte values, categorized by the guess made by an algorithm. Each row represents a byte, and the columns represent different guesses. The color intensity indicates the timing value, with darker shades representing higher values. ### Components/Axes - **X-axis**: Byte values (0 to 5) - **Y-axis**: Guesses (cookie=0 to cookie=SECRETZ) - **Color Scale**: Darker shades indicate higher timing values ### Detailed Analysis or ### Content Details - **Byte 0**: The guess cookie=0 has the highest timing value, followed by cookie=1, cookie=2, and so on. - **Byte 1**: The guess cookie=0 has the highest timing value, followed by cookie=1, cookie=2, and so on. - **Byte 2**: The guess cookie=0 has the highest timing value, followed by cookie=1, cookie=2, and so on. - **Byte 3**: The guess cookie=0 has the highest timing value, followed by cookie=1, cookie=2, and so on. - **Byte 4**: The guess cookie=0 has the highest timing value, followed by cookie=1, cookie=2, and so on. - **Byte 5**: The guess cookie=0 has the highest timing value, followed by cookie=1, cookie=2, and so on. ### Key Observations - **Byte 0**: The guess cookie=0 consistently has the highest timing value across all guesses. - **Byte 1**: The guess cookie=0 consistently has the highest timing value across all guesses. - **Byte 2**: The guess cookie=0 consistently has the highest timing value across all guesses. - **Byte 3**: The guess cookie=0 consistently has the highest timing value across all guesses. - **Byte 4**: The guess cookie=0 consistently has the highest timing value across all guesses. - **Byte 5**: The guess cookie=0 consistently has the highest timing value across all guesses. ### Interpretation The heatmap suggests that the algorithm guesses cookie=0 for all byte values, resulting in the highest timing values. This indicates that the algorithm is likely not correctly identifying the byte values, as the guess cookie=0 consistently results in the highest timing. The other guesses (cookie=1 to cookie=SECRETZ) have lower timing values, suggesting that they are more accurate guesses. However, the algorithm's performance is significantly poor, as it consistently guesses the wrong byte value. </details> Fig. 16: Bytewise leakage of the secret (S,E,C,R,E,T) from PostgreSQL. The known prefix (cookie=) is shifted left by 1 character in each step, allowing the same memory layout to be reused. In each plot, the highest timing (shown in red) indicates the correct guess. <details> <summary>Image 20 Details</summary>  ### Visual Description ## Heatmap: Timing Analysis of Cookie Guesses ### Overview The heatmap displays the timing analysis of different cookie guesses across five bytes. Each row represents a byte, and each column represents a guess. The color intensity indicates the timing value, with darker shades representing higher timing values. ### Components/Axes - **X-axis**: Byte 0 to Byte 5 - **Y-axis**: Guess 0 to Guess 5 - **Color Scale**: Darker shades indicate higher timing values - **Legend**: Colors correspond to different guesses ### Detailed Analysis or ### Content Details - **Byte 0**: The guesses range from 1.20 to 1.25 ms, with the highest timing value being 1.25 ms. - **Byte 1**: The guesses range from 1.22 to 1.28 ms, with the highest timing value being 1.28 ms. - **Byte 2**: The guesses range from 1.23 to 1.27 ms, with the highest timing value being 1.27 ms. - **Byte 3**: The guesses range from 1.24 to 1.28 ms, with the highest timing value being 1.28 ms. - **Byte 4**: The guesses range from 1.25 to 1.29 ms, with the highest timing value being 1.29 ms. - **Byte 5**: The guesses range from 1.26 to 1.30 ms, with the highest timing value being 1.30 ms. ### Key Observations - **Byte 0**: The guess "cookie=Z" has the highest timing value. - **Byte 1**: The guess "okie=SZ" has the highest timing value. - **Byte 2**: The guess "kie=SECZ" has the highest timing value. - **Byte 3**: The guess "ie=SECZ" has the highest timing value. - **Byte 4**: The guess "ie=SECZ" has the highest timing value. - **Byte 5**: The guess "ie=SECZ" has the highest timing value. ### Interpretation The heatmap suggests that the timing values vary significantly across different guesses and bytes. The highest timing values are consistently observed for the guess "ie=SECZ" across all bytes. This could indicate that the guess "ie=SECZ" is the most time-consuming or resource-intensive in the context of the analysis. The other guesses have lower timing values, suggesting they are faster or more efficient. The variations in timing values could be due to differences in the complexity or efficiency of the guesses. </details> Timing [ns] . cookie=SECR0 cookie=SECR5 Timing [ns] , , cookie=SECRE9 cookie=SECRE0 cookie=SECRE5 cookie=SECREA cookie=SECR9 cookie=SECRA Byte 4 cookie=SECRS cookie=SECRE cookie=SECRM Byte 5 cookie=SECREH cookie=SECREM Guess Fig. 17: Bytewise leakage of the last two bytes of the secret (E,T) from ZRAM. Times for guesses (0-9, A-Z) for each of the bytes are shown. The highest value in each plot (shown in red) indicates the correct secret value for the byte. . cookie=SECRZ cookie=SECREZ cookie=SECRET