1
$\begingroup$

In an answer of here someone mentions:

if you have a hash-function-with-oracle-powers, then it is rather easy to generate a pseudo random stream from a secret key, by hashing K||n where K is the secret key and n is a counter. By XORing this key-dependent pseudo-random stream with the data to encrypt, you have a stream cipher.

In the same post there is also this part regarding using cryptographic hash functions for creating a stream cipher:

A cryptographic hash function is a function which is resistant to preimages, second preimages, and collisions. As far as I know, it has not been proven that these conditions are sufficient to build a stream cipher.

As far as I know all of the currently existing symmetric algorithms, especially AES, are only believed to be secure. The only evidence we have in regards to their security is their use in practice and that attacks that have been tried so far were not catastrophically reducing the security of those algorithms.

Is the issue that "it has not been proven that these conditions are sufficient to build a stream cipher" really the only issue? What are other issues with stream ciphers that are induced by hash functions? Are they probably less secure? Are they probably slower? Are they probably using to much memory? Is it just that there are other encryption algorithms researched that promise better results?

I would assume a hash function with a larger block size has the advantage that longer keys or longer nonces could be used. For SHA-512 one could use a key with 384 bit and a nonce of 128 bit length. Another possibility would be to keep using 256 bit keys, use 128 bit nonces and have a better maximal message size of 2^128 blocks (or 2^137 bit for SHA-512) compared to ~2^39 bit for AES-GCM with only 96-bit nonces (which would be a nice goal in my opinion).

Improve this question
$\endgroup$
1
7
$\begingroup$

Is the issue that "it has not been proven that these conditions are sufficient to build a stream cipher" really the only issue?

So, collision resistance is indeed not enough to build a secure stream cipher, the standard example would be to take a collision resistant hash function and appending 128 $0$ bits to the output. This clearly inherits the collision resistance but also does not provide output that is indistinguishable from random.

Are they probably slower?

This is usually identified as the core issue. Computing hash functions is typically 3-10x slower than computing dedicated symmetric constructions like AES. This is most likely due to the nature of hashing which has a "stronger" threat model, having to provide security in the face of the adversary knowing all values in the computations whereas AES only needs to offer security when the adversary does not know one input - the key.

Are they probably less secure?

While we could use hash functions that provide no pseudorandomness in their output, the standard constructions we use have been carefully designed to offer uniformly random looking output.
The detailed arguments depend on the underlying construction, but we can generally build a secure keystream generator as some variation of $H(k\|p\|n\|\text{ctr})$ for modern hash functions with appropriate padding $p$.
The underlying security assumption is then similar to that of HMAC, requiring Merkle-Damgard hashes' internal compression function to be a dual-input PRF and Sponge-based hashes' internal permutation to be a random permutation which is already assumed for collision resistance.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ Another thing that may not be required for hash functions is that key needs to be protected against e.g. side channel attacks. That's also not a problem with most hash functions (otherwise HMAC would be in trouble) but this may not be apparent from any hash function / implementation. $\endgroup$
    – Maarten Bodewes ♦
    Jul 6 at 12:06
  • $\begingroup$ Also, PRF is one way and can provide a wide range of functions instead of PRPs. $\endgroup$
    – kelalaka
    Jul 6 at 17:09
6
$\begingroup$

A cryptographic hash function is a function which is resistant to preimages, second preimages, and collisions. As far as I know, it has not been proven that these conditions are sufficient to build a stream cipher.

The output of a cryptographic hash function, being collision and pre-image resistant does not necessarily mean that they produce output indistinguishable from random. Because with a chosen plaintext attack, the generated stream can be easily extracted. If the stream is distinguishable, then the discernible pattern may reveal information about plain text. As far as I know (others correct me if I am wrong), no such problem has been known with any of the currently used hash function. [And as others have pointed out, it may be because no such cyptoanalysis of hash functions used as stream generator has been done with sufficient rigor as it was never intended to be used that way]

There are some issues with how your question has been presented. There is nonce, counter and key. You are talking about nonces below but no counter and the equation you quoted $H(k\mathbin\|n)$ from answer has got counter but no nonce so you have not made clear how you use them.

Anyway as far as we know, $H(k\mathbin\|n\mathbin\|\text{ctr})$ where $n$ and $\text{ctr}$ are respectively, nonce and counter might be a good stream generator for most hash functions I guess, as long as $k$, $n$ and $\text{ctr}$ all have fixed length (you don't have to worry about length extension type attacks for fixed length input). But more generally you must use functions that are thought to be pseudo-random functions (like HMAC) for a reasonable guarantee of security if you want to use hash based stream. As in $\operatorname{HMAC}_k(n\mathbin\|\text{ctr})$ . And because HMAC uses double hashing and block ciphers like AES have high optimization, I guess it does not provide the performance that state-of-the-art streams (chacha, AES-CTR/GCM) provide even if it is secure enough.

Improve this answer
$\endgroup$
6
  • $\begingroup$ How does the length extension attack work on CTR mode? $\endgroup$
    – kelalaka
    Jul 6 at 13:10
  • $\begingroup$ @kelalaka I said "MAY". Actually, I was not thinking much about how to actually do it while I wrote the answer. I cannot think of a realistic scenario for that but can imagine a wild scenario where n can be of any arbitrary length (i.e. multiple blocks) and an attacker can control IV but cannot repeat it. So he creates something like $n' = n\|i\|padding$ and extends length from that. Or finds some cipher with huge nonce and right format for that, and performs CPA with control over nonce (uses the small nonce), gets the stream and performs length extension to get original stream $\endgroup$
    – Manish Adhikari
    Jul 6 at 13:24
  • $\begingroup$ Of course trying it on counter value would be out of question $\endgroup$
    – Manish Adhikari
    Jul 6 at 13:25
  • $\begingroup$ @kelalaka Thought of a less "wild" scenario, a system has a flaw that makes it very likely that it picks an IV of the right format as described above and is susceptible to chosen ciphertext attack. The ciphertext needs to be authenticated using MAC but does not authenticate the IV. The IV is prepended to chosen ciphertext and the system would not decrypt the target ciphertext (one that uses IV of the right format). A CCA2 in this case can reveal the key stream for the target ciphertext via length extension. $\endgroup$
    – Manish Adhikari
    Jul 6 at 16:07
  • $\begingroup$ This is unrealistic in Modern Cryptography. Why do we need to define a variable-length to complicate the analysis and security? We already know the problems around it, there are tons of exercises about this and similarly PRFs. $\endgroup$
    – kelalaka
    Jul 6 at 17:08

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.