6
$\begingroup$

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$?

$\endgroup$
  • 2
    $\begingroup$ Using HMAC instead of plain hash is probably better security-wise. This can lead to something like HKDF for generating the keystream. $\endgroup$ – Artjom B. Apr 7 '16 at 14:42
  • $\begingroup$ related: crypto.stackexchange.com/q/1070/23623 and crypto.stackexchange.com/q/33867/23623 $\endgroup$ – SEJPM Apr 7 '16 at 19:21
  • $\begingroup$ HMAC halves the performance (in CTR mode at least) and the security improvement is rather dubious. Just make sure to use the key as first input and always use the same message length and a plain hash should be fine. $\endgroup$ – CodesInChaos Apr 7 '16 at 19:41
  • 1
    $\begingroup$ BTW, this is exactly the design of Salsa and ChaCha, a hash function in counter mode with the key and nonce being hashed as well. The Salsa & ChaCha cores are much "weaker" as cryptographic hashes than something like SHA-256, but much faster. cr.yp.to/snuffle.html $\endgroup$ – rmalayter Apr 11 '16 at 4:31
  • $\begingroup$ @CodesInChaos What "message length"? $\endgroup$ – Melab Apr 11 '16 at 13:44
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What counts as a query? $\endgroup$ – Melab May 28 '16 at 14:43
1
$\begingroup$

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.

$\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.