Is collision resistant hash enough for one-block counter mode?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.