12

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?

e-sushi
  • 17,891
  • 12
  • 83
  • 229
prakharjain
  • 303
  • 1
  • 3
  • 10
  • 1
    This question is too broad. There are many introductory resources about Keccak online. – fkraiem Feb 04 '16 at 15:50
  • 4
    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. – otus Feb 04 '16 at 16:24
  • 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. – prakharjain Feb 04 '16 at 16:35
  • Ok, so we expect something about sponge construction here, length extension attacks and SHAKE at the least. – Maarten Bodewes Feb 04 '16 at 18:44
  • 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 [tag:sha-1], [tag:sha-256], and [tag: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. – e-sushi Feb 04 '16 at 19:22
  • Actually, I am reading a book - Cryptography and Network Security - William Stallings. I have not read all articles here. I just posted because I didn't found any alike question.

    Wanted some better explanation of the article from experts here. I will edit the questions to details later.

     – prakharjain Feb 04 '16 at 20:49
  • If you are happy with an answer, please click on the tick mark. Or else, specify what more is needed. Just don't sit idle without responding to answers. –  Feb 11 '16 at 11:36
  • sorry, I was expecting a better explanation and was busy lately due to exams. anyways i accepted your answer. – prakharjain Feb 11 '16 at 15:37

3 Answers3

14

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).

Thomas Pornin
  • 86,974
  • 16
  • 242
  • 314
  • I would put state truncation and shift operators in the similarities column, it's the sha2 fixed points that scare me – Q-Club Apr 28 '18 at 00:07
  • 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. – Maarten Bodewes Apr 28 '18 at 00:57
11

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.

e-sushi
  • 17,891
  • 12
  • 83
  • 229
  • 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. – perror Feb 04 '16 at 20:04
  • 1
    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. – Maarten Bodewes Feb 05 '16 at 11:59
  • Note also a core difference: The sponge construction relies on a permutation whereas Merkle-Damgard relies on a one-way collision-resistant compression function. – SEJPM Feb 05 '16 at 12:22
8

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.

poncho
  • 147,019
  • 11
  • 229
  • 360
  • 1
    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. – Maarten Bodewes Feb 05 '16 at 00:46
  • 1
    @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. – SEJPM Feb 05 '16 at 12:28