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

Presented at Black Hat USA 2020 Virtual, Aug. 6, 2020, 12:30 p.m. (40 minutes)

<p><span style="font-size: 10pt;" data-mce-style="font-size: 10pt;">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.</span></p><p><span style="font-size: 10pt;" data-mce-style="font-size: 10pt;">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.</span></p><p><span style="font-size: 10pt;" data-mce-style="font-size: 10pt;">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.</span></p><p><span style="background-color: initial; font-size: 10pt;" data-mce-style="background-color: initial; font-size: 10pt;">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. <span>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.</span></span><br></p>

Presenters:

  • Paul Grubbs - Researcher, Cornell University
    Paul Grubbs is a PhD candidate in Computer Science at Cornell University. His research is in applied cryptography and security, focusing mainly on interesting questions that arise at the boundary between cryptography and systems. He uses theoretical foundations from cryptography and other fields, empirical methods, and practical knowledge of real systems to design, analyze, and build solutions to security problems. He is the recipient of a 2017 NSF Graduate Research Fellowship.

Links:

Similar Presentations: