The Sixty-Four Keys

A pin tumbler lock is a machine that says yes to exactly one key out of a million. Master-key a building and every lock in it starts saying yes to sixty-four. Two of those keys were issued to somebody. The rest were issued to nobody, and they open your door.

Every dimension below is transcribed from a published trade specification and cited. Every count is enumerated in front of you and again offline in research/the-sixty-four-keys/verify.mjs.

The lock on your front door is older than the light switch and does the same job as a password prompt: it holds a secret, you present a candidate, it answers yes or no. What makes it worth a second look is that the answer is computed mechanically, by six little brass columns, and the way those columns are built decides how hard the secret is to steal. Not by metaphor. By arithmetic you can do here.

Below is a cylinder built to the published dimensions of the Schlage Classic keyway: six chambers, ten cut depths numbered 0 to 9, one increment of fifteen thousandths of an inch between depths. Set the six cuts of a key and watch what the pins do.

The rule the picture obeys is one line of the specification, and it is the whole mechanism. For Schlage Classic the effective plug diameter is 0.500 inch: that is the distance from the bottom of the keyway to the shear line, the seam between the rotating plug and the fixed shell. The published root depth of a cut (how far the cut sits above the back of the key) and the published length of the bottom pin that matches it add up, at every one of the ten depths, to exactly 0.500 inch. Cut the key right and the top of the pin lands on the seam. Cut it one increment shallow and the pin sticks up fifteen thousandths of an inch into the shell, and the plug will not turn. That table is printed below the picture, recomputed from the transcribed numbers, and you can watch the sum come out the same on every row.

So an ordinary cylinder is an AND gate with six inputs. Six chambers, ten depths each: a million bittings, and exactly one of them turns the plug. You can check the one by counting all million.

What mastering actually does

A building wants one key that opens every door and a different key for each door. The cheapest way to get that, and the way almost every commercial building in the United States gets it, is to cut each pin stack in two places instead of one. A short spacer, the master pin, is dropped into the stack. Now the column has two seams, and either of them can be brought to the shear line. The chamber has stopped being an AND input with one accepted value and become an OR with two.

Press Master this lock above and watch a second break appear in each column. The arithmetic changes immediately, and not by a little. Six chambers, each accepting either of two depths, is not one key. It is two to the sixth.

“This lock can be operated not only by the obvious keys cut 11111 and 44444, but by a total of 2⁵ different keys, including, e.g., 11114, 11141, etc.” Matt Blaze, Cryptology and Physical Security: Rights Amplification in Master-Keyed Mechanical Locks, 2003

Here are all of them for the lock above. The two in gold are the keys the system issued: the change key for this door and the top master key for the building. Click any of the others to put it in the lock and watch the plug turn.

A fair question at this point is whether those extra keys are your neighbours'. They are not, and the reason is worth stating precisely because the loose version of this story gets it wrong. In a total position progression system, the kind the trade standardised on, no change key is ever cut to the master's depth at any position. So a key that opens your lock and is not your key must be using the master's depth somewhere, which means it is not anybody's change key. The instrument checks this by looking rather than by arguing: it builds every change key a single-level system on this master could issue, then asks, for each lock, how many of the keys that open it belong to another tenant.

So the sixty-two are not a neighbour. They are worse in one way and better in another. Better, because nobody is walking around with them. Worse, because they are the reason the lock is dozens of times easier to open by a key it was never meant to accept: a bitting drawn at random is sixty-four times likelier to open a fully mastered cylinder than a plain one, and if you draw only from keys a standard machine will actually cut, the factor is however many of the sixty-four survive MACS, which is 48 for the lock above and 55.6 averaged over every legal system. Mastering also makes a lock easier to pick, for the same reason. And above all, because they leak. Each one of them is a fact about the master key, and the lock will tell you which ones they are, one chamber at a time, for free.

The lock will answer any question you ask it

This is the 2003 result, and the reason a lock is worth a cryptographer's attention. Blaze's framing is that a lock is an online oracle: you present a candidate, it returns one bit. The question you always ask about an oracle is whether it will let you test one piece of the secret at a time.

“There is no ‘communication’ among pins; the lock will operate not only with all pin stacks aligned at the change key depth or all pin stacks at the master key depth, but also by keys that align some stacks at the change depth and others at the master depth.” Blaze 2003, §3.2

That sentence is the whole attack. Hold your own change key, which you are entitled to. Cut a test key identical to it except at one chamber, where you try a different depth. If the plug turns, that depth is the master's cut at that chamber, because nothing else in the lock could have accepted it. Now do the next chamber. Six chambers, nine other depths each: fifty-four test keys in the worst case, against a million if you were guessing whole keys.

“Observe that our attack consumes P(D − 1) key blanks and requires P(D − 1) probes of the lock, in the worst case. If it is possible for the attacker to cut keys between probes of the lock, however, a simple optimization reduces the number of blanks consumed to P in the worst case.” Blaze 2003, §3.2.2. P is the number of pin stacks, D the number of depths.

Try it. The lock below has a master you do not know. You hold its change key. Pick a chamber, pick a depth, and ask.

Fifty-four is Blaze's bound from the specification alone. A locksmith knows two more things, and both are printed in the same spec sheet the pin lengths came from, so both are available to anyone attacking the system.

The first is the master pin list. Schlage publishes master pins of 0.030, 0.045, 0.060, 0.075, 0.090, 0.105 and 0.120 inch: two increments up to eight, with no one-increment pin and no nine-increment pin. A master cut therefore cannot sit next to a change cut, and cannot sit nine depths away either. That alone knocks nine candidate depths per chamber down to seven.

The second is the progression. The same spec sheet gives the Schlage Classic progression as two step, and the trade press explains what that buys: with ten depths and a two-step progression you get “one master key cut and four remaining cuts which could be used for the change keys.” Master and change depths differ by an even number of increments. Combine that with the pin list and each chamber has exactly four candidate master depths, not nine. The page recomputes that count from the two published facts rather than taking the trade's word for it, and gets four at every one of the ten change depths.

So the staircase, all of it recomputed live:

The same bug, in software, in 1974

The reason this is a cryptography result and not a locksmithing curiosity is that the identical mistake has a famous software ancestor, and Blaze cites it. TENEX, an operating system for the PDP-10, checked passwords one character at a time and stopped at the first mismatch. That is a perfectly sensible loop until you notice that the time it takes to fail is a message. Butler Lampson's account:

“The following trick finds a password of length n in 64n tries on the average, rather than 128ⁿ/2 (Tenex uses 7 bit characters in strings). Arrange the passwordArgument so that its first character is the last character of a page and the next page is unassigned, and try each possible character as the first. If CONNECT reports BadPassword, the guess was wrong; if the system reports a reference to an unassigned page, it was correct.” Butler W. Lampson, Hints for Computer System Design, ACM Operating Systems Review 15(5), October 1983

Linear instead of exponential, because the check leaked one position at a time. A master-keyed cylinder leaks in exactly the same shape, for exactly the same reason: the chambers do not consult each other. Blaze makes the comparison himself, calling his method's resemblance to the TENEX attack striking. One is brass and one is a page-fault handler, and the counting argument does not notice the difference.

How many of those keys can actually be cut

There is one restriction left, and it is a small piece of good news that the lock gets for free. A key machine cuts at a fixed angle, so a very shallow cut cannot sit next to a very deep one: the cutter would eat its neighbour. Manufacturers publish this as the Maximum Adjacent Cut Specification. For Schlage conventional cylinders, Allegion states plainly that the MACS is 7, which forbids the adjacent pairs 0 and 8, 0 and 9, and 1 and 9.

MACS shrinks the nominal million: only 753,754 of the 1,000,000 bittings can be cut on a standard machine, which the page computes twice, once by a transfer matrix and once by trying all million. And it can shrink the sixty-four too, because a key that mixes change cuts with master cuts can end up with a shallow cut beside a deep one even when neither the change key nor the master key does. So: across every legal pair of change and master keys, how many of the sixty-four survive?

That number does not appear to have been published, so here it is, computed exactly rather than sampled. The count of cuttable crossbred keys for one system is itself a two-state transfer matrix along the key, which makes the whole distribution over all legal systems reachable by a dynamic program whose state is the pair of depths in one chamber and the running pair of partial counts. No sampling. The verifier checks the dynamic program against exhaustive search on three smaller specifications where exhaustive search is possible, and against a Monte Carlo run on this one.

Under standard Schlage practice the mean is 55.6 of 64, and in 57 per cent of systems all sixty-four are cuttable on an ordinary machine. MACS is not a defence. It is a rounding error on one, and the tail where it does bite (the rare system where only a handful of the sixty-four can be cut normally) is thin. Blaze notes the same thing from the workbench: on the locks he examined with MACS restrictions it was “generally still possible to cut working test keys by using a steeper than usual angle,” so even the keys this chart calls uncuttable are only awkward, not impossible.

The contrast worth seeing is the small format interchangeable core, the brass cylinder in most institutional door hardware. BEST A2 has seven chambers and a MACS of 9. With ten depths, a MACS of 9 forbids nothing at all. A fully mastered A2 core has 128 keys and every one of them cuts on a standard machine.

1987, 2002, 2003

The last part of this is not arithmetic, and it is the part that made the paper famous.

Blaze wrote the method down and put a footnote on the word “new”:

“Several correspondents have suggested that similar approaches to master key reverse engineering have been discovered and used illicitly in the past and the method occasionally circulated informally, e.g., on Internet message boards. (We subsequently found a message originally sent to a private mailing list in 1987 from Doug Gwyn that describes a similar method.) However, there do not appear to be references to this particular attack in the published literature of either the locksmith or underground communities.” Blaze 2003, footnote 2

On 23 January 2003 the New York Times put it in the business section under the headline “Master Key Copying Revealed.” The locksmith trade was furious. Schlage's own head instructor for master-key classes, Lloyd Seliber, told the paper the technique was not news at all: “This has been true for 150 years,” and he taught it in training programmes. A security consultant quoted in the same article answered that this was precisely the problem: it might be old to locksmiths, but “it's new in the security industry. Security managers don't know about it.” Bruce Schneier, writing in the same issue of the journal that carried Blaze's paper, put the shape of it in one sentence: the technique “was known in the locksmithing community and in the criminal community for over a century, but was never discussed in public and remained folklore.”

Both sides were telling the truth. The fact was old; the sentence was new. What changed in 2003 was not what a lock does but who was allowed to know it, and the people whose job was to buy locks had been on the wrong side of that line for a century. Seliber, the man who said it had been true for 150 years, is thanked by name in the acknowledgements of the paper that said it out loud.