Skip to main content
Engineering LibreTexts

12.1: Definitions

  • Page ID
    7369
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Authenticated Encryption

    As with CPA and CCA flavors of security, we can define AE security in both a "left-vsright" style or a "pseudorandom ciphertexts" style. Both are reasonable choices. To make life simpler we will only define the pseudorandom-ciphertexts-style of AE security in this chapter

    In CCA$ security, the attacker has access to the decryption algorithm (except for ciphertexts generated by the library itself). This captures the idea that the result of decrypting adversarially-generated ciphertexts cannot help distinguish the contents of other ciphertexts. For AE security, we want a stronger condition that \(\operatorname{Dec}(k, c)=\operatorname{err}\) for every adversarially-generated ciphertext \(c\). Using the same ideas used to define security for MACs, we express this requirement by saying that the attacker shouldn’t be able to distinguish access to the "real" Dec algorithm, or one that always outputs err:

    Definition \(12.1\) (AE)

    Let \(\sum\) be an encryption scheme. We say that \(\sum\) has authenticated encryption (AE) security if \(\mathcal{L}_{\text {ae\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {ae\$-rand }}^{\Sigma}\), where:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Discussion

    The two libraries are different from each other in two major ways: whether the calling program sees real ciphertexts or random strings (that have nothing to do with the given plaintext), and whether the calling program sees the true result of decryption or an error message. With these two differences, we are demanding that two conditions be true: the calling program can’t tell whether it is seeing real or fake ciphertexts, it also cannot generate a ciphertext (other than the ones it has seen) that would cause Dec to output anything except err.

    Whenever the calling program calls DECRYPT \((c)\) for a ciphertext \(c\) that was produced by the library (in cTXT), both libraries will return err by construction. Importantly, the difference in the libraries is the behavior of DECRYPT on ciphertexts that were not generated by the library (i.e., generated by the attacker).

    Associated Data

    AE provides a secure channel between Alice and Bob that is safe from messagemodification and message-injection by the attacker (in addition to providing confidentiality). However, AE still does not protect from replay of messages. If Alice sends a ciphertext \(c\) to Bob, we know that Bob will decrypt \(c\) without error. The guarantee of AE security is that Bob can be sure that the message originated from Alice in this case. If an attacker re-sends the same \(c\) at a later time, Bob will likely interpret that as a sign that Alice wanted to say the same thing again, even though this was not Alice’s intent. It is still true that Alice was the originator of the message, but just not at this time.

    You may wonder how it is possible to prevent this sort of attack. If a ciphertext \(c\) is a valid ciphertext when Alice sends it, then it will always be a valid ciphertext, right? A clever way around this problem is for Alice to not only authenticate the ciphertext as coming from her, but to authenticate it also to a specific context. For example, suppose that Alice & Bob are exchanging encrypted messages, and the 5 th ciphertext is \(c\), sent by Alice. The main idea is to let Alice authenticate the fact that "I meant to send \(c\) as the 5 th ciphertext in the conversation." If an attacker re-sends \(c\) later (e.g., as the 11 th ciphertext, a different context), Bob will attempt to authenticate the fact that "Alice meant to send \(c\) as the 11th ciphertext," and this authentication will fail.

    What I have called "context" is called associated data in an encryption scheme. In order to support associated data, we modify the syntax of the encryption and decryption algorithms to take an additional argument \(d\). The ciphertext \(c=\operatorname{Enc}(k, d, m)\) is an encryption of \(m\) with associated data \(d\). In an application, \(d\) could be a sequence number of a conversation, a hash of the entire conversation up to this point, an IP address + port number, etc. - basically, as much information as you can think of regarding this ciphertext’s intended context. Decrypting \(c\) with the "correct" associated data \(d \operatorname{via} \operatorname{Dec}(k, d, c)\) should result in the correct plaintext \(m\). Decrypting \(c\) with any other associated data should result in an error, since that reflects a mismatch between the sender’s and receiver’s contexts.

    The intuitive security requirement for authenticated encryption with associated data (AEAD) is that an attacker who sees many encryptions \(c_{i}\) of chosen plaintexts, each authenticated to a particular associated data \(d_{i}\), cannot generate a different \(\left(c^{*}, d^{*}\right)\) that decrypts successfully. The security definition rules out attempts to modify some \(c_{i}\) under the same \(d_{i}\), or modify some \(d_{i}\) for the same \(c_{i}\), or produce a completely new \(\left(c^{*}, d^{*}\right)\).

    Definition \(12.2\) (AEAD)

    Let \(\Sigma\) be an encryption scheme. We write \(\sum . \mathcal{D}\) to denote the space of supported associated data signifiers ("contexts"). We say that \(\sum\) has authenticated encryption with associated data \((AEAD)\) security if \(\mathcal{L}_{\text {aead\$-real }}^{\Sigma} \approx \mathcal{L}_{\text {aead\$-rand }}^{\Sigma}\), where:

    fig-ch01_patchfile_01.jpg
    Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

    Discussion

    One way to "authenticate a message to some context \(d\) " is to encrypt \(m \| d\) instead of just \(m\) (in an AE scheme). This would indeed work! Including \(d\) as part of the plaintext would indeed authenticate it, but it would also hide it. The point of differentiating between plaintext and associated data is that we assume the associated data is shared context between both participants. In other words, we assume that the sender and receiver both already know the context \(d\). Therefore, hiding \(d\) is overkill - only authentication is needed. By making a distinction between plaintext and associated data separately in AEAD, the ciphertext length can depend only on the length of the plaintext, and not depend on the length of the associated data.

    The fact that associated data \(d\) is public is reflected in the fact that the calling program chooses it in the security definition.

    "Standard" AE corresponds to the case where \(d\) is always empty: all ciphertexts are authenticated to the same context.


    This page titled 12.1: Definitions is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.

    • Was this article helpful?