11
$\begingroup$

SHA-1 and SHA-2 share the same structure and mathematical operation as their predecessors - SHA-0 and MD5. Both SHA-0 and MD5 have been broken. This is one of the main reasons why SHA-1 is considered insecure and is being phased out for SHA-2.

NIST announced in 2007 a competition to produce the next generation NIST hash function: SHA-3.

What is the major difference in structure and mathematical operation between the previous SHA-1 and SHA-2 functions and SHA-3?

$\endgroup$
  • 1
    $\begingroup$ This question is too broad. There are many introductory resources about Keccak online. $\endgroup$ – fkraiem Feb 4 '16 at 15:50
  • 4
    $\begingroup$ Not sure I agree. The basic difference can be broken down to the high level construction chosen and the mathematical operations used in the round function. A good answer would not be long, especially if it linked to other questions/resources for the specifics. $\endgroup$ – otus Feb 4 '16 at 16:24
  • $\begingroup$ I agree the question is too broad if you want to know about Keccak but I have not found much explanation with difference between SHA-3(Keccak) and previous generations SHAs. $\endgroup$ – prakharjain Feb 4 '16 at 16:35
  • $\begingroup$ Ok, so we expect something about sponge construction here, length extension attacks and SHAKE at the least. $\endgroup$ – Maarten Bodewes Feb 4 '16 at 18:44
  • $\begingroup$ Let’s simply try to get rid of some of the broadness of your question… could you please clarify what research you’ve done? See, we do expect you to do a significant amount of research before asking here, including searching this site for sha-1, sha-256, and sha-3 that might shed light on your question. At worst it will help you frame a better question; at best it might even answer it. $\endgroup$ – e-sushi Feb 4 '16 at 19:22
10
$\begingroup$

The difference is: All SHA-0, 1 & 2 and MD5 come under a class of algorithm called Merkle–Damgård construction, while SHA-3 falls under Sponge functions.

Merkle–Damgård construction is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. Merkle–Damgård construction

And, Sponge functions are a class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length.

Sponge Function

The main reason for the change is because a number of attacks were discovered for its predecessors, there was a fear that the very secure SHA-2 would be broken soon. So, to avoid that they chose Keccak as it was completely different from existing SHA algorithms and the AES.

$\endgroup$
  • $\begingroup$ Not to mention that MD5 (which was clearly broken) was also based on the Merkle-Damgård scheme). So, they were real suspicions that flaws would be found soon. $\endgroup$ – perror Feb 4 '16 at 20:04
  • 1
    $\begingroup$ This is indeed the reason why the SHA-3 competition was started. I'm not sure that this is the main reason why Keccak was chosen though, and I did at least follow the mailinglist. $\endgroup$ – Maarten Bodewes Feb 5 '16 at 11:59
  • $\begingroup$ Note also a core difference: The sponge construction relies on a permutation whereas Merkle-Damgard relies on a one-way collision-resistant compression function. $\endgroup$ – SEJPM Feb 5 '16 at 12:22
14
$\begingroup$

They are all hash functions. Apart from that, they are structurally quite different. The SHA family (SHA-0, SHA-1, and the SHA-2 functions such as SHA-256 and SHA-512) use the Merkle-Damgård construction, around an internal permutation which happens to be an extended Feistel network. Low-level primitives include boolean bitwise operations, and addition over 32-bit or 64-bit integers.

In SHA3, the structure is that of a sponge function, which is quite different. Moreover, the inner permutation is not a Feistel network; low-level primitives are boolean bitwise operations over 64-bit words, but not additions. This avoidance of operations that involve carry propagation helps a lot with performance on hardware implementations (FPGA, ASIC).

$\endgroup$
  • $\begingroup$ I would put state truncation and shift operators in the similarities column, it's the sha2 fixed points that scare me $\endgroup$ – Q-Club Apr 28 '18 at 0:07
  • $\begingroup$ The output sizes are identical (by design) to SHA-2. SHA-3 was created as a drop in replacement after all; it just differs internally. $\endgroup$ – Maarten Bodewes Apr 28 '18 at 0:57
8
$\begingroup$

While Switch is right about the difference between Merkle–Damgård and Sponge constructions, I don't believe he is correct as to NIST's reasoning.

I happened to talk to a NIST cryptographer (John Kelsey) about this. He indicated that they selected Keccak not because they distrust the SHA-2 design (Merkle–Damgård is provably secure if the compression function is collision-resistant, and we have no reason to doubt the SHA-2 compression functions). And it's not to get greater crypto-diversity (even though it does that; the designs of SHA-2 and SHA-3 are quite different). Instead, John indicated that the most attractive thing they saw in Keccak was its flexibility.

While the sponge construction can be used to create a hash function, it can also be used to create other things, such as an XOF (Extensible Output Function; essentially as hash function with an arbitrary length output). NIST has standardized SHAKE-128 and SHAKE-256 as SHA-3 based XOF's. In addition, you can do other things with a sponge construction; it's quite possible that NIST will standardize those usages as well.

$\endgroup$
  • 1
    $\begingroup$ That's a bit strange. Skein seems to have this kind of flexibility as well, and that's certainly Merkle–Damgård. Furthermore, as it contains a 256 bit tweakable block cipher, it would be very useful to create a complete symmetric cryptosystem. That's why I supported it anyway. There are of course other considerations such as speed as well though. $\endgroup$ – Maarten Bodewes Feb 5 '16 at 0:46
  • 1
    $\begingroup$ @MaartenBodewes, while Skein is fancy in design and implementation, you can actually do (nearly) everything that is possible with Skein equally well with Keccak and some other things as well (i.e. you can use the sponge for AE) and Keccak profited much more from the standardization because Intel will sooner or later make SHA-3 extensions (hopefully) and in hardware Keccak should beat Skein in speed, because of the bit permutations. $\endgroup$ – SEJPM Feb 5 '16 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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