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
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
- 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.
- 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.
- 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.
