3
$\begingroup$

A sponge has by definition 'wasted' operations (the part of the state which always remains private but goes through all the ops of the permutation).

In return for that waste you get a MAC at the end - some claim that it's for free for some reason.

But the ops wasted on the hidden state cannot compete with something like Poly1305.

So the question is can you have a permutation such that it would be efficient on modern hardware to use it as sponge versus using it in a ChaCha (half-XEX) fashion accompanied by Poly1305? Or can you have an AEAD sponge construction that would allow a secure full state involvement?

Take for example the Keccak-p permutation (1600 bit state).

It would be more efficient to replace the ChaCha permutation in ChaCha20-Poly1305 with Keccak than to use Keccak in a sponge/duplex construction for AEAD.

Sponges are also vulnerable to DDoS because you have to go through the entire ciphertext before rejecting on the tag at the very end. Poly1305 will be an order of magnitude or more faster in rejecting.

$\endgroup$
9
  • 2
    $\begingroup$ One difference is that the sponge construction and Carter-Wegman MACs (such as Poly1305) have different security goals. A sponge construction really is used as a hash (that is, has collision resistance), while Poly1305 cannot be used that way. Given that sponge constructions have higher security goals, it's not surprising that they're more expensive. $\endgroup$
    – poncho
    Oct 12, 2023 at 1:28
  • $\begingroup$ sure, but in an AEAD scenario that doesn't really matter. And when comparing a sponge to a MD construction hash the same problem persists - wasted operations in the sponge. Typically the expansion operations used for msg blocks are very cheap. Sponges are very elegant constructions but it seems like they are doomed to inferior performance? $\endgroup$ Oct 12, 2023 at 1:33
  • 2
    $\begingroup$ Well, for MAC performance, it's hard to beat a well-designed CW construction. There, the message processing part doesn't need any cryptographic properties (they need to meet some almost-universal properties, but that's easier, and also provable); so they can use an efficient algorithm to process message blocks (such as Poly1305's 'add-and-multiply-mod-$2^{130}−5$); a handful of multiplies is quite fast on high-end processors... $\endgroup$
    – poncho
    Oct 12, 2023 at 2:16
  • 1
    $\begingroup$ Note that for CTR mode you don't need to keep any state between the blocks other than the counter. So I agree with poncho that the wider sponge operation to forward the capacity is weighted against the MAC construction. Where sponges might come into place is when HW support is added because in that case you can do about anything with the sponge other than unlimited signatures and asymmetric key encapsulation for encryption (for which we could use CRYSTALS in a PQC world). $\endgroup$
    – Maarten Bodewes
    Oct 12, 2023 at 9:12
  • $\begingroup$ @MaartenBodewes Once sponge permutations are added to HW what's stopping you from getting even better performance by using the permutation with Poly1305 the way ChaCha does? That's the root of the question. $\endgroup$ Oct 12, 2023 at 14:37

2 Answers 2

7
$\begingroup$

Are sponges inherently inefficient when compared to other constructions?

In a way, yes. The sponge/duplex is serial rather than parallelisable. However, there are ways of making permutation-based cryptography parallel, like Farfalle, NORX, and AEGIS-128X/256X.

Furthermore, as mentioned by @Maarten Bodewes, there is increasingly SHA-3 hardware support, which boosts SHAKE based AEAD scheme performance, for example. Similarly, the hardware accelerated AES round function has been used for very efficient schemes in a way similar to the duplex construction. As an example, AEGIS-128X/256X is significantly faster than AES-OCB, AES-GCM, and ChaCha20-Poly1305 assuming the right hardware support. So are the non-parallelisable versions (AEGIS-128L and AEGIS-256), highlighting how duplex-style algorithms can be fast.

You also can't ignore the positives of the sponge/duplex constructions, such as ease of implementation, use case flexibility despite one primitive, considerable research, and so on. It has been the basis of many CAESAR and NIST LWC competition submissions, indicating a shift to permutation-based cryptography. If its performance was a problem, it would not have been this successful.

In return for that waste you get a MAC at the end - some claim that it's for free for some reason.

The reason this is 'for free' is because a sponge-based AEAD scheme is one-pass rather than two-pass like generic composition. In other words, you don't have to process the message again.

AEADs like AES-GCM and ChaCha20-Poly1305 are sometimes called 1.5-pass because even though they do Encrypt-then-MAC, the MAC computation is faster than collision-resistant MACs like HMAC.

But the ops wasted on the hidden state cannot compete with something like Poly1305.

This is a good thing. Poly1305 isn't collision resistant like the sponge/duplex, which is required for AEAD commitment. What people need to understand is that users of AEAD schemes intuitively expect them to have this property. Without it, vulnerabilities arise in protocols. If the aim is security by default/preventing misuse, all future AEAD schemes should be fully committing. The duplex is the most obvious and tried/tested way of doing this besides reverting to generic composition.

You can think of commitment as analogous to misuse resistance, except you would not intuitively expect a nonce-based AEAD scheme to be misuse-resistant. There are warnings about reusing a nonce everywhere. By contrast, nobody warns you about a lack of commitment and relatively few people understand when a protocol is vulnerable. Sure, there are 'patches' to existing AEAD schemes, but they're clunky (e.g. they increase ciphertext expansion or require replacing the AEAD tag, may produce timing side-channels during decryption, etc) or modify the scheme itself.

Or can you have an AEAD sponge construction that would allow a secure full state involvement?

Again, full-state absorption prevents AEAD commitment, what should be a fundamental security property. If you're still unconvinced that this is a problem, ask yourself why NIST wanted to discuss it in the third workshop on block cipher modes, with 4 accepted papers on the topic. Since then, there have been numerous recent publications, adding to the literature starting in 2017 but only recently being taken more seriously.

The key takeaway is that whilst performance is great, it should not be the main goal. Cryptography is about security. Performance at the expense of meaningful security causes problems.

$\endgroup$
9
  • $\begingroup$ You list ciphers which have fast permutations due to hw acceleration and are used in a sponge construction. But is it not the case that you can take those same permutations and use them with a half-XEX construction (ex. ChaCha) and obtain even greater performance by pairing them with Poly1305? $\endgroup$ Oct 13, 2023 at 1:50
  • $\begingroup$ How are you coming to that conclusion? That's not necessarily the case, and there are faster MACs than Poly1305. If you have a large state and rate, you can process lots of data at a time whilst getting authentication 'for free' as explained, avoiding a second pass over the message. AES round function designs are more complicated. You also don't seem to be acknowledging the issue of commitment, which is exactly why I keep mentioning it. You don't want to be using Poly1305 or similar in a new design. $\endgroup$ Oct 13, 2023 at 14:25
  • $\begingroup$ One of the papers you linked mentions that they fixed the commitment issue by simply including the nonce in the Poly1305 MAC. Is that not sufficient? I tried an experiment where I used the BLAKE permutation as a sponge hash vs. MD hash, performance was significantly degraded. How can it be otherwise? $\endgroup$ Oct 13, 2023 at 15:16
  • $\begingroup$ Which paper? That doesn't work because Poly1305 isn't collision resistant, and that wouldn't be fully committing even if it did work. BLAKE wasn't designed for use in the sponge, and you're deviating between discussion of the sponge/hashing and the duplex/AEADs, which are completely different use cases. That's also one algorithm/experiment with presumably one set of hardware, so you cannot generalise that every sponge/duplex is slower than the alternatives. I suggest you look at benchmarks on eBACS and in papers/competition reports. $\endgroup$ Oct 13, 2023 at 15:46
  • $\begingroup$ "Actually Good Encryption? Confusing Users by Changing Nonces" You can also rely on preimage resistance by including both the key and the nonce in the MAC. BLAKE is not the exception, you can pick any permutation used as a sponge and convert it into a half-XEX + Poly1305 1.5 pass construction and performance will increase vs. the sponge construction. $\endgroup$ Oct 13, 2023 at 18:18
1
$\begingroup$

Sponges are very versatile and simple with strong security. They are usually not optimal for each case performance-wise. Biggest performance issue is they are sequential (some are configurable parallel like NORX).

Comparing Sponges to ChaCha20-Poly1305 is unfair since Sponge has $2^{c/2}$ (where $c$ would be usually $2k$) all-around security while ChaCha20-Poly1305 is limited to $2^{64}$ outputs per key/nonce. Sponge is more resilient in nonce reuse case. Sponge is also fully committing which has already been mentioned.

Capacity in sponge could be considered as kind of tweak/key schedule rather than wasting operations. Although key schedule can be pre-computed, efficient parallel modes typically also require tweak. All that can make sponge more efficient when processing is limited to sequential and easier to analyze.

Take a look at SpoC which makes required capacity smaller by masking it.

Even full rate AEAD is possible with additional state and more complex mode: Designing Full-Rate Sponge based AEAD modes

$\endgroup$

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.