root labs rdist

January 31, 2012

Why stream ciphers shouldn’t be used for hashing

Filed under: Crypto,Protocols,Security — Nate Lawson @ 10:48 am

I recently saw a blog post that discussed using RC4 as an ad-hoc hash in order to show why CBC mode is better than ECB. While the author’s example is merely an attempt to create a graphic, it reminded me to explain why a stream cipher shouldn’t be used as as a cryptographic hash.

A stream cipher like RC4 only has one input (the key) and one output, a variable-length keystream. During initialization, the key is expanded and stored in an internal buffer. When the user wants to encrypt or decrypt (both are the same operation), the buffer is updated in some way and keystream bits are output. It’s up to the caller to take that keystream data and XOR it with the plaintext to get the ciphertext (or vice versa). Very simple, right? You just initialize the stream cipher’s state with a key and then turn the crank whenever you want keystream bits.

A cryptographic hash algorithm like SHA-1 also has one input (the data) and one output, the digest. A variable-length stream of input data is crunched in blocks, giving a final output digest that should be difficult to invert, among other properties.

At first glance, it seems that a stream cipher can be used as a cryptographic hash by setting the data to hash as the key, turning the crank, and using some of the keystream as the digest. The reasoning goes, “since it should be difficult to recover the original stream cipher key merely by seeing some of the keystream, the output is usable as a hash”. While this may sound reasonable, it is often wrong, leading to various security problems.

There are numerous, vital design distinctions between stream ciphers and hashes. First, a stream cipher is designed to output an extremely long keystream sequence while a hash digest is a relatively small, fixed-length output. There are design differences that arise from expanding a key vs. compressing input. Also, resistance against a chosen input attack is a requirement for a cryptographic hash, while it may not have been considered for a stream cipher. What could an attacker gain if they can choose the input keys? By definition, they already know the secret key in this case.

The RC4 weakness that led to WEP being broken was a related-key attack. Even though an attacker could not choose WEP keys, the RC4 key was the concatenation of a counter and the secret key. Thus, subsequent outputs of the keystream are derived from closely related input keys.

But to use RC4 for hashing, it would have to be resistant not only to related key attacks, but to a chosen key attack. In this case, the attacker can target weaknesses in your key schedule algorithm by maliciously choosing many keys versus merely knowing that some relation exists between unknown keys that the attacker can’t choose. While chosen-IV attacks are part of the consideration for stream ciphers, I haven’t heard of full chosen-key resistance being an important design criteria. (Please correct me if I’m out of date on this, especially with eStream).

In contrast, resistance to a chosen-input attack is the very definition of a cryptographic hash algorithm. This resistance comes at a performance cost. Turning a hash algorithm into a stream cipher can be done (say, an HMAC using a key and counter), but it’s slower than stream ciphers that were designed as such. Stream cipher designs are optimized for performance and are usually not focused on preventing chosen-key attacks. An interesting corrolary is that analyzing a stream cipher’s key scheduling algorithm as a hash function (e.g., collision resistance) is often a good way to understand its possible weaknesses.

To summarize, don’t use cryptographic primitives for non-standard purposes. There are often built-in assumptions based on the original intended application that could compromise your modified design.

11 Comments

  1. Maybe this should a discussion that should be taken offline, but as a person new to security, I would like to know the fundamental differences in stream ciphers and hashes when applied in real world examples. For example if a passwords were to be encrypted using RC4 as opposed to SHA-1 (not even sure it can be called encryption), it would result in what exactly, how would it be achieved, etc? I am probably blind to how this differs to what is offered by SSL as my understanding is that it is simply an exchange of keys which then hashed using an algorithm such as SHA. Be happy to discuss this via email especially considering I am a newbie to the security world.

    Comment by PM — January 31, 2012 @ 12:22 pm

    • It would be called “password hashing”, not “encryption”. Also, that’s not how SSL works.

      Why don’t you read the archive of this blog (started in 2007)? You’ll come across a number of posts, including a presentation that’s an intro to SSL.

      Comment by Nate Lawson — January 31, 2012 @ 4:52 pm

      • Thanks Nate. Will have a look at it. Dumb question. What is the difference between hashing and encryption?

        Comment by PM — February 5, 2012 @ 12:48 pm

  2. How does this apply to bcrypt’s Eksblowfish-based approach for hashing passwords?

    This system uses a static well-known key (“OrpheanBeholderScryDoubt”) and uses the salt for the (thought to be extremely expensive) key setup, then runs the algorithm blowfish algorithm a shitload of times (alternating the salt and password for the key at each step). The output is the password’s “hash”.

    Comment by Peter — January 31, 2012 @ 12:52 pm

    • No, it uses that “Orphean” string as plaintext and the password/salt as the key.

      As stated in this post, it means Blowfish must be strong against related-key attacks since passwords may differ in only small amounts. But password hashing is quite different from regular hashing (e.g., plain SHA-1), which is what the post was really about.

      Comment by Nate Lawson — January 31, 2012 @ 4:48 pm

  3. I think it may be worthwhile having a post on the differences between using hashes for securing passwords, and using hashes for securing data integrity / authenticity (as part of a signature). I see many people get this wrong, in terms of confusion around the differences between collision and pre-image recovery and how they relate to the two common uses for hashing.

    Comment by Andrew Jamieson — January 31, 2012 @ 5:01 pm

  4. An other big problem is that RC4 is not resistant to first and second preimage attacks and absolutely not collision resistant if you use 256 bits key.

    It’s really easy to find 2 keys that generate the same first bytes of keystream.
    Even for “long” keystreams as an example :

    data 1 :
    5d8f3b1fd7451db4da66368d48aaeacc19619c4ed23cb32f4eb11a8a0a9a62f94add5f1208adcfb0fccc51ec2e4e40f3bfa819129707804143b8cd68bb029d9f7d64312a9e528a7c1c5113e691c93dca81b05bee42be444bf14d25f0c960356cea1ce1efaf516c77dbbe583fbf1e4ba4bed8b791d14f1fca6f93795db45cf6c50e5afc13de18f25dbb73274e09b50527ad32a5ccf328da5412b436664653ec9463595870e1ab586ceefcbb47ac3db2626ff0bfc17524dbc4289c274cf7da51546b1b508c3386159f5b96626067c2cafb7cc69c69bb3600e8fc82f82aca470ea8a619e657e41ad50e84f00637abd52a0853d21143354b112a56f1354f54807f

    and data 2 :
    00fffffffafef9f9fdf7f7f3f9f0f3f6eef1f1e1efe4f1ecdff7d8ece1edcfebdbf2d6dee9bee2d5f4c3edb4eddab3e0dfc9cec0d4c5c8ded598e9c0d0abbaedb4b9d6acc59ebcade19fb2c7bd83b0d4bca684e8a38ae27bcfb4926cdda2a68083dd788ab3a7d35e71f081927eb37f9d5cb3708f74c9667a9a9d6ec79d5b79b82ec05f359b6bc25e8f794a9b52958b2cab11d15ca9531dcf3a8b1149e441524f629d561d554351579cfbeddf45d72c5e0596f4d6d0b9d09ed3b8e144c520ef6a5beeb4703fed094c68df335a4790fbd54c52503cf5649db2145d2b2c6db65b68198b578b8ba965325efaf8035cf80ca985a09c71bccce90f99c1378a409527b7

    generate the same first 248 bits of keystream :

    80dc5f0cbf84ae113ab8dd9bacfb9e9351e95d01e24fed9c18a5722ce69704

    Comment by Eloi Vanderbeken — February 1, 2012 @ 1:11 am

    • Absolutely.

      Chosen key resistance is much harder than related key resistance, and to use a cipher (stream or block) as a hash function, it needs to be strong against both. That’s the summary of this article.

      Comment by Nate Lawson — February 2, 2012 @ 11:56 am

  5. Does the same argument apply to using block ciphers in Davies-Meyer mode, for example AES-hash? (As per https://cryptolux.org/mediawiki/uploads/1/1a/Aes-192-256.pdf, the answer is probably “yes, but practically not yet.”.)

    Comment by Felix — February 13, 2012 @ 5:22 am

    • Block ciphers have generally had related key attack resistance as a design criteria since before AES was chosen. There’s no real reason why stream ciphers can’t have the same criteria, and modern ones might. That’s why I mentioned eStream.

      What I’m saying is that without this being an explicit design criteria, it’s unwise to use them in this way.

      Comment by Nate Lawson — February 24, 2012 @ 3:09 pm


RSS feed for comments on this post.

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 85 other followers