Encrypted hash vs hashed encryption

Question

Problem

Is there any combination of hash and encryption algorithms with show the following properties:

File $\rightarrow$ Hash $\rightarrow$ Encrypt $==$ Hash $\leftarrow$ Encrypt $\leftarrow$ File

So a combination of hashing and encryption which can be applied in arbitrary order so that it leads to the same result.

---

Use case

I want to add optional encryption to an existing file synchronisation service. Currently only trusted nodes exist, which store data unencrypted. They use the file hash as an identifier.

My idea is, to add untrusted nodes which store the data encrypted. Only the trusted nodes have the key.

In order to detect changes, hash values are compared. Since the data only exists in encrypted form on untrusted clients, they can only compute the hash of encrypted files. On trusted clients, data exists unencrypted and has a hash of the unencrypted version stored along. Now it would be far easier to just encrypt the hash on the fly instead of encrypting the whole file and computing the hash of it.

Don't overlook the extension in my edit!

---

Edit (2019-03-26)

I noticed that I should clarify some things about the use case:

1. Two equal files do not exist in our application since they are deduplicated!
2. We split files into equally sized blocks. So in this example all files have the same length!
3. There are multiple nodes. For simplicity let's look at the case where we have 2 trusted ($N_{t1}$, $N_{t2}$) and 1 untrusted node ($N_u$). They are all in sync at an arbitrary point in time. Now node $N_{t1}$ creates a new file, encrypts it and synchronizes it with $N_u$. Now $N_{t2}$ comes back online and wants to determine which files have changed.

Further, I want to respond to Ilmari Karonen's answer (also too long for a comment):

The case $m_1 = m_2$ does not exist (see my clarification above).

We use relatively small blocks (128KB). So plaintext-guessing-attacks are an issue?

I thought about something like your first scheme already (please correct me if there is a structural difference):
I could just store the hash of the unencrypted file (which is our current file identifier) $H(m)$ together with the encrypted file $E_K(m)$. This would allow offline key-guessing attacks though:
1. Try to decrypt the ciphertext $E_K(m)$ with different keys $K_i$:
$E^{-1}_{K_i}(E_K(m)))=m_i$
2. Hash the result $H(m_i)$
3. Check if this is equal to the stored hash $H(m_i)\stackrel{?}{=}H(m)$
If so, we found the plaintext :/
When the used keys are long enough, this shouldn't be a problem. But with increasing computing power, it is only a question of time until this can be cracked.

Is your third scheme different from what I try to avoid (see use case): In order to calculate $H_K(m)$, I need to encrypt and hash the plaintext ($H(E_K(m))$). This needs a lot of computational power for big directories. Alternatively, I could compute it once and save it. This would decrease data efficiency significantly. Nevertheless, if it is considered secure, I guess it is the best we have since I don't want to compromise on security.

Your second scheme seems interesting, although I didn't understand it completely yet (I will have to check the links you posted). Do you think this scheme is more promising with the clarified use case than the third scheme?

Answer 1

What you want does not exists with any secure encryption scheme and collision resistant hash function.

Any encryption scheme that is at least CPA secure¹ cannot be deterministic. Therefore not only can the equality you ask for not hold, it's even true that for $c_1 = \mathsf{Enc}(k,H(m))$ and $c_2 = \mathsf{Enc}(k,H(m))$, it holds with overwhelming probability that $c_1\neq c_2$. similarly, $h_1\neq h_2$ with overwhelming probability for $h_1 = H(\mathsf{Enc}(k,m))$ and $h_2 = H(\mathsf{Enc}(k,m))$, since the encryption scheme is secure and the hash function is collision resistant.

Furthermore, due to a secure encryption scheme being probabilistic, ist must also be expanding. I.e., for $c = \mathsf{Enc}(k,m)$ it holds that $|c|>|m|$.

Since a hash function compresses inputs to a fixed length, it must therefore hold that $$|\mathsf{Enc}(k,H(m))| > |H(\mathsf{Enc}(k,m))|$$ and thus by extension necessarily that $$\mathsf{Enc}(k,H(m))\neq H(\mathsf{Enc}(k,m))$$ even if you would try to somehow correlate the randomness used in the two encryptions.

---

¹This is the absolute bare minimum of what we consider a secure encryption scheme in most cases. As Maarten points out in the comments there are some narrowly defined use-cases in which weaker notions of security may be acceptable.

Answer 2

Yes, there are schemes that can do (more or less) what you ask for. Not necessarily in exactly the way you sketched it, but it's possible to e.g. have an encryption scheme $E_K$ (with key $K$), an unkeyed function $f$ and a (possibly key-dependent) deterministic hash function $H$ such that $$f(E_K(m)) = H(m).$$

A simple example would be to let $H$ be any secure cryptographic hash-function, such as any of the functions in the SHA-2 or SHA-3 families, and let $E_K$ be any conventional encryption scheme modified by appending $H(m)$ to the end of the ciphertext $E_K(m)$. The function $f$ then just needs to trivially extract the hash of the plaintext from the end of the ciphertext.

Alternatively, we could make $H$ depend on the encryption key $K$ e.g. by wrapping the hash function inside the HMAC (or, for SHA-3, KMAC) construction. This would prevent potential attackers (including your untrusted nodes) from computing hashes of arbitrary plaintext messages and seeing if they match any of the ciphertexts. (The untrusted nodes can still compute $f$, of course, since that just amounts to extracting the precomputed HMAC/KMAC value from the ciphertext $E_K(m)$.)

Another way to achieve the same result would be to let $E_K$ be a deterministic encryption scheme, such as AES-SIV without a nonce, let $f$ be any cryptographic hash function and simply define $H(m) = H_K(m)$ as $f(E_K(m))$. Or, for the particular case where $E_K$ is AES-SIV, we could just let $f$ extract the synthetic IV that is stored in the first 128 bits of the ciphertext, and which is basically a MAC of the plaintext.

---

Are these schemes secure? It depends on what you mean by the word "secure".

Obviously, by construction, all these schemes have the property that, given two ciphertexts $c_1 = E_K(m_1)$ and $c_2 = E_K(m_2)$, it's possible for an attacker to determine whether or not $m_1 = m_2$ simply by comparing $f(c_1)$ and $f(c_2)$. According to traditional security definitions based on ciphertext indistinguishability, this is sufficient to constitute a break, and thus none of these schemes can meet those security definitions (as pointed out by Maeher).

On the other hand, the last scheme (using AES-SIV) obviously meets the definition of DAE security, which is essentially the same as IND-CCA2 security (one of the strongest types of ciphertext indistinguishability) except that the encryption scheme is allowed to return the same (or recognizably similar) ciphertexts if the same plaintext is encrypted twice.

It seems to me that the second scheme above (using HMAC / KMAC as $H$) should also be DAE secure, as long as the encryption scheme $E_K$ itself is DAE (or IND-CCA2) secure. The first scheme (with unkeyed SHA-2 / SHA-3 as $H$) does not satisfy the definition of DAE security, since it also allows an attacker to determine whether or not a given ciphertext encodes a given plaintext without knowing the key. That said, it may still be adequately secure for many purposes — certainly it's no less secure than separately publishing the hash and the encryption of each plaintext, since that's basically what it does.

Is this still a reasonable notion of security? If you don't care about revealing the equality of two plaintexts (and it appears that you don't, since your scheme is designed to reveal that), or allowing plaintext-guessing attacks (for the first scheme, with unkeyed $H$), then I would say that it probably is.

Of course, you do need to be aware of this "structural weakness" in your system (and also make sure that your users are aware of it, so that they can decide whether it's acceptable to them) — just as you should be aware e.g. of the fact that basically all conventional encryption schemes, even those considered to be secure under traditional definitions, will fully or partially leak the length of the plaintext.