5
$\begingroup$

The main motivation for Oblivious RAM (ORAM) is that, for instance, in the "cloud" setting a client outsources his data to a server in the form of encrypted blocks. Later on, he wants to perform read and write operation on these encrypted blocks, which apparently may leak information about what data is stored. ORAM now ensures that the server cannot tell which blocks the client is interested in and whether he is reading or writing.

My question is: Are there any concrete examples/attacks, where the access pattern on encrypted data leaks sensitive data?

Improve this question
$\endgroup$
3
  • $\begingroup$ This is a bit broad to answer, as it strongly depends on what kind of O-RAM implementation you’re asking about: HASH-based Oblivious RAM, Oblivious RAM via FHE, Oblivious RAM via Symmetric Encryption, … Some of them have concrete examples and/or attacks, others don’t. $\endgroup$
    – e-sushi
    May 21, 2014 at 15:48
  • 2
    $\begingroup$ @e-sushi I don't quite get what your comment is trying to convey. He is NOT asking about attacks on ORAM (this is indeed a much used abbreviation). He is asking about the attacks on non oblivious encrypted data-structures that are the motivation to develop ORAM construction (be that Hash based or whatever) $\endgroup$
    – Maeher
    May 21, 2014 at 16:52
  • 1
    $\begingroup$ @Maeher Hmmm, in that case it’s definitely a bit too broad… and lacks research efforts, as a quick lookup for “attack access patterns encrypted data” spits out a truckload of papers like this one and this one. Giving it the benefit of the doubt, I initially interpreted the question and its description as asking for such attacks in an O-RAM setting… where different implementations may lead to different access patterns, which is why I pointed to the missing info re implementation type. $\endgroup$
    – e-sushi
    May 21, 2014 at 18:31

2 Answers 2

Reset to default
2
$\begingroup$

By observing data access patterns in emails researchers were able to infer search pattern.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Hello curious, please add an excerpt from the paper in your answer to show why the it is a good source. $\endgroup$
    – rath
    May 22, 2014 at 6:08
  • $\begingroup$ This paper is a great find and very relevant. On the other hand, its threat model makes some assumptions that might not be realistic in practice. It requires that the server know some of the queries (a known-plaintext setting) and have a priori knowledge on some frequency statistics concerning the unencrypted emails. I find it hard to tell whether their attacks will be realistic in the real world or not. $\endgroup$
    – D.W.
    Jun 23, 2014 at 1:49
3
$\begingroup$

There is a new paper on the topic, the paper is not publicly available yet; however, its slides are available at David Cash, Paul Grubbs, Jason Perry, Tom Ristenpart - Leakage-Abuse Attacks against Searchable Encryption .

A short summary of the talk is available at Seny Kamara - Workshop on Encryption for Secure Search & Other Algorithms:

David Cash also discussed inference attacks. In addition to standard inference attacks, however, he also described attacks where the adversary exploits more than leakage and, in particular, knows or chooses some of documents. The findings were very interesting. One thing that came out of this study was that the IKK attack—while very interesting in theory—is not really practical. There are several technical reasons for this but I’ll leave you to read David’s paper when it appears if you are interested. This study also looked at a new class of schemes (not SSE/structured schemes) that have appeared in the literature recently and showed that they were vulnerable to adversaries who know and/or can choose documents (though to be fair they were not designed with that adversarial model in mind).

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.