Is it feasible to build a stream cipher from a cryptographic hash function?

Question

A few years ago I devised a symmetric-key system that worked like so:

H()   = some hashing function
h     = the number of bits in the result of H()
key   = bits to be used as a key
^     = the XOR operation
+     = concatenation
len() = the length function (in bits)

max = ceiling(len(cipertext) / h)
pad = pad_0 + ... + pad_max
pad_0 = H(key) ^ H(plaintext)
pad_n = H(pad_(n-1))
cipherpart_n = plaintext_n ^ pad_n
ciphertext = H(plaintext) + cipherpart_0  + ... cipherpart_max

Basically, it builds up a "pad" based on the hash of the message and hash of the key and XORs the message against it.

I am not actually an expert, so I was wondering why an approach like this isn't very common.

Answer 1

With the corrected system (which actually uses the key), I see these weaknesses:

• If the attacker can guess some plaintext_n, he can derive pad_n from ciphertext_n and from this all the following pad_i - which means that he can read the rest of the message.
• The ciphertext starts with a H(plaintext), which means that an attacker which can guess the plaintext has a means to verify this guess. To avoid this, the plaintext should at least be randomly padded. (But then you could simply use these random bytes as the initialization vector instead of the hash of the plaintext).
• The entropy of your actual key stream (the pad) is reduced to h bits, even if the key itself had bigger entropy. This might be better if you input the key again to the hash function for creating the higher-order pad_n.
• As already said by Jack, the need to hash the plaintext before you can start to encrypt it means that you need two passes over the plaintext, which means that the encrypting algorithm is not an online-algorithm (the decryption is).

Other than this, your algorithm is similar to the Output feedback mode of operation for Block ciphers, with the initialization vector derived from the message, and without new key input for the following steps.

Here is a variant which would not have these weaknesses (and hopefully no others):

initvec = random
pad_0 = H(key + initvec)
pad_n = H(key + pad_(n-1))

ciphertext = initvec + cipherpart_0 + ... + cipherpart_max

(The rest as in your example.)

This does not do integrity-protection ... for this you would append some keyed MAC at the end (so it can be an online algorithm).

Then we have actually the OFB mode of a strange "encryption only" block cipher derived from the hash function. The only problem would be that it would be quite slower than a normal block cipher, as Jack already mentioned.

Disclaimer:

Note that while this construction is secure in the random-oracle model (see this blog entry for a proof of a similar construction, using a counter instead of previous hash), the proof uses properties which are not implied by the collision-resistance and preimage-resistance properties of a hash function (which is what hash functions are constructed for).

So while this might work, it does not have to work with real-world hash functions.

Answer 2

This approach, at a high level, is actually fairly common; many stream ciphers operate on this very principle. For instance, Salsa20 uses what is effectively a hash function (a PRF) to convert a secret input (that includes a counter) into the keystream which is XORed with the plaintext. However, this kind of function can be much faster than a secure cryptographic hash, because it does not need to prevent preimages or collisions as a cryptographic hash does. For instance, OpenSSL's SHA-1 runs at about 50 MiB/s for small inputs (on my desktop machine), whereas its AES-128 implementation runs at around 90 MiB/s.

I'm rather confused by your specific scheme, though. You set the first pad to the hash of the plaintext, rather than the key. So given the first piece of the ciphertext (H(plaintext)) one could rederive the entire stream. If this is really what you meant to write, it's also quite slow, since it requires you to read the entire message before you can process any piece of it.

Update:

I should mention that if there is any full block of known or guessable plaintext in your message, your scheme is easily broken because given $pad_{(i)}$ anyone can compute $pad_{(i+1)}$. So guess one block of plaintext, $XOR$ it against the ciphertext to recover a possible pad value, then compute the next pad value and see if the recovered ciphertext in that block seems valid.

Answer 3

You may be interested in BEAR and LION.

http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf

---

The authors basically build block ciphers (with variable block sizes $m$) from a keyed hash function (a function family $H_K : {0,1}^* \to {0,1}^k$) or a normal hash (a function $H': {0,1}^* \to {0,1}^k$) and a stream cipher (a function $S : \{0,1\}^k \to \{0,1\}^n$, for arbitrary $n$ from context; here $n = m-k$).

These work by fist splitting the input block of size $m$ in two parts, one (L) of size $k$ and one (R) of size $m-k$, doing the encryption/decryption, and putting the two parts again together. We also have two keys $K_1$ and $K_2$, each of length $k$.

For BEAR, the encryption is done by

$$ L := L ⊕ H_{K_1}(R) $$ $$ R := R ⊕ S(L) $$ $$ L := L ⊕ H_{K_2}(R) $$

and decryption the other way around:

$$ L := L ⊕ H_{K_2}(R) $$ $$ R := R ⊕ S(L) $$ $$ L := L ⊕ H_{K_1}(R) $$

For LION, we use a un-keyed hash function $H'$, and we have two calls of the stream cipher instead of the hash function instead of two keyed hash calls. Encryption:

$$ R := R ⊕ S(L ⊕ K_1) $$ $$ L := L ⊕ H'(R) $$ $$ R := R ⊕ S(L ⊕ K_2) $$

Decryption:

$$ R := R ⊕ S(L ⊕ K_2) $$ $$ L := L ⊕ H'(R) $$ $$ R := R ⊕ S(L ⊕ K_1) $$

E.g. decryption is in both cases just encryption with swapped key halves.

The paper proves that these are secure (against certain attacks) as long as even one of the component functions is secure (e.g. breaking the composed primitive allows breaking both of the components). For added resistance against other attacks there is also a version (LIONESS) which uses both keyed hash and stream cipher twice.

---

I don't really understand why anyone would want a block cipher if they already have a stream cipher, but there you go. See also what Jack Lloyd said, above, about Salsa20.

Here is a rough sketch of a proposal to do the Salsa20 style of counter-mode with a modern secure hash function: http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004487.html

Answer 4

The answer has two sides:

• First, the feasibility from the security side: If used cryptographic hash function is indistinguishable and proper padding is used, you can use the resulting "hashstream" as you would use any other stream cipher (like RC4). To add it up, if the function has no weaknesses, you can also easily compute keystream at block $n$ as $H(\text{key}|n)$, I see no reason why that wouldn't be secure.

• Second, the real feasibility. Common requirement on ciphers is actually to be as fast as possible, and while there's similar requirement on hash functions, it's usually not stressed too much. Even compared to complicated block ciphers, either based on Feistel networks or AES-like, computation of hash function for the same block (output) size usually takes many times longer. If you don't mind some slowness (or are only working with small data), it is probably OK, but since we have some striking-fast stream ciphers with similar levels of security, this approach is probably not going to attract much general attention.

In short: Secure, but comparably very slow.

PS., for your protocol: having $s=H(\text{plaintext})$ in the ciphertext unencrypted allows attacker to simply find (some matching) preimage of $s$, and decent preimage attacks exist for many hash functions. As the previous answer suggested, you definitely want to avoid that.