Musings

Cut Your Own Master Keys

Locksmithing, plumbing, and a few other trades seem to persist in a guild-like mentality, where the “secrets” of the trade are passed on from Masters to Initiates. In the case of locksmiths, this is a signal case of what is elsewhere derided as “Security Through Obscurity.” When the “secret” leaks out, you are stunned to learn just how insecure the system really is.

A standard pin-tumber lock has P pins, each of which can be cut at H different heghts. That means H^P different combinations which, for modest values of H and P, could number in the millions. Since trying each combination involves cutting a blank and inserting it into the lock, this would seem to make pin-tumber lock invulnerable to brute force “keyspace search” attacks.

The situation changes dramatically when, in addition to the “change key”, which opens just this particular lock, there’s also a “master key” which opens all similar locks in the building. In this case, each pin has a second cut at some (unknown to you) height. As cryptographer Matt Blaze discovered, such systems (which all of us encounter in our day-to-day lives) are vulnerable to escalation of privileges (the owner of a change key being able to create a master key) through an elementary “Adaptive Oracle” attack.

The “Oracle” (which tells you when you’ve guessed right), in this case, is the lock that fits your change key. With P+1 key blanks (costing less that $2) and small bit of effort, you can create your own master key. The algorithm is so blindingly simple that you can probably guess it from just this description.

No? OK, here’s what you do.

Cut a blank to be identical to your change key, except at the location of the first pin, where you leave it uncut. Try it in the lock. If it doesn’t work, start trimming away until you find the height of the second cut. Since there are only H-1 heights to test, you will be done soon. Now take a second blank and repeat the procedure with the second pin. After using P blanks, you have learned the heights of the master cuts on all P pins. Use your last blank to cut yourself a master key.

There are many more details and variations in the paper. And, apparently, this has been known in some circles for a very long time. Now we all know.

Thanks to Ed Felten for the links.

Update: Of course, it’s obvious that you only need P, not P+1, blanks. But blanks are cheap, anyway.