43

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?

8
  • 4
    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
  • 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
  • It's very important that the function receives an infinite set of bits and produces a finite length of bits Feb 10, 2018 at 2:02
  • 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

2 Answers 2

26

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
  • 6
    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, 2022 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, 2022 at 2:38
0

Cryptographic hash functions, in general, take an arbitrary length input and produce a fixed-length output, known as the hash.

Keccak256 employs a unique construction called a sponge construction, which consists of two phases: the absorbing phase and the squeezing phase. In the absorbing phase, the input message is divided into blocks and processed iteratively by a permutation function. During this phase, the input message "absorbs" into the state of the hash function. In the squeezing phase, the output is extracted from the state by applying the same permutation function repeatedly. This process continues until the desired output length is reached.

Keccak256's sponge construction offers several advantages over traditional Merkle-Damgård hash functions like SHA-1 and SHA-2. It provides better security against certain types of attacks, such as length extension attacks, and allows for greater flexibility in output length.

https://www.nervos.org/knowledge-base/what_is_keccak256_(explainCKBot)

The introduction of the sponge construction aimed to provide a practical framework for expressing security claims in cryptographic protocols.

While hash functions are typically proven secure in the random oracle model, where a hash function acts as a random oracle, real-world hash functions operate with finite memory and can have internal collisions.

Utilizing the sponge construction with a random permutation creates a random sponge, which closely emulates a random oracle's strength, except for limitations related to finite memory. Random sponges are effectively used as substitutes for random oracles in verifying security assertions.

https://keccak.team/sponge_duplex.html

1

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.