I don’t have a lot of time to write; I’m having my fifth (I think) upper endoscopy done tomorrow, which means that the day’s going to be a wash; and Yom Kippur is thursday, and I need to cook, so between the personal crap and work, I’m not going to have much time for blogging. So I’m trying to make use of the time I have to write one short but (hopefully) interesting post.
One thing that I’ve mentioned in passing is the distinction between message confidentiality, and message integrity.
Confidentiality is most of what we’ve been talking about
so far. Confidentially provides a guarantee that when you send an encrypted message, no one but your intended recipient is able
to read the plaintext.
Integrity is something very different. Integrity guarantees
that if you send an encrypted message, there’s no way that the encrypted message could have been tampered with after you encrypted it, without the recipient knowing it.
Suppose you’re using CBC mode for a message in DES, and you’ve
got an attacker who wants to screw up your message. What happens if the attacker flips a couple of bits in one block? First, the plaintext for that block will be corrupted. Second, the
ciphertext for that block is used for decrypting the next block – so the plaintext for the next block will also be corrupted.
Can you tell that there was a corruption in the message? If the plaintext was something like human language, you can see that it makes no sense. But that’s relying on our meta-knowledge about
the structure/nature of the plaintext. In fact, just looking at
the encrypted message, there is no possible way for us to detect tampering!
In CBC mode – and in fact in all of the modes we’ve looked at, an attacker can change bits of the ciphertext, corrupting the message, and we can’t tell. That’s why we say that
these modes of operation can’t provide any guarantees of message
How can we get around that? The easiest thing is to add something called a message authentication code (MAC).
A MAC is basically a hash-code: a short string appended to the
message which in some way summarizes the message, so that if any
part of the message was changed, the MAC will not match the message, and so we’ll know that the message was corrupted.
It’s easiest to understand the MAC using a bit of notation:
Mac = M(T, K), where “M” is the MAC function, T is the plaintext of the message, and K is an encryption key. So you take your plaintext and your key, feed it to M, and get back a short string which is the MAC for your message.
MAC functions need to have some basic properties to be
successful in protecting integrity:
- Changing a single bit of the input message must produce
a significant change in the MAC.
- Given a MAC value V, a MAC function M, and a key K, it must be difficult to compute a plaintext T where M(T,K)=V.
- Given an oracle O(T) which computes M(T,K), and the
ability to compute O(T) for an arbitrary set of chosen
plaintexts, it must be difficult to guess the MAC for a
particular message without submitting it to O. (That is, even
in the scenario of a ideal chosen plaintext attack,
where you can choose any set of messages you want, and
get the MAC for those messages, that won’t help you to guess
the MAC of any message outside of that set.)
- Given a message T, it must be difficult to find a message
U such that M(T,K)=M(U,K).
If you’re familiar with digital signatures, some of this
should be ringing bells. The idea of a digital signature is very
close to this. The main difference is that a digital signature
is asymmetric: the sender and the receiver have different keys. The sender has a private key, and signs the message;
everyone else has a public key, and can verify that the sender
signed the message. With MACs, both the sender and the receiver have the same key. MACs provide no guarantee of who originated the message; they just guarantee that the message
wasn’t changed between the time it was encrypted by the sender
and decrypted by the reciever.
Next post, I’ll go through one or two MAC algorithms, and then talk about modes of operation that incorporate MAC-like integrity