Convergent encryption (CE), $E_k(d)$, is a way to encrypt the data $d$, with the characteristic that the encryption key $k$ is $k=h(d)$, where $h(\cdot)$ is a cryptographic hash function.

Consider a cloud storage with client-side deduplication. The common procedures of uploading a file $d$ are to calculate and the send $h(d)$ to cloud. Cloud checks whether it has seen $h(d)$ before. If so, the user doesn't need to upload again. Otherwise, the user uploads $d$ explicitly.

In the above scenario, we don't consider data confidentiality. Honest-but-curious cloud may know the file content. Thus, the user encrypts file before uploading it. However, different users might choose different keys independently, resulting in different ciphertexts even in the case of the same $d$. Hence, CE is used here; instead of uploading $d$ explicitly, the user uploads $E_k(d)$. One may see that different users with the same $d$ must have the same ciphertext, which is deduplicatable.

Recently, researchers found that CE is vulnerable to dictionary attack. In particular, if $d$ is predictable (or say low-entropy), CE is not secure enough. In other words, if the adversary already knows $d\in X=\{x_1, x_2, \dots, x_t\}$ and $X$, then it may calculate CE of each element in $X$ to infer which one is $d$.

A system was recently proposed to fix this problem. http://eprint.iacr.org/2013/429.pdf

Here comes my question eventually: I agree CE is vulnerable to dictionary attack and the above system is able to fix the problem. However, I am wondering whether the client-side deduplication per se is vulnerable to dictionary attack in the case of predictable file because user needs to send $h(d)$ to cloud. Because practical hash function (eg., SHA256 in DropBox) is deterministic, the adversary eavesdropping on $h(d)$ can still adopt the hash-and-then-try-to-match strategy (i.e., dictionary attack), with the attempt to recover $d$.

Is my understanding correct?

  • 1
    $\begingroup$ Sending the hash of the plaintext suffers from the same problems as convergent encryption. The best writeup of the security properties of CE I've seen so far is zooko's Drew Perttula and Attacks on Convergent Encryption $\endgroup$ – CodesInChaos Jul 6 '14 at 13:01
  • $\begingroup$ To the best of my knowledge, it seems that there is no solution currently for dictionary attack on deterministic hash function $\endgroup$ – user4478 Jul 6 '14 at 13:26
  • 1
    $\begingroup$ @user4478, what are you asking, exactly? The title asks why a hash function doesn't have a dictionary attack, while the second last paragraph correctly states it does. $\endgroup$ – otus Jul 6 '14 at 19:06
  • $\begingroup$ @otus, I think that hash function does have dictionary attack, but I cannot find any mentioning this. I did some research on the Internet, looking for related papers. However, nobody mentioned this drawback. $\endgroup$ – user4478 Jul 7 '14 at 13:46
  • 1
    $\begingroup$ @user4478, the paper you linked to mentions this, which is why that protocol never sends the hash to a server. Instead it uses as key $G(H(M)^d \bmod N)$, where $d$ is a secret that an attacker doesn't know. $\endgroup$ – otus Jul 7 '14 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.