Physical analogue for MACs

Question

What would be a good analogue with which to describe Message Authentication Codes to a person who has little to no understanding of cryptography?

For instance, a vault is a reasonable analogue for symmetric authenticated encryption: anyone with the key can open the vault and inspect, alter, or replace the contents. Without the key, you can't know or manipulate what's inside. Similarly, a royal wax seal is an okay one for digital signatures: anyone can validate that a message originated from the person with that particular stamp with assurances that the message hasn't been altered since the envelope was sealed.

Is there a good physical example of something with similar semantics to MACs?

Answer 1

Just thinking out loud here:

1. Take a picture of the contents of a box.
2. Put these pictures in a safe.
3. Ship box and safe together, lock with key of sender.
4. Receiver unlocks safe, compares pictures with contents of box.

The safe and keys are already common for symmetric encryption too.

Answer 2

A MAC is a shipping note or delivery note, which comes in a locked box.

You need a key to open it, otherwise you can't see its content, and it has the be the same key as the one used by the sender. Inside, there is a description of something else, like "this delivery contains 173 kg bananas and 43 kg apples". If the box is undamaged and can be opened with the correct (previously known) key, then we know what the delivery should contain. If that's equal to the real delivery, we can conclude that it wasn't manipulated.

Answer 3

Here is a decent analogue: a hidden watermark on paper, activated chemically perhaps. Maybe the watermark is a pattern of dots. Anyone with knowledge of the watermark and how to activate it could verify the authenticity of the document, whereas anyone without knowledge would not be able to. I assume bank notes in real life have similar watermarks, although that is purely speculation.

Here's another possible analogy: suppose you had an item in a clear acrylic display case that had a built-in lock, specifically one of those locks that required it to be locked with the key itself. Example:

Then someone without the key, upon coming across this case, could not verify that it was locked with a specific key, though they would know it was locked with some key. Someone with the "real" key could simply try to unlock the case, and if they succeeded, well, there you go.

This fits relatively well with a real MAC: the theoretical "algorithm" would be to use a case with the corresponding key(s). An attacker without the key cannot easily alter the document in question without alerting the key-bearer(s): any sort of brute-force physical attack on the case would likely leave marks on the case (e.g., saws, acid, etc.) The only exception would be lockpicking, but many physical analogues for other cryptographic primitives suffer from lockpicking too, so we'll ignore it.

There are a few inconsistencies, however: in a real cryptographic primitive, if the attacker has no knowledge of the scheme, the attacker may not necessarily know that a particular value is indeed a MAC tag. With the display case, however, it is quite clear that the document in question is protected, no matter how little an attacker knows. Further, with a real MAC, if you don't possess the key, you cannot verify the authenticity of the item in question. With the acrylic display case, you can pretty much look at it and figure out whether or not an unauthorized party has modified it: maybe someone took a bandsaw to the hinges to remove the door. That'd be pretty hard to miss.

On the other hand, as a third party looking at the display case, you don't necessarily know who have keys, so a bit of subterfuge could go unnoticed. Anyway, despite giving this matter a fair bit of thought, I have yet to come up with a better physical analogue, so take this as you will.

Answer 4

A padlock is a good analogy.

Consider a combination lock, where Alice and Bob know the secret combination. Alice can send Bob a message by writing down her message on a piece of paper, putting the piece of paper inside a metal chest, and locking the chest with the padlock. Then, Alice sends the chest by courier to Bob. Now Bob, who knows the combination, can open the combo lock and read Alice's message. No one else will be able to tamper with the message, since they don't know the combination to the lock. For example, the courier cannot tamper with the integrity of the message, since the courier doesn't know the combination. Here the secret combination plays the role of the MAC key.

If you want the analogy to be slightly closer to a MAC, make it a transparent chest (with no slits or openings in it), so anyone can see through the chest but can't touch or tamper with the paper inside.

Answer 5

A physical analog to a MAC would be a numbered tamper-evident seal, such as a tag used to ensure the cargo door of a truck remains closed. Such seals cannot be removed without leaving visible damage to the seal. They are uniquely numbered by a trusted seal manufacturer, who provides assurance that no two tags have the same identifying markings.

When a trucker accepts a shipment, the shipper takes a new tamper-evident seal of his own, writes the number on the cargo manifest, signs the manifest, then puts their product and manifest in the cargo area of the truck*. They then wrap the seal around the door latch on the outside of the truck and fasten it securely so the doors cannot be opened without damaging the seal. The trucker then drives the load away. When the trucker reaches his destination, the recipient examines the tag for damage, then breaks the seal and opens the truck door. He then checks that the number of the seal matches the number printed on the cargo manifest. The undamaged seal provides assurance that nobody including the trucker had access to the goods the shipper originally put in the truck.

A seal provides assurances similar to those provided by a MAC:

• The shipper buys their seals from a trustworthy company that promises to sell seals in the range of 1000 to 2000 only to John's Widget Co. This provides the authentication that it was John's Widget Co that bought the seal and sealed the truck shut and not someone else. A MAC uses a shared secret known only to the sender and receiver, and couldn't have been created by someone else.

• The number on the tag proves that this exact truckful of stuff matches the number on the manifest, meaning someone didn't swap a sealed truck substituting "John's Cheap Widgets" for "John's TopShelf Widgets". The MAC tells the recipient that this message is the one that was protected, and not just any old message from the sender.

• The tamper-evident nature of the seal proves that nobody opened the truck, just as a MAC proves that nobody changed the message.

• The seal provides no physical protection against theft or tampering because it's not a lock, just as a MAC doesn't stop anyone from reading or changing the message. It just tells the recipient when tampering occurred.

• The numbers on the seal don't tell anyone about the contents of the truck, just as a MAC doesn't reveal the contents of the message it's protecting.

* In reality, a shipping manifest is usually sent under separate cover, which is a significant difference between a MAC and a signed manifest sealed inside the truck.

Answer 6

A MAC Scheme for Optical Lenses

MACs provide authentication over arbitrary bitstrings, but there is no decent hash function for arbitrary physical objects. I believe that dropping the goal of trying to be a general purpose "any physical object" MAC, you can get much closer to meeting the properties of a cryptographic MAC.

Here is a physical analogue of a MAC for optical lenses. I've imagined a world where there is a need to be able to verify the integrity of lenses sent from place to place, with analogous developments to what has happened in crypto.

Public Algorithm

There is a publicly known mechanism for validating MACs over lenses - a standard jig containing mirrors and lasers into which you place the lens, and a paper holder (lets say it's A4). Manufacturers can sell you certified jigs that are know to meet the standard.

The jig is designed such that the laser beams pass through the lens multiple times as they bounce around the mirrors, before finally shining on the paper (or hitting another non-reflective part of the jig).

The jig design is critical to the security of the system - many jigs were designed in the old days that had weaknesses allowing attackers to break the scheme. Jigs these days are typically developed by academics, then standardised by national bodies as a result of a competition comparing security, size and ease of use (speed) across the entrants.

Secret Key

Sender and receiver share a secret: a particular configuration of lasers and mirrors (which positions all of the mirrors and lasers are in, potentially which lasers are on or off).

There is a finite but very large set of valid configurations (which means that the jig supports lasers being in one of a set positions, not an analogue configuration). An example configuration might be specified as: Laser n; position. Mirror n; position. L1:45; L2:0; L3:90; L4:20; ... L15:0; M1:45; M2:80; ... M10:90.

(There are some weak keys, e.g. very short ones, all zeros, and more subtle issues like setups that typically lead to null MACs. The algorithm specifies constraints for constructing strong keys.)

Verification

Sender dispatches a lens (the message) to the receiver, alongside a piece of paper with some dots on it (the MAC).

The receive puts the lens into the jig (the algorithm), sets up the mirrors and lasers according to the shared secret configuration (key input), and slots the paper into its holder (MAC input).

When the lenses are on, if each dot on the paper is illuminated by a laser (and there are no lasers shining onto the paper where there are no dots), then the MAC is verified and the receiver knows that they have received the correct lens.

Generation

This is an analogue of a symmetric MAC scheme - generation follows the same process as verification, but blank paper is used and the position of the dots are recorded rather than checked.

---

Comparison to MAC Properties

Avalanche Effect

Provided the algorithm (jig) is well defined, a small change to the lens will lead to a large change to the MAC, as each laser beam passes through the lens a number of times at multiple different points: by the time it hits the paper a small change in the lens will have a large change in the position of the spots in the paper.

(c.f. pictures or other representations of messages).

Detection not prevention

The MAC does nothing to stop an attacker swapping out or altering the lens or MAC - it just alerts the receiver to the change.

(c.f. lock boxes)

Deriving the key from example valid message:MAC pairs

An attacker cannot derive the secret key from example plaintext:MAC pairs.

(c.f. wax seals, signatures, key or combination locks that can be disassembled)

Existential Forgery

Without knowing the secret key, there is no practical way for an attacker to create a valid MAC for their lens.

(c.f. locks that open whatever key you insert / combination you put in)

Chosen Plaintext Attack

A cryptographic MAC should be resistent to attack even if the attacker has access to an oracle that will produce valid MACs for arbitrary plaintexts (Chosen Plaintext Attack).

This scheme is not as resistant as you would like under these circumstances - the null message of a non-distorting lens reveals more information about the secret key than is ideal. It doesn't immediately reveal the key provided the jig (algorithm) is well designed, but you could imagine a small set of well chosen lenses that could give the attacker a significant advantage.

So users of this scheme need to try and avoid providing attackers access to an oracle of this kind - something you try to avoid in a real cryptosystem too!

Does Not Reveal The Message

If you want to also put the lens in a strongbox and ship the MAC outside the box, the MAC doesn't reveal much useful information about the lens without knowing the key.

(c.f. manifests, photos, ...)

Answer 7

If a wax seal is an analogue for a signature, then there's also an implication of authentication in it - i.e. the integrity of the wax seal indicates whether the message had been opened, giving a reasonable assertion that the message has not been tampered with.

By extension, other methods of sealing messages such as placing them in envelopes (which can be inspected to see show signs of being opened) can be viewed to authenticate the contents.

Answer 8

From my undersanding

MAC = a token/representation that shows authenticity and integrity

I remember in old manual passports and documents a Rubber Stamp is used to stamp across intersection of pieces of information

I.e rubber stamp on intersection of signature and white space OR stamp on intersection of photo and page

The stamp is secret as it can only be made with authority and stamping at intersection prevents altering the document , as any alteration will be visible to eye

Same stamping etc is woven into bank notes

Answer 9

Your handwriting could be a strong indication that the message was written by you, although that's not unforgeable.

You can also use personal references or references to earlier, secure communications you had with that person (i.e. meet me at the cafe where we first met). (got confused with authentication here)

Another option would be to use custom-made or rare ink. The recepient can later use chromatography (with varying degrees of accuracy depending on the budget) to at least give a good indication that parts of the message were not altered. For example, scan the paper (to keep the contents), cut it in strips and dunk them in a bowl of water and observe the rainbow.

Or you can agree on some secret value (or group of values) $S$, assign a value to each letter and say the XOR of all letters is $S$. You can then add content to meet the target. Writing the code for this would also be an interesting excercise.