Plaintext Recovery Against Post-Filtering Access Control

This paper, Plaintext Recovery Against Post-Filtering Access Control by Zachary Espiritu and David Cash, demonstrates that fine-grained access control (FGAC) mechanisms in databases are vulnerable to side-channel attacks that can be amplified into full plaintext recovery. The authors show that FGAC side-channels must be evaluated in the presence of rich predicates, which can turn membership tests into scalable reconstruction of high-entropy records.

The paper addresses two main settings:

1. PostgreSQL Row-Level Security (RLS) Timing Attacks

The authors exploit a timing side-channel in PostgreSQL's RLS implementation. The paper explains: "PostgreSQL added a notion of LEAKPROOF operators that do not have any explicitly observable side-effects, and allows for post-filtering on queries composed of only LEAKPROOF operators. Such operators include equality (=) and comparison (, etc.). If a predicate is entirely composed of LEAKPROOF operators, the optimizer is allowed to reorder the evaluation of the predicate with respect to the policy, so that the predicate is evaluated first."

The attack works because the time to evaluate Q(TP) will be time(Q, TP) ≈ time(Q, T) + time(P, Q(T)) where the policy evaluation time depends on the size of the intermediate result before filtering. The authors develop a two-phase attack:

• Phase I (Attribute Enumeration): Using binary search with range queries (BETWEEN), the attacker recovers all values present in each attribute. The paper states: Instead of probing each candidate value linearly, we issue range queries that test whether any matching records exist on one side of a split point. This achieves O(S log(D)) oracle queries where D is domain size and S is the number of values present.

• Phase II (Tuple Assembly): Using conjunctions, the attacker associates values across columns to reconstruct full rows. The paper describes: We do this by incrementally constructing candidate tuples and using the timing oracle with conjunctions to perform cross-attribute existence checks.

The evaluation shows the attack achieves high accuracy. Under CPU load up to 95%, with k=4 queries per probe type, accuracy exceeds 99.9% for join policies. The binary search approach provides 27.8× speedup for SSN recovery compared to linear probing, and the attack can recover 100% of rows with high precision when starting from the most selective attributes.

2. Elasticsearch/OpenSearch Document-Level Security (DLS) Scoring Attacks

The authors exploit scoring side-channels in full-text search systems. They identify a new prefix-expansion (PE) side-channel in match phrase prefix (mpp) queries. The paper explains: Given a query q = (phr,tr) and a document d, let pf(q, d) be the phrase frequency of q... also, let exp(tr, D) be the set of expansions of tr, which are indexed terms starting with tr.

The attack constructs two oracles:

• ExactOracle: Tests if a term exists in the index by comparing scores between a test document and a control document with a fresh term.

• PrefixOracle: Tests if any term begins with a given prefix, exploiting how prefix expansion affects BM25 scores.

These oracles are combined to enumerate all terms via a breadth-first search over the trie of terms starting from the empty string. The paper states: The enumeration performs O(V) oracle calls (one membership test per visited node, plus a prefix test to decide whether to descend), so the total cost is linear in the size of the explored portion of the prefix trie.

For search as you type (SAYT) indexes, the authors extend the attack to recover n-grams (up to 4-grams), which enables approximate document reconstruction. The paper demonstrates: We achieve 100% accuracy, which confirms our scoring oracles consistently distinguish indexed and non-indexed n-grams. Example reconstructions show that While text is not complete, the overall meaning is preserved.

Mitigations Proposed

For RLS, the authors propose using composite indexes with tenant-leading columns: Our approach is to bind the predicate into the same index access as the attacker's predicate so the scan is confined to the querying tenant's rows. This requires changing the index to (site id, atr) format and rewriting the policy as a subquery. The evaluation shows this closes the side-channel for our scenario; the oracle can only make random guesses.

For DLS, the authors suggest: A simple mitigation is to modify the computation of dfmpp to only expand terms that are visible to a user or one could simply omit the computation of idfmpp from mpp scores.

Key Conclusions

The paper concludes: post-filtering FGAC systems with rich queries can fail to deliver the isolation they promise and that this architecture is inherently brittle. The authors expect that rich queries will interact badly with post-filtered FGAC in other contexts. They note that physically separating indexes into per-tenant distinct structures closes the channel entirely but this comes with extra overhead of managing multiple database or index instances, which is the whole motivation for FGAC in the first place.

The work was disclosed to PostgreSQL, Elastic, and OpenSearch on January 25, 2026, with Elastic considering the vulnerabilities low priority at this time. The paper was originally published at USENIX Security Symposium 2026.

Based on this paper, I can implement the following specific improvements to AI systems:

Improvement: Modify the AI system's query generation and optimization layer to detect when it is about to issue queries against post-filtering FGAC systems. The AI should automatically rewrite queries to avoid timing-based information leakage by:

• Converting range predicates (BETWEEN) into single-point lookups when operating under RLS

• Adding artificial noise delays proportional to the expected intermediate result size

• Batching queries to mask per-query timing variations

Capability: The improved AI can safely query databases with RLS without inadvertently leaking tenant data through timing differences, even when the AI's own queries are used as part of a larger data analysis pipeline.

---

Overall improved AI system capability: The enhanced AI can interact with post-filtering FGAC databases and search indexes securely, perform legitimate data operations without creating exploitable timing or scoring side-channels, detect ongoing attacks, and recommend or implement structural mitigations—all while maintaining high accuracy and efficiency in its core tasks.