Stream Cipher Key Stream from Successive Hashes

Question

I'm currently studying crypto and wondered what would be wrong with the following process...

I want to encrypt a long message $M$ with a short symmetric key $K$ and a public nonce $X$.

The idea is to increase the length of $K$ with successive hashes $$K' = H(X\mathbin\|K) \mathbin\| H(H(X\mathbin\|K)) \mathbin\| \cdots$$ until $length(K') = length(M)$.

Then encrypt with $$M' = X \mathbin\| (M \oplus K').$$

I'm not suggesting that I would use that instead of using something like libsodium.

But I would like to have some intuition about stream ciphers with something that I can understand completely.

Is there anything fundamentally broken with this approach? Is it possible to adjust this approach with minimal changes to make it not broken?

Answer 1

The Insecurity of Proposed Scheme

It is not as secure as it seems, in modern cryptography standards it is totally insecure. It is vulnerable to basic Known-Plaintext attacks (KPA) and in Modern Cryptography, we want a cipher secure against at least Chosen Plaintext Attack (CPA) or better Ind-CPA.

Now take the idea

$$K' = H(X\mathbin\|K) \mathbin\| H(H(X\mathbin\|K)) \mathbin\| \cdots.$$

If there is a known-plaintext block for the first output $H(X\mathbin\|K)$ then attackers can hash again and again (sometimes written as $H^s(X\mathbin\|K)$ ) to reveal the others without needing a key. So your design fails the next-bit test, i.e. the next bit of your keystream is predictable with 100%. The known block is not restricted to the first block, it can be anywhere except for the last block. All output keystream after the known block can be calculated. The previous blocks are secured with the pre-image resistance of the hash function.

The CTR mode with Hash

Instead, we used the CTR mode ( [1] as it is designed for PRF - Pseudo-Random Function - ( here we assume that the $H$ is a PRF). The CTR mode is CPA secure.

$$H(k,0) \mathbin\| H(k,1) \mathbin\| \cdots \mathbin\| H(k,\ell)$$ where the $\ell$ is the number that your message size divided into output size $b$ of the $H$ i.e. $\ell = len(m) / b$

The CTR mode doesn't require a PRP (Pseudo-Random Permutation, not proven yet, however, like AES), since it doesn't need the reverse of the encryption. For example, see the ChaCha20. Some restricted environment saves a lot of space for the implementation.

Transforming this scheme into OFB mode

The OFB mode is also CPA secure (the ECB is not). OFB produce the stream as $O_j = E_k(O_{j-1})$ with $O_0 = IV$. The encryption is performed as $C_j = P_j \oplus O_j$

As noted by SEJPM in the comments; Let define $H'(m)=H(m\|K)$ and produce the keystream similar to OFB.

$$K'=H'(X)\mathbin\| H'(H'(X))\mathbin\| \ldots$$ Note that in every step the key is added again. So the attacker needs the key to process from the known output stream. Assuming the used hash is a Random Oracle (RO) then this converts it into PRF then we can use the security arguments OFB.

Note that the hashes are candidates to Random Oracles.