Poly1305 is a widely-deployed polynomial hash function. The rationale behind its design was laid out in a series of papers by Bernstein, the last of which dates back to 2005. As computer architectures evolved, some of its design features became less relevant, but implementers found new ways of exploiting these features to boost its performance. However, would we still converge to this same design if we started afresh with today’s computer architectures and applications? To answer this question, we gather and systematize a body of knowledge concerning polynomial hash design and implementation that is spread across research papers, cryptographic libraries, and developers’ blogs. We develop a framework to automate the validation and benchmarking of the ideas that we collect. This approach leads us to five new candidate designs for polynomial hash functions. Using our framework, we generate and evaluate different implementations and optimization strategies for each candidate. We obtain substantial improvements over Poly1305 in terms of security and performance. Besides laying out the rationale behind our new designs, our paper serves as a reference for efficiently implementing polynomial hash functions, including Poly1305.

Secure network protocols like TLS, QUIC, SSH and IPsec allow for additional padding to be used during encryption in order to hide message lengths. While it is impossible to conceal message lengths completely, without drastically degrading efficiency, such mechanisms aim at causing as much frustration as possible to the prospective attacker. However, none of the protocol specifications provide any guidance on how to select the length of this padding. Several works have highlighted how the leakage of message lengths can be exploited in attacks, but the converse problem of how to best defend against such attacks remains relatively understudied. We make this the focus of our work and present a formal treatment of length hiding security in a general setting. Prior work by Tezcan and Vaudenay suggested that sampling the padding length uniformly at random already achieves the best possible security. However we show that this is only true in the limited setting where only a single ciphertext is available to the adversary. If multiple ciphertexts are available to the adversary, then sampling the padding length according to a Gaussian distribution yields quantifiably better security for the same overhead. In fact, in this setting, uniformly random padding turns out to be among the worst possible choices. We confirm experimentally the superior performance of Gaussian padding over uniform padding in the context of the CRIME/BREACH attack.

The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and establish the tightness of each term in our bound through matching attacks. We show how our bound differs both qualitatively and quantitatively from the known bounds for AES-GCM, highlighting how subtle design choices lead to distinctive security properties. We translate our bound to the nonce-randomized setting employed in TLS 1.3 and elsewhere, and we additionally improve the corresponding security bounds for GCM. Finally, we provide a simple yet stronger variant of ChaCha20-Poly1305 that addresses the deficiencies highlighted by our analysis.

This work presents a systematic analysis of symmetric encryption modes for SSH that are in use on the Internet, providing deployment statistics, new attacks, and security proofs for widely used modes. We report deployment statistics based on two Internet-wide scans of SSH servers conducted in late 2015 and early 2016. Dropbear and OpenSSH implementations dominate in our scans. From our first scan, we found 130,980 OpenSSH servers that are still vulnerable to the CBC-mode-specific attack of Albrecht et al. (IEEE S&P 2009), while we found a further 20,000 OpenSSH servers that are vulnerable to a new attack on CBC-mode that bypasses the counter-measures introduced in OpenSSH 5.2 to defeat the attack of Albrecht et al. At the same time, 886,449 Dropbear servers in our first scan are vulnerable to a variant of the original CBC-mode attack. On the positive side, we provide formal security analyses for other popular SSH encryption modes, namely ChaCha20-Poly1305, generic Encrypt-then-MAC, and AES-GCM. Our proofs hold for detailed pseudo-code descriptions of these algorithms as implemented in OpenSSH. Our proofs use a corrected and extended version of the "fragmented decryption" security model that was specifically developed for the SSH setting by Boldyreva et al. (Eurocrypt 2012). These proofs provide strong confidentiality and integrity guarantees for these alternatives to CBC-mode encryption in SSH. However, we also show that these alternatives do not meet additional, desirable notions of security (boundary-hiding under passive and active attacks, and denial-of-service resistance) that were formalised by Boldyreva et al.

IPsec allows a huge amount of flexibility in the ways in which its component cryptographic mechanisms can be combined to build a secure communications service. This may be good for supporting different security requirements but is potentially bad for security. We demonstrate the reality of this by describing efficient, plaintext-recovering attacks against all configurations of IPsec in which integrity protection is applied {\em prior} to encryption -- so-called MAC-then-encrypt configurations. We report on the implementation of our attacks against a specific IPsec implementation, and reflect on the implications of our attacks for real-world IPsec deployments as well as for theoretical cryptography.

We describe new attacks which break any RFC- compliant implementation of IPsec making use of encryption-only ESP in tunnel mode. The new attacks are both efficient and realistic: they are ciphertext-only and need only the capability to eavesdrop on ESP-encrypted traffic and to inject traffic into the network. We report on our experiences in applying the attacks to a variety of implementations of IPsec.