36

As the Ethereum platform relies on the Keccak256 hash algorithm, I'd like to get a better understanding of it.

My rough understanding is something like this:

a function accepting a finite set of bits into a giant imaginary rubik's cube which is then shunted about in a specific way. A subset of 256 bits are then returned. The function has the property that a change to a single input bit causes the output to change in an unpredictable way.

Is the above approximately true? You might see where I got the rubik's cube idea from if you look at Figure 1 here (I think this is the right spec).

There's also this, which I've read through, but it has not really soaked in.

How does the Keccak256 hash function work?

9
  • 3
    This might be too broad. Found something that might help: slideshare.net/RajeevVerma14/keccakpptx (and it does have cube diagrams).
    – eth
    Jan 21, 2017 at 22:45
  • @eth thanks, shall I delete?
    – Lee
    Jan 21, 2017 at 22:46
  • I think keep it and we can let the community vote and provide feedback (there might also be ways to edit it that might improve the question but I don't know enough so haven't upvoted), or someone might write a really good answer that you're looking for.
    – eth
    Jan 21, 2017 at 22:49
  • @eth I'll perhaps remove that last two questions... let's see
    – Lee
    Jan 21, 2017 at 22:54
  • 7
    The sponge construction is the core. You divide the input into n blocks P0...Pn-1 (padding) and then starting with a block of zeros XOR the first formed block P0 and apply a permutation function f, the output of this function is passed to the next step that uses P1 and repeats until you have used all the blocks up to Pn-1. At this step, the data has been absorbed. You "squeeze" it by selecting a portion of the last state of the system and applying the function f to it until you obtain the desired number of bits in the output. This is very oversimplified but is the general idea.
    – Jaime
    Mar 29, 2018 at 20:17

1 Answer 1

22

Keccak is nice that it has arbitrary inputs and an infinite input space. This enables one to "make a hash" of a super large file where each input causes the internal state to scramble up some more. The hash should entirely change if a single bit of data in the source is different - unlike say a CRC32, or a checksum. It means your password could be a million chars long maybe. It's stored on disk as a hash, much smaller in size.

Regarding Keccak, it uses a "Sponge Construction" lord knows what that is read up on it here: https://keccak.team/keccak_specs_summary.html If I understand it's a permutation chosen from a set of seven Keccak permutations, denoted I assume by reference to their bit depths as b∈{25,50,100,200,400,800,1600}.

The state is organized as an array of 5×5 lanes, each of length w∈{1,2,4,8,16,32,64} and 25 cells deep. When implemented on a 64-bit processor, a lane of Keccak can be represented as a tidy 64-bit CPU word.

Finally, to even entertain the thought of similar input causing collisions, you have to imagine this data traversing from base 25, through base 50, up to 1600 and back. Smart money is on this being quite very resistant to collisions (it's design goal?).

2
  • 4
    Minor comments: Not every hash has an infinite input space, many hash algorithms cannot take inputs longer than 2^64 bits. However I believe Keccak indeed allows inputs of arbitrary lengths. Second, a single input bit flip changing the entire output is also true (and important) for checksums. The difference between checksums and hashes is the reversibility.
    – jlh
    Jan 9 at 14:09
  • 1
    @jlh cheers I have updated based on your comment. I think the other ones would break the 2^64 bits chunk up and keep going no? I guess we are talking filesize here interesting point.
    – Tomachi
    Mar 16 at 2:38

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.