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

Matt Blaze

AT&T Labs ­ Research

which is accessible at

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

Abstract

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

The following events become completely fictitious after a few paragraphs, it's a good job too.



Monday, September 27, 2010, 17:00 GMT+09:30, Adelaide, South Australia.

A black Honda Civic rolled smoothly to a stop under a pergola, and the four occupants stepped out. We'd just returned from a weekend interstate, visiting family. As I stepped out of the car, something on the ground caught my eye. a small metal object glinted in the sunlight. Hmm? Whatever it was, Dad might run over it next time he drove in. I stooped to pick it up. A key? A standard Yale Lockwood entry set key. Well, standard apart from the fact that the shaft was bent about fifteen degrees from the head and the head had a number of grind marks on both sides running perpendicular to shaft. I un-snapped my own set from by waist to compare the newcomer. Nope, no matches. Bending back down to where the key had landed, I placed my eyes at ground level and looked for a possible trajectory. Hmm, nup, couldn't have come over any of the neighbours' fences. Could be a master key, but I wouldn't like to try it in a lock, or it will probably snap off in there. I examined nearby windows and doors for any sign of forced entry, but everything was in order. After informing the others of my discovery, I pocketed the key and continued inside.

The cat rubbed against my ankle as I stood at the door, the way she often does. "Hey, how's it going?" I bent to stroke the back of her neck. "What happened to your foot?" She was limping on her front right paw, but there was nothing obviously wrong with it. As I opened the back door, she stood behind me, clinging to my leg in a cowering way. I thought it was odd. "What is it, mate?" I stroked the back of her neck again. Phwoah, a stench hit me as soon as I opened the door. It was a stench like we used to get when dead rabbits would sit under the house for a week or so.

"Nraawr," the cat's teeth showed as she stayed close behind me, ears pricked, tail erect. I reached for the light switch, unable to see anything inside the house up to this point. Click. I reeled backward, my shoe taking out the side of the cat's head. She "Nraawr." She leapt sideways to avoid being struck by my other foot as well. I took a cautious step forward, looking directly ahead although I'm certain it really would have been a good idea to have checked the rest of my surroundings first. A human hand protruded past the top of the back of a lounge chair, as if someone was laying there with one arm raised. How on Earth they could have got there, I had no idea, nor was I about to try and guess. Another step, and I was looking down, directly into a human face. Wait, human? Yes, I think so. It was badly mangled. I think this is about the point where most people at least shiver, or in movies, scream. I did neither, instead raising an eyebrow, just one, the left one. I am not going to try to describe what the body looked like, for it was ghastly beyond a need for description. Yes, there was the rest of a body down there too. Well, most of one anyway...

Upon preliminary inspection, all appeared to be present and correct. A second glance revealed the the left arm was not folded under them as I had at first supposed, but rather was missing. Now, I don't discriminate against people with disabilities, just because the majority of people are born with two arms doesn't mean it's the "correct" number. Having said that, this person apparently did have a second arm at some point in time, and the dried blood on their shirt suggested the appendage was only recently removed. I looked around, as if half expecting to find the arm, but there was no sign of it, only a trail of blood leading toward the back of the house. My right hand flashed to my pocket, returning with my phone. The camera lens cover flicked open with a half plastic half metallic noise like that of a switch blade knife, and my index finger slid mechanically onto the shutter button. Ka-ch.

The Police arrived roughly thirty minutes later, Detective Sergeant Smelter declaring the entire house a crime scene, putting up caution tape and whatnot. I know a girl who develops crime scene photos, and I always thought it would be a pretty cool job, I was starting to wonder now though. I was sitting outside with the rest of the family two hours later when the Sergeant approached us. "Sir," he addressed my father, "My men have identified the deceased as a Master Hoffman Key." I didn't catch the rest of what he said because my attention was drawn to a pair of men in lab coats walking out of the house with a pair of black garbage bags.

I never did get to find out what happened to that other arm, wonder where it went...

Log in or registerto write something here or to contact authors.