Turning a cipher into a hashing function This is theoretical question. I'd like to know if it's possible (and what are eventually the consequences), not that I'm going to do it in one of my projects. ;)

The first hashing functions created were based on a symmetric cipher (just like the first Unix crypt was based on DES). The idea was simple. Use the password as key to encode a constant.

I'd like to know if it's still possible to convert any modern symmetric cipher into a hashing function (and second question: into a cryptographic hashing function). Is it possible (easier) to guess the key, when you have an encoded and decoded messages?
Not only we can turn block ciphers into hash functions, but we do.

The usual hash functions (MD5, SHA-1, SHA-256...) use the Merkle-Damgård construction which relies on a block cipher E. A running state r is initialized to a conventional value. Then the input data is split into a number of chunks, each chunk being used as key for the block cipher: r is encrypted with E, using the current chunk as key; the result is added (or XORed) with r, and this yields the new state r for the next chunk. Last obtained state is the hash output.

If you want to apply the Merkle-Damgård construction on a standard block cipher such as AES, you will run into the following problems:


The size of the internal state is the size of the hash output, and it is also the block size of the cipher. AES is a 128-bit block cipher, leading to a 128-bit output, which is a bit too small with regards to today's technology (it would imply resistance to collisions only up to 264 evaluations, which is expensive but doable).
The MD construction exercises unusual features of the block cipher. In particular, the input data is used as key, and collision attacks (a major concern for hash functions) correspond to related-key attacks on the underlying cipher. Related-key attacks are not a problem for block ciphers when they are used for what they were designed to, i.e. encryption. AES is known to have slight weaknesses with regards to related keys but this is not a problem for encryption. It will become a problem if AES is used as building block in a MD-based hash function. (Resistance to related-key attacks was not a design criterion of the AES competition.)


Therefore, MD-based hash function use custom block ciphers which are designed to be especially robust against related-key attacks (or, at least, so we hope for). In the case of SHA-1, the inner block cipher was blessed with a name of its own, SHACAL.

Another example is Whirlpool, based on the block cipher "W", an AES derivative with a larger block size (512 bits) and a revamped key schedule to make it much stronger against related keys (and, unfortunately, it makes it much slower too). This addresses the problems explained above. (Whirlpool does not use the Merkle-Damgård construction, but Miyaguchi-Preneel, a distinct construction which has its own quirks.)

Yet another example is Skein, one of the SHA-3 candidates. It builds over an internal block cipher called Threefish; again, a block cipher with large blocks (512 bits in the "standard" Skein, extensible to 1024 bits).



A few SHA-3 candidates reused not the AES, but parts of the AES; in particular, ECHO and SHAvite-3. The idea was to be able to optimize the hash function with hardware meant to speed up AES, especially the AES-NI opcodes of recent x86 processors. But that's not reusing the block cipher itself.

What must be remembered is that building a hash function out of a block cipher is hard. This is not the same usage context. A fundamental difference is that a block cipher has a key which the attacker does not know (and tries to guess), while a hash function has no secret (when trying to build a collision, the attacker knows everything about every operation in the hash function).