Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

Is there any security concerns with building a CSPRNG using a broken hash function like MD5 or SHA1? The design is such that a CRC-like function is used for mixing entropy and MD5 is used as the output function. If this is a security concern, what is the technical reason? What would be a better replacement when efficient is a concern?

share|improve this question
How do you want to use these? For mixing randomness into the pool(efficiency isn't that important there) or for generating the output stream (you can use AES-CTR for that) – CodesInChaos Feb 4 at 18:47
@CodesInChaos In this case, using a CRC-like function for mixing, and md5 or sha1 for the output stream. – Rook Feb 4 at 18:52
The CRC like function for mixing gives me a bad feeling, but without details its hard to say anything concrete. The MD5 for output is rather harmless, but quite inefficient (MD5 is four times as fast for input than for output) – CodesInChaos Feb 4 at 19:19

1 Answer

up vote 2 down vote accepted

Well, it is quite possible to have a CSPRNG that uses MD5, or SHA-1, despite their known flaws. In fact, see Hash_DRBG with SHA-1 for an example that is officially endorsed by the US Government. They don't endorse it for MD5; however, they really don't endorse MD5 for any reason (except within the TLS key derivation function).

The problem with MD5 and SHA-1 is that it is possible to create two different images that hash to the same value (with MD5, it turns out that you have quite a bit of flexibility, with SHA-1, it's been estimated to be practical, however I have not heard of anyone actually generating a colliding pair). However, creating a collision means that the attacker gets to select both pairs; with a CSPRNG, the attacker cannot influence the internal state (he can only observe). This implies that the ability to create a collision has no impact on CSPRNG security; after all, even if the attacker generates a colliding pair, he has no way of making the CSPRNG use one of the preimages he has created.

Also, one warning: just because it is possible to design a CSPRNG based on SHA-1 or MD5 doesn't mean that design that you have in mind is actually secure.

Now, when you talk about efficiency, well, SHA-1 and MD5 aren't great; they're designed to hash things quickly, not generate hashed bytes quickly (oddly enough, those aren't the same thing). The CTR_DRBG CSPRNG from the same document is somewhat better; however, the output of a good keystream generator (such as ISAAC) is going to be faster still.

share|improve this answer
+1 Great paper. The CTR_DRBG CSPRNG design looks great. Do you know of a paper that talks about keystream generators for DRBG? – Rook Feb 7 at 21:10
@Rook: I don't know of any specific paper; however, the fundamental security property of a keystream generator and a CSPRNG ("indistinguishability from a truly random stream") is pretty much the same. – poncho Feb 7 at 22:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.