Motivation
Privacy and encryption
One of the most basic goals of cryptography is to enable parties to communicate
over an open communication channel in a secure way. One immediate question that
arises, however, is what do we mean by "secure communication". We learned that
it is possible to obtain private communication over an open channel. That is, we
showed how encryption can be used to prevent an eavesdropper (or possibly a more
powerful adversary) from learning anything about the content of messages sent
over an unprotected communication channel.
Message integrity
How, not all security concerns are related to the ability or inability
of an adversary to learn something about messages being sent. In many cases, it
is of equal or greater importance to guarantee message integrity (or
message authentication) in the sense that the
message sent by one party is indeed the same message received by the other
party.
Message Authentication Codes (MAC): Setting
Sender, Receiver, Active Adversary
Fig 1. The setting for message authentication
codes
As described in Fig 1, the sender sends a message C, and receiver receives it
over an insecure channel. The adversary may modify the message transiting
through the channel. We call this type of adversary "active adversary". (Contrary
to this, the passive adversary doesn't modify the contents of the message; we
considered a passive adversary in the encryption scenario.)
Goal
The receiver can always check whether the message is authentic.
Example
Consider the case that a large supermarket chain sends an email request to
purchase 10,000 crates of soda from a supplier. Upon receiving such a request,
the supplier has to ask itself two questions:
- Is the order authentic? That is, did the supermarket chain really issue
the order, or was it issued by an adversary who spoofed the email address
of the supermarket (something that is remarkably easy to do).
- If the order was issued by the supermarket, then the supplier must still
ask whether the details of the order that it received are exactly those
sent by the supermarket, or were these details somehow changed en
route by an adversarial router.
Notice that the order itself is not secret and therefore the question of
confidentiality does not arise here at all. Rather, the problem is that of
message integrity. Such examples are very common. Indeed, any unprotected
online purchase order, online banking operation, email or SMS message cannot be
trusted whatsoever.
Syntax and Security
Syntax
A cryptographic primitive that provides message integrity is a message
authentication code (MAC). A MAC consists of three algorithms \( ({\sf MGen}, {\sf Mac}, {\sf MVer}) \) such that:
- The key generation algorithm \({
\sf MGen } \) takes as input
the security parameter \( n \) and outputs a key \( K \).
- The tag-generation algorithm \( { \sf Mac} \) takes as input
a key \( K \) and a message \( M \in \{0,1\}^* \), and outputs a tag \( T \). The algorithm
may be randomized, and we write \( T
\leftarrow {\sf Mac}_K(M) \).
- The deterministic verification algorithm \( {\sf MVer } \)
takes input a key \( K \), a message \( M \), and a tag \( T \). It outputs
a bit \( b \), with \( b = 1 \) meaning valid and \( b =0 \) meaning
invalid. We write this as \( b := {\sf MVer}_K(M, T) \).
Fig 2. Using MAC to ensure message
integerity
MAC vs Digital Signature
As you know that digital signatures provide similar security guarantees. The
main differences are:
- MAC works in the symmetric key seting. That is, both the receiver and the
sender share the same key.
- On the other hand, the digital signature is a public-key cryptographic
primitive. The sender (signer) holds a private signing key, and the all other
people can verify using the public verification key.
- MAC is much faster than digital signatures. For example, HMAC simply needs
a couple of hashing operations.
Security: Unforgeability
We call that a MAC scheme is secure if no polynomial-time
adversary should be able to generate a valid MAC tag on any new message.
Secure MAC Scheme: HMAC
Notations
Q. What is \( \{0,1\}^* \)?
It means the set of arbitrary-length binary strings, that is, the set of all
binary data.
Q. What is \( || \)?
It's a concatenation operation, which means connecting the two
strings together.
Description of HMAC
We describe the HMAC. Let \( H: \{0,1\}^* \rightarrow \{0,1\}^n \) be a
collision resistant hash function.
The idea for the construction is that the tag should be something like
the hash on both the key and the message. Since the adversary doesn't know
the key, it will probably have hard time in guessing the right hash
value on (key, message). However, simply computing H( K || M ) is known
to be insecure, and the construction uses the "double-layer" hashing.
 HMAC with SHA-256 hash function
- \( {\sf MGen}(n) \):
- Choose a \(n\)-bit random key \( K \).
- \( {\sf Mac}_K(M) \):
- Compute the inner-layer padded key \( ikpad := K \oplus ipad \).
Here
\( ipad \) is called the inner
padding; for SHA-256 it's 64 bytes of 0x36.......36. Usually,
\( K \) is shorter than \( ipad \).
- Compute the inner-layer hash \( hash_1 := H( ikpad || M ) \)
- Compute the outer-layer padded key \( okpad := K \oplus opad \).
Here
\( opad \) is called the outer
padding; for SHA-256, it's 64 bytes of 0x5c....5c.
- Compute the outer-layer hash \( hash_2 := H( ~okpad ~||~ hash_1 ) \).
- Output \( T := hash_2 \).
- \( {\sf MVer}_K(M, T) \) :
- Compute \( T' := {\sf Mac}_K(M) \).
- If \( T = T' \), output 1; otherwise
output 0.
| |
Authenticated Encryption (AE): Achieving Confidentiality and Integrity Simultaneously
AE: Encrypt-Then-MAC
To achieve both confidentiality and message integrity simultaneously, we follow
the paradigm of "Encrypt-Then-MAC".
Let \( ({\sf Gen}, {\sf Enc}, {\sf Dec}) \) be a
secure encryption scheme and \( ({\sf MGen}, {\sf Mac}, {\sf
MVer}) \) be a secure MAC scheme.
We describe the authenticated encryption \( ({\sf Gen'}, {\sf
Enc'}, {\sf Dec'}) \):
- \( {\sf Gen'}(n): \)
- \( K_e \leftarrow {\sf Gen}(n) \).
- \( K_m \leftarrow {\sf MGen}(n) \).
- \( K := (K_e, K_m) \). Output \( K \).
- \( {\sf Enc'}_K(M) \)
- Parse \( K \) as \( (K_e, K_m) \).
- \( C \leftarrow {\sf Enc}_{K_e}(M) \).
- \( T \leftarrow {\sf Mac}_{K_m}(C) \).
- \( C' := (C, T) \). Output \( C' \).
- \( {\sf Dec'}_K(C') \).
- Parse \( K \) as \( (K_e, K_m) \).
- Parse \( C' \) as \( (C, T) \).
- Check if \( {\sf MVer}_{K_m}(C, T) \stackrel{?}{=} 1 \). If not, return
\( \bot \).
- Otherwise, output \( {\sf Dec}_{K_e}(C) \).
Interestingly, this authenticated encryption is proven to be an IND-CCA
encrpytion scheme.
Recall that in the CCA (chosen ciphertext attack), the adversary has both
encryption and the decryption power.
However, due to unforgeability of MAC, even though the adversary has the
decryption capability, it cannot create a valid ciphertext. This is because in
order to create any valid ciphertext, the adversary must create a valid MAC
tag.
In a sense, the decryption capability can never be taken advantage of by the
adversary. So, the adversary is forced to become a CPA adversary.
If \( ({\sf Gen}, {\sf Enc}, {\sf Dec}) \) is an IND-CPA encryption scheme, and \( ({\sf Gen'}, {\sf
Enc'}, {\sf Dec'}) \) is a secure MAC scheme, then the above AE constuction
is IND-CCA secure.
AE: GCM mode
Galois/Counter Mode
(GCM) is a mode of operation for symmetric-key cryptographic
block ciphers which is widely adopted for its performance. The details of this
mode is beyond the scope of this course.
AES-GCM is IND-CCA secure.
See the following code to see how this mode is used in python3.
pip3 install pycryptodomex --user
#!/usr/bin/python3
from Cryptodome.Cipher import AES
key = bytes.fromhex("000102030405060708090a0b0c0d0e0f")
iv = bytes.fromhex("00112233445566778899aabbccddeeff")
# encryption
cipher = AES.new(key, AES.MODE_GCM, iv)
cipher.update(b"auth header")
data = b"let's encrypt this message"
(ct, tag) = cipher.encrypt_and_digest(data)
print("ct=", ct.hex())
print("tag=", tag.hex())
# decryption
cipher2 = AES.new(key, AES.MODE_GCM, iv)
cipher2.update(b"auth header")
dec = cipher2.decrypt_and_verify(ct, tag)
print("dec=", dec)