Authentication Functions: Encryption, MAC and Hash
Chapter Forty-Three
Syllabus topic Module 1, "Message Authentication and Hash Functions: Authentication Functions"
Pages 260 to 264 of 678
In one line
There are three ways to produce an authenticator: encrypt the message, compute a keyed tag, or compute an unkeyed digest and protect it. Each gives a different set of services, and only the second and third are called message authentication.
In the wording a student can write in an examination: an authenticator is a value to be used to authenticate a message. The functions that produce one fall into three classes: message encryption, in which the ciphertext of the entire message serves as its authenticator; a message authentication code, a fixed-length value computed from the message and a secret key; and a hash function, a function mapping a message of any length to a fixed-length hash value, which serves as the authenticator once it is itself protected.
Class 1: message encryption
The idea is that if the message decrypts to something sensible, it must have been encrypted by somebody holding the key, so it is authentic. The idea is nearly right and the gap is the whole topic.
With a symmetric key
Asha encrypts the message with the key she shares with Bharat. Bharat decrypts it. Nobody else can have produced a ciphertext that decrypts sensibly, so the message is confidential and apparently authenticated.
The gap: how does Bharat know the decryption is correct? If the plaintext is an arbitrary binary file, then every ciphertext decrypts to some binary file, and Bharat has no way to tell the one Asha sent from one an attacker made up. Authentication requires that Bharat be able to recognise a valid plaintext.
Two answers, and the difference between them matters.
Internal error control. Compute a checksum or frame check sequence over the plaintext, append it to the plaintext, and encrypt the whole thing. The receiver decrypts and checks. This works, because an attacker who alters the ciphertext produces a plaintext whose checksum will not match.
External error control. Compute the checksum over the ciphertext and append it outside the encryption. This does not authenticate, because an attacker can construct any ciphertext they like and compute a correct checksum over it. The receiver's check passes and the plaintext is rubbish, or worse, is something the attacker chose.
So the order matters, and it is examinable: the error-control value must be computed on the plaintext and encrypted with it. That is the same lesson as the CBC bit-flipping chapter in a different form.
With a public key
Asha encrypts with Bharat's public key. This gives confidentiality only, and no authentication at all, because Bharat's public key is public and anybody could have sent it.
For authentication, Asha encrypts with her own private key, which anybody can undo with her public key. That gives authentication and a signature and no confidentiality.
Authentication Functions: Encryption, MAC and Hash
For both, Asha signs with her private key and then encrypts with Bharat's public key. Four public-key operations for one message, which is why the hash-based arrangement of the next section is used instead.
Class 2: a message authentication code
A fixed-length tag computed from the message and a shared secret key, appended to the message and checked by recomputation. The next chapter is about it.
What it gives. Authentication, and integrity, and nothing else. The message is not encrypted, which is often exactly what is wanted: a public announcement that must be provably from its source.
Three arrangements.
Message plus tag, unencrypted. Authentication only.
Tag computed on the plaintext, then the whole thing encrypted. Authentication and confidentiality, with the authentication tied to the plaintext.
Message encrypted, then a tag computed on the ciphertext. Authentication and confidentiality, with the authentication tied to the ciphertext. This is the arrangement modern protocols prefer, because the receiver can check the tag before decrypting and so need never process an attacker's ciphertext at all. It is called encrypt-then-MAC.
Class 3: a hash function
A hash takes a message of any length and produces a fixed-length digest, with no key. So a bare digest authenticates nothing: an attacker who alters the message recomputes the digest.
The digest must therefore be protected, and there are four ways.
- Encrypt the message and the digest together with a shared key. Confidentiality and authentication.
- Encrypt only the digest with a shared key. Authentication, no confidentiality, and much cheaper than encrypting the whole message.
- Encrypt only the digest with the sender's private key. Authentication and a digital signature. This is what every signature scheme in Module 2 does.
- Encrypt only the digest with the sender's private key, then encrypt the lot with a shared key. All three services.
And the fifth, which needs no encryption at all: append a shared secret to the message, hash the result, and send the message with that digest. Nobody without the secret can compute the digest. That is the idea HMAC makes safe, and the HMAC chapter shows why the naive version of it is forgeable.
Worked example: choosing an arrangement
Case 1: a public examination timetable on a college website. Everybody may read it and nobody may alter it. Hash the timetable and sign the digest with the college's private key. No encryption at all, because there is nothing to hide. Anybody can verify.
Case 2: a marks file between two offices that share a key. Confidential and authenticated, and no third party need be convinced. Encrypt with AES, then compute a MAC over the ciphertext. Encrypt-then-MAC, so a forged ciphertext is rejected before decryption.
Authentication Functions: Encryption, MAC and Hash
Case 3: a payment instruction that the bank must be able to prove came from the college. Non-repudiation is required, so a MAC will not do. Hash, sign the digest with the college's private key, and encrypt the result with the bank's public key. Two public-key operations on short values and one symmetric encryption of the message.
Case 4: a broadcast to two thousand students. A signature, because a shared key would have to be shared with all two thousand, and then any of them could forge a broadcast.
The step that carries the marks. In each case, naming which services are needed first and then choosing the arrangement, rather than choosing a mechanism and describing what it happens to give.
Distinctions that carry marks
| Arrangement | Confidentiality | Authentication | Signature |
|---|---|---|---|
| Symmetric encryption of the message, with internal error control | yes | yes | no |
| Symmetric encryption, with external error control | yes | no | no |
| Public-key encryption with the receiver's public key | yes | no | no |
| Encryption with the sender's private key | no | yes | yes |
| Sign, then encrypt to the receiver | yes | yes | yes |
| Message plus MAC, unencrypted | no | yes | no |
| MAC on the plaintext, then encrypt | yes | yes | no |
| Encrypt, then MAC on the ciphertext | yes | yes | no |
| Hash, then encrypt both with a shared key | yes | yes | no |
| Hash, then encrypt the digest with a shared key | no | yes | no |
| Hash, then encrypt the digest with the private key | no | yes | yes |
| Message plus hash of (message plus a shared secret) | no | yes | no |
| Internal error control | External error control | |
|---|---|---|
| The check value is computed on | the plaintext | the ciphertext |
| Then | encrypted with the message | appended outside |
| Authenticates | yes | no |
| Because | an altered ciphertext gives a plaintext whose check fails | an attacker can compute a correct check over any ciphertext |
What beginners get wrong here
Saying encryption authenticates. It authenticates only if the receiver can recognise a valid plaintext, which needs internal error control or naturally structured data.
Confusing internal and external error control. Internal works; external does not. The check value goes inside the encryption.
Saying public-key encryption authenticates. Encrypting with the receiver's public key authenticates nothing, because the key is public.
Encrypting the whole message to authenticate it when a digest would do. Hashing and protecting the digest is far cheaper and is what every real protocol does.
Thinking a bare hash authenticates. It has no key. The digest must be encrypted, signed, or computed over the message plus a secret.
Quick revision
- Three classes of authentication function: message encryption, a message authentication code, and a hash function whose digest is then protected.
- Encryption authenticates only if the receiver can recognise a valid plaintext. Hence internal error control (check value on the plaintext, encrypted with it) works, and external error control (check value on the ciphertext) does not.
- Public-key encryption with the receiver's public key gives confidentiality and no authentication. With the sender's private key it gives authentication and a signature and no confidentiality.
- A MAC gives authentication and integrity and no confidentiality. Encrypt-then-MAC is preferred, because the tag can be checked before decrypting.
- A bare hash authenticates nothing; the digest must be encrypted with a shared key, signed with a private key, or computed over the message plus a shared secret.
- Hash then sign the digest is what every signature scheme does, because it signs a short fixed-length value instead of the message.
Authentication Functions: Encryption, MAC and Hash
Test yourself
1. Name the three classes of authentication function. Message encryption, where the ciphertext of the whole message is the authenticator; a message authentication code, a fixed-length value computed from the message and a secret key; and a hash function, whose fixed-length digest becomes an authenticator once it is itself protected.
2. Why does symmetric encryption not by itself authenticate a message? Because the receiver must be able to tell a correct decryption from an incorrect one. If the plaintext is arbitrary binary data then every ciphertext decrypts to some plausible-looking plaintext, and the receiver cannot distinguish the sender's message from an attacker's invention. The plaintext must therefore carry recognisable structure, which is what a check value supplies.
3. Distinguish internal from external error control and say which authenticates. Internal error control computes a check value over the plaintext, appends it to the plaintext, and encrypts both; the receiver decrypts and verifies, so any alteration of the ciphertext produces a plaintext whose check value fails. External error control computes the check value over the ciphertext and appends it outside the encryption; an attacker can fabricate any ciphertext and compute a correct check value over it, so the check passes and nothing is authenticated. Only internal error control authenticates.
4. What does encrypting with the receiver's public key provide, and what does encrypting with the sender's private key provide? Encrypting with the receiver's public key provides confidentiality only, because anybody can use a public key, so the message proves nothing about its origin. Encrypting with the sender's private key provides authentication and a digital signature, because only the sender could have produced it, but no confidentiality, since anybody can undo it with the public key.
5. What is encrypt-then-MAC and why is it preferred? The message is encrypted and the message authentication code is then computed over the ciphertext. It is preferred because the receiver can verify the tag before decrypting, so a forged or altered ciphertext is rejected without ever being processed by the decryption routine, which removes a whole class of attacks that exploit the decryption of attacker-chosen data.
Authentication Functions: Encryption, MAC and Hash
6. Why does a bare hash value not authenticate a message? Because a hash function takes no key, so an attacker who alters the message simply recomputes the digest and sends the pair. The digest must be protected: encrypted with a shared key, encrypted with the sender's private key, or computed over the message concatenated with a shared secret.
7. Give the arrangement that provides confidentiality, authentication and a digital signature, and say why the digest is used. Hash the message, encrypt the digest with the sender's private key to form the signature, then encrypt the message and signature together with a key shared with the receiver, or with the receiver's public key. The digest is used because public-key operations are expensive and limited in size, so signing a short fixed-length value rather than the whole message makes the scheme practical.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.