Authenticated Encryption: Introduction
Recap: The course first covered the requirement for confidentiality ie semantic security against a CPA attack.
Encryption here secures against eavesdropping only
Then we looked at integrity ie existential unforgeability under a chosen message attack.
we now turn to encryption that is secure against tampering - ensuring confidentiality and integrity.
We will guard against powerful adversaries who can modify packets in transmission.
Note that CPA security cannot guarantee secrecy under active attacks. There are chosen ciphertext attacks that can be used to reconstruct messages.
Only use one of two modes:
If message needs integrity but no confidentiality use a MAC
If message needs integrity and confidentiality use authenticated encryption modes.
Authenticated Encryption
An authenticated encryption system \((E,D)\) is a cipher where:
\[E: K \times M \times N \rightarrow C\]
but:
\[D: K \times C \times N \rightarrow M \cup \{ \bot \} | \bot \notin \M\]
The nonce is optional. The decryption algorithm is now allowed to emit a special symbol (bottom) where the cipher text is rejected.
The system must provide two properties to be secure:
Semantic security under a CPA attack
Ciphertext integrity: attacker cannot create new ciphertexts that decrypt properly
Note that CBC with random IV does not provide authenticated encryption, since we never output \(\bot\).
This has several implications:
attacker cannot fool bob into thinking a message was sent from alice. (except in the case of a replay). Replay attacks need another defence.
Defends against chosen cipher text attacks (very powerful attack).
Constructing Authenticated Encryption
*nstructing Authenticated En
We already have CPA secure systems, and we have secure MACs, so can we just combine them?
AE was introduced in 2000. Before then, crypto libraries provided APIs that separately supported CPA-secure encryption (eg CBC with rand. IV) and for MAC (eg HMAC).
Every project had to combine the two itself without a well defined goal. Not all combinations provided AE.
Most common mistakes in projects were incorrect combinations of these.
Here are three examples of combinations:

The difference between IPSec and SSH is that the signature is of the ciphertext rather than the message.
The problem with SSH is that the mac could leak bits of the message. This would be fine for a mac, but break cpa security.
There are pathological examples with the SSL approach, there can be a bad interaction between the encyrption scheme and mac.
Always use encrypt then mac.
Once the concept of Authenticated Encryption had caught hold, a number of standard approaches for combining MAC and encryption were developed.
NIST introduced the GCM and CCM standards:
GCM CTR mode encyrption then CW-MAC.
CCM CBC-MAC then CTR mode encryption
There is also EAX - CTR mode encryption then CMAC.
All are nonce based.
They support Authenticated Encryption with Associated Data. Part of the message is encrypted, all is authenticated. The header, for example, will not be encrypted since the routers need to forward it. Header still needs to be authenticated.
There is a way to directly construct an authenticated encryption system, called OCB, which is much faster than encrypt then mac:

Note it is parallelizable, and you only evaluate the cipher once per block.
So if this is so much quicker, why isn’t it the standard? It’s because of patents…
Use one of the three standards (GCM - fastest on Intel hardware), don’t try to implement encrypt-then-mac yourself.