Let $C$ be a symmetric cipher $H$ a hash function.

Alice uses $C$ with a key $k$ to encrypt plaintext message $m$ yielding ciphertext $c$. She then calculates the hash of the message $h_m = H(m)$ and the hash of the ciphertext $h_c = H(c)$.

Alice then sends $k$, $h_m$, and $h_c$ to Bob.

Is there any combination of $C$ and $H$ for which Bob can prove -- just from the hashes and the key alone -- that there is indeed some message $m$ for which $h_m = H(m)$ and $h_c = H(C(m,k)$.

Note that Bob does not actually have to discover $m$ and that there can be multiple $m$ that have the same hashes.

In short: find the function $magic$ in this diagram

m  --------- H --------> h_m

|                         |
C(_, k)                 magic(_, k)
|                         |
V                         V

c ---------- H --------> h_c

where $magic(h_m, k)$ calculates the hash of the ciphertext from the hash of the plaintext (but the other way around would also work).

  • $\begingroup$ I didn't send $m$ or $c$ though. $\endgroup$ – Tobias Brandt Jan 18 at 14:28
  • 1
    $\begingroup$ "...and that there can be multiple $m$ that have the same hashes..." that's generally true for cryptograhic hashes. But it is also true that it should be computationally infeasible to find them (second pre-image resistance). If you don't include that in your consideration then you're done: any hash value is likely to have a message that hashes to it :P $\endgroup$ – Maarten Bodewes Jan 18 at 16:04
  • 1
    $\begingroup$ @MaartenBodewes The question is not just whether there is an $m$ for $h_m$ -- that's obvious. In adition, it must be true that after encrypting said $m$ with the known key $k$, the result hashes to $h_c$. $\endgroup$ – Tobias Brandt Jan 20 at 9:48
  • $\begingroup$ Hmm, what if you put a $\geq 128$ bit secret in front of the message and hash the message including secret. Then you could use the same hash for the ciphertext I suppose. If you still need a hash over the ciphertext itself then you could add another hash over the ciphertext & plaintext hash. However, you'd have to send both hashes in that case. $\endgroup$ – Maarten Bodewes Jan 21 at 15:06

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.