Talk:Authenticated encryption

History

From Block cipher modes of operation: ... After observing that compositing a confidentiality mode with a authenticity mode could be difficult and error prone, the cryptographic community began to supply modes which combined confidentiality and data integrity into a single cryptographic primitive. The modes are referred to as authenticated encryption, AE, and authenc. Examples of authenticated encryption modes are CCM (SP800-38C), GCM (SP800-38D), CWC, EAX, IAPM, and OCB.

May 2002

Patents can be a bear for me because I'm not always aware of the minor legal issues. But I think this is one of the earliest Authenticated Encryption modes: US2003/0223585 A1, "Method and Apparatus for Performing Encryption and Authentication", May 2002 by Tardo and Matthews. It appears they perform the single pass operation (see the methods accompanying Figure 7), but it also appears that Authenticate and Encrypt (A&E) is performed. According to Krawczyk, A&E is insecure but I don't think it affects the legal standing of the "single pass" innovation.

May 2003

Kohno, Viega, Whiting, "CWC: A High-Performance Conventional Authenticated Encryption Mode", IACR, May 2003 (http://eprint.iacr.org/2003/106).

December 2003

Jutla, "Encryption Modes with Almost Free Message Integrity", Journal of Cryptography, December 2003 (http://www.springerlink.com/content/q615311611mx2057/).

Repudiation

Maybe it should be noted that authenticated encryption, being symmetric, cannot supply non-repudiation like a digital signature would. I.e. all parties which know the key can easily make authenticated messages. E.g. suppose Alice sends Bob a message "I, Alice, owe Bob $100". Bob keeps the message and eventually demands to be paid, but Alice now denies having sent the message. Suppose both agree to giving a trusted third party the key, then there is no way for this third party to tell whether the message was actually written by Alice, as it could equally have been written by Bob, who, by necessity, also knows the key. Likewise, Bob could have altered the message to read "I, Alice, owe Bob $1000" with no (cryptographic) way for the trusted third party to figure out who is telling the truth.

Non-repudiation can obviously be added on top of authenticated encryption by signing the authentication tag using an asymmetric algorithm. The default lack of non-repudiation is no criticism of AE, as it may not be required, is easily supplemented, and unavoidable in any purely symmetric cryptosystem. Aragorn2 (talk) 10:23, 19 June 2019 (UTC)

Non-repudiation can obviously be added on top of authenticated encryption by signing the authentication tag using an asymmetric algorithm. The default lack of non-repudiation is no criticism of AE, as it may not be required, is easily supplemented, and unavoidable in any purely symmetric cryptosystem.

131.196.163.169 (talk) 13:02, 26 November 2023 (UTC)

Constructs with a digital signature per-message are aplenty, see, for example, IEEE P1609.2. However, I do not think that anyone calls them AEAD, so this might be off-topic here. Dimawik (talk) 20:13, 26 November 2023 (UTC)

Privacy vs. confidentiality

@Olivander1337: The term privacy is routinely used to define confidentiality in AEAD schemes. See, for example, the title of Mihir Bellare's paper [1]. I have no issue with adding a note that this use is not related to the privacy preservation. Dimawik (talk) 15:14, 5 November 2023 (UTC)

Key-committing AEAD

The following just-added text is moved here for a discussion. The reason is simple: the text reads like the GCM mode was broken, but in reality the Len's paper appears to describe an attack on poor implementations. As far as I can understand, in the case considered the brute-force attack was not that hard to pull off to begin with, without acceleration. I see absolutely no problem with describing the key-committing AEAD here, just in a proper context: as a new research and based on some kind of peer-reviewed paper that was authored by a non-inventor of a better AEAD. If I am wrong in my interpretation of the papers, just let me know (here) where I am wrong (I am very thick-skinned). Dimawik (talk) 01:34, 22 February 2024 (UTC)

Most existing (as of 2021) AEAD schemes are not key-committing: it is possible to craft a ciphertext+MAC combination that can be decoded without error by multiple keys. If a target that decrypts such combinations also indicates to the sender whether the decryption is done without error, it can serve as an oracle that tells the attacker whether its secret key is one of the attacker's multiple candidate keys. As a result, it takes significantly less time to try through a list of potential keys or passwords compared to brute-forcing.

To mitigate this attack without removing the "oracle", a key-committing AEAD that does not allow this type of crafted messages to exist can be used. AEGIS is an example fast (if the AES instruction set is present), key-committing AEAD. It is possible to add key-commitment to an existing AEAD scheme.

I thought I am clear enough that it only works when you have a silly target that works as an oracle. Whether that "silliness" is down to "bad implementation" or a cornerstone of some protocol design (like OPAQUE) is another thing. Artoria2e5 🌉 03:41, 22 February 2024 (UTC)

Anyways, there are stronger citations available. poncho's prepend padding scheme is explored in more detail in https://eprint.iacr.org/2020/1456.pdf. Bellare and Hoang https://eprint.iacr.org/2022/268.pdf gives a more concrete definition of "key committing security". (Adding "message commitment" for "franking" also seems to be a thing. Use cases, use cases...) --Artoria2e5 🌉 04:19, 22 February 2024 (UTC)

Len et al. pretty much start their article with the statement: This will not work to recover much information about, e.g., random 128-bit keys. At this point alarm goes on in my head, as the only sane choice for the AES key generator should use sufficient entropy: obviously, a system using keys with low entropy is breakable (since the keys are predictable). For example, NIST SP 800-57 Part 1 rev. 5 explicitly states:

Symmetric keys shall be either generated by an approved method (e.g., using an approved random number generator; see SP 800-133) or derived from a master key/key-derivation key (see Section 8.2.4) using an approved key-derivation function (see SP 800-108). Symmetric keys may also be generated using key-agreement techniques (see Section 8.1.5.2.3)

— SP 800-57 8.1.5.2.1 Key Generation

So the choices are:

1. random key - no problem
2. key derived from master key. Three cases here (8.2.4):
   • a common shared secret per SP 800-56A or SP 800-56B. This derivation includes random numer - no problem
   • a key generated from master key. The master key obviously should have high entropy that, if approved KDF (SP 800-108) are used, will pass into generated keys - no problem
   • a key generated from password (our case). In this case SP 800-133r2 no less explicitly states that

     When a key is generated from a password, the entropy provided (and thus, the maximum security strength that can be supported by the generated key) shall be considered to be zero

     — SP 800-133 6.2.3, boldface is mine

     unless the password is generated randomly (in which case, no problem again).
3. key-agreement machinery uses random numbers.

Mathematics in the article is certainly amusing. Still, the key problem (pun intended) that allows attack in the first place, IMO, is not an existence of oracle that is implemented so poorly that it allows an unlimited amount of attacks without doing something drastic, but the cryptographic design in which passwords and keys are related without involving any randomness. Bellare is a very definite expert in the field, so I see no problem describing the key-commitment idea schemes in general based on the introduction to the Bellare and Hoang preprint (as well as Albertini1 et al.). As a first step towards this goal, I will revert my removal of the text above. Dimawik (talk) 11:50, 22 February 2024 (UTC)

Partially rewrote the section. Dimawik (talk) 06:09, 23 February 2024 (UTC)

After finding more solid papers, perhaps, Key commitment can be turned into a separate article (by the User:Somebody "Notme" Else, naturally). There is one {{cn}} left; the statement is obvious (and is actually used by the padding constructs), but I did not find it in compact and explicit form in the papers. Dimawik (talk) 06:50, 23 February 2024 (UTC)

Under Bellare & Hoang 2020, my impression is that the issue issue seems to be not in the possibility of having multiple keys, but in the difficulty of finding combinations of key-nonce-AD-plaintext that collide into the same ciphertext. They call basic key commitment "CMT-1" and discuss the number of operations required to break a scheme's CMT-1 security on p18. Actually, just Ctrl-F "operation", there's also a bit on p12. Artoria2e5 🌉 11:44, 1 March 2024 (UTC)

Most likely, we are in agreement, just discussing the same difficulty from different angles. The breach in Len et al. was only practical due to the fact that 1000x reduction in communications might have allowed the attack to stay entirely under the radar due to limited key space (they accept this fact themselves). I would expect simply trying the 1000 passwords to be faster than performing the calculations necessary to put the test in one packet. So, if the attack requires ginormous traffic to begin with (inevitable for random passwords), the concept becomes a purely academic matter. For the avoidance of doubt: (1) the words above is my personal opinion, I am not suggesting to put anything like that into the article; (2) due to my background, I fully appreciate the value of pure research and do consider the key commitment a rewarding field of study. My initial goal in this discussion was to simply explain my desire for this article to avoid hinting that the classic AEAD methods are broken (they are not to the best of my knowledge). The system Len et al. were attacking had next to zero security to begin with due to the key generation methods chosen. The researchers found a cute method to bypass some other restriction in the system, kudos to them. Dimawik (talk) 22:29, 1 March 2024 (UTC)