I don't understand the example. Presumably the server doesn't have the user-owned encryption key. So how can the server "detect that the user id has been tampered with" if it doesn't have the key necessary to authenticate the user id?
You could water down the example a bit to make it work:
1. Assume there's some other authentication mechanism for client-server communication, e.g. TLS.
2. The client sends the user ID unencrypted (within TLS) so the server can route, but encrypts the message contents so the server can't read it.
3. The final recipient can validate the message and the user ID.
This saves the client from having to send the user ID twice, once in the ciphertext and once in the clear.
But another more interesting use case is when you don't even send the associated data: https://news.ycombinator.com/item?id=43827342
Even if I gain access to the database, if the keys are managed securely, I can't read another user's data (or even really my own). I have to go through the authorization logic of the application that will decrypt it on my behalf.
However, if I can create a row in the database with my ID and another user's data, I can then convince the server I am authorized to view that cell, and it will happily decrypt it on my behalf, assuming something like AES-CTR or some other stream cipher without authentication.
Authenticated encryption like AES-CTR-HMAC solves that problem, because now the application will see that I am authorized to view that cell (because it sees the user ID matches mine) and it will decrypt it for me (using that user ID as the associated data), but the decryption will fail because the associated data does not match, leaving me unable to exfiltrate the data that I convinced the server belonged to me, and probably setting off some kind of alarm because that sort of decryption should never fail unless things have been tampered with.
I'm not overly fond of the example and I find it confusing as well. I think the example may be a bit confusing because the term "authentication" is overloaded between application-level authentication and cryptographic authentication, i.e., "if the chat protocol authenticates the user ID" sounds like it is talking about the user logging into the server securely. The user is authenticated by having a secret negotiated with the server. In the next bullet, they talk about "authenticating" the associated data, referring to it in the cryptographic context, but they don't indicate why that would be a problem because in their example, the malicious actor still doesn't have the key. The article handwaves it as "the attacker might be creative."
If they had the key, but not the associated data, you'd still be in a relatively bad situation, because the associated data is not secret. It doesn't serve as a second key because it is not high enough entropy and is ideally zero entropy conditional on already having all information from the originating context.
That guarantee is not provided with unauthenticated stream ciphers. For example, some stream ciphers work by essentially using a deterministic but unpredictable PRNG seeded with the key and IV to generate a bitstream, and then XOR the plaintext with that bitstream to generate the ciphertext.
With such a stream cipher, If Eve knows that the data format is, e.g., the an 8-byte unsigned integer user ID followed by the rest of the payload, Eve can take the first 8 bytes of the ciphertext and XOR it with Bob's user ID (public information) and her own user ID to corrupt the message in such a way that the ID in the resulting cleartext would contain her user ID instead of Bob's, and thus pass the validation that it seems like you are proposing.
Let C[] be the cipher text, K[] be the key stream, B be Bob's ID, and E be Eve's ID:
C[:8] = B ^ K[:8]
C[:8] ^ B = K[:8]
C' = C[:8] ^ B ^ E ++ C[8:]
C' would decrypt, validate as "belonging" to Eve, and contain Bob's data.
If you are using an AEAD cipher mode, then you always have AD, but sometimes that AD might be the empty string. In that case, the advantage to using contextual AD as opposed to using the empty string as AD and then doing additional verification on the decrypted object is that it prevents some kinds of timing attacks, because cryptographic libraries will often implement AEAD constructions to fail in constant time, where as your scheme will take longer if post-decryption validation of contextual data encoded in the plaintext fails compared to if decryption fails.
OK fair.
> and I would consider whatever "secret key" you pass into HMAC along with the ciphertext to be the "associated data"
The secret key isn't associated data. You take your base HKDF key and expand new crypto for an authenticated cipher from the offset as info (+ maybe other parameters like file name). That key is then used to decrypt. If you squint I guess you could call that AD but it's functionally a very different role.
> because cryptographic libraries will often implement AEAD constructions to fail in constant time, where as your scheme will take longer if post-decryption validation of contextual data encoded in the plaintext fails compared to if decryption fails.
I think you've misunderstood what I said. As I repeat above, the AEAD key is derived from the offset. There's no post-decryption validation of contextual data because the plaintext is empty. HKDF derivation is constant time and authenticated decryption is constant time. Once decrypted you have a valid block at that location. There's nothing extra left to validate (or perhaps the decrypted contents, but that's irrelevant for cryptographic purposes).
My broader point is that I have yet to encounter a use-case for a non-empty AD string.
As you said, same effect: the scheme you have described is not an alternative to AEAD. It is an example of AEAD. You're still using the offset as associated data, you just happen to be composing your AEAD scheme out of another AEAD scheme into which you pass an empty string as associated data.
Other than differences in the limit to the number of messages you can encrypt before nonce exhaustion or the number of bits of secrecy or authentication strength provided, the external interface and use case of your system perfectly matches that of AES-GCM or other popular AEAD constructions.
Ahh, but that’s not a trivial part of the design and why this is strictly better than using a single AES-GCM key with AD. And also it’s more generic across whatever type of key you choose to derive.
Somehow I assumed that the server was able to authenticate the receiver id, but as you correctly point out, that would require knowing the encryption key. I'll have to think about a fix for the example.
If Alice saves some data to her account, but Eve manages to access the database, Eve can change the database state to convince the application to retrieve Alice's data for her (by cloning it into a row with her own user ID). However, when the application attempts to decrypt that data, it will fail because of the AEAD. This ensures that both the database and some service with access to the encryption key (or the encryption key itself) would have to be compromised in order for Eve to exfiltrate her illicit copy of Alice's data.
I finally updated the example to a new one, though it's still message-based (it fits the rest of the article better). If I had come across your example earlier, I might have stayed away from a message-based formulation of the problem at all... Better luck next time I guess :)