S-Leak: Practical Leakage-Abuse Attack Against Conjunctive SSE in Cloud Storage

Conjunctive Searchable Symmetric Encryption (CSSE) enables secure multi-keyword searches over encrypted data stored on remote cloud servers. However, leakage-abuse attacks have been shown to pose a severe security threat to Searchable Symmetric Encryption (SSE) systems. Most existing attacks focus on single-keyword SSE, while the few proposed against CSSE suffer from one of two drawbacks: inaccurate leakage analysis of CSSE system, or combinatorial explosion of candidate keyword combinations that incurs enormous time and space overhead. In this paper, we reveal a fundamental vulnerability in practical CSSE schemes: s-term leakage, where the keyword with the minimal document frequency in a query leaks distinct patterns. We propose S-Leak, the first practical passive attack framework that progressively recovers conjunctive queries in CSSE-deployed systems by exploiting s-term leakage and global leakage. Our three-stage design identifies the s-term, prunes low-probability conjunctions, and reconstructs full queries. We also introduce new metrics to assess recovery in conjunctive scenarios. Experiments on real-world datasets show S-Leak is effective across CSSE configurations. For 161,700 conjunctive queries, it recovers at least one keyword with 95.15% accuracy, two with 82.57%, and all three with 58%, while remaining effective against defenses such as SEAL padding and CLRZ obfuscation. Our work exposes underestimated s-term leakage risks in practical CSSE deployments and provides actionable defense guidelines for system designers.