UC San Diego

We study authenticated encryption (AE) schemes, or symmetric cryptographic protocols designed to protect both the privacy and the integrity of digital communications. When the AE schemes that we propose or study are secure, we prove so using the modern cryptography approach of practice-oriented provable security; this approach involves formally defining what it means for an AE scheme to be secure, and then deriving proofs of security via reductions from the security of the construction's underlying components. When we find that an AE scheme is insecure, we support our discoveries with example attacks and then propose security improvements. We first study the AE portion of the Secure Shell (SSH) protocol. The SSH AE scheme is based on the Encrypt-and-MAC paradigm. Despite previous negative results on the Encrypt-and-MAC paradigm, we prove that the overall design of the SSH AE scheme is secure under reasonable assumptions. Our proofs for SSH contribute to the field of cryptography in several ways. First, we extend previous formal definitions of security for AE schemes to capture additional security goals, namely resistance to replay and re-ordering attacks. We also formalize a new AE paradigm, Encode-then-E&M, that captures the differences between the real SSH AE scheme and the previous Encrypt-and-MAC model. We state provable security results about both the Encode-then-E&M paradigm and the SSH AE scheme. Motivated by the differences between previous models and real AE schemes, we then consider and prove security results about generalizations of two other natural AE paradigms, MAC-then-Encrypt and Encrypt-then-MAC, as well as further generalizations of the Encode-then-E&M paradigm. Motivated by practical requirements and the IPsec community, we propose CWC --- the first block cipher-based AE scheme that is simultaneously provably secure, fully parallelizable, and free from intellectual property claims. Finally, we discover and propose fixes to security defects with the WinZip AE-2 AE scheme. Our attacks exploit interactions between AE-2's provably secure Encrypt-then-MAC core and the rest of the system. Since WinZip could have avoided certain attacks by applying the provable security approach to the whole AE-2 scheme, our results suggest the importance of pushing the provable security approach further into real systems