The writeup formerly known as "How to make a master key given one change key and its lock". Renamed through the good offices of dannye.

This is based on a paper entitled

Cryptology and Physical Security: Rights Amplification in Master-Keyed Mechanical Locks

by

AT&T Labs ­ Research

which is accessible at

http://www.crypto.com/papers/mk.pdf

This paper describes new attacks for amplifying rights in mechanical pin tumbler locks. Given access to a single master-keyed lock and its associated change key, a procedure is given that allows discovery and creation of a working master key for the system. No special skill or equipment, beyond a small number of blank keys and a metal file, is required, and the attacker need engage in no suspicious behavior at the lock's location. Countermeasures are also described that may provide limited protection under certain circumstances.

The paper is rather lengthy, so I will summarize its main idea and implications. It shows how to manufacture a master key if all you have is a change key, i.e. a key that only fits one lock in the master-keyed system, and access to the corresponding lock - the typical situation of a lowly employee. "Rights Amplification" is fairly obvious jargon for reaching the exalted state of being able to unlock any door in the system.

After publishing the paper (September 2002), the author received numerous emails from irate locksmiths, saying either that he had gravely damaged the industry by publishing this ancient but secret method, or that he was wrong and the method did not work. He decided to ignore them. He also remarks that the level of cryptological security of master key systems falls well below that of computer networks.

The method does not work for all master-keyed systems, so I will start by describing the (very common) type of system it does work for.

Most locks are essentially mechanisms for comparing a string of N digits, each of which can take M values, with a given string built into the individual lock, and letting you turn the key if and only if the two match exactly. Each of the N digits corresponds to the height of the "cut" in one "pin stack" within the lock: the lock can only turn if all the cuts are aligned with the "shear line" which separates the turning part from the fixed part of the lock. For convenience, the "bitting", which is the technical term for the height of the sticking-out bits on a key, usually takes only discrete values. Blaze says: "Typically, the number of pins is in the range of four to seven, and the number of possible heights ranges from four to ten." All we need to completely specify any key is to give the string of bitting heights, e.g. 24143.

Master key systems are a bit more complicated. Each lock, in addition to the bitting corresponding to the single "change key" which opens it and it alone, will have a master cut corresponding to the master key. In some (Total Position Progression (TPP)) systems the master cut differs from the change key in all positions (e.g. 33421), in some (Rotating Constant (RC)) the change keys share the master bitting for a certain number of positions, and these matching positions are different for different change keys: e.g. the master key could be 24421 and different change keys would be 24143 and 13422.

Note that in a TPP system, if one has access to a large number of change keys, the master key may be found by a process of elimination, since in each position its bitting will be the only one not appearing. I quote from Matt Blaze: "Several correspondents have noted that this technique is occasionally employed by enterprising university students, especially at better engineering schools."

Now for the method, which Blaze calls "An Adaptive Oracle-Based Rights Amplification Attack". The method works without having to damage or interfere with the lock in any way. It involves procuring a number of blank keys and cutting them to the following formula:

Each new key should be the same as the change key, except in one position. In this one position, cut all possible bittings differing from the change key. Repeat over all positions.
Hence, for the change key 24143, one should cut oneself 44143, 34143 and 14143 for the first position, 23143, 22143 and 21143 for the second position, etc. Now, for each position, simply try to turn the lock with each of the alternative keys in turn. This is the "oracle": the lock itself tells you when you have the correct cut. The master key bitting in that position is just that of the successful alternative key. Now move on to the next position and repeat. Having worked out the master key bitting in each position, use your last blank key to make one!

Naïvely, one would think quite a few blanks are needed to do this: in the case of a lock with 4 heights and 5 positions, (4-1) x 5 + 1 = 16 might be needed (for a lock with 9 heights and 7 positions, (9-1) x 7 + 1 = 57). However, by starting with the highest bitting and gradually cutting down (44143, 34143, 14143) you reduce the number to 6 (8), at the cost of having to go away and do the cutting between each trial.

The beauty of the method is that you can apply it without raising the least suspicion, since, by assumption, you already have legitimate access to at least one lock and its key. If you are not in this position, then more violent or subterfugitive methods may be necessary...