4
$\begingroup$

I know that sponge functions are different in many ways. Yet I'd like to know if SHA-3 can nonetheless be said to be "based", if not simply "inspired", by the Merkle-Damgård construction. To be more precise it seems to be a wide-pipe construction followed by an entropy collection procedure.

Is it accurate to say that SHA-3 (keccak) is based on Merkle-Damgard?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Both are iterated hash functions, and that's pretty much where the similarity ends. $\endgroup$
    – CodesInChaos
    Commented Apr 6, 2017 at 18:42

2 Answers 2

Reset to default
3
$\begingroup$

I have to agree that they are similar aren't they? Block after block with a chain value /state passed along. The two constructions are show below...

md

sponge

If they were substantially different, one would look like

other type

Or a crocodile. At a certain (reasonable) level of abstraction, they both produce a hash value by successively updating a state passed from message block to message block. A permutation isn't semantically a million miles away from a compression function, especially if you wiggle about the location of the XOR operator. With the XOR, they both feature a compression function. It's not like saying a plane is a motorbike, but rather a jet is derived from a propeller plane. Sure there are unique minor implementation issues, but the substantive architecture remains constant. It's probably true to say that Keccak was more than "inspired" by Merkle-Damgård. And in the hash mode, Keccak outputs a hash.

Where it gets more difficult to equate the two is the alternate mode of random number generator. After the MD calculates the final hash, it stops. On the other hand, the sponge can infinitely iterate itself producing pseudo random output. The only way I can get MD to do this is to add a counter as additional message blocks and repeatedly output the updated state. So still doable.

I think that if they both look similar architecturally, and both produce similar outputs hash wise and PRNG wise, one has to conclude that they're properly similar. It's called the Duck Test.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your PRNG construction seems broken (at least, if you use for later steps the results which were already output – then an adversary can repeat it). You need to hide the intermediary input. $\endgroup$
    – Paŭlo Ebermann
    Commented Jan 13, 2018 at 16:22
16
$\begingroup$

No. That is about as accurate as saying that airplanes are based on motorcycles, because they both have engines.

In MD, the input to the hash is converted to a key, which is used by a block cipher to encrypt the initial value, then the entire encrypted value is the hash.

In a sponge based hash, the input is XOR'd into the initial value, then the entire value is ran trough a permutation, and finally a small piece of the permuted value is used as the hash

Improve this answer
$\endgroup$
0

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.