6
$\begingroup$

I suggested to my client to use SHA3 instead of SHA2. I know that SHA3 is based on Keccak algorithm which won the NIST's competition.

I want to explain the structure of sponge functions in very simple terms; does anybody have a simple explanation of cryptographic sponges?

$\endgroup$
3
  • 1
    $\begingroup$ The keccak team have a website, and they kind of have a summary for the sponge construction in this link. $\endgroup$ – Hinton Zsh Aug 6 '20 at 14:10
  • 1
    $\begingroup$ @NezarAboGhanem A period sneaked into you link so I get a 404. This should work. $\endgroup$ – thesquaregroot Aug 6 '20 at 14:24
  • $\begingroup$ Sorry, I didn't realize that. @thesquaregroot thank you for providing the right link. $\endgroup$ – Hinton Zsh Aug 6 '20 at 14:27
6
$\begingroup$

I find that the following image from Wikipedia, though perhaps a bit too technical for your purposes, is still helpful with a little explanation:

Sponge function diagram

Essentially, a function $f$ is used repeatedly in two phases, absorbing and squeezing.

In the absorbing phase, small chunks of the input data are mixed into the beginning of the buffer using XORs (using the variables from the image: $r \oplus P_i$). This updated buffer value is then passed through $f$ and the process continues. With each step a small amount of input date (the bit-length of $r$) is "absorbed" into the buffer using $f$ to semi-randomize the entire buffer.

In the squeezing phase, the same process is repeated but instead of XOR-ing the first $r$ bits with data, they are extracted as the next $r$ bits of the output.

tl;dr: The input is mixed into a buffer in small chucks in between phases where a buffer is randomized, then the buffer is randomized repeatedly while small chucks of it are taken as output.

For more detailed information, see this webpage and this paper by the Keccak team.


It feels worth calling out that your purposes for recommending SHA-3 over SHA-2 may be more important. Does their application of SHA-2 suffer from the possibility of length-extension attacks? Are there other benefits of SHA-3 that you could benefit from? As mentioned here the situation isn't really "move to SHA-3 because it's a better version of SHA-2."

It's possible you're already aware of this, but your client may not be. As such, a simple description of how it works may not really be all they need, even if that's all they're asking for.

$\endgroup$
2
  • $\begingroup$ Could you add few citations (like research papers) for further study? $\endgroup$ – hola Oct 5 '20 at 16:53
  • 1
    $\begingroup$ @hola I've added the link from the comments on the question as well as to the Keccak team's paper on cryptographic sponge functions, which is linked to from the same page. Hopefully that at least gets you started. $\endgroup$ – thesquaregroot Oct 5 '20 at 17:00
2
$\begingroup$

simple explanation

A simple explanation can mean very different things to different people. thesquaregroot's answer tackles this from the "simple but still technical" perspective. For me, simple means (borderline) non-technical.

A sponge construction is named after a sponge. Not per se the animal, but the derived device, that you use to clean a blackboard, or your kitchen counter. The sponge is capable of absorbing liquid and chalk, and afterwards squeezing it out.

Every time you use the sponge to absorb liquid and chalk (data) it will remember this action, it is forever in its history. When a sponge is squeezed, the outcome is a mix of all the sponge's history: the sponge mixes all its former input, usually resulting in a goo-y mash of chalk, with the original inputs unrecognisable.

Another analogue is a perpetual stew: a big stew that's regularly replenished with fresh ingredients. The outcome is never the same, since it depends on the ingredients added, on how many people eat from it, or the season and seasoning, and possibly other factors.


A sponge can be built into many things, among which a hash function: you use the sponge to absorb the input data, and then squeeze out just enough to form a hash.

Or you can use it very neatly for Fiat-Shamir transforms, e.g. https://github.com/dalek-cryptography/merlin/, based on STROBE: the messages to the interactive verifier are absorbed, and the challenges are simply squeezed out.

Or you can use a sponge as a stream cipher: absorb key material and squeeze out as much cipher stream as you need.

At that point, the physical analogy with a sponge is getting difficult: a sponge can only squeeze out as much as was absorbed, while a cryptographic sponge can continue to squeeze out as much as necessary, until the security possibly starts breaking down.


Disclaimer: I've tried to have this answer to focus on intuition, which could impede on technical correctness. If you feel like I should mention some incorrect analogy, please let me know!

$\endgroup$

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.