10
$\begingroup$

Next to the traditional MD5 and SHA-1, other hashing algorithms exist based on symmetric encryption algorithms. An example is the Matyas–Meyer–Oseas construction.

What are the advantages/disadvantages of this approach instead of using traditional hash functions, such as MD5 and SHA-1?

$\endgroup$

3 Answers 3

13
$\begingroup$

The disadvantage of this approach is that block ciphers are not necessarily designed with this goal in mind. Specifically, AES has related-key problems, and DES completely breaks in Davies-Meyer. In general, block ciphers are not necessarily ideal ciphers and should be used as intended which is as pseudorandom permutations. In contrast, SHA256 and the like were constructed specifically with the collision resistance goal in mind. It doesn't mean that they achieve this goal, but they have a far better chance.

$\endgroup$
7
$\begingroup$

What are the advantages/disadvantages of this approach instead of using traditional hash functions, such as MD5 and SHA-1?

Those are not precisely alternative approaches. MD5 and SHA-1 use Davies-Meyer construction with certain block ciphers that do not see much use on their own (SHACAL has seen some). So in a way you are already doing that if you use MD5 or SHA-1 (which you should move away from!) or even SHA-2.

In addition to the extra requirements these hash function modes place on the block cipher as Yehuda Lindell mentions, the size of current block ciphers is also problematic.

AES, specifically, only has a 128-bit block size. That means in Davies–Meyer it only gives you a 128-bit hash, which has 64-bit collision resistance. Speed might also suffer. AES has a maximum key size of 256 bits. That means a Davies–Meyer hash with at most a 256-bit block size. Assuming it is about as fast as SHA-1 (reasonably close in software) it will run half as fast – with long inputs.

In Matyas–Meyer–Oseas the block size of the cipher is equal to both the block size and the output size of the resulting hash. So it is even worse with AES.

Some less used block ciphers (like SHACAL!) would do better of course.

$\endgroup$
-1
$\begingroup$

Matyas–Meyer–Oseas one-way compression method is a cryptographic algorithm based in block ciphers. The difference is that the subkeys of each round are calculated differently unlike normal block ciphers were you specify the key before data encryption. It can be seen as a special MAC algorithm.

The advantages of this algorithm compared to SHA-1 are computational complexity when trying to get a hash collision.

Theoretically SHA-1 needs $2^{61}$ operations for a full collision but Matyas–Meyer–Oseas needs $k \cdot 2^{\frac{n}{2}+1}+2^{n-k+1}$

Please take a closer look at this paper where the complexity of breaking Matyas-Meyer-Oseas is discussed in full detail.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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