Authenticated Encryption with Variable Stretch

In conventional authenticated-encryption (AE) schemes, the ciphertext expansion, a.k.a.stretch or tag length, is a constant or a parameter of the scheme that must be fixed per key. However, using variable-length tags per key can be desirable in practice or may occur as a result of a misuse. The RAE definition by Hoang, Krovetz, and Rogaway (Eurocrypt 2015), aiming at the best-possible AE security, supports variable stretch among other strong features, but achieving the RAE goal incurs a particular inefficiency: neither encryption nor decryption can be online. The problem of enhancing the well-established nonce-based AE (nAE) model and the standard schemes thereof to support variable tag lengths per key, without sacrificing any desirable functional and efficiency properties such as online encryption, has recently regained interest as evidenced by extensive discussion threads on the CFRG forum and the CAESAR competition. Yet there is a lack of formal definition for this goal. First, we show that several recently proposed heuristic measures trying to augment the known schemes by inserting the tag length into the nonce and/or associated data fail to deliver any meaningful security in this setting. Second, we provide a formal definition for the notion of nonce-based variable-stretch AE (nvAE) as a natural extension to the traditional nAE model. Then, we proceed by showing a second modular approach to formalizing the goal by combining the nAE notion and a new property we call key-equivalent separation by stretch (kess). It is proved that (after a mild adjustment to the syntax) any nAE scheme which additionally fulfills the kess property will achieve the nvAE goal. Finally, we show that the nvAE goal is efficiently and provably achievable; for instance, by simple tweaks to off-the-shelf schemes such as OCB.

Provably Secure Authenticated Encryption

Damian Vizár

Authenticated Encryption (AE) is a symmetric key cryptographic primitive that ensures confidentiality and authenticity of processed messages at the same time. The research of AE as a primitive in its own right started in 2000. The security goals of AE were captured in formal definitions in the tradition in the tradition of provable security (such as NAE, MRAE, OAE, RAE or the RUP), where the security of a scheme is formally proven assuming the security of an underlying building block. The prevailing syntax moved to nonce-based AE with associated data (which is an additional input that gets authenticated, but not encrypted). Other types of AE schemes appeared as well, e.g. ones that supported stateful sessions. Numerous AE schemes were designed; in the early years, these were almost exclusively blockcipher modes of operation, most notably OCB in 2001, CCM in 2003 and GCM in 2004. At the same time, issues were discovered both with the security and applicability of the most popular AE schemes, and other applications of symmetric key cryptography. As a response, the Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR) was started in 2013. Its goals were to identify a portfolio of new, secure and reliable AE schemes that would satisfy the needs of practical applications, and also to boost the research in the area of AE. Prompted by CAESAR, 57 new schemes were designed, new types of constructions that gained popularity appeared (such as the Sponge-based AE schemes), and new notions of security were proposed (such as RAE). The final portfolio of the CAESAR competition should be announced in 2018. In this thesis, we push the state of the art in the field of AE in several directions. All of them are related to provable security, in one way, or another. We propose OMD, the first provably secure dedicated AE scheme that is based on a compression function. We further modify OMD to achieve nonce misuse-resistant security (MRAE). We also propose another provably secure variant of OMD called pure OMD, which enjoys a great improvement of performance over OMD. Inspired by the modifications that gave rise to pure OMD, we turn to the popular Sponge-based AE schemes and prove that similar measures can also be applied to the keyed Sponge and keyed Duplex (a variant of the Sponge), allowing a substantial increase of performance without an impact on security. We then address definitional aspects of AE. We critically evaluate the security notion of OAE, whose authors claimed that it provides the best possible security for online schemes under nonce reuse. We challenge these claims, and discuss what are the meaningful requirements for online AE schemes. Based on our findings, we formulate a new definition of online AE security under nonce-reuse, and demonstrate its feasibility. We next turn our attention to the security of nonce-based AE schemes under stretch misuse; i.e. when a scheme is used with varying ciphertext expansion under the same key, even though it should not be. We argue that varying the stretch is plausible, and formulate several notions that capture security in presence of variable stretch. We establish their relations to previous notions, and demonstrate the feasibility of security in this setting. We finally depart from provable security, with the intention to complement it. We compose a survey of universal forgeries, decryption attacks and key recovery attacks on 3rd round CAESAR candidates.

EPFL2018

Power Yoga: Variable-Stretch Security of CCM for Energy-Efficient Lightweight IoT

Emiljano Gjiriti, Reza Reyhanitabar, Damian Vizár

The currently ongoing NIST LWC project aims at identifying new standardization targets for lightweight authenticated encryption with associated data (AEAD) and (optionally) lightweight cryptographic hashing. NIST has deemed it important for performance and cost to be optimized on relevant platforms, especially for short messages. Reyhanitabar, Vaudenay and Vizar (Asiacrypt 2016) gave a formal treatment for security of nonce-based AEAD with variable stretch, i.e., when the length of the authentication tag is changed between encryptions without changing the key. They argued that AEAD supporting variable stretch is of practical interest for constrained applications, especially low-power devices operated by battery, due to the ability to flexibly trade communication overhead and level of integrity. In this work, we investigate this hypothesis with affirmative results. We present vCCM, a variable-stretch variant of the standard CCM and prove it is secure when used with variable stretch. We then experimentally measure the energy consumption of a real-world wireless sensor node when encrypting and sending messages with vCCM and CCM, respectively. Our projections show that the flexible trade of integrity level and ciphertext expansion can lead up to 21% overall energy consumption reduction in certain scenarios. As vCCM is obtained from the widely-used CCM by a black-box transformation, allowing any existing CCM implementations to be reused as-is, our results can be immediately put to use in practice. vCCM is all the more relevant because neither the NIST LWC project, nor any of the candidates give a consideration for the support of variable stretch and the related integrity-overhead trade-off.

RUHR-UNIV BOCHUM, HORST GORTZ INST IT-SICHERHEIT2021

Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance

Reza Reyhanitabar, Damian Vizár

A definition of online authenticated-encryption (OAE), call it OAE1, was given by Fleischmann, Forler, and Lucks (2012). It has become a popular definitional target because, despite allowing encryption to be online, security is supposed to be maintained even if nonces get reused. We argue that this expectation is effectively wrong. OAE1 security has also been claimed to capture best-possible security for any online-AE scheme. We claim that this understanding is wrong, too. So motivated, we redefine OAE-security, providing a radically different formulation, OAE2. The new notion effectively does capture best-possible security for a user’s choice of plaintext segmentation and ciphertext expansion. It is achievable by simple techniques from standard tools. Yet even for OAE2, nonce-reuse can still be devastating. The picture to emerge is that no OAE definition can meaningfully tolerate nonce-reuse, but, at the same time, OAE security ought never have been understood to turn on this question.

Springer2015

Provably Secure Authenticated Encryption

Damian Vizár

EPFL2018