The idea
Locking a message does not stop someone changing it. An attacker who cannot read the ciphertext may still alter it, and the lecture says plainly that encryption and decryption give confidentiality, not integrity.
What you want for integrity is a short fingerprint of the message. If the fingerprint matches after delivery, the message is the one that was sent. Public-key encrypting a long message would be far too slow, so instead you squeeze the message down to a fixed-size digest and protect that. A hash function does the squeezing.
How it works
Message integrity and the digest
The lecture defines integrity as: no one can tamper with the message or forge it. One way to preserve it is to use a hash function to create a message digest of the message. The digest is a compressed image of the message that can be used like a fingerprint. It is also known as a Modification Detection Code (MDC).
The slide on integrity checking has a figure with an insecure channel and a channel immune to change, and the message arriving unaltered. The figure extracted to labels only.
How it works
Hash functions
The goal is a fixed-length, easy-to-compute digital fingerprint. Apply a hash function H to a large message m and get a fixed-size message digest H(m). The lecture lists three properties.
- Many-to-1. Many messages share the same digest.
- Fixed-size output. It produces a fixed-size message digest, the fingerprint.
- One-way. Given a message digest
x, it is computationally infeasible to find anmsuch thatx = H(m).
How it works
Example: the internet checksum as a poor hash
The internet checksum has some properties of a hash function. It produces a fixed-length digest (a 16-bit sum) of the message, and it is many-to-one. But given a message with a given hash value, it is easy to find another message with the same hash value.
Worked example
Two different messages with identical checksums
Message 1,
IOU1,00.9,9BOB, in ASCII hexadecimal:49 4F 55 31,30 30 2E 39,39 42 4F 42.Message 2,
IOU9,00.1,9BOB:49 4F 55 39,30 30 2E 31,39 42 4F 42.Compare: only two bytes differ in the first two rows. Message 1 has
31in the first row and39in the second. Message 2 has them the other way round.Why the sum is unchanged: the same two byte values,
31and39, sit in the same byte position in both messages, only in different rows. Addition does not care which row holds which, so any sum over the rows is identical. As a check on 16-bit words,5531 + 2E39=836Aand5539 + 2E31=836A.Conclusion: the messages differ but the checksums are identical. An attacker who knows message 1 can build message 2 by swapping two characters.
AnswerIOU1 00.9 9BOB and IOU9 00.1 9BOB both give the checksum B2 C1 D2 AC.
Summing each byte column of the three rows gives the slide’s checksum: 49 + 30 + 39 = B2, 4F + 30 + 42 = C1, 55 + 2E + 4F = D2, 31 + 39 + 42 = AC.
How it works
Hash function algorithms
- MD5 is widely used (RFC 1321). It computes a 128-bit message digest in a 4-step process. For an arbitrary 128-bit string
x, it appears difficult to construct a messagemwhose MD5 hash equalsx. - SHA-1 is also used. It is a US standard [NIST, FIPS PUB 180-1] with a 160-bit message digest.
How it works
From digest to MAC
A hash guarantees the message has not been changed. It does not authenticate the sender. One way to fix that is to change the MDC into a Message Authentication Code (MAC).
A MAC uses a keyed hash function: a symmetric key is used when creating the digest. The sender sends the message together with its MAC (the slide label is “M + MAC”) across the insecure channel. The receiver recomputes the MAC with the same key. If the MAC matches, the message can be authenticated.
Where marks get lost
A plain digest can be replaced along with the message
If Mallory can change the message, she can recompute an unkeyed digest to match. Only a keyed digest stops her, because she does not have the key. This is why the lecture moves from MDC to MAC for authentication.
In the exam
- Encryption gives confidentiality, not integrity. Hashing gives integrity. A MAC adds authentication.
- The three hash properties: many-to-1, fixed-size output, and infeasible to find
mfromx. - MD5 is 128 bits (RFC 1321, 4 steps). SHA-1 is 160 bits (FIPS PUB 180-1).
- Be ready to explain the IOU1 and IOU9 example in a sentence: different messages, same checksum, easily constructed.
Aside
Two points where the lecture and current practice differ
The slide on integrity states “Message digest must be kept secret and must be encrypted when sent through a communication channel”. A plain digest is a public fingerprint, and the protection comes from sending it over a channel the attacker cannot alter or from keying it, so the statement is loose. The lecture also presents MD5 and SHA-1 without saying that collisions have since been found in both, so neither is regarded as safe for new designs. The lecture’s wording is kept as the exam answer.
Check yourself
- Encryption alone does not protect against modification.
- A digest is a fixed-size, many-to-1, one-way fingerprint of the message.
- The internet checksum fails because a second message with the same checksum is easy to find.
- MD5 gives 128 bits and SHA-1 gives 160 bits.
- A MAC is a keyed hash. A matching MAC authenticates the message.