Stream cipher with Diffie-Hellman and Cryptographic Hash Function? [duplicate]

Question

I know: Never do your own crypto. But this question is just theoretical.

Assume you do a Diffie-Hellman Key Exchange with a server to produce a shared secret $x$. Then use a cryptographic hash function like SHA3 to generate a pseudorandom bitstream like this:

$$p_i = \operatorname{SHA3}(x||p_{i-1}).$$

To encrypt $i$^th packet of data, labelled $m_i$, compute

$$c_i = m_i \oplus p_i.$$

I realize that the key stream for a OTP must be completely random to ensure perfect secrecy, but would this scheme at least be as hard to break as the underlying hash function or Diffie-Hellman?

In my opinion, it should be, but I'm new to cryptography.

Since the shared secret is only used for one session, assuming the hash function is a random oracle, no keystream is ever used twice. By including $x$ in every $p_i$ an attacker has to break (not only find a collision) the first sent packet in order to decrypt the rest of the session, breaking any other packet will most likely be a collision and not give away the needed $x$, only the content of this packet. Also, breaking any packet requires at least plaintext knowledge but it gives you only this particular hash, not the previous/next hashes.

Answer 1

Since the shared secret is only used for one session, assuming the hash function is a random oracle, no keystream is ever used twice.

This construction, like all stream ciphers, will cycle and produce the same key stream.

All that has to happen is $p_i$ has to equal any of the previously observed output blocks and we'll have a cycle.

If the hash is $n$-bits wide then we can expect this to occur after approximately $2^{n/2}$ blocks by the birthday paradox. The precise size of the cycle will vary from key to key.

This is kind of a problem. Some keys could have much smaller cycles than others. At its extreme, SHA-3 could have a fixed point where by SHA-3(x) = x. The cycle length would thus be one if we were unlucky enough to hit upon this value. Note that fixed points like this can absolutely occur under the random oracle model, although it is rather unlikely.

You can fix this by introducing a counter in to your state update function. Each input to the hash would be unique.

Under the random oracle model, the oracle would choose an $n$-bit hash output uniformly at random for each iteration of the state update function. This is because it never sees the same input message twice; the oracle never gets the chance to return a previously seen state.

In theory, you'd now be back to perfect secrecy. The oracle is now flipping fair coins for each bit of the message, which is analogous to the set-up we see the in the OTP.

This is just an academic point though. Obviously, in reality no hash is a random oracle. The security just reduces to the security of the underlying hash.

Answer 2

You've just invented your own stream cipher. Rather than trying to make sure it is secure, it is better to use a stream cipher that is already known, such as AES-CTR or AES-GCM (which adds an authentication tag). Also note that stream ciphers based on secure hash functions are relatively slow compared to most stream ciphers.

Answer 3

Mathematically speaking it should be, but don't forget the weakest chain here : Diffie-Hellman is vulnerable to MitM attacks... So something in addition must be used to ensure your security.