Hunting Invisible Salamanders: Cryptographic (in)Security with Attacker-Controlled Keys

The talk discusses the insecurity of authenticated encryption (AE) schemes like Galois/Counter Mode (GCM) when used in settings where the attacker knows or can guess the key. The lack of committing property in modern AE schemes makes them non-committing and insecure in such settings. The talk demonstrates attacks that result from improper use of non-committing AE and recommends committing AE schemes that can be used today.

• AE is a widely used cryptographic primitive on the internet
• AE is often used for two parties who want to communicate securely to first agree on a random symmetric key and then encrypt a plaintext with it and send it to the receiver
• Modern AE schemes lack the committing property and are insecure in settings where the attacker knows or can guess the key
• Improper use of non-committing AE can result in attacks like bypassing message franking protocol and partitioning oracle attacks
• Committing AE schemes can be built using the primitives from common libraries like OpenSSL
• Committing AE schemes can be less efficient than non-committing AE
• Committing AE is not needed unless attacker-controlled keys are part of the threat model

The talk gives an example of how an adversary can partition the space of possible keys into sets that are bigger than one by sending a ciphertext that decrypts under more than one key. This allows the adversary to check more than one guess for each ciphertext it sends, resulting in exponential speedups over online brute-force attacks when low-entropy secrets like passwords are used to derive AE keys.

Deploying new cryptography often means using existing building blocks in new ways. A prime example is authenticated encryption (AE). Until recently, AE schemes like Galois/Counter Mode (GCM) were mostly used in settings where key exchange first established a hidden, random encryption key (think TLS or IPSec). Increasingly, though, schemes like GCM are also being used in settings where the attacker knows, or can guess, the key. This attack setting is the subject of my talk. It is aimed at security professionals who design, implement, and deploy cryptography, but will be accessible to a general security audience.My talk will have three main parts. First, I will explain our attack setting, specifically where, why, and how a real attacker could know (or just have a good guess about) an AE encryption key. I’ll go over a few examples, including password-based AE, and discuss the committing security property AE must have in this setting. Intuitively, if an AE is committing, it is hard to find a ciphertext that decrypts correctly under more than one key.Next, I will show that, surprisingly, modern AE schemes lack this committing property (they are non-committing) and are insecure in our setting. For GCM, GCM-SIV, or any Poly1305-based scheme, it is easy to find ciphertexts that decrypt correctly under multiple keys. I will walk through a simple two-key example with GCM and outline how to go from two to hundreds of thousands of keys with a little bit of math.Finally, I will demonstrate attacks that result from improper use of non-committing AE. I’ll first show that with the two-key GCM example above, any Facebook user could have bypassed the “message franking” protocol for reporting abusive content in Secret Conversations and sent unreportable abusive messages. Then I will introduce partitioning oracles, a new class of decryption error oracle (akin to padding oracles) on non-committing AE that can recover keys (instead of plaintext). Partitioning oracle attacks can lead to exponential speedups over online brute-force attacks when low-entropy secrets like passwords are used to derive AE keys. They arise in many places: for example, I will show that when the OPAQUE password-authenticated key exchange protocol is implemented incorrectly, partitioning oracle attacks result. I’ll conclude with guidance on how to recognize when committing AE is needed. I’ll also recommend committing AE schemes that can be used today.