1
$\begingroup$

Let $H:\{0,1\}^*\rightarrow \{0,1\}^\ell$ be a collision resistant hash function (CRH), and let $\Pi = (\mathsf{enc,dec})$ be an encryption scheme with the following properties:

  • $\Pi.\mathsf{enc}: \mathcal{K} \times \{0,1\}^\lambda \rightarrow \{0,1\}^\ell, \lambda\leq \ell,$ define as follows: $\Pi.\mathsf{enc}(k,m) = m \oplus H(k)$
  • $\Pi.\mathsf{dec}: \mathcal{K} \times \{0,1\}^\ell \rightarrow \{0,1\}^\lambda$ define as follows: $\Pi.\mathsf{dec}(k,c) = c \oplus H(k)$

is $\Pi$ chosen plain-text secure (CPA)? To the best of my knowledge, if $H$ is modeled as a pseudorandom generator (PRG) or a pseudorandom function (PRF), then $\Pi$ is CPA if a distinguisher cannot distinguish the output of the PRG/PRP from an output produced by a truly random function. However, I am not able to find such a reduction for a CRH.

Let's say Alice uses $\Pi$ to share a message $m$ over pair-wise channels with Bob and Charles (Alice-Bob, Alice-Charles share a symmetric key produced by a Diffie-Hellman exchange).

  • Alice sends $c_b = m\oplus H(k_{AB})$ to Bob and $c_c = m\oplus H(k_{AC})$ to Charles

Let's assume Decisional Diffie-Hellman. if an adversary is able to break the CRH, can it extracts $m$ from $\{c_b, c_c\}$? (we can assume that besides Bob and Charles, Alice sends the same message to other people).

Edit: I think the answers to this question help explain why CRH is not enough to provide CPA security. However, in my opinion, it does not fully answer this question because, as mentioned in the answers below, simply providing a uniformly distributed output does not imply CPA. Non-determinism is needed.

$\endgroup$
9
  • 1
    $\begingroup$ ChaCha20 series? $\endgroup$ – kelalaka Mar 30 at 9:46
  • 2
    $\begingroup$ With $\Pi.\mathsf{enc}(k,m) = m \oplus H(k)$, and the standard definition of CPA security (which allows using the same key repeatedly), the question is not about the pitfalls of a merely collision-resistant hash function instead of a pseudorandom function. The construction is trivially unsafe w.r.t. CPA for both kinds for $H$. $\endgroup$ – fgrieu Mar 30 at 11:24
  • 2
    $\begingroup$ Strongly related question, I'm not forcing a close-as-duplicate here as the CPA issue fgrieu mentioned also comes on top. $\endgroup$ – SEJPM Mar 30 at 11:52
  • 1
    $\begingroup$ @fgrieu, see my answer below, I think he was looking for something like that. I think that should be CPA2-secure no, because all for each query to encryption oracle all adversary would see is r, H(r) pairs for many random numbers and if it would allow her to distinguish cipher text, it would imply that it is not pseudo-random, because if $F_k (r)$ is indistinguishable from random both $F_k(r) ⨁ m_1$ and $F_k(r) ⨁ m_2$ should be $\endgroup$ – Manish Adhikari Mar 30 at 12:30
  • 1
    $\begingroup$ I don't think the hash function adds anything to this concept, does it? You can just take H(k_AB) and call that k_AB and now you're asking about a simple XOR cipher, which has known weaknesses in most scenarios $\endgroup$ – user253751 Mar 30 at 17:21
3
$\begingroup$

It depends what you mean by collision resistance.

If by collision resistance you mean that the output of $H(.)$ cannot be distinguished from a stream with full collision entropy (i.e. a $H_2=\ell$) then by Jensen's inequality we cannot distinguish from a stream with Shannon entropy at least this large and so the conditions for a one-time pad are met.

If by collision resistance you mean that hash function collision cannot be found without less work than $n$ hash function evaluations, then no. Let $n=2^{256}$, let $\ell=1024$ and define $H(x)$ to be SHA3(x)||SHA3(x). Collisions in $H(x)$ are in one-to-one correspondence with SHA3 collisions and so cannot be found with fewer that $2^{256}$ hash evaluations (with the proviso that SHA3 remains strong). Thus there is a 256-bits of collision resistance, but the encryption function is now horribly weak as the every other 512-bit block of key stream is a repeat of the previous.

$\endgroup$
2
$\begingroup$

I hope that I am misunderstanding your question otherwise it looks horribly unsafe and deterministic. See, Play a CPA game. Round 1:

  1. choose two messages $m_0$ and $m_1$ and send it to oracle, and you get either $H(k)⨁ m_1$ or $H(k)⨁ m_2$. You now have two candidates for $H(k)$. Round 2 repeat the same with different messages and you know $H(k)$,

A hash function itself is not modeled as a pseudo-random function, an actual function would be sampled from a family and would be unknown to the adversary, (that would be sampling a key in this case, if the key is unknown function is unknown). A hash function itself would not be that

See, first a CPA safe encryption is non-deterministic, and CPA game assumes that the key is reusable, which is not the case with your encryption scheme. I think what you were looking for would be a PRF, instead of a hash. Encrypting each time, the encryptor chooses a random number $r$. PRF is sampled with the key $k$ and is known as $F_k$. Doing $c=F_k (r) ⨁ m$, cipher is $(r,c)$ would probably do though I am still not sure whether it is secure. I assume something like this is what you were actually trying to ask in the first place

$\endgroup$
3
  • 1
    $\begingroup$ Manish Adhikari, thank you for the non-determinism clarification. After @fgrieu comments, I remembered that indeed I need to use a Nonce. $\endgroup$ – vxek Mar 30 at 15:49
  • $\begingroup$ One can easily use key for any hash function $H(key||nonce||counter)$. $\endgroup$ – kelalaka Mar 30 at 22:56
  • $\begingroup$ @kelalaka yes but I was just going by OP's question $\endgroup$ – Manish Adhikari Mar 31 at 5:52
2
$\begingroup$

is $\Pi$ chosen plain-text secure (CPA)?

Not necessarily; you could easily design a collision resistant hash function for which this construction is not CPA secure.

For a trivial example, let $H'$ be an arbitrary collision resistant hash function as set $H(x)= 0 | H'(x)$; $H$ is obviously just as collision resistant as $H'$, but in this construction there is an obvious distinguisher.

This shows that there is no reduction from CPA-security to collision resistance.

if an adversary is able to break the CRH, can it extracts $m$ from $\{c_b, c_c\}$

Again, not necessarily (assuming that there exists an $H'$ which is secure).

Here is another contrived counterexample: let us define $H$ to be exactly $H'$, except for the two inputs $H(0) = H(1) = 0$ (where both inputs 0 and 1 are 1 bit). $H$ is obviously non collision resistant; however within the protocol (where the user always provides inputs longer than 1 bit), it acts just like $H'$, which we assumed to be secure.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.