Message Authentication Codes

May 9 2023 Home | Cryptography by Hand | Prev | Next ·

Previously, we learned how to use one-time pads to encrypt and decrypt messages. One-time pads are powerful because they provide perfect secrecy: Encrypted messages are forever indecipherable to people who don't know (and can't guess) the message's secret keys.

However, one of the one-time pad's biggest weaknesses is its vulnerability to modification, also known as malleability. For example, if an attacker intercepts the one-time-pad-encrypted message "send $500 to me" and knows or can guess its structure or decrypted contents, the attacker can change the message to "send $999 to me", "burn your money", or any message of the same length or shorter, and send the modified message to the intended recipient. The recipient would decrypt the message but have no idea that its contents were changed.

Similarly, if the way you send encrypted messages is noisy or likely to accidentally alter your messages, the messages could get delivered with errors — a changed digit here or there. The recipient could still decrypt the messages, but they might contain nonsense. He couldn't determine whether the garbage was intentional or due to errors.

Message authentication codes (MACs) can prove (with high probability) that messages are authentic — that they have been neither tampered with nor corrupted during transmission. MACs are numbers (also called "tags") attached to messages. Recipients verify messages (check their authenticity) by recreating their MACs and comparing them to the attached MACs.

There are numerous MAC algorithms with different security guarantees. I'll describe one with excellent guarantees that you can do by hand. Unfortunately, authentication (checking whether messages are authentic) is not as straightforward as encryption: It requries long multiplication and division. You can use calculators and other aids if you wish.

• How MACs Work
• MACs Cannot Guarantee Authenticity
• When to Use MACs
• Creating Keys
  • Choosing Key Security Parameters
  • Generating Your Key's Random Numbers
    • Dice Notation
    • Generating Random Numbers for Different Security Parameters
  • An Example MAC Key
  • Making MAC Keys Infinitely Reusable
• Signing Encrypted Messages
• Verifying Received Messages
• Why MACs Work
• Example Programs
  • Python
  • dc(1)

Generally speaking, a message authentication code (MAC) is a number (a "tag") attached to a message. Generating and verifying a MAC requires a secret MAC key known only to a message's sender and receiver. Like one-time pad keys, MAC keys must be random and must remain absolutely secret.

When a sender wishes to send a message, he:

1. encrypts the message (using the one-time pad, for example)
2. selects a MAC key that the recipient knows
3. computes the encrypted message's MAC using the MAC key and the ciphertext; and
4. attaches the MAC to the ciphertext.

Calculating and attaching a MAC to a message is called signing.

When a person wishes to verify a received message, he:

1. selects the same MAC key that the sender used (this could be by prior agreement or indicated by a MAC key ID printed on the encryption key or in the message)
2. computes the encrypted message's MAC using the MAC key and the ciphertext; and
3. compares the result to the message's attached MAC.

If the MAC the recipient calculated matches the one attached to the message, the message is probably authentic; otherwise, the message has been altered or the sender or the receiver made a mistake calculating the MAC.

When authenticating a one-time-pad-encrypted message, the encryption key's ID is considered part of the encrypted message, so you must count its digits when deciding m. Your choices will determine attackers' chances of successfully forging messages (creating messages with correct MACs attached).

Here are five suggested prime numbers for p for different block sizes b:

Remember, p must be at least two greater than m.

Given m and p, the probability that a message you receive is authentic is:

Equivalently, the probability that an attacker can successfully forge a message without being discovered is 1 minus that formula, or:

Here are some values for P_a(m, p) for different values of m and p:

After you choose b, m, and p for your key, you have to generate 2 + log₂ m random numbers for your key. This section explains how to generate these numbers.

After choosing b, m, and p for your key, generate the following numbers randomly, all of which must be between 0 and p-1, inclusive:

• an integer q
• an integer r; and
• log₂ m integers labeled from 1 to log₂ m.

If p is one of the primes I suggested earlier, use the dice notation formulas in this table to generate the numbers:

The random numbers must be less than p. If you generated a number that is p or greater, try again.

MAC keys created using the procedure above can only be used once (like a one-time pad encryption key). To make it infinitely reusable, you must generate a random number between 0 and p-1, inclusive, for each message you send. (Use the random number generation procedure above.) Both the sender and receiver must know these numbers. If you encrypt messages using the one-time pad, the best place to write these numbers is on the bottoms or backs of encryption keys. Clearly separate these random numbers from the encryption keys' digits. For ease, label each such random number "z". For example, the bottom or back of a one-time pad encryption key might say "z = 755" if its random number is 755.

The following instructions assume your MAC key is formatted like the example MAC key in the "Creating Keys" section. Adapt the instructions to your keys as necessary.

To sign (add a MAC to) a message:

1. Encrypt your secret message as usual, but don't burn the encryption key until you've completed this procedure.
2. Copy the message you'll send (the result of step (1) above) to a piece of scratch paper. Use the scratch paper in steps (3) to (8) below.
3. Let b be the MAC key's block size (in digits). If the total number of digits in the copied message isn't evenly divisible by b, append "1" plus as many 0's as necessary to the end of the copy to make the total number of digits evenly divisible by b. On the other hand, if it's already evenly divisible by b, append "1" followed by b-1 0's. Examples:
   • If b = 3 and the message is "184 521 986 266 9" (13 digits), append "10" to the end of the message copy to make it "184 521 986 266 910".
   • If b = 3 and the message is "184 521 986 266 90" (14 digits), append "1" to the end of the message copy to make it "184 521 986 266 901".
   • If b = 3 and the message is "184 521 986 266 900" (15 digits), append "100" to the end of the message copy to make it "184 521 986 266 900 100".
4. Group the copied message's digits into groups of b digits. Include the appended digits from step (3) above when you do this.
5. Count the number of groups of b digits from the previous step. Prepend this count to your groups. For example, if your groups are "184 521 986 266" (four groups), prepend "004" so that your groups become "004 184 521 986 266".
6. Treat each group of b digits as an integer. Let n be 1. Repeat these steps until there is only one integer left:
   1. If the number of integers is odd, put a 0 at the end of your list. For example, if your list of integers is "004 184 521 986 266" (five integers), make it "004 184 521 986 266 0" (six integers). The number of integers should be even now.
   2. Group adjacent integers into pairs starting from the left. For example, if your integers are "004 184 521 986 266 0", form the groups (4, 184), (521, 986), and (266, 0).
   3. Find the nth random number below b, p, q, and r in your MAC key. If n is 1, the random number should be labeled "1:"; if n is 2, it should be labeled "2:"; and so on. Call this nth random number x.
   4. Replace each pair of integers with (ax + b) mod p, where a and b are the pair's first and second integers, respectively, and p is the MAC key's prime number. This should leave you with half as many integers as before.
   5. Increment n by one.
7. Now there should be only one integer left. Call this integer x. Let q and r be the random numbers labeled "q" and "r" in your MAC key, respectively. Compute (qx + r) mod p. Call the result y.
8. Find the random number labeled "z" on the bottom or back of your encryption key. Calculate (y + z) mod p. The result is the message's MAC.
9. Send the message from step (1) and the MAC in that order. Obviously, don't label the parts of your message as such! Clearly separate the MAC from the rest of the message so that the recipient knows it's a MAC.
10. Burn the encryption key and your scratch paper. You can reuse your MAC key for future messages.

For example, suppose you encrypt a message using the one-time pad. The resulting message is:

21956 85864 91266 53163 62122

(This message includes the encryption key's ID, 21956.)

To sign the message, pick a MAC key. Suppose the MAC key is:

     MAC Key
  block size: 3
    p = 1009

q = 212   r = 132

1: 206     5: 729
2: 365     6: 736
3: 990     7: 208
4: 472     8: 207

For step (2), copy the message to a piece of scratch paper.

For step (3), count the number of digits in the copied message. There are 25. This isn't evenly divisible by the MAC key's block size, b = 3; therefore, append "10" to the copied message so that the number of digits is 27, which is divisible by 3. Your scratch paper now looks like this:

21956 85864 91266 53163 62122 10

For step (4), group these digits into groups of 3 digits (because the MAC key's block size is b = 3 digits). Your scratch paper should have a line like this:

219 568 586 491 266 531 636 212 210

For step (5), count the number of groups. There are 9 groups, so prepend "009" to the list. Your scratch paper should look like this:

009 219 568 586 491 266 531 636 212 210

For step (6), treat the groups of 3 digits as integers. There are 10 integers. 10 is not 1, so you have to do step (6)'s sub-steps. Write "n = 1" on your scratch paper and do the following:

For step (6)(A), there are 10 integers, which is even. So don't add a 0 to the end of the list.

For step (6)(B), group the integers into pairs:

(9 219) (568 586) (491 266) (531 636) (212 210)

For step (6)(C), find the random integer labeled "1:" on the MAC key (because n = 1), which is 206.

For step (6)(D), noting that the MAC key says that p = 1009, replace each pair of integers with (206a + b) mod 1009, where a and b are the pair's first and second integers, respectively:

(9 219) (568 586) (491 266) (531 636) (212 210)
  55       550       512       41        495

For step (6)(E), increment n by one and write "n = 2" on your scratch paper.

There are now 5 integers — half as many as before. You still have more than one integer, so repeat step (6)'s sub-steps:

For step (6)(A), there are 5 integers, which is odd. So append 0 to the end of the list of integers:

55 550 512 41 495 0

For step (6)(B), group the integers into pairs:

(55 550) (512 41) (495 0)

For step (6)(C), find the random integer labeled "2:" on the MAC key (because n = 2), which is 365.

For step (6)(D), noting that the MAC key says that p = 1009, replace each pair of integers with (365a + b) mod 1009, where a and b are the pair's first and second integers, respectively:

(55 550) (512 41) (495 0)
  445       256      64

For step (6)(E), increment n by one and write "n = 3" on your scratch paper.

There are now 3 integers. You still have more than one integer, so repeat step (6)'s sub-steps:

For step (6)(A), there are 3 integers, which is odd. So append 0 to the end of the list of integers:

445 256 64 0

For step (6)(B), group the integers into pairs:

(445 256) (64 0)

For step (6)(C), find the random integer labeled "3:" on the MAC key (because n = 3), which is 990.

For step (6)(D), noting that the MAC key says that p = 1009, replace each pair of integers with (990a + b) mod 1009, where a and b are the pair's first and second integers, respectively:

(445 256) (64 0)
   882      802

For step (6)(E), increment n by one and write "n = 4" on your scratch paper.

There are now 2 integers. You still have more than one integer, so repeat step (6)'s sub-steps:

For step (6)(A), there are 2 integers, which is even. So don't add a 0 to the end of the list.

For step (6)(B), group the integers into pairs:

(882 802)

For step (6)(C), find the random integer labeled "4:" on the MAC key (because n = 4), which is 472.

For step (6)(D), noting that the MAC key says that p = 1009, replace each pair of integers with (472a + b) mod 1009, where a and b are the pair's first and second integers, respectively:

(882 802)
   389

For step (6)(E), increment n by one and write "n = 5" on your scratch paper.

Now you have one integer: 389. Proceed to step (7), which tells you to find the "q" and "r" integers on the MAC key. They are q = 212 and r = 132. Compute y = (389q + r) mod 1009 = (389 × 212 + 132) mod 1009 = 871.

For step (8), locate the number labeled "z" on the encryption key you used. Suppose z = 751. Calculate (y + z) mod 1009 = (871 + 751) mod 1009 = 613. This is the message's MAC.

For step (9), send this message to your partner, with the MAC clearly distinguished from the rest of the message (so the recipient knows it's the MAC):

21956 85864 91266 53163 62122 613

Finally, following step (10), burn the encryption key and the scratch paper. Keep the MAC key for future use.

The following instructions assume your MAC key is formatted like the example in the "Creating Keys" section. Adapt the instructions to your keys as necessary.

To verify (check the MAC attached to) a message you've received:

1. Follow this procedure before you decrypt the message.
2. Find the message's attached MAC and separate it from the rest of the message. Call the message's attached MAC t_a. Ignore it in step (3) below.
3. Follow steps (2) to (8) from the signing procedure to calculate the message's MAC. Call the MAC you calculate t_c.
4. Compare t_a and t_c:
   1. If they match, then the message's MAC is correct and you can be confident that the message is authentic. Decrypt the message as usual.
   2. If they don't match, ignore the message. You cannot trust it because either:
      1. you made a mistake calculating its MAC t_c (you should try again)
      2. the sender made a mistake calculating the message's MAC (t_a)
      3. someone other than your partner wrote the message; or
      4. the message was modified or corrupted in transit.
5. Burn the encryption key and the scratch paper you used to calculate t_c. Do this regardless of step (4)'s outcome.

You could ignore a message's MAC and simply decrypt the message: You don't need to verify a message to decrypt it. However, ignoring MACs means that you won't know for sure whether messages are genuine and unaltered. If message forgery or corruption is highly unlikely, this might be acceptable. The choice is yours.

The mathematical proof for this MAC procedure is far more complex than the one for encryption via one-time pads. I won't outline it here, but it's based on Theorem 6.2 from D. R. Stinson, "Universal hashing and authentication codes," 1992; read that if you want a detailed proof and background reading.

The additional random z number acts like a one-time pad for the MAC, making the otherwise limited-use MAC key infinitely reusable (assuming each encrypted message has its own random z value). The aforementioned paper by D. R. Stinson does not mention z.