Breaking Encrypted Databases: Generic Attacks on Range Queries

## Overview

Marie-Sarah Laventhol (NCC Group, cryptography researcher, PhD from Royal Holloway on encrypted search schemes) presented novel side-channel attacks on encrypted database systems that support range queries. Problem context: data breaches expose millions of records annually; organizations storing sensitive data (medical, financial, personal) face liability and privacy violations if breaches occur. Motivation: can cryptography protect leaked data while preserving query functionality? Ideal scenario: encrypted medical records remain useless to attacker even if stolen, while allowing healthcare administrators to query (e.g., "find all patients aged 40-50 to study treatment efficacy"). Encryption challenge: traditional database encryption encrypts data at rest but keeps plaintext on server for indexing/querying, enabling compromised administrators or system access to read data; client-side encryption prevents server access to plaintext but makes querying encrypted data algorithmically difficult. Range-query encrypted databases promise: maintain data encryption without decryption on server, yet enable efficient range queries (SQL: "SELECT * WHERE value BETWEEN x AND y"). Research contribution: new side-channel attacks exploiting information leakage from these schemes. Attacks break encryption despite all data being encrypted—attacker recovers plaintext values by analyzing query leakage patterns. Two leakage sources: (1) access pattern leakage—which specific rows matched query (row IDs); (2) volume leakage—how many rows total matched query.

## Encrypted Database Architecture and Threat Models

**Evolution of Threat Models and Solutions**: Legacy approach—TLS encryption of network traffic protects from eavesdropper but not from disk theft or compromised server administrator. Cloud outsourcing threat model shift—customers must assume server hardware/storage can be stolen; solution: transparent data encryption (TDE, native encryption)—encrypts data at rest, server holds encryption keys in key store, decryption happens in server memory. Enterprise solution: field-level encryption managed by server with separate key store; server never stores plaintext on disk, but administrators with database access can decrypt. Stronger threat model: don't trust database server or administrators; client-side field-level encryption (Microsoft Always Encrypted, MongoDB client-side encryption, CipherCloud proxies)—encryption keys controlled entirely by client, keys never transmitted to server, server stores only encrypted values and index structures, queries executed against encrypted data.

**Client-Side Encrypted Database Architecture**: Client encrypts data before transmission to server; server stores encrypted records indexed by encrypted search tokens; client sends encrypted range query to server; server processes query using encrypted tokens, returns matching encrypted row IDs and encrypted values; client decrypts results in application layer. Server never holds encryption keys, never decrypts data, never sees plaintext—even compromised system administrator sees only ciphertext. Performance advantage over naive encryption: server can maintain efficient indexes allowing range queries on encrypted numeric data without decryption, avoiding sequential scan of entire table for every query. This efficiency comes at cryptographic cost: encryption scheme must leak information to support server-side range-query processing without revealing plaintexts.

## Side-Channel Attack Methodology and Leakage Exploitation

**Leakage Categories**: Access pattern leakage—attacker observes which specific row IDs the server returns for each query; volume leakage—attacker observes how many rows matched each query. Example: medical database with patient IDs (1-100) and ages (1-100); attacker observes queries "return rows {3, 15, 27, 44}" and "return rows {2, 31, 52}" without knowing values; attacker also observes query-1 returned 4 rows, query-2 returned 3 rows. Attack combines: multiple observed queries over same dataset, knowledge of query ranges (attacker knows they requested ranges, may know approximate boundaries), statistical inference—determining plaintext values from access patterns and volume information.

**Range-Query Attack Scenario**: Suppose attacker observes queries on age field with ranges [1,10] (4 results), [1,20] (8 results), [1,30] (11 results), [20,30] (3 results), [50,60] (2 results). From volume: ages roughly distributed as ~4 in [1,10], ~4 more in [11,20], ~3 more in [21,30], ~2 in [50,60]. From access patterns: if attacker knows which row IDs are in age-1-10 range, can track individual records—row 3 is always in ranges ≤ age X, never in ranges ≥ age Y, allowing inference of row-3's approximate age range. With sufficient queries over different ranges, attacker narrows down each record's possible value range until plaintext is recovered (or reduced to small candidate set enabling brute force). Attack assumes: attacker can issue queries (compromised client or observation of legitimate queries); attacker knows approximate query ranges or can infer them from patterns; no noise/obfuscation added to leakage.

**Distinction from Full Encryption**: Even with all data encrypted, side-channel information (which rows, how many rows) is sufficient to break encryption scheme—not through cryptographic weakness of cipher itself but through architectural leakage. Secure encrypted-database designs must hide both access patterns AND volume, requiring architectural changes (padding query results to uniform size, performing obfuscated searches)—trades off performance for security.