Slashdot Log In
Encrypted But Searchable Online Storage?
Posted by
timothy
on Thu Apr 16, 2009 03:20 PM
from the give-some-to-that-lawyer dept.
from the give-some-to-that-lawyer dept.
An anonymous reader asks "Is there a solution for online storage of encrypted data providing encrypted search and similar functions over the encrypted data? Is there an API/software/solution or even some online storage company providing this? I don't like Google understanding all my unencrypted data, but I like that Google can search them when they are unencrypted. So I would like to have both: the online storage provider does not understand my data, but he can still help me with searching in them, and doing other useful stuff. I mean: I send to the remote server encrypted data and later an encrypted query (the server cannot decipher them), and the server sends me back a chunk of my encrypted data stored there — the result of my encrypted query. Or I ask for the directory structure of my encrypted data (somehow stored in my data too — like in a tar archive), and the server sends it back, without knowing that this encrypted chunk is the directory structure. I googled for this and found some papers, however no software and no online service providing this yet." Can anyone point to an available implementation?
Related Stories
Submission: encrypted online storage with encrypted search by Anonymous Coward
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
It's not possible even in theory (Score:5, Informative)
It's not possible to do this even in theory, unless you're relying on very weak encryption. The point of encryption is that you can't infer anything about the contents. If Google was able to infer enough to give you meaningful search results (if for example each word was encrypted by itself, and you searched for the encrypted version of the word), they would therefore necessarily be able to know enough to perform a frequency analysis attack on your data and compromise it in no time flat unless it was a very small amount of data (thus meaning search isn't really of value anyway).
You'll find a similar problem plagues any attempt at searching. Searching requires a certain knowledge or meta knowledge of the material being searched; and that knowledge necessarily dramatically weakens your encryption.
Re:It's not possible even in theory (Score:5, Interesting)
It is possible. When you upload the data, you also upload an index. When you connect again, you download the index (which is much smaller than the data) and search that on the local machine. Neither the index, nor the data, is ever unencrypted on the server.
As for frequency analysis, I don't think any encryption algorithms published in the last 40 years have been vulnerable to this sort of attack...
Parent
Re: (Score:2)
Re:It's not possible even in theory (Score:5, Informative)
Parent
Re: (Score:3, Insightful)
That's not how I read it. But the approach still sounds useless:
If Alice wants to search for the word W, she can tell Bob (the server) the word W and the ki corresponding to each location I in which W may occur
What's the use of encrypting the data if you're going to send keywords in cleartext to a party you're trying to hide the data from?
Re:It's not possible even in theory (Score:4, Interesting)
Parent
Re: (Score:3, Informative)
Re:It's not possible even in theory (Score:5, Funny)
Gee guys, isn't this a little bit too much work just to hide your porn?
Just mark the directory as hidden, your mom will not find it.
Parent
Re: (Score:3, Informative)
And that would practically defeat the purpose of the encryption.
For the index to be useful it has to provide too much information about the encrypted data. The point of encryption is to ensure that nothing can be inferred about the contents of the encrypted data. If you give them a nice big bunch of information about whats encrypted, why bother encrypting it in the first place?
Given enough information in the index they could actually derive your encryption key as well with some simply brute forcing.
Maybe, maybe not (Score:2)
Unless you do the indexing client-side, and upload an index that's somehow encrypted...
I'm not saying I know how to do this, but it seems possible.
Re:Maybe, maybe not (Score:4, Interesting)
Maybe something like this -
Create an index of hashes using the unencrypted data on the client.
Encrypt the data on the client so we now have an index of hashes that apply to an encrypted file.
Upload the hash index and the encrypted data file to the server.
To search, hash the search criteria on the client.
Server search the indexes for the hash value, returning a list of encrypted files with an index matching the criteria hash.
Parent
Re: (Score:2)
Not possible in theory? You should tell the authors of the linked paper that describe how to do it in theory.
Re: (Score:2)
Re: (Score:2)
Yeah, I'm not sure I understand how meaningful searches can be done without decryption-- but then I don't pretend to be any kind of a genius about these things. It seems much more likely to me that there could be some kind of a system where unencrypted search indexes are kept locally while the files are encrypted and sent to an online storage service. Then you could search locally for the file you're looking for, fetch the encrypted information from the online storage, and then decrypt it locally.
That so
Re:It's not possible even in theory (Score:4, Insightful)
I'm curious - why would you post a comment claiming that this can't even be done in theory, when the submitter included links in the summary to a paper that shows that it can?
Parent
Re: (Score:3, Interesting)
Because the paper doesn't propose any solution that is practical, or which even leads to a practical solution.
In theory I can cure all forms of cancer - all I have to do is go through each cell in the victim's body and pluck out the cancerous ones.
It is possible to a certain extent (Score:3, Interesting)
There are encryption algorithms that allow addition. That is, the sum of two encrypted messages is an encryption of the sum. I've forgotten how these work exactly, I think they are some many to one mapping, and the addition operation is not simply adding the encrytped numerical representations.
I came across these when looking at voting systems that allow N distributed people to vote in a way that sums the result before it is decrypted rather than decrypting to do the sum.
Anyhow what this means is that is
Re:It's not possible even in theory (Score:4, Insightful)
Can I have an anti-theft system for my car, so that nobody can steal it but anybody who wants to can take it for an anonymous test-drive?
Parent
You want to... (Score:4, Insightful)
Use an encrypted query to match against the encrypted text. The problem is, if the text is REALLY encrypted, then there shouldn't be enough information to do this - the encrypting of the original text should make it impossible to even match against it.
If it didn't, then an attacker who got hold of the encrypted text and some of your encrypted queries might well be able to mount an attack based on commonalities between the two.
Re:You want to... (Score:4, Funny)
NOT TRUE! I use a combination of XOR and rot-13 encryption and I'm able to do text searches just fine. The trick is to encrypt the search string, then it'll work perfectly. This is because the encryption doesn't depend on the position within the text, but that shouldn't hurt security too much.
Parent
Easy (Score:2)
This sounds pretty easy,
a) obtain database, indexing tools, search tool
b) install on the machine and encrypt the entire hard drive with any of the many available whole-disk encryption tools
c) ssh in and run queries.
Good luck with that.... (Score:2)
The best I think you can do is store and transfer the data in encrypted form and put the indexes and any search logic on the client. Maybe the index could be stored on the server as well and synced to the client, but creating the
It depends on the encryption (Score:3, Insightful)
If the data is encrypted in independent "chunks" from which search terms can be built then this is trivial: You pre-encrypt your search terms and search for them. Searching a word ROT13 [wikipedia.org]-encoded document works this way, as each character is encrypted individually and an encrypted search term is made up of encrypted characters.
Once you get past this, it's no longer easy. You basically have to either make the term you are searching for look like all possible values of the encrypted text and return all matches, or decrypt the document somewhere.
If the encryption is good and any particular chunk, extract, or other slicing-and-dicing of the encrypted data without the key looks random, you are pretty much stuck with decrypting it somewhere.
The alternative is to store an index, or at least a list of keywords, in clear text. For example, a document describing how to build a nuclear bomb could have a list of 10 or 20 non-classified keywords attached to it to aid searching. But that's not what you are asking for.
searching encrypted data (Score:2)
http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf [berkeley.edu]
Re: (Score:2)
Doh! Just noticed you already are aware of that particular work. Anyway, congrats, you're already aware of the state of the art!
GNUnet (Score:2)
It's been done. GNUnet [gnunet.org].
A guy walks into a bar... (Score:5, Insightful)
Re: (Score:3, Interesting)
But... That's not a valid car analogy since you're not allowed to drink and drive.
Re:A guy walks into a bar... (Score:4, Funny)
Not good enough. The bartender could audit his liquor to see how much of each bottle was dispensed.
This is why when they do this sort of thing, the gentleman just serves the bartender a National Security Letter and takes more than what he wants without paying a dime.
Parent
Re: (Score:3, Interesting)
...if I tell you a story in French and you don't understand it, you will have no idea what I told you and will not be able to answer questions about my story. However, if you are able to memorize all I told you phonetically I can ask if I said a word or not just by the sound. Yet you don't know exactly what I asked for, nor the meaning of the answer but you are able to answer that question since it doesn't imply meaning.
So a possibility for the OP would be to store the information in a language unknown to a
not impossible; not easy (Score:3, Interesting)
Keep the files on the remote server, encrypted. Keep the search index in a database, encrypted in chunks. Rsync your search database between your local machine and the server. Actual searches of the databases would be done locally.
Result: terrible performance whenever you access your data from a new machine (must sync entire search database). Good performance the rest of the time. Remote server never sees anything but cyphertext.
I don't understand... (Score:3, Funny)
...isn't this easy?
Plaintext: "Attack at dawn"
Ciphertext: "lkaoiuast98u;aw"
Search query: "oiua"
Result: "lkaoiuast98u;aw"
What could be simpler?
(no, I'm not an idiot, this is a joke.)
querying encrypted data howto (Score:3, Interesting)
As long as your query looks something like this...
SELECT * FROM mydata WHERE stuff LIKE '%YToyOntzOjc6InBhY2thZ2UiO3M6MjM5OiKyKHPh9ZawDX6KyA62cMd6p+mjBybGwJyCaNfFb7S.........
Seriously though, if I understand your objective I think it would be feasible to develop something like that, but I don't think its something you could integrate into Google's search services unless they added something on their end.
You could pass a decryption key along with your query and the server would then decrypt records as it performed the search. It would be very resource intensive.
As an close example, I have a web based password storage application in which I did not want to keep the encryption keys on the same server as the password database. So I generate a key with which to encrypt the records and the user keeps their key and must supply it every time they want to decrypt a record. I don't go so far as to enable searching of the encrypted data, I have a description field specifically for that purpose. The web application is called Passbox [sourceforge.net] and is written in PHP.
What an oxymoron! (Score:3, Interesting)
Yeah, Id like my cake and eat it too!
The only way this could work is if you has tags in the meta header of the encrypted file
telling you that yes I am encrypted, but I have an image in me or my encrypted data is of the type accounting.
This might work for indexing searches where you want to be able to return all the files on the pc (encrypted or not) that are images or etc...
There is a way, kind of: PIR (Score:3, Informative)
There is a cryptography technique called Public Information Retrieval which allows you to do just that: Send an encrypted query to a server, let it perform some operations on your behalf, and send you an encrypted query result. The server neither knows the contents of the encrypted data, nor the content of the query, but you have your result nonetheless.
The intuition is that there exists a sort of "black-box" operation which some cryptographic techniques can use. For example, if I have two encrypted bits a and b (where I can't tell what a and b actually are), I can still perform the operation a xor b. The result is encrypted, and I don't know the actual operands or the result, but I know that what came out is indeed the encryption of the xor of the encrypted bits. Such cryptosystems are forms of "Homomorphic Encryption".
Using this, we can then give the server a search term thus encrypted and, using the black-box opertaion, have it do some set of operations which will reveal the result. The server will execute the exact same set of operations independent of the search term, so it knows nothing (and needs to know nothing) of the search term contents. Of course, this implies that the server has to operate on every element of the encrypted data to do its job, but that's the fundamental tradeoff. If you're willing to accept that, and the additional computational overhead, you can design such a system.
I put something similiar to this together myself.. (Score:4, Interesting)
1 - Mask the filename
2 - Encrypt the contents
3 - Add recovery data in case the file got damaged
4 - Ability to view unmasked filename from web
I put together a batch file I could drag/drop multiple files onto that used WinRAR to compress the files (individually), with encrypted filenames, a password (of course), and included archive recovery data. It then used ReNamer to encrypt the
I had a webpage that would accept a password, and unencrypt the filenames so they were viewable in readable form on the page. Each one was a hyperlink. There was an extra step required if you wanted the downloaded filename to be unencrypted as well.
After uploading 115G or so, my host alerted me to the fact that they didn't allow me to keep offsite backups there.
My solution didn't allow me to search within the files, but it did allow me to store files on the server that they had no way of viewing the contents of, or guessing the contents of based on filename.
Re:Am I missing something? (Score:5, Insightful)
You're missing something. SSL is for data that is in transit. The poster wants the data to be encrypted on the server. That's easy - any encryption program can do it. But then s/he also wants to search it. That is harder.
Parent
Re:Am I missing something? (Score:5, Informative)
Search works by tokenizing a document, and creating an inverse index from tokens to documents. The tokens does not need to mean anything to the search engine. If you generate the tokens on the client, and don't transmit the dictionary that maps from word to token id, you can have "encrypted search".
The problem with doing that directly is that if you want to do proximity based search you need information on the token order, and they could do frequency analysis to come up with plain text guesses if they guess the language right. You can counteract that by mapping the same word to multiple tokens to even out the frequency of each token id, but it means you would need to search for multiple tokens to find all occurrences of a word.
If you don't are about word proximity it's much safer, as the index would only contain each token once per document at most.
Parent
Re: (Score:3, Insightful)
Re:Am I missing something? (Score:5, Insightful)
No, this is not what SSL is for at all. SSL you have a party you wish to communicate with, but an insecure channel.
Here, you don't want to communicate anything useful to anyone. This is more a privacy preserving data mining problem. It goes something like this:
I have a long list of secret numbers 1...n. I do something to these numbers, so that Google doesn't know what they are, and then I send them to Google. Next, I want to know how many numbers are larger than, say k. So, I ask Google, but in a clever way, so that Google doesn't know what I'm asking.
Google then tells me how many of my original numbers were larger than k. However, Google doesn't know my original numbers, and they don't know what question I asked. There needs to be some theoretical mapping that preserves this privacy, but still allows the data mining to occur.
Parent
Re: (Score:3, Interesting)
Re:Am I missing something? (Score:4, Funny)
It can't, that's why I use Live Search. It doesn't understand the query, the data, or the result. Unfortunately, for the OP, it doesn't support encryption.
Parent
Re: (Score:3, Insightful)
Do you know which word "2" represents, or what is in documents 103 and 178?
That's how you do it. You need to ensure there's no way of doing statistical analysis on the token list to recover plaintext info, and you need to not give them the dictionary mapping from plaintext to tokens.
Re: (Score:3, Insightful)
Yes you are =)
SSL only encrypts the transport.
It seems that the poster wants to have his data _stored_ in an encrypted way that is only decipherable by him, not by any of the machines/users at the storage facility. Yet, when he wants to do some search, he somehow expects the server to be able to do so... AFAIK that's not feasible.
(you could store whatever encrypted stuff remotely, but querying will require fetching, reading and decrypting the (relevant portions of) data locally...)
Re: (Score:3, Interesting)
Sure the *NAME* is "Secure Sockets Layer", and perhaps that was what it was originally developed for, but it's just wrong to say that it can't be used otherwise, and/or that it only encrypts data "in transit", not on a server. Take a look at this:
http://us2.php.net/manual/en/function.openssl-public-encrypt.php [php.net]
Here's the use of SSL functionality without (ahem) a socket. Right from the docs:
This function can be used e.g. to encrypt message which can be then read only by owner of the private key. It can be als
Re:huh? (Score:5, Funny)
if the server cannot decipher the query it cannot execute it on a binary blob of encrypted data. FAIL.
Gung jbhyq qrcraq ba ubj gevivny lbhe rapelcgvba zrgubq vf.
Parent
Re:huh? (Score:4, Informative)
Parent
Re: (Score:3, Funny)
I tried the vi command, but I get this weird error:
'vi' is not recognized as an internal or external command,
operable program or batch file.
Does this mean ROT13 is not compatible with Windows?
Re: (Score:3, Funny)
I think so... perhaps you should try another operating system [gnu.org]?
Be aware though, it's got a weird text editor...
Re:huh? (Score:5, Insightful)
Well that depends whether the OP wants to perform something like a fulltext search (i.e. the ability to look for keywords within the content of each document) or a metadata search.
There's nothing to prevent you setting up a CMS where each piece of content is encrypted, but the metadata describing that content is out in the clear and searchable. Security in such a scenario would be less than optimal (e.g. people could guess certain things about your content based on the statistical pattern of length for each of the millions of encrypted content items), and of course you'd have to be very careful about the metadata fields and how you are populating them.
Parent