Possible problems in using a hash algorithm to construct a stream cipher

Question

I'll define an example hash-based stream cipher as such:

• $H: \{0,1\}^* \rightarrow \{0,1\}^{256}$ is the hash function.
• $K=\{0,1\}^{256}$ is the secret key.
• $N=\{0,1\}^{128}$ is the nonce.
• $C=\{0,1\}^{128}$ is the counter.
• $X=H(K||N||C)$ is the keystream output.

I've read several of the questions posed on this site about basing a stream cipher on hash functions. One of the replies said that the properties that make a hash function "secure" might not be enough to make a secure stream cipher. Would having the outputs of many similar inputs make it possible to calculate $K$?

Answer 1

It would be good to define what you require for the cipher to be secure before trying to determine it's security properties. Take the example of CPA security - Katz and Lindell (Introduction to Modern Cryptography 2nd ed.) state that a symmetric scheme has indistinguishable multiple encryptions under chosen plaintext attack (i.e. the scheme is CPA secure for multi-encryptions) if the following relation holds in the so called "Left - Right Oracle" Game:

$ \textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{LR-cpa}(n) = 1] \leq 1/2 + \textbf{negl(n)}$

where $\textbf{K}$ is an encryption key of length $n$ and $\textbf{negl}(n)$ is a "negligible'' function in $n$ (this relation is a re-statement of definition 3.23 in the above text by Katz and Lindell)

Given the above definition of CPA security, it can be shown that CTR modes are CPA secure so long as the underlying "block cipher" is a pseudo-random function and you are dealing with a "q-query" adversary, i.e., you are limiting the number of oracle queries by the adversary to $q$ such that $q^{2}<< 2^{n}$ where $n$ is the size of the block (cf. so called "CTR Mode Theorem" over here: http://spark-university.s3.amazonaws.com/stanford-crypto/slides/04.5-using-block-annotated.pdf)

If your underlying "block" is a PRF and you have constructed a proper randomized counter mode, then your scheme would be "CPA secure" by the results stated above.

If you require CCA security, on the other hand, your scheme would need to be non-malleable in the manner of authenticated encryption schemes. So the answer to your question on security depends partly on what you require or what you wish to achieve from a security definition standpoint.

Answer 2

This is secure assuming that the hash function is a PRF. It is also secure for common Merkle–Damgård hash functions like SHA-256. Furthermore, it is secure if one uses a $n × n \rightarrow n$ compression function $F$ as $C = P \oplus F(\text{Key}, \text{Nonce}\mathbin\|\text{Counter})$, provided that $F$ is a PRF and $n$ is large enough to prevent brute-force attack.