Cons for stream ciphers that are based on hash functions

Question

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).

Answer 1

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.

Answer 2

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.

Answer 3

From an old school code-breaker, please allow me to give you a certain cryptographic analysis perspective that is the first thing taught in the military, but ignored by academia.

Firstly, do yourself a favour and read Shannon's 1945 and 1949 papers. Focus on Chapter 11 Equivocation (Conditional entropy).

When analysing cryptographic solutions, you must understand them from an entropy, and a conditional entropy perspective. Entropy signifies the size of the search to be conducted, and conditional entropy is the size of the remaining "possible" key or message candidates with respect to the given ciphertext.

When conducting cryptanalysis, there are a few unbroken rules

(a) The security solution designer is not allowed any assumptions.

This is because we don't create better security systems by dropping the standards of security, but by raising them just beyond what we consider impossible. It's the only way to attain "impossible".

Every time you read the statement "will take millions of years to brute force" you should interpret it as "Insecure - Its just a matter of time before it is broken". Time is NOT a security characteristic - that's why any security system which relies on the workload assumption of Practical Secrecy systems MUST NEVER be considered quantum secure. There is an even greater risk developing - Artificial Intelligence using Quantum Computing resources. If we are told to expect quantum computers by 2040, we must assume that they were available in 2010.

Shannon warned that Practical Secrecy systems should never be used for secure communication unless it can be proven that no fast solution to the system exists. That's harder than you think to accomplish. Pseudo-security. Looks like the real thing but isn't.

(b) When conducting analysis, one must assume that the assailant has infinite resources and time. This eliminates a lot of confusion during analysis. It allows for quick eliminations of assumptions.

(c) the assailant gets the benefit of any doubt or assumption unless it can be proved otherwise. If you want to rely on the "time assumption" you must prove that there is no faster way, otherwise assume that he can do this instantly. Just to make you aware - There are at least 22 different ways to perform the factoring of prime products faster than a brute-force search. And they can be combined.

From a general cryptanalysis perspective:

Firstly, with regards to a closed system that is a pure cipher, the security of a cipher is dependent on two things only. The starting entropy (size) of the system as a whole (keys * nonces) and the redundancy of the language used in the message. With these two quantities you can calculate how much ciphertext needs to be intercepted to successfully benefit from a key or message brute force attack.

This can be plotted on a logarithmic graph for visual analysis and simple additive manipulation.

The graph above shows plots for the characters (x axis) in 4 different types of messages against a 32 bit key (y axis).

• K0,M0 - Conditional entropy of known plaintext
• K1,M1 - Conditional entropy of "normal" plaintext
• K2,M2 - Conditional entropy of "50% Redundancy" plaintext
• K3,M3 - Conditional entropy of "random" plaintext

The length of the intercepted ciphertext required for a successful key or message brute force is related to the amount of redundancy in the message.

Looking at K1 and M1 we see the conditional entropy of a "normal" message. We know that various languages on average have massive amounts of redundancy, over 80%. So with AES-256 you divide key entropy by redundancy 256/0.8 = 320. This means that you only need 40 bytes of AES-256 to break it under brute-force attack. The 320-bit indicates the unicity point on the graph. the point where message equivocation = 0 (2^0 = 1). Where a single valid result will occur when the last candidate ciphertext is eliminated.

But we never brute-force attacked the key (that's for the ignorant to assume)- we used inverse functions for entire secrecy systems, to attack the message. An inverse function is easily derived for a one time pad, but is more complicated but not impossible as mechanics get complicated. Given a message and the ciphertext, it will reveal the key.

But AES-256 has a problem - it is not a pure cipher. It is possible that a different key may lead to the same valid decryption. And there are a whole range of problems there.

If it was pure, it would be pointless to do multiple rounds (inefficiency).

All closed deterministic systems can be hacked. The only way to escape the insecurity condition that every closed system cipher with deterministic mechanics has, is to use open systems with probabilistic mechanics. There are military ciphers in this category already, one is being presented to the world in November this year.

Finally - to get to answer the question directly. The idea is to use a closed system (fixed start key entropy), take a secret key, and use it like a PRNG to continually generate hashes as a keystream which is then used to encrypt messages like a one time pad.

The solution will be secure from a military perspective for the following messages.

• Random string messages - secure for any length - but beware, there will only be 2^32 variations in our example. Don't use that as the one time pad key for a subsequent message. You can use it for other purposes though.
• Messages as long as the key used - secure (like a one time pad)
• Normal language messages - secure for messages shorter than 40 characters
• Compressed messages - insecure for any length of compressed message if treatment of message is not applied. Remember, every key possibility is attempted, leading to every hash sequence.For every hash key combination, the attacker will look for the compressed file header or footer. Same as a known plaintext. Also, insecure for known uncompressed plaintexts. Theres more workload to break, but not secure.
• Predictable message - known plaintext or chosen plaintext - insecure for any message length.

If you start a system with limited entropy (keys + nonces + IVs + variations), the conditional entropy of keys and message with respect to the ciphertext intercepted, will always be reduceable under an attack to the point where a single viable message will remain - and it happens faster than you think. A stream cipher can work, if you send more entropy along with the message, than can be removed by an attacker performing a brute-force attack (think Quantum/AI attacker).

In addition, please note that one-time pads have a flaw - known plaintext reveals the key - So if you send a web page with an XOR encryption, it can be intercepted, the key can be easily derived, the web page address can be changed, and sent on to the receiver.But this can be addressed with various validation techniques.

Thanks for your time.

Answer 4

• As long as you're using a good long random key (256 bit or more), nonce (never reusing!), padded minimum data size (no messages < key size) in your stream cipher, a cryptographic hash + xor will work fine. H(k∥n∥ctr).

• The main issue is performance

• I would suspect that the security guarantees might even be better than other ciphers, since certain hashes, like keccak, have fairly favorable proofs around the inability to reverse them. But because the speed is worse for minimal or possibly zero gain, nobody that I could find has sat down and bothered proving this.