Home | Cryptography by Hand | Prev | Next
·
|
December 30 2024
Home | Cryptography by Hand | Prev | Next
·
|
Now that we know what message authentication codes (MACs) are, we'll start with a MAC that's easy to do by hand and provides moderate assurance. It's based on an algorithm called Encrypt-Last-Block Cipher Block Chaining MAC (ECBC-MAC).
You need two copies of a MAC key: One copy for you and one for your partner. The key has one or more random permutations of the digits 0 to 9 (that is, the digits 0 to 9 shuffled). Here is an example with three permutations:
MAC Key p1: 0 8 4 2 3 1 5 7 9 6 p2: 9 8 2 5 4 6 1 0 7 3 p3: 4 7 8 3 1 0 6 2 9 5
Additionally, you must create p random digits for every message you intend to sign with your MAC key, where p is the number of permutations the MAC key has. If you encrypt messages using the one-time pad, you can conveniently write these groups of p digits on the bottoms and backs of your one-time pad encryption keys. For ease, label the p digits z1, z2, and so on to zp. For example, if your MAC key has three permutations, the bottom or back of a one-time pad encryption key might contain:
z1: 4 z2: 0 z3: 7
Another one-time pad encryption key might contain:
z1: 6 z2: 2 z3: 2
Different one-time pad encryption keys MUST have their own random z numbers.
The probability that a message is genuine depends on how many permutations its MAC key has. If an attacker changes a single message digit:
| Number of Permutations | Probability the Change Goes Unnoticed |
|---|---|
| 1 | 11.111% |
| 2 | 1.235% |
| 3 | 0.137% |
| 4 | 0.015% |
| 5 | 0.002% |
| ... | ... |
| p | (1/9)p |
If the attacker changes multiple message digits:
| Number of Permutations | Probability the Change Goes Unnoticed |
|---|---|
| 1 | 10.000% |
| 2 | 1.000% |
| 3 | 0.100% |
| 4 | 0.010% |
| 5 | 0.001% |
| ... | ... |
| p | (1/10)p |
MAC keys contain random permutations of the digits 0 to 9, inclusive. There are two easy ways to create such permutations: poker cards and 10-sided dice. Either way, you'll also need a piece of paper and a pen or pencil.
To create a random permutation with a deck of poker cards:
For example, drawing these cards:
creates the permutation 4 0 8 3 1 7 9 6 2 5.
To create a random permutation with a 10-sided die:
For example, your sheet of paper starts out looking like this:
0 1 2 3 4 5 6 7 8 9
If your first roll of the die shows 4, you would cross 4 out and append it to the permutation:
0 1 2 3 - 5 6 7 8 9 4
If the next die roll shows 0, you would cross 0 out and append it to the permutation:
- 1 2 3 - 5 6 7 8 9 4 0
If the next die roll shows 4, you would roll again because 4 is already crossed out. If the re-roll shows 8, you would cross 8 out and append it to the permutation:
- 1 2 3 - 5 6 7 - 9 4 0 8
And so on. The final permutation might look like 4 0 8 3 1 7 9 6 2 5.
There are ways to speed this process up. You could use other means, such as picking numbered balls out of a basket. Whichever method you use, every permutation must be equally likely.
Once you and your partner have a MAC key, sign (add a MAC to) a message thus:
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.)
Suppose your MAC key is:
MAC Key p1: 0 8 4 2 3 1 5 7 9 6 p2: 9 8 2 5 4 6 1 0 7 3 p3: 4 7 8 3 1 0 6 2 9 5
Suppose further that the encryption key you used contains these z numbers:
z1: 4 z2: 0 z3: 7
To ease step 3, copy the encrypted message (plus the key ID) to your scratch paper, but leave space underneath it for your signing calculations.
The MAC key has three permutations, so we'll do step 3 three times, once for each permutation. For the first permuatation (p = 1), we start by writing 0 on the scratch paper underneath and just to the left of the encrypted message:
21956 85864 91266 53163 62122 0
For step 3.2, read the encrypted message's digits from left to right (first to last). The first is 2:
21956 85864 91266 53163 62122 0
so for step 3.2.1, calculate 0 + 2 modulo 10. The result is 2, so find the permutation's 3rd digit. (Remember, the permutation's digits start at index 0, so 2 means the 3rd digit.) The permutation's 3rd digit is 4, so write it underneath the 2 in the encrypted message:
21956 85864 91266 53163 62122 04
The encrypted message's next digit is 1. 4 + 1 modulo 10 is 5, so find the permutation's 6th digit, which is 1. Write it underneath the 1 in the encrypted message:
21956 85864 91266 53163 62122 041
The encrypted message's next digit is 9. 1 + 9 modulo 10 is 0, so find the permutation's 1st digit, which is 0. Write it underneath the 9 in the encrypted message:
21956 85864 91266 53163 62122 0410
Repeat this process (step 3.2) until you go through all of the encrypted message's digits. Your scratch paper should look like this:
21956 85864 91266 53163 62122 041017 15292 86917 47913 69045
Notice that the final result is 5. For step 3.3, find z1 on the encryption key, which is 4, and add it to the final result 5, modulo 10, which is 9. Thus 9 is the first digit of the message's MAC:
21956 85864 91266 53163 62122 041017 15292 86917 47913 69045 9
We've only used the first permutation. Repeat step 3 for the second and third permutations. Your scratch paper should look like this:
21956 85864 91266 53163 62122 041017 15292 86917 47913 69045 9 025433 85582 83627 26014 98367 7 085168 67064 31357 87903 52308 5
The encrypted message's MAC is 975. Include it with the message, but clearly separate it so your partner knows it's the MAC:
21956 85864 91266 53163 62122
MAC 975
Then burn the scratch paper and encryption key.
When you receive a signed encrypted message, verify it thus:
Encrypt-Last-Block Cipher Block Chaining MAC (ECBC-MAC), which underpins this MAC procedure, is provably secure even when attackers have infinite time and resources. I won't show proofs here because they're complicated, but if you're curious, read these papers:
According to the papers, when considering a single permutation in the MAC key, attackers have an advantage of 3q2m2/2l+1 over simply guessing the permutation, where:
(m and l are actually bits instead of digits, but this is irrelevant for our purposes.)
An oracle query is security-speak for tricking you into calculating and revealing a MAC for a message of the attacker's choice. If attackers see multiple MACs produced by the same MAC key, they might gather clues about the key's contents, giving them tremendous advantage over purely guessing.
However, short of capturing you, attackers cannot make oracle queries for your MAC key. True, you use the same key for multiple messages, but you encrypt each message's MAC with its own random z numbers (a one-time pad key, which you never reuse). Therefore, q = 0, which means attackers must either guess the key's permutations (absurdly unlikely) or fake MACs when they alter your messages (doable, but still hard). Either way, it's pure guesswork.
If an attacker alters a message, he must correctly guess the new message's MAC to deceive the receiver. His chances depend on how he alters the message:
Each set of z numbers is a one-time pad key for a MAC. Even if you use the same MAC key for identical messages, each message gets its own z numbers, which produce different MACs. Attackers cannot determine the values that the z numbers encrypt, so you can sign as many messages as you want with the same MAC key.