Can you make a hash out of a stream cipher? A comment on another question made me wonder about something:


  Assume you're on a rather constrained platform &mdash; say, a low-end embedded device &mdash; 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.
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.