Study Reveals Vulnerabilities in Chase-Shen Encryption Scheme
/ 4 min read
Quick take - A recent study has introduced a query reconstruction attack on the Chase-Shen substring-searchable symmetric encryption scheme, marking the first leakage cryptanalysis of this technology, which is designed for secure querying of encrypted databases but exhibits vulnerabilities that can compromise user privacy.
Fast Facts
- A recent study reveals a query reconstruction attack on the Chase-Shen substring-searchable symmetric encryption (substring-SSE) scheme, marking the first leakage cryptanalysis of this type.
- The attack exploits reduced leakage profiles under an honest-but-curious server model, utilizing key leakage elements like path length and response volume.
- Experimental results show a query recovery rate of 50-60%, indicating significant vulnerabilities in the Chase-Shen scheme, which is designed for secure querying of encrypted databases.
- Identified leakage patterns include query prefix and index intersection, which can compromise user privacy by revealing shared query information.
- The study highlights the need for improved countermeasures to mitigate data leakage while maintaining the functionality of substring-SSE, especially in sensitive applications like genomic data querying.
Significant Advancement in Cryptanalysis: Query Reconstruction Attack on Chase-Shen SSE Scheme
Overview of Searchable Symmetric Encryption
A recent study has unveiled a significant advancement in cryptanalysis, presenting a query reconstruction attack on the Chase-Shen substring-searchable symmetric encryption (substring-SSE) scheme. This marks the first leakage cryptanalysis of such a scheme. Searchable symmetric encryption (SSE) is a technology designed to enable efficient querying of encrypted databases while minimizing information leakage. This method is particularly valuable for secure cloud-based storage and processing, allowing users to perform queries on sensitive data without exposing the actual content. The Chase-Shen scheme specifically facilitates querying for arbitrary substrings, which is advantageous for applications like securely querying genomic databases.
Vulnerabilities in SSE Schemes
However, many SSE schemes, including Chase-Shen, exhibit various data leakage patterns. These patterns include access, volume, co-occurrence, and search pattern leaks, which can compromise user privacy. The researchers have introduced a novel inference-based query reconstruction attack that exploits a reduced leakage profile and operates under a weaker attack model known as the honest-but-curious server. This model is different from the fully malicious model presumed by the original creators of the scheme. Key elements of leakage utilized in this attack include path length, response volume, and common prefix length.
The methodology employs auxiliary data, which is similar to the target database but sampled independently, to enhance the effectiveness of the attack. Statistical modeling of substring queries based on leakage and auxiliary data is optimized using simulated annealing. Experimental validation was conducted on datasets such as English Wikipedia and genomic data, revealing a high query recovery rate of 50-60%, with even higher rates for character-based recovery.
Implications and Future Research
The Chase-Shen scheme employs suffix trees for efficient substring matching and utilizes an encrypted dictionary to store pseudorandom function (PRF) values and encrypted indices. Leakage patterns identified during the attack include query prefix, leaf intersection, and index intersection patterns, disclosing information about shared query prefixes and matching results. The attack achieves around 50% query reconstruction accuracy over datasets containing 100,000 strings, demonstrating high success rates in reconstructing client-issued queries through the analysis of observed leakage and auxiliary data.
The findings of this study underscore the vulnerabilities inherent in substring-SSE schemes and highlight the critical need for improved countermeasures to mitigate leakage while preserving query functionality. Potential countermeasures such as volume leakage suppression could diminish the effectiveness of the attack, but this might come at the possible expense of query functionality. As substring-SSE permits clients to securely query encrypted databases for specific substrings without decrypting the data, maintaining security is vital, particularly in sensitive applications involving genomic data. The study emphasizes the broader range of queries permitted by substring-SSE, complicating efforts to secure the system compared to traditional keyword-based SSE. The results indicate that even limited leakage can significantly jeopardize query privacy, necessitating further research into effective and secure countermeasures to protect against such vulnerabilities.
Original Source: Read the Full Article Here
