Home | Cryptography by Hand | Prev | Next
·
|
December 30 2024
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 two with excellent guarantees that you can do by hand.
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:
Calculating and attaching a MAC to a message is called signing.
When a person wishes to verify a received message, he:
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.
One-time pads guarantee perfect secrecy (when used correctly): Attackers cannot decrypt messages without knowing their secret keys.
However, MACs cannot 100% guarantee that messages are authentic. Even if attackers can't guess a message's secret MAC key (the key used to generate the message's MAC), they can always intercept the message, change it and its attached MAC, send the modified message along, and hope that they guessed the modified message's MAC correctly. If they do, the recipient will think the modified message is authentic. Thus no MAC can guarantee 100% certainty.
However, MACs can increase certainty arbitrarily. For example, we can guarantee with 99.99999% certainty that messages are authentic by increasing the MAC key and value sizes. If our certainty is high — or, equivalently, an attacker's chance of successfully forging a message (altering or faking a message) is low — attackers won't try to modify intercepted messages because they will probably fail. The procedures I describe let you choose how much certainty you want.
Use MACs whenever messages could be garbled in transit or forged (altered or faked) by attackers. Generally, if you decide to use MACs, you should create MACs for all of your messages. If you create MACs for only some messages, an attacker could forge messages without MACs or strip MACs from intercepted messages; either way, the recipient would have no way to verify received messages. But if you and your partner agree to always use MACs, receiving a message without an attached MAC is immediately suspicious.