Introduction
Dendrochronology, or the study of tree “growth rings” (as in, the plant), is the scientific method of assigning exact calendar years to annual growth rings in wood. Arborists use dendrochronology to infer events about a tree’s surrounding environment, allowing them to answer questions like: What was the temperature in this region 100 years ago? What year did a volcanic eruption in the area occur? This technique allows us to infer surprisingly detailed information about the past—all from a single point-in-time snapshot of the tree.
In my new, solo-authored research paper appearing at ACM CCS 2026 and at BlackHat Europe 2026, I show that there’s an analogous, exploitable phenomenon in the B+-tree indexes used in several encrypted databases based on trusted execution environments (TEEs). Specifically, an attacker can recover a similar “growth ring” structure from a single, point-in-time snapshot of the database’s encrypted index that leaks the plaintext histogram of the database. This, in turn, allows the adversary to infer the plaintext of the underlying encrypted data—once again, under an extremely weak adversary model.
Despite how surprisingly simple this vulnerability is, it affects a multitude of encrypted databases, including:
- Microsoft SQL Server’s Always Encrypted with Secure Enclaves, which uses Intel SGX or Microsoft VBS enclaves
- Alibaba Cloud’s ApsaraDB Always-Confidential with Intel SGX
- Many other academic constructions (such as StealthDB and HeDB, and many others which have been deployed as early as 2011)
Why is this interesting?
End-to-end encrypted databases aim to allow a client to end-to-end encrypt data between the client and an untrusted database server in such a way that allows the data to still issue queries over the data. Designing such a database is not straightforward—confidentiality (e.g., encryption) eliminates structure which we would normally use to search over the data efficiently, but, in some cases, we might be okay with leaking a little bit of information about the underlying plaintext in order to increase efficiency. Because of this, there is not really one “best” encrypted database scheme—it depends on your efficiency requirements and how much information you are willing to leak to a potential adversary.
One way that industry and academic encrypted database designers in industry and academia have tried to simplify encrypted database design is by using trusted execution environments (TEEs) like Intel SGX, AMD SEV, and others. Instead of designing a new database engine from scratch, designers can leverage the claimed security guarantees of a TEE (namely, that the memory is confidential to adversaries that compromise the server) to supposedly “safely” reuse mature components of existing plaintext database engines.
Of course, this security guarantee relies on the assumption that we can trust the hardware of the TEE—and there is a rich line of work that shows confidentiality attacks on the TEE primitive itself. These show that powerful, persistent adversaries who can compromise various kernel components or execute arbitrary code on the victim can break the confidentiality guarantees of TEEs.
But persistent adversaries are not the only adversaries relevant for real-world databases. Commercial vendors increasingly emphasize weaker threat models in which an attacker exfiltrates point-in-time snapshots of database state. Unlike strong persistent models which capture sustained server compromise, snapshot models capture incidents arising from database user or server administrator compromise.
It was previously believed that, in the snapshot model, it was impossible to recover an important kind of leakage—histogram leakage—about the plaintext data stored in Always Encrypted with Secure Enclaves as it used randomized encryption. In this new work, I show that a common algorithmic invariant leads to an extremely simple attack that reveals the plaintext histogram to a snapshot adversary—even if the adversary just gets one snapshot of the encrypted database.
The TEE-Hybrid Architecture
Microsoft’s database falls into a category known as a TEE-hybrid database. The goal of this architecture is to allow an existing database engine to be used—mostly unmodified—with the exception of a small component which runs inside of the TEE.
Microsoft’s database engine is based on B+-trees, which are search trees which map indexed attributes to their corresponding record IDs. Maintaining a B+-tree requires the server to perform comparison operations on the indexed attributes so it knows how to search for and where to store each attribute. However, the idea of encrypting attributes is in direct tension with this idea—how can the server maintain the required index structure if it only receives completely random ciphertexts?
The TEE-based approach solves this problem in the following way:
- When the client wants to upload a record that contains an encrypted attribute, the client-side driver encrypts the indexed attribute using AES with a known attribute key. Then, it sends the ciphertext to the server.
- Instead of using the plaintext comparison operators (which would be meaningless over the ciphertext), the TEE implements the comparison operator for index maintenence. When the server needs to compare two ciphertexts, it sends both ciphertexts to the TEE. The TEE internally knows the attribute key, so it can decrypt both ciphertexts, compare their plaintexts, and output a comparison result to the server.
- This architecture allows the existing database engine to maintain the B+-tree essentially as normal—just by delegating comparison operations to the TEE—without ever revealing the plaintext values to the untrusted region of the server.
In the figure, we show an B+-tree which stores encrypted attributes. The letters A, B, C, and D denote plaintext values, but those are not actually visible to the server since they are encrypted. Here, we can see that the server uses the TEE comparator to order ciphertexts by their plaintext values.
We can see that the storage of the index itself leaks plaintext order of the ciphertexts. This is the observation that was exploited by prior snapshot model cryptanalysis by Seah et al.. Notably, because the ciphertexts use a randomized encryption scheme, it does not leak the frequency, or the histogram of the records. In other words, from a single snapshot, an adversary cannot see which encrypted values are equal to each other.
Before we discuss how to extract frequency leakage, it’s worth asking—does frequency leakage even matter?
Yes, Frequency Leakage Matters
To understand why frequency leakage is dangerous, it is useful to compare it to order-only leakage. Consider an encrypted column containing 10 encrypted patient ages and the adversary sees their ciphertexts stored in sorted plaintext order. That reveals which encrypted records come before others, but it doesn’t reveal whether neighboring entries have the same age, where one age ends and the next begins, or even how many distinct ages appear. The 10 sorted entries could represent ten different ages, one age repeated ten times, or many possibilities in between.
Frequency leakage significantly changes this picture. In the figure, the ten entries reveal frequency leakage which divides them into groups of 2, 5, and 3. The attacker now knows that the first two records share one hidden value, the next five share another, and the last three share a third. This ordered list of group sizes is the plaintext histogram.
As shown, this histogram allows for significantly more accurate reconstruction. Those counts also help an attacker guess the values themselves. With order alone, an attack using a public or previously known distribution must infer the group boundaries from that auxiliary histogram. If its histogram is stale or comes from a different population, those boundaries can be wrong. However, the adversary has no way of correcting those boundaries and has to take them as the ground truth. With histogram leakage, the attacker learns constraints on groups of ciphertexts from the target database. They can use these constraints to more accurately “align” its guesses to the real plaintext values.
Because of this, claims of order-only leakage for Always Encrypted (and other TEE-based EDBs) are significant: they exclude the frequency information which gives classical inference attacks (like the ones described above) their power. Microsoft even emphasizes this point in later security analyses, with statements like:
PPE attacks that rely on the static DB [e.g., snapshots] are not applicable to enclave-enabled EDBs which store data strongly-encrypted [e.g., using randomized encryption] (source)
I’ll show that this is false by showing a PPE attack against Always Encrypted’s randomized encryption scheme which relies solely on a single snapshot of the database.
The Vulnerability
Our attack relies on a subtle detail that we actually saw earlier in the figure. While databases can contain multiple records with the same indexed value, essentially all practical B+-tree storage engines enforce uniqueness of physically stored keys. Thus, to satisfy the uniqueness invariant in non-unique indexes, databases extend the user-visible key $k$ with a unique tie-breaker component $u$. Then, the B+-tree entries are lexicographically sorted by $(k,u)$. Databases can instantiate this tie-breaker in different ways, but the most common way to instantiate it is the record ID associated with each key (as is done in Microsoft SQL Server).
However, in Always Encrypted’s B+-tree index (and other TEE-hybrid databases), the tie-breakers are not encrypted. They are visible in plaintext in a single snapshot of the index.
Do you see the issue?
The sequence of tie-breakers immediately gives us the following simple frequency recovery attack against the B+-tree from the B+-tree diagram. We scan the leaves from left to right to get a sequence of tie-breakers, then observe whenever a descent occurs in the tie-breaker sequence:
The drops from 15 to 2, from 14 to 1, and from 11 to 5 are the growth rings. IDs cannot decrease within a group of equal values, because the index sorts those records by ID. Each drop therefore marks a boundary between different plaintext values. Counting entries between the drops gives groups of 3, 6, 2, and 4 records, which exactly matches the plaintext histogram.
Once again, I stress that this doesn’t require persistent compromise of the server—only a single snapshot. In fact, the adversary can take this snapshot remotely using a database user account—for example, in Microsoft SQL Server, an attacker who compromises an untrusted database administrator account that doesn’t have access to the encryption key can use SQL Server’s Database Console Command API to memory dump the encrypted index B+-tree. It can then perform the above attack directly.
Limitations
One limitation of the attack is that a boundary does not always produce a drop. If IDs keep increasing across two different values, the attack may merge their groups and recover only an approximation of the histogram. In the example below, B and C are inserted in sorted order: all B records have lower IDs than the C records. Their IDs rise from 10 to 11 at the hidden B/C boundary, so the attack sees no descent there.
I discuss this technicality in more detail in the paper, but it does not affect the attack’s performance in experiments where the data is inserted randomly.
Impact
I tested our attack against all TEE-hybrid databases for which I could find publicly available artifacts, which were:
- Microsoft SQL Server’s Always Encrypted with Secure Enclaves
- StealthDB, an academic TEE-hybrid database from 2019
- HeDB, an academic TEE-hybrid database from 2023
The evaluation uses the attack to recover the plaintext histogram and then uses the state-of-the-art “multinomial attack” from Bindschaedler et al. to perform plaintext inference as described in Section 3. As shown in the figure, the frequency leakage recovered by the dendrochronology attack massively increases the adversary’s ability to accuracy guess the plaintext values associated with each ciphertext.
Strawman: What If We Encrypt the Record IDs?
Hiding the record IDs fixes the direct single-snapshot attack, but it does not necessarily end the story. If an attacker gets snapshots at different times and can recognize the same ciphertext across them, they can tell which snapshot first contained each record. These “birth times” act as stand-ins for the hidden IDs. They preserve insertion order across snapshots, but records inserted between two captures get the same birth time, even if their actual IDs differ.
At the starting \(\mathsf{T}_3\), \(\mathsf{T}_6\), and \(\mathsf{T}_{10}\) positions, record IDs 8 and 7 first appear in the same snapshot, so their real drop becomes a flat 3 to 3. The boundary between the second and third plaintext values is lost: their true groups of 3 and 2 records look like one group of 5. The other two descents survive, so the attacker still learns an approximate histogram.
Takeaways
I really enjoyed working on this research project, primarily because—in the words of one of the anonymous reviewers—it has this kind of nice “obvious after the fact” flavor to it that makes it really easy to appreciate.
As with any such “obvious” idea, one should then ask: why has this seemingly simple vulnerability gone unnoticed for many years? (The earliest such database, TrustedDB, appeared as early as 2011.)
While I can only speculate, I think prior analyses of TEE-based EDBs modeled the TEE-based index as a sorted sequence of ciphertexts and abstracted additional practical index metadata—such as tie-breakers—out of the model. This highlights an occupational hazard of designing TEE-based applications: the promise of reusing a plaintext storage engine invites designers to treat the existing engine as a black box, when, in reality, its algorithmic invariants become critical parts of the security boundary (and surprising vectors of leakage). Seemingly benign features that make legacy storage engines practical end up becoming surprising sources of leakage.
With that, I leave you with some broader lessons and takeaways:
- Index metadata reveals plaintext structure. A B+-tree needs a way to order duplicate keys, and many storage engines use increasing record IDs as tie-breakers. When those IDs remain visible beside encrypted keys, drops in their sorted sequence expose boundaries between plaintext values, even if the TEE behaves correctly.
- A snapshot attacker can learn more than order. For affected TEE-hybrid indexes, one point-in-time snapshot can reveal those boundaries without observing live queries or compromising the enclave.
- Secure co-design with TEEs, whether for databases or other applications, cannot treat existing algorithms as a neutral implementation detail. Such components must be carefully analyzed as part of the security boundary—and, as shown in Section 6, simple modifications to secure those algorithms could have non-obvious pitfalls too. I expect that as additional TEE-based applications become more mainstream, vulnerabilities like these will arise from natural consequences of the underlying (plaintext) algorithms.
Want to learn more? Check out the full paper, “Snapshots of TEE-Based Encrypted Databases Leak Plaintext Histograms via Dendrochronology”, for more formal analysis, additional case studies, experimental details, and to appreciate TiKZ diagrams I spent too much time working on.
Acknowledgments
Special thanks to Casey Nelson for reviewing earlier drafts of this post, as well as: the anonymous CCS reviewers for their helpful feedback on the paper; Seny Kamara, Tarik Moataz, and Andrew Park for early, helpful discussions; and Microsoft and Alibaba for their responses in the coordinated disclosure process.