85

I could not find any evidence pointing towards homomorphic encryption. What I could find were different combinations of deterministic and format-preserving encryption. There is probably also a variant that preserves order, but I couldn't find any material depicting it. This post is based on material published on the CipherCloud website at CipherCloud Cloud ...


32

I don't think they have implemented homomorphic encryption at all. They have just implemented regular AES encryption (they have a FIPS 197 certificate for their AES), but in what appears to be a very insecure way. Why would they choose to do that? Because they had no choice. Here's what I mean: The challenge for cloud encryption providers like CipherCloud ...


27

I haven't posted in a while, so long in fact that the email tied to my Stack Exchange account is no more, I forgot my StackEx password, and I had to create a new account. (I'll leave it to the reader to decide if this is the real me.) But I did want to just to follow up here, because there were some unanswered questions from my last post and the follow-up ...


20

They are not using any exotic encryption. In fact, based on data, it appears it's just 1:1 mapping (tokenization) after lowering the case on plain text data. I don't know about others but to me this pattern just stood out when I had a look at the demo video. To see it yourself, check their publicly visible demo video. Hit HD, go full screen to 2:19. You will ...


16

There are a number of considerations here, I'll try to lay them out one at a time for ease of following: What must the site do with the data? Oftentimes, we ask web sites to do things on our behalf when we are not actually visiting them. For example, I may want crypto.SE to email me when there are responses to this post. The site could not do that ...


13

I also watched the video (thanks Sid, for the link) and after looking at it, it reveals some of the other methods that Ciphercloud appears to be using to preserve search. Nothing appears to be an implementation of any sort of homomorphic encryption. I snapped a copy of one screen after the response from John is entered and encrypted, and have attached an ...


10

GCM mode is best, as it can not be attacked using padding oracle attacks, which are much more common than commonly thought. It is also the only one providing integrity protection, something that is certainly much overlooked. Make really sure your NONCE is random though, or use one that is uniquely defined (even in time) within the database. ...


10

This is not a limitation of the cryptographic functions, like SHA or PBKDF, since the zero byte isn't processed any differently. Since the purpose of a salt is generally to travel alongside a human password, libraries that handle the password as a zero-terminated string might also handle the salt as such a string. Obviously, a 0x00 in the salt would ...


10

I don't know how CipherCloud works. However, a related question is: How could you encrypt data in a database, in a way that allows you to achieve these goals? What are the best cryptographic techniques currently known, for that goal? As it happens, that question has a good answer. Take a look at CryptDB, a system built by MIT researchers to encrypt all ...


9

CipherCloud's website now clearly states, here, that CipherCloud DOES NOT use homomorphic encryption. This also states that CipherCloud DOES NOT implement 1:1 mapping or ECB mode in any customer deployment. Other statements are next to acknowledging that CipherCloud's early demos did that, citing the will to illustrate the functionality, features that where ...


9

If you go through the math, it appears that exactly the expected amount of ciphertext expansion is happening. Here's what's happening: The GCM takes the plaintext as a byte string of size N, and generates a ciphertext which is a byte string of size N+28, where 12 of the 28 is the nonce, and the other 16 is the authentication tag. Then, that octet string ...


7

Using a static IV isn't simply "poor form" — it introduces crippling weaknesses to the security of your ciphertexts. Likewise, using correctly-generated IVs (the requirements differ from mode-to-mode, but cryptographically random IVs almost always meet those requirements) isn't "better"; it's absolutely necessary. That said, there is absolutely no ...


6

Let's try to avoid random per-password salts. If the only requirement for salt is to be unique, which is the case for good password hashing schemes, you'll need: $globalSalt$ is a secret random 32-byte string. $userId_n$ is a unique user identifier. You can use, for example, $HMAC$-$SHA256(globalSalt, userId_i)$ to generate salt for each user $i$. Or, with ...


6

My question is where (along with encrypted data? somewhere else?) [...] should I store the MAC in database? In theory you can store the MAC wherever you want, as long as you store it and get the association right between MAC and ciphertext. Practically however it's smartest to append the tag to the cipher text. This minimizes the chances that you screw up ...


6

The mode of operation does not just matter; it defines the properties of the IV! The mode of operation is the part that specifies the size of the IV, the contents of the IV as well as the impact of abusing the IV. AES is a block cipher; by itself it only allows the key and a single message block as input; AES itself doesn't specify or know about any IV. For ...


5

Adi Shamir's secret database of all primes is to cryptography venues what the Dahu is to French summer camps. For why, see the answers to this related question. The three other future work items in the quoted presentation are in the same vein (Breaking RSA-1024 with Fermat factoring; Breaking RSA-1024 using $1024 = 2*2*2*2*2*2*2*2*2*2$; Breaking RSA-1024 ...


5

Unfortunately, without some additional assumptions about the strings (e.g. that the first 8 bytes are unique), there is no way to reduce the chance of collision below the usual chance levels. If you need unique 64-bit ids, the options are: Do a database lookup when generating keys and pick another key if it is already in use (you state that you want to ...


5

Yes, this is fine, at the record level. (What you've built would be classified as a "Encrypt-then-Authenticate" scheme in the literature, and there are standard provable security results for such schemes.) Well done on constructing a solid, well-engineered cryptographic scheme. An AEAD mode would spare you from having to invent such a scheme, but what you'...


5

What you are proposing in effect means that you use a not-really-random one-time-pad, which is used twice (i.e. a two-times-pad). This is not secure. Using a single hash to generate a key from a password is a bad idea - especially if the password is short, it is easy to brute-force it (i.e. try lots of passwords). Using the simple XOR cipher to encrypt a ...


4

I would say that CBC+HMAC mode is the best of the three (although not the fastest), because of the various security requirements on the IV/nonce. For GCM and CTR, the counter must be unique, for every pair encryption key/plaintext. I assume the key will be always the same. Uniqueness is very difficult to securely achieve in practice. If you rely on some ...


4

IMO AES-CTR+HMAC is more secure than AES-GCM. The most significant difference is that AES-CTR+HMAC relies on the nonce for confidentiality but not for integrity. AES-GCM on the other hand relies on the nonce for both. So nonce failures are much more severe with AES-GCM. The main advantage of AES-GCM is that it's significantly faster.


4

I don't think there is an existing library that can satisfy your needs. Homomorphic encryption is powerful and requires lots of computations. However, in your case which allows user-defined keywords, I suggest you to take a look at Searchable Encryption. Searchable Encryption is the algorithm that should be of interest. It allows cloud server to search '...


4

This is a really bad (and somewhat pointless) idea (if you do it on your own), because it provides less security than standard hashing and should only be considered if password escrow is a necessary feature. If you don't need the password escrow (= recover the password using the heavily secured airgapped private key) you can simply password-hash the password ...


4

If you use a deterministic encryption algorithm (so that you can actually verify passwords without the private key) it basically works like a backdoored hash. An attacker will be able to use a brute force or dictionary attack normally. One obvious problem with any reversible encryption is that it reveals (at least something about) the password length. (E.g. ...


4

You can simply handle password verification on login and escrow independently: Store a salted password hash (e.g. bcrypt) together with its salt. You can use this to verify logins, just like what you'd use if you had no escrow. Also store the password encrypted with asymmetric encryption (e.g. RSA-OAEP, ECIES). Since these are randomized, they are not ...


4

Reading your message, we (in ZeroDB) realize that we need to add some things to our documentation. Provides authenticity and secrecy (most important) That one we do have now provides integrity over the whole database (no silent dropping of data) We pretty much have it at the level ZODB we base on has (ACID-compliant) leaks as less information to ...


4

I'll start with the usual reminder: Please don't roll your own crypto, chances are you're getting it wrong. For password databases, KDBX (KeePass' format) usually is a good example which you strongly should consider using. For an analysis of some format, also see "On The Security of Password Manager Database Formats" by Gasti and Rasmussen (PDF). For ...


4

I want to say don't use SSNs like usernames for practical and ethical reasons. Yet I hope that if you switch to normal username/passwords you won't remove the (weak) password protection on encrypted SSNs that you already have. There also may be legal requirements surround SSN storage, but I know nothing about that. Definitely don't use SSNs because you ...


3

What you describe is a digital signature, which works using methods very similar to the one you suggest. Examples include elgamal-signature and RSA signature schemes (the second of which I would recommend you read). Digital signatures allow you to provide a public signature that 'proves' you provided the message. As the author, you would produce database $m$...


3

Is there a technically feasible way for companies like CipherCloud to use homomorphic encryption (HE) while preserving full functionality in a third party SaaS app (e.g. Salesforce)? Fully homomorphic encryption can theoretically1 compute any function. Therefore, if a computer can perform a task on plaintexts, then fully homomorphic encryption could ...


Only top voted, non community-wiki answers of a minimum length are eligible