Understanding the impact of partitioning oracle attacks on stream ciphers

Yesterday I came across some conversation discussing partitioning oracle attacks, against authenticated stream ciphers like ChaCha20 and Salsa20 with poly1305 for MAC.

As I understand it (though the paper is a little dense), the exploit requires:

• an interactive client/server where messages are encrypted under keys derived from passwords.
• the encryption is "non-committing".
• The server responds indicating if decryption was a success.

Though this discussion raised a number of concerns for me:

1. These multiple key things seem crazy, I always understood symmetric ciphers like ChaCha20-256 required searching a $$2^{256}$$ bit keyspace for a single correct key. I read that you can actually calculate using linear equations approx 200,000 valid keys for decryption. Is this really true, if so we shouldn't consider the bit-strength $$2^{256}$$ even for ECDH agreed on keys should we?

2. In an example local application where one uses say, libsodium's secret box (Xsalsa20+Poly1305) and Argon2 to derive a password and encrypt some file, if this file is stored on a system with no other API or info, is this vulnerable to this attack? (e.g. by calling libsodium and watching if the MAC primitive is successfully verified) or are "offline/stored" files like this safe? i.e. like a padding oracle attack, does this whole thing require that the server knows the correct key, and as such can give away information?

3. Is this only an issue with password-based keys? Doesn't this attack also mean one can reduce the keyspace for ECDHE agreed keys to $$2^{256}/200k$$ when destined for use with ChaCha/Salsa?

• @kelalaka, any thoughts on this one? :) Mar 8, 2021 at 16:08
• I've started to read, however, I need more time. But it seems PAKE is dead? Mar 8, 2021 at 16:15
• Yep that's my take. Mar 8, 2021 at 16:18
• I don't agree on this part: page 3: The adversary has some way of inferring when an encrypted message is successfully received (e.g., due to a reply message or lack thereof). Anonymous boxes are sealed_box'es and you cannot send a message bak. Therefore no partitiion oracle Mar 8, 2021 at 21:30
• huh: known password partitioning with Oracle? If an attacker wishes to compromise the password of a particular user whose password has never been breached, the attack would fail Mar 8, 2021 at 21:35

In short, we can call this a speed-up password search on non-committing AEAD schemes like AES-GCM and ChaCha20-Poly1305 with low oracle calls. If your password has good strength then you are safe.

A committing encryption scheme is a scheme that computationally intractable to find a pair of keys and a ciphertext that decrypts under both keys.

The defined targeted multi-key collision resistance (TMKCR) security by the following game in which for a given target key set $$\mathbb{K} \in \mathcal{K}$$ for a randomized adversary $$\mathcal{A}$$ must produce a nonce $$N^*$$, associated data $$AD^*$$, and a ciphertext $$C^*$$ such that $$\text{AuthDec}_K(N^*,AD^*,C^*) \neq \perp$$ for all $$K \in \mathcal{K}$$. And the advantage is defined as

$$\textbf{Adv}_{\text{AEAD},\mathbb{K}}^{tmk-cr} = \Pr \left[ \textsf{TMKCR}_{\text{AEAD},\mathbb{K}}^\mathcal{A} \right] \implies \textsf{true}$$

As one can see, if the attacker somehow partitions the keyspace then they can reduce the oracle queries this means the attack has less online interaction to be detected.

For example, consider AES-GCM which is not committing, and select two keys and an arbitrary ciphertext then the adversary will look for creating a valid tag so that when during decryption the tag is valid [1]( note; AES-GCM doesn't require decryption to validate the authentication tag, however, separating decryption and tag validation requires to pass on the data, and usually this is not preferred for performance reasons)

The aim is the recovery of a password $$pw$$. Consider that you want to test the membership of two passwords $$S_1^* = \{pw_1,pw_2\}$$. Create two keys $$K_1 = PBKDF(salt,pw_1)$$ and $$K_2 = PBKDF(salt,pw_2)$$ (the salt can be found by sniffing!), now use Dodis et, al's approach [1], construct a ciphertext $$C'$$ with a tag such that it decrypt correctly under the keys $$K_1$$ and $$K_2$$. Now send the splitting value $$\hat{V}$$ to the server. If the server indicates the decryption is successful then $$pw \in S_1^*$$. With iterating this procedure the attacker can find the password in $$|\mathcal{D}|/2 +1$$ queries while the default brute-force requires $$|\mathcal{D}|$$ queries. This attack has degree 2, if $$k$$ degree is possible then this will decrease the query amount substantially.

With SageMath code they were able to find $$k=2^{16}$$ colliding ciphertext very quickly. They simulate their adaptive partitioning oracle attack that constructs splitting ciphertexts of size $$k$$ iteratively for different sets of keys until the oracle returns valid. At this point, the adversary performs a binary search in $$\log k$$ queries to find the secret.

On the left, on the above picture, their success rate, and on the right is the time to generate the $$k$$-way collisions.

It turns out that multi-key collision attack on the Poly1305 is harder than GCM due to the appended 0x01. They are only able to generate at most 10, compare to GCM that reaches 18 degrees. this still gives a factor- of-ten speedup in partitioning oracle attacks

Misuse-resistant schemes like AES-GCM-SIV also applicable to this attack.

Attack on protocols

• OPAQUE

Countermeasures

• Limiting the length of the ciphertext
• Entropy requirements on shared secrets
• Use committing AEAD scheme, there is non in any standards, yet!.
• Use single key Encrypt-then-HMAC ( long live HMAC ) or KMAC.

Questions

1. These multiple key things seem crazy, I always understood symmetric ciphers like ChaCha20-256 required searching a $$2^{256}$$ bit keyspace for a single correct key. I read that you can actually calculate using linear equations approx 200,000 valid keys for decryption. Is this really true, if so we shouldn't consider the bit-strength $$2^{256}$$ even for ECDH agreed on keys should we?

First, a small correction. If the keys are uniformly generated then on average it is not $$2^{256}$$, one bit less. let $$k$$ be the target key that the adversary search with a way to test the correctness of the key. Since each key has $$\Pr[k_i = k] = 1/2^{256}$$ to be correct then the expected number of guess is;

$$\sum_{i=1}^{2^{256}} i \cdot \Pr[k_i = k] = \sum_{i=1}^{2^{256}} i \cdot \frac{1}{2^{256}} = \frac{2^{256} (2^{256} - 1)/2}{2^{256}} = 2^{255} - {\textstyle\frac12}.$$

Of course, during the search, there will be many false positive keys to be eliminated, which doesn't add much to the search time.

As we talked about above, they search for a possible password space $$\mathcal{D}$$ where $$|\mathcal{D}|= 800000$$. The committedness of the scheme enables the attacker to reduce the oracle calls substantially.

If you are using a strong password or generating them with ECDHKE plus KDF call then you will be safe. The point is that humans tend to use bad passwords including cryptographers.

1. In an example local application where one uses say, libsodium's secret box (Xsalsa20+Poly1305) and Argon2 to derive a password and encrypt some file, if this file is stored on a system with no other API or info, is this vulnerable to this attack? (e.g. by calling libsodium and watching if the MAC primitive is successfully verified) or are "offline/stored" files like this safe? i.e. like a padding oracle attack, does this whole thing require that the server knows the correct key, and as such can give away information?

This attack requires an oracle that returns a value like the padding oracle attacks. If there is no return, then there is not a test even for a normal online password guessing attack $$k=1$$. They have looked at the libraries the use OPAQUE and AEAD schemes and saw that some of them are not applicable. See the emits error column. The attack on Shadowsocks was interesting since the attacker had a side channel to test.

1. Is this only an issue with password-based keys? Doesn't this attack also mean one can reduce the keyspace for ECDHE agreed keys to $$2^{256}/200k$$, when destined for use with ChaCha/Salsa?

If the keys are uniform randomly generated then the attack will not work. It is a password search.

• I hope I've given the gist of the work. Mar 9, 2021 at 11:43
• yes this is a fantastic answer, thank you. - to confirm my understanding, it sounds like this doesn't affect a solution like the one I raise in "concern 2)" above, where there is only a file encrypted via salsa20+poly1305 and a strong password via argon, as you ALSO need any oracle that knows the key and can respond to attack like this... and secondly, it sounds like we should still consider Salsa/chacha keyspace/bit strength to be 2^256, this multi key (non-commiting) issue doesn't reduce the keyspace? - do I have that right? Mar 9, 2021 at 12:43
• i.e. just confirming my understanding of your answer in terms of concern 2 and 3 I raised above... thus not a serious impact here Mar 9, 2021 at 12:45
• Yes. I'll go over them when I get to pc. Strong password is the countermeasure. Also, in the article they show a table that the attack fail since the oracle doesn't return anything at all. This is similar to padding oracle where only plaintext is revealed here the key due to the password set. The attack reduces the oracle call for testing the password. It is not a key search, it is password search. As you can see they test the passwords with partitioning. Mar 9, 2021 at 12:49
• @Woodstock updated the answer, let me know if I miss a point on your questions. Mar 9, 2021 at 13:51