Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

January 24, 2003

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 HP 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.

Posted by distler at January 24, 2003 10:56 AM

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/82

1 Comment & 1 Trackback

That was a crystal-clear short explanation. Thanks!

Posted by: Seb on January 31, 2003 4:16 PM | Permalink | Reply to this
Read the post How to make a Master Key...
Weblog: EmptyHighway
Excerpt: Wow, I always knew tumblelocks were easy to pick, but this is ridiculous. Thanks to the musings of another fine Texan....
Tracked: March 4, 2003 3:35 PM

Post a New Comment