Partitioning Oracle Attacks

This is so great.

Assume this fact pattern: an interactive client-server cryptosystem where messages are encrypted under keys derived from passwords, AND (1) the server will reveal whether decryption of a trial message succeeded (super common!) AND (2) the encryption scheme is "non-committing", meaning roughly that the output of the encryption construction doesn't encode the specific key used (this is the norm for mainstream ciphers).

Well, now you have a problem. If you can create a message that decrypts properly under 2 different (password-derived) keys, you can "guess" two passwords per query to the system; that's obvious. But you're not limited to 2. For instance, AES-GCM, the most popular AEAD in the industry, isn't key-committing, and you can with a laptop and SageMath create a ciphertext that encrypts validly under (wait for it) 200k different known keys, by solving a system of linear equations. (It's about 4M long).

In a sort of general attack setting, you can already see how this is going to work: you can iterate over messages that guess 200k passwords at a time. When you get a hit, you do a search, partitioning and re-partitioning the space of possible passwords until you discover the right one.

The paper uses this approach to break the Shadowsocks circumvention proxy, which uses GCM, and where condition (1) is met because successful serverside decryption opens a listening UDP socket for 5 minutes that you can just scan for.