How is CipherCloud doing homomorphic encryption? Much of the literature and latest papers suggest that homomorphic encryption is still not practical yet.

How is CipherCloud able to achieve this? Does anyone have an idea? Their website does not provide much information about how their system works.
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 Security Learning Center - Featured Content. CipherCloud notes that the actual product has additional encryption features that offer stronger security and don't suffer from the listed weaknesses (see CipherCloud response section).

Material 1: A screenshot from their whitepaper Best Practices in Securing Your
Customer Data in Salesforce,
Force.com, and Chatter on page 10:

[image removed due to DMCA request]

Description: This screenshot depicts contact details (name, address, phone, etc.) in three columns.


The first column shows the policy which determines how different fields should be encrypted. For most fields this is "AES Crypto Encryption", for some fields such as phone numbers it's a specialized form of encryption, such as "Telephone Number Encryption".
The second column shows the plaintext ("As seen by authorized users")
The third column the ciphertext ("As seen by Unauthorized Users")


Analysis: When a field consists of several parts(say firstname and lastname) they split it into those parts and encrypt them individually.

Some important fields, such as "annual revenue" aren't encrypted at all, probably because they need to do use it in calculations.

The encryption for names and addresses preserved the length of the individual words and the position of spaces. There are special tags between words that seem to mark encrypted parts and separate tokens.

Preserving length strongly hints at deterministic encryption, as does support for search. In theory, it'd be possible to use difference nonces for different records, but I consider that unlikely since it'd be hard to keep a search index in such a case.

Material 2: Feature list from the same whitepaper (page 11):


  Encryption Options: AES-256, Function Preserving Encryption,
  Length Restricting Encryption, etc. Ability
  to select on a field-by-field basis


Analysis: Same length encryption was already observed in Material 1. Presumably preserved functions search and ordering. Probably it's possible to choose which functions to preserve on a per-field basis. Material 3 will demonstrate a form of encryption that allows search, but does not appear to preserve ordering.

Material 3: CipherCloud Connect AnyApp Demo Video around 2:30 and 3:00:

[screenshot omitted due to DMCA request]

Description: This shows a typical message board that is part of the yammer web-application. There are two open windows showing the same thread. One shows the encrypted messages (as the yammer.com server sees it), the other the plaintext form as it is seen when accessed through CipherCloud. The message bodies are encrypted, the usernames and post times are not. The encrypted messages are a mix of Asian and ASCII characters.

Analysis:

There is a clear correspondence between plaintext words and ciphertext token. Each token starts with zqx1, ends with 0j1xqz and corresponds to one word. Punctuation marks are not encrypted at all.

Words that occur multiple times in the plaintext (for example meet, to, want) appear as identical tokens in the ciphertext.

The words new and will are even more interesting. They occur both in lowercase and uppercase form. The encrypted form of New might look like zqx1賓翡祀徠鈞祁記勤机琦芸稶70j1xqz1 and the encrypted form of new like zqx1賓翡祀徠鈞祁記勤机[linebreak]20j1xqz2.

So I assume the first part of the token encodes the word in a case insensitive form and the second part supplies the casing information. Sid made the same observation in his post. This form of encryption allows the case insensitive search they demoed in the video, where a search for apac turned up a message containing APAC since the beginning of the word is the same, regardless of case. This certainly looks like a 1:1 mapping between lower case words and the first part of the token.

The first part of the token seems to have a constant size of 9 Asian Characters. Given a large number of such characters, that would be enough to encode 128 bits or one AES block. So one possible implementation would use AES in ECB or CBC mode with constant IV encrypting a single block. But this paragraph is pure speculation that can't be proven from the limited observations we made.

An inherent weakness in such a scheme is that it doesn't offer semantic security.  If the same word gets encrypted in different places, an attacker can see that the same word was used in both places. If he can figure out one of them, he automatically knew the other too.

The attacker could also employ some kind of word-level frequency analysis on tokens. Once part of the ciphertext has been recovered, the known words serve as a context for further guesses. Once a certain knowledge threshold has been exceeded this should allow recovery of most words. So it's essentially to prevent an attacker from learning any (ciphertext, plaintext) pairs, even for harmless messages. Quoting public material or storing drafts which later will be published is also quite dangerous.

A similar non-deterministic scheme

The above scheme is essentially a word-level substitution cipher. Classical substitution ciphers usually use a single letter (or a small fixed amount of letters) as a substitution unit. Modern block ciphers such as AES trivially allow using whole words as a substitution unit which was a bit difficult to do without a computer.

Those early substitution ciphers had similar weaknesses to the above scheme (1:1 mapping between letters, deterministic encryption, and frequency analysis). Of course with short/letter units these weaknesses where much more pronounced than with long/word units.

One technique used to reduce the impact of these weaknesses is having multiple possible substitutions for each plaintext unit and randomly choosing one during encryption. This technique is called Homophonic substitution. This technique can obviously be applied to word-level substitution ciphers as well.

When a word has n possible ciphertexts, one could still do searches by triggering n separate searches over the encrypted data and merging the results. This would turn above 1:1 mapping into a 1:n mapping, make the encryption non-deterministic and, depending on the chosen probability distribution, frequency analysis might be less effective as well. Of course, such a combined search would leak some information to the server about which ciphertext units might correspond to the same plaintext unit.

There is no evidence that CipherCloud uses a homophonic word substitution cipher. I only mentioned this scheme because it's the simplest change to the above scheme that doesn't contradict the claims in their DMCA notice. Ciphercloud claims not to suffer from the above weaknesses, thanks to "patent pending mechanisms". I certainly hope that their mechanisms are better than simply switching to a homophonic word substitution cipher.

CipherCloud's claims in their DMCA notice:

As a counterpoint to this analysis here are some claims made in their DMCA notice:


  Such false, misleading and defaming statements include the following sample:
  
  (2) "If the same string gets encrypted in different places, an attacker can see that the same string was used in both places." [statement from an old version of this post]
      * Again, CipherCloud's product is NOT deterministic.
  
  (4) "As CodesInChaos suggested in an earlier answer, this makes the solution extremely vulnerable to frequency-analysis attacks." [from AdrenaLion's post]
      * The referenced scheme does NOT represent CipherCloud functionality. In fact, CipherCloud has patent-pending mechanisms to defeat frequency-analysis attacks.
  
  (7) "Basically they end up with a 1:1 mapping of lower case words." [Sid's post, referring to the message board discussed in this post]
      * The statement is patently false. Sid implies that what was perceived from a public demo is CiperCloud's product offering. [emphasis mine] CipherCloud does not incorporate 1:1 mapping.


(10 sample statements were included in the DMCA notice, I picked those most relevant to this post. I inserted notes linking quoted statements to their original posts)

Conclusion

The observed encryption has significant weaknesses, most of them inherent to a scheme that wants to encrypt data while enabling the original application to perform operations such as search and sorting on the encrypted data without changing that application. There might be some advanced techniques (homomorphic encryption and the likes) that avoid these weaknesses, but at least the software demoed in the video does not use them.

The only way I see to reconcile the statements in their DMCA notice with the observed encryption properties is that the actual CipherCloud product is significantly different (and better) than what is shown in their promotional material.

If they don't want to be judged based on the information they published about their product, perhaps they should update their material to match their actual product more closely.

CipherCloud response

CipherCloud post a response on their blog: Responding to the Myths about CipherCloud’s Encryption Technology

Pretty little concrete information, but here some relevant parts:


  I wanted to provide some clarity to the question of whether CipherCloud uses homomorphic encryption.  The answer is NO.  Homomorphic encryption is far from ready for practical usage due to performance and lack of capabilities. 
  
  The cited CipherCloud product demo in the board threads was focused on highlighting our reverse-proxy concept for cloud information protection to organizations using cloud applications. Some of the fundamental security features made available  (e.g. full-field encryption, randomization through IVs, etc.) were disabled because we were not comfortable sharing such IP on the internet while our patents are still pending.




1 The actual Asian characters were different from the one in my post, but the general form was the same.
2 The linebreak is an artifact of the browser displaying the text. It might have hidden some characters.