This week I am in Tokyo to present a research paper in cryptography at the 24th International Conference on Fast Software Encryption, the reference academic conference on symmetric crypto. This paper is the result of a semester project that I started last year during my master at EPFL, in collaboration with Damian Vizár from the LASEC laboratory. The paper is already available on ePrint and its title is “Linking Online Misuse-Resistant Authenticated Encryption and Blockwise Attack Models”. I’ll try to explain what that means.
This paper is about a subfield of crypto called authenticated encryption (AE). To understand this notion, let’s imagine that you connect to your bank’s website to order a money transfer. You essentially want two security properties for your communications with the bank. First, it must be confidential: no one else than you and the bank should know the amount and recipient. Second, it must be authenticated: only you can order transfers from your account, and no one should be able to modify the message that you sent (to change the amount or the recipient).
These two properties have long been implemented in cryptographic protocols such as TLS, but for a long time two separate algorithms were used to guarantee confidentiality and authenticity. Yet, in the past two decades, a line of research focused on developing so-called authenticated encryption (AE) algorithms, which combine both properties within a single algorithm. In particular, the AES-GCM algorithm is now widely used in TLS, and the ongoing CAESAR competition is proposing and analyzing more authenticated ciphers. Such AE schemes promise better efficiency than the generic composition of two algorithms, but a more thorough security analysis is necessary to guarantee the simultaneous confidentiality and authenticity properties.
Another important property of ciphers is that two encryptions of the same message (or related messages) shouldn’t be linkable. For this purpose, most schemes (more precisely, all deterministic stateless schemes) require a separate input called nonce that must not be reused for separate messages. This can for example be based on a counter, that is, the first message has a nonce equal to 1, the second message a nonce equal to 2, and so on. This way, two encryptions of the same message but with distinct nonces yield two distinct ciphertexts. Additionally, AE schemes often accept an additional input called associated data (AD): this contains public information (such as IP addresses) that you want to authenticate with the message.
Yet in practice it can prove difficult to ensure non-repetition of the nonce: if one clones a virtual machine whose state contains the counter, the two clones will use the same nonces for subsequent messages. We call this behavior “nonce-misuse”. To protect against this, some schemes were proposed and advertise to provide nonce-misuse resistance: the scheme is secure unless you repeat the full tuple <nonce, associated data, message>.
Most ciphers work by splitting messages into small blocks (usually 16 bytes) and processing them one after another. Such ciphers are said to be online when the encryption of each block doesn’t depend on future blocks but only on previous ones. This means that the algorithm doesn’t have to know the full plaintext message to start producing ciphertext chunks. In practice, the main advantage of online ciphers is that they have a constant (and low) memory footprint (in the order of a few blocks), and work in a single pass.
Yet, the online property may allow more powerful attacks: a so-called blockwise attacker could query the encryption of the first block and wait for the corresponding ciphertext block to adapt its strategy to select the next block(s). For example, under this blockwise-adaptive attacker model, the CBC mode of operation was proven to be insecure.
With that in mind, our paper focuses on understanding whether the recently proposed “online misuse-resistant authenticated encryption” model that captures the security of AE schemes can be related to older “resistance to blockwise attackers” notions that were not targeted to AE schemes. Although these notions were originally defined to analyze different things, we show that there are essentially equivalent, modulo some adaptations to make them compatible.
Kudelski Security Research 