Paper 2026/2465

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

Abstract

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.