Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I ask myself some questions about the compression function of SHA-2 (and SHA-1) hash function. Are these compression functions based on a block cipher? I've not found this information on Wiki... So, I think that these compression functions have been designed from scratch, without relying on a block cipher.
What about the compression function of MD5?
Thank you for your answer.
For each of the "MD" functions (MD4, MD5, SHA-1, SHA-256, SHA-512, and derivatives), one can view the compression function as a "tilted block cipher": the message block is used as key, and the function encrypts the current state.
More formally, if you look at MD5, then there is a block cipher $B$ that takes as inputs a 512-bit key and a 128-bit block. The Merkle-Damgård construction then uses a 128-bit running state $r$, initialised to a conventional initial value. The processing of message block $X$ consists in computed $B(X,r)+r$, which becomes the new value for $r$: the current state is encrypted, using the message block as key, and the encryption output is added (in the case of MD5, this is word-wise addition) to the previous state.
If you look at the block cipher details for MD4, MD5 and SHA-1, then you can see that it is a kind of generalised Feistel scheme. In a "normal" Feistel scheme, the input block is split into two halves, and one half is then combined (usually by XOR, but it also works with other reversible combinations like modular addition) with the other half; then the two halves are swapped. In MD5, the input block is split into four words; a function is computed from three words, result being combined with the fourth, and then the words are rotated. Successive SHA functions tend to add a few extra operations but don't change the general structure.
For all the classic MD functions, the inner block cipher was designed "from scratch", i.e. specifically for the hash function. However, in the case of SHA-1 of SHA-256, the block cipher was afterwards awarded a name of its own, SHACAL. I am not aware of any significant deployment of SHACAL as an encryption function.
Similarly, one might want to take an existing block cipher, and turn it into a hash function: this is what Whirlpool is about.
This block cipher / hash functions relationship is subtle, and, altogether, disappointing. Excellent performance of hash functions does not translate to fast encryption: while MD5 can crunch lots of data per second it does so by 512-bit blocks; the underlying block cipher, for the same amount of work, processes only 128 bits, so its bandwidth is going to be only 1/4th of that of MD5. Security is not that good either: most block ciphers are not very strong against related-key attacks because such attacks use an esoteric, impractical setup that does not apply to practical situations; however, when the block cipher is turned into a hash function with the Merkle-Damgård construction, the related-key attacks become collision attacks, and these are very practical. This is why Whirlpool uses a block cipher called W, derived from Rijndael (i.e. AES), but with a much strengthened key schedule: W is believed immune to related-key attacks, and this was done so to make Whirlpool immune to collision attacks.
You might want to investigate the design documents for Skein, a former SHA-3 candidate. Skein is built upon an internal block cipher (dubbed "Threefish"), but it uses it with another structure ("ARX") in which the block cipher is not "tilted", which avoids the trouble with related-key attacks, and allows a better performance mapping between hashing speed and encryption speed.
