Are sponges inherently inefficient when compared to other constructions?

Question

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.

Answer 1

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.

Answer 2

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