Cryptography in the Real World

This post is about implementing cryptography with real objects—rods, chains, and locks—and it is going to be light on formulas and heavy on pictures. Fun!

Many cryptographic schemes have real-world analogues, some less trivial than others. Digital signatures are the most obvious example, where the cryptographic scheme achieves pretty much the same task as traditional signatures: non-deniability vis-à-vis a third party. There are, of course, differences that can be confusing to some: a real signature does not guarantee integrity of the text (physical properties of the medium could); both types of signatures require verification keys but digital signatures corresponding to different verification keys are not necessarily distinct.

We are all familiar with a real-world implementation of public-key encryption (although I use it much less frequently these days than its digital analogue): a mailbox for outgoing letters. Indeed, anyone can put a letter in through a narrow slit, and only the postman can unlock the box and take letters out.

Once we have public-key encryption, we can implement key exchange in much the same way SSL does it. How can Alice and Bob end up with a common key (of the real-world variety—a shiny metal object) that could not be copied by an intermediary if they have never met before? Alice may ship to Bob a mailbox, which only she can open, Bob will put a copy of his key inside, and send it back to Alice. Security of a standard-issue mailbox relies on the fact that it is usually bolted to the wall, and difficult to shake or turn it upside down. This can be a problem with a mailbox that is portable enough to be shipped by mail, so some additional mechanisms that guarantee secrecy of the content in transit might be necessary: for instance, Bob can seal the slit in a tamper-evident way, such as covering it with his signature.

A more clever way of sending valuable content via untrustworthy mail service is sometimes called the Russian Postal System puzzle. In this puzzle Boris the Muscovite wants to send by mail a diamond ring to Anna, who lives in St. Petersburg. He sends the ring in a locked box to Anna, who upon receiving the box (to which she does not have the key!) attaches her own padlock and returns it to Boris. He then removes his lock, and sends the box (now locked only with Anna’s padlock) to her. This method is vaguely similar to the Diffie-Hellman key exchange protocol, although I wouldn’t recommend using it in practice: it assumes guaranteed delivery, which is something that Russian Post is not exactly famous for (a recent study ranked countries according to the proportion of returned letters mailed to a non-existent address. No letters mailed to Russia ever came back).

Proceeding to more realistic examples, I’d like to share an interesting security mechanism that I spotted in Florence this summer. Europe’s first orphanage wanted to enforce two seemingly conflicting properties: a guarantee of anonymity for the mothers bringing their children to the facility, and some degree of control over the babies (they were only interested in newborns). The picture of the extant part of the solution is below: only a small enough child could be placed on the turntable beyond the iron grid of a sufficiently fine size.

The next two examples of cryptographic mechanisms in the real world are best described in pictures. The first I took myself by the Lake Tahoe a few years ago. It implements a 1-out-of-7 encryption scheme, where unlocking any one padlock out of seven will open the gate.

I especially like how the scheme got extended to support an extra key by adding a bar fixed in place by padlocks on both side.

Another arrangement of padlocks achieving similar functionality comes from here (via Crypto-Gram):

It effectively implements 1-out-of-15 encryption, where removal of any one padlock will allow retraction of the rod whose shape I hazarded below:

The diameter of the hidden part of the rod is chosen so that it passes through a hole without a padlock but does not when all padlocks are in place.

What about more flexible secret sharing schemes, such as k-out-of-n encryption, where any k keys can unlock the door? I offer one of my own below but encourage you to suggest other solutions in the comments.
Hopefully, the drawing is self-explanatory: unless at least k locks are removed, the chain with the key at the end does not reach the keyhole. To avoid a copying attack, where a duplicate key is made from an imprint, a more comprehensive solution should be put in place to prevent physical access to the key. Another possibility is to combine it with the retractable rod idea from above. One benefit of this solution is its flexibility—weighted schemes can be implemented by choosing unequal intervals “unlocked” by padlocks, realizing scenarios where one person’s contribution can be larger than others’.

What’s not in this post? We didn’t cover visual cryptography, or convincing your children you are not cheating in the game of “Where’s Waldo?”, answering sensitive questions with scratch-off cards, or many ingenious verifiable voting schemes that use a combination of real-world phenomena (such as one-wayness of shredding) and advanced cryptography. A recent work by Alex Glaser, Boaz Barak, and Rob Goldston on zero-knowledge verification of warheads with a ray of neutrons deserves a post of its own. We are also interested in our readers’ experience with security solutions in the real world—share your thoughts and observations in the comments section below.