Attacking Suggest Boxes in Web Applications Over HTTPS Using Side-Channel Stochastic Algorithms

Alexander Schaub, Emmanuel Schneider, Alexandros Hollender, Vinicius Calasans, Laurent Jolie, Robin Touillon, Annelie Heuser, Sylvain Guilley, Olivier Rioul

TL;DR

This paper demonstrates that even with HTTPS encryption, attackers can infer user search queries by analyzing the timing and size of network packets exchanged with search engine suggest boxes. They introduce novel stochastic algorithms that leverage these side-channel leaks to reconstruct queries with significant accuracy, highlighting that current randomization techniques are insufficient for robust privacy.

What Problem Does This Paper Address?

In the age of ubiquitous HTTPS, users often assume their online activities are private. However, this paper tackles the persistent threat of side-channel attacks, specifically focusing on how sensitive information can be exfiltrated from seemingly secure web applications. The core problem is that while HTTPS encrypts the content of network traffic, metadata like packet sizes and timing can still leak information. The authors specifically target the "suggest box" feature of search engines like Google and Bing, where typing a few characters triggers a request for search suggestions. They aim to demonstrate that by analyzing the patterns of these requests, an attacker can deduce the user's actual search query, even when the search engine employs measures like payload randomization and compression to obscure this information. This is crucial because search history is highly personal and can reveal sensitive details about an individual's interests, health, or even financial situation.

Methods

The paper's primary contribution lies in its novel stochastic algorithms designed to overcome the challenges posed by randomized packet lengths and compression.

  • Side-Channel Leakage Analysis: The core idea is to analyze the network traffic between a user and a search engine's suggest box. Specifically, they focus on three parameters: packet lengths, packet direction, and packet timing.
  • Probability Distribution Estimation: Due to randomization and compression, a direct mapping between a search query and a packet signature is no longer reliable. Instead, the authors develop methods to estimate the probability distribution of packet lengths for a given search prefix. This involves fetching the suggestion response, simulating the randomization and compression process multiple times, and observing the resulting packet size variations.
  • Stochastic Algorithms (Stack Algorithm): To infer the most probable search query from these probability distributions, they introduce a "stack algorithm." This algorithm builds upon a prefix tree (Trie) representation of a dictionary (initially a French dictionary). At each step of a user typing, the algorithm considers possible next characters, calculates the likelihood of different prefixes using the estimated packet length probabilities, and maintains a stack of the most probable partial solutions.
  • Threshold Variant: A variation of the stack algorithm uses a threshold to prune less likely prefixes, aiming for a more efficient computation.
  • Likelihood Functions: They explore different functions to combine prefix probabilities, including the product of probabilities (which performed best), sum of probabilities, and weighted sum.

Datasets

The paper does not explicitly mention or introduce new benchmark datasets. Instead, their methodology relies on:

  • Simulated Search Queries: They simulate user typing by generating prefixes of French words from a dictionary.
  • Real-World Search Engine Responses: They capture actual network traffic from Google and Bing's suggest box features.
  • French Dictionary: A simple French dictionary is used to restrict the search space of possible queries, assuming users type meaningful words.

Key Insights and Ideas

  • HTTPS is Not a Panacea for Metadata Leakage: The most striking insight is that even with strong encryption like HTTPS, side-channel attacks can still be highly effective. The metadata of network traffic (packet size, timing) can reveal sensitive information.
  • Randomization and Compression are Not Enough: Search engines' attempts to obscure traffic patterns through randomization and compression are insufficient to thwart these attacks. The authors show that stochastic methods can still infer queries with reasonable accuracy.
  • Stochastic Algorithms are Key: The paper highlights the necessity of probabilistic and stochastic approaches to handle the inherent uncertainty and variability introduced by randomization and compression.
  • Dictionary-Based Pruning is Effective: Restricting the search space to a valid dictionary significantly reduces computational complexity and improves the accuracy of the attack.
  • Suggest Boxes are Vulnerable: The suggest box feature, designed for user convenience, inadvertently creates a rich source of side-channel information due to its frequent network interactions.

Key Results

  • Significant Query Recovery: The proposed stack algorithm, using a product of probabilities as the likelihood function, achieved an 81% success rate in finding the target word within the final list of possible words.
  • Top-3 and Top-1 Accuracy: The algorithm found the target word in the top 3 suggestions 52% of the time and ranked it as the best match 34% of the time for 5-letter French words.
  • Performance Across Variants: Different likelihood functions and algorithm variants (stack vs. threshold) showed similar performance, with the product of probabilities generally yielding the best results.
  • Impact of Dictionary Size: The paper notes that a 5-letter French dictionary contains significantly fewer valid words than all possible 5-letter sequences, demonstrating the benefit of dictionary pruning.

Limitations and Future Work

  • Dictionary Dependence: The attack's effectiveness is tied to the quality and completeness of the dictionary used. The authors acknowledge that using a more comprehensive English dictionary might yield similar results.
  • Backspace Handling: The current algorithm does not handle backspace key presses, which would require significant modifications to the data structures and algorithms.
  • Space Key Handling: Similarly, handling the space key would necessitate altering the dictionary representation (e.g., using a cyclic structure).
  • Wifi vs. Ethernet: While the attack works on both, Wifi introduces additional complexities due to packet fragmentation and the need to determine a constant offset for accurate size estimation.
  • Localization and Customization: The attack assumes the attacker and victim receive the same suggestions. Differences due to localization, customization, or "Private Mode" usage could impact accuracy.
  • Future Work: The authors suggest exploring handling of the space and backspace keys, testing with different dictionaries, and investigating the use of response times as an additional side-channel. They also propose countermeasures like padding packets to a fixed size and disabling compression.

Summary updated

BibTeX
@article{schaub2014attacking,
  author = {Alexander Schaub and Emmanuel Schneider and Alexandros Hollender and Vinicius Calasans and Laurent Jolie and Robin Touillon and Annelie Heuser and Sylvain Guilley and Olivier Rioul},
  title = {{Attacking Suggest Boxes in Web Applications Over HTTPS Using Side-Channel Stochastic Algorithms}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2014},
}
Figure