Can you make a hash out of a stream cipher?

Question

A comment on another question made me wonder about something:

Assume you're on a rather constrained platform — say, a low-end embedded device — with no built-in crypto capabilities, but you do have access to a simple stream cipher; say, RC4 or one of the eSTREAM ciphers. What other crypto primitives can you build out of that stream cipher? In particular, are there any practical ways to build a cryptographic hash function and/or a MAC out of just a stream cipher?

We already have questions about turning a hash into a stream cipher and about turning a stream cipher into a block cipher, but this particular transformation doesn't seem to have been covered yet.

Obviously, if the platform constraints permit it, one could ignore the stream cipher and just implement a standard hash function from the ground up. What I'm wondering is whether having the stream cipher available might let one do better than that in terms of code size, memory usage and/or speed.

While a construction that treats the stream cipher as a black box would be nice, schemes that only use parts of the stream cipher (like RC4-Hash, which, alas, has practical collision attacks) would be interesting too, at least if they're simple enough.

Answer 1

I am pretty sure that it is not advisable to use a stream model to construct a cryptographic hash. I do not have a full theoretic proof in hand, but can think about it from the perspective of a famous stream cipher, RC4. It is susceptible to related-key attack. Now to use RC4 for constructing a hash function, you need to argue that it should be resistant to a stronger adversarial model, viz chosen-key attack, whereupon the adversary can target the weakness in key scheduling. I am sure full chosen-key is not under consideration for RC4 (correct me if I am wrong). On the other hand, you allow the adversary to pick the key in the very first part of the definition of any form of resistance (apart from chosen-target-forced-prefix resistance which is not yet formally defined) for cryptographic hash function! So, I am pretty sure that it is not advisable.

However, if we look at few results from the theoretical point of view, Coron et al. showed the equivalence between ideal cipher model and the random oracle model. This give some hope: convert the stream cipher to block cipher secure in the ideal cipher model and then by equivalence it is secure in random oracle model; but we get stuck here (how to move from RO model to an instantiation of a hash function. After all, the million dollar question is whether we trust random oracle model after Canetti et al worked showed weakness in the random oracle model!

Answer 2

A Pseudo Random Generator (PRG) and a hash function are both Pseudo Random Functions (PRFs), but they have different security considerations. (At least, historically they do. Moving forward some of them may be more closely aligned.) Due to this, building a hash from an existing PRG designed under older security constraints probably isn't a good idea for the intuitive construction of using the plaintext as the key to the PRG and the PRG output as the hash. See this nice summary: Why stream ciphers shouldn’t be used for hashing.

Answer 3

This is a really bad idea. Most stream ciphers, certainly RC4 and anything in a Counter Mode construction are ultimately a PRNG XORed onto the plaintext. This is fine for encryption -- the information theory is pretty easy to understand -- but is no basis for a hash function.

The goals of a hash function and a cipher are different. As it turns out, you can make a block cipher into a hash function, but even then not any block cipher makes for a good hash function.

Think of it this way -- a cipher is like a game of cards. It relies upon the fact that you can't see what's in your opponent's hand, and what makes it hard or intractable is the uncertainty. But a hash function is like a game of chess. Everyone knows everything, and the goal of the hash function is to make it so complex that you can't go backwards and that there's no easy way to predict forwards.

Answer 4

Edit: See the comments, this construction is not provably secure

After some more thought, the answer is "yes", you can construct a hash from a stream cipher. (My other answer from a few days ago was only negative, eg, how not to construct it.) Here is a construction.

First build a block cipher $B$ from the stream cipher $S$:

• Take the PRG $P$ from $S$.

• You can build a PRF family $F$ from a PRG using the CGM construction. Use $P$ to build $F$.

• You can build a PRP (block cipher) $B$ from a PRF using a Feistel network. (The Luby-Rackoff theorem states that a secure PRF can be used to construct a secure PRP using 3 (or 4 depending on security desires) rounds of a Feistel network.) Use $F$ to build $B$.

Now we have a PRP from a PRG. (And we didn't use a hash to do so, as some stream cipher to block cipher constructions do; using a hash in this construction seems uselessly circular). Now build a hash from a block cipher:

• You can build a collision resistant compression function $h$ from a PRP using the Davies-Meyer compression function. Use $B$ to build $h$. (Edit: Not necessarily - DM requires an ideal cipher, which is stronger than what $B$ is. The security proof doesn't follow in this step. This may be fixable by finding a different $h$ construction or $B$ construction, but I have not found one.)

• You can build a collision resistant hash function $H$ from a collision resistant compression function using the Merkle–Damgård construction. Use $h$ to build $H$.

As to your practical considerations: Is it efficient? I can't speak in general, so let's analyze this construction. Popular hash functions like MD5 and the SHA family use the same Merkle–Damgård construction, so to compare our $M$ against them we'll just focus on analyzing our $h$.

• Speed: Every $h$ iteration, we have 3+ rounds of a Feistel network, each of which consists of keying $F$ and generating a small output from it. Keying our $F$ and generating $n$ bits of output itself requires $n$ re-keys of $P$ and $n$ number of $2n$ bit outputs from $P$ due to how the CGM construction works, and none of it is parrallelizable. So our $n$ bit $h$ requires at least $3n$ re-keys of $P$ and $6n^2$ bits of output from $P$. Considering the speed of modern stream ciphers this is very slow compared to modern hash algorithms, but might be practical in a situation where: hashing is rare, hashed input is small, or hashing is not very time critical.

• Implementation overhead: We need to implement the CGM construction, Feistel network, and DM function. Building $F$ from $P$ re-uses $P$'s implementation and adds a feedback loop pushing $n$ bits of output back into the key for $P$ with a branch condition on 1 bit, and no more than $n$ additional bits beyond the input will need to be stored in memory at a time. The Feistel network construction is minimal overhead, just a few XORs and array swapping. The DM construction is just a couple inputs into the Feistel network and another XOR. That looks like it is less overhead than a SHA-2 compression function.

We should be able improve on this scheme. We might be able to build a compression function from a PRF more directly than going through the PRP. And the biggest loss of efficiency here is CGM, maybe another construction might turn a PRG into a PRF more efficiently than CGM does.

Edit: This may work if we can build a compression function differently. Until then, it's just an interesting construction with no security proof. I'm leaving it largely as-is as a starting point for a future self or other to fix.