Snapshots of TEE-Based Encrypted Databases Leak Plaintext Histograms via Dendrochronology

Researchers identified a vulnerability in several trusted-execution-environment (TEE)-based encrypted databases in which snapshots leak plaintext histograms, recovering value frequencies that prior work assumed were hidden. The attack exploits the unique tie-breakers that storage engines append to indexed keys to impose a strict total order, and the researchers demonstrated it against Microsoft SQL Server's Always Encrypted, StealthDB and HeDB even when the TEE itself is secure. The findings show the order-only leakage model understates exposure for snapshot adversaries and point to broader lessons for TEE applications built on legacy code.

Arborists use dendrochronology, or the study of tree "growth rings" as in, the plant , to infer past environmental events. We identify an analogous, exploitable phenomenon in the indexes used by several encrypted databases EDBs based on trusted execution environments TEEs . Such EDBs have been shown to leak the order of indexed values, but not the histogram or frequency of each value , with respect to a weaker class of snapshot adversaries. This order-only leakage substantially reduces the impact of possible inference attacks. We show, in fact, frequency is recoverable in the snapshot model from many TEE-based EDBs, even if the TEE itself is "secure". Our insight is simple: practical storage engines impose a strict total order on indexed keys by augmenting each key with a unique tie-breaker. If the adversary learns information about the tie-breakers, they can recover the frequencies of plaintext keys. We show this enables stronger inference attacks on several TEE-based EDBs including Microsoft SQL Server’s Always Encrypted, StealthDB, and HeDB to demonstrate this vulnerability’s ubiquity and point to broader lessons for TEE applications designed around legacy code.