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

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

-

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

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.

-

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.

-
 Also, I'm putting the H(plaintext) at the beginning so that it can all stream, and so that we can confirm the decrypted message. – John Gietzen Jul 13 '11 at 16:50

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

-
 It looks like the stream cipher term used by the paper is a bit more narrow than the type of stream ciphers one can get from block ciphers using a mode of operation - it is simply a function producing an (arbitrary long) key stream from a key, without any relation to ciphertext and plaintext. (This corresponds to the OFB and CTR modes of block ciphers.) – Paŭlo Ebermann♦ Jul 17 '11 at 12:18 This is what Wikipedia calls a synchronous stream cipher. – Paŭlo Ebermann♦ Jul 17 '11 at 12:25 ... and of course, an undated paper :-( (From the file date, it is from July 2006 or earlier.) – Paŭlo Ebermann♦ Jul 17 '11 at 12:31 I added a sketch of the algorithms shown in the paper. – Paŭlo Ebermann♦ Jul 17 '11 at 20:01