Key equivalence and why it's bad (I)

| Comments (2) | COMSEC
A British jail is changing all its locks because the keys were shown on TV:
An ITN team mistakenly filmed keys on a visit to Feltham Young Offenders' Institution, West London — sparking fears they could be copied.

It meant the nick's 11,000 locks and 3,200 keys all had to be replaced.

First, I'm fairly skeptical that you can reverse-engineer the keys for a lock based on just seeing the key on TV (and unless the lock is incredibly badly engineered, I don't see how you can do it with the lock) unless it's some extreme close-up shot, in which case it should be easy for the jail to figure out what keys were compromised and just rekey them, rather than the whole jail. Second, keys are just part of the jail defense-in-depth system, so hopefully compromise of keys isn't a disaster. After all, it's not that hard to pick most locks, so you can't count on only the lock anyway.

In general it's not that attractive a property of a security system that just seeing one of the elements allows the attacker to break the system. This is sort of inherent in the construction of ordinary physical locks but even there you could improve the situation a bit by (for instance) putting the beveled sections of the key on the inside rather than the outside so just looking at the key doesn't reveal much information. It's of course harder to cut keys that way with conventional cutting machines but arguably that's a feature since it means that you need specialized equipment to duplicate the keys1, which presents a modest barrier. The bottom line is still that with physical lock systems if you can examine the key (even briefly) or the lock (sometimes quite extensively) you can typically figure out what the key looks like enough to get in.)

In digital security systems, by contrast, we can do quite a bit better. Let's start by talking about a simple password system like you would use to log in to your bank (and like people used to use to log in to their computers back when they were multiuser). The way this works is that you type your password into your Web browser and it's sent over the Intertubes (hopefully encrypted with SSL) to the server on the other side, which needs to check it. The easiest way to do this is to have the server just store a copy of the password locally and do a memory comparison.

This has a big problem3. If someone breaks into the server and gets a copy of the password list they get a copy of everyone's password and can impersonate users. This is what's called a password equivalent or a key equivalent for reasons that will become clear a little later. This lets them leverage a disclosure exploit (i.e., one that lets them read files on a system) into an intrusion exploit (i.e., one that lets them break in or pose as another user). It also means that the password file has to be stored with very strict permissions. The fix for this problem is well known. You don't store the password itself but rather you store a one-way function (originally computed with DES but now typically with a hash function) of the password. Call this H(Password). When the user provides their password you compute H(password) and compare it to the stored value. If they match, the user is in. This scheme has the advantage that compromise of the password file is much less dangerous. In fact, on old Unix systems password files used to be publicly readable until it became clear that you could simply try a bunch of candidate passwords until you got a hash that matched (this is called a dictionary search) at which point we went back to hiding the passwords. Even so, a dictionary search is a lot harder than just reading the passwords off the disk.

Even with this fix, simple passwords have the big problem that if you can convince the user to authenticate to you just once then you know their password (it doesn't help here that users tend to use the same password on multiple sites). This is the basis of both (pre-SSL) password sniffing attacks and of phishing. So, the state we have now is that we can make examining the lock basically useless (as long as people choose really strong passwords) but since authenticating requires presenting a copy of the key, if you can examine the key (e.g., by impersonating the lock) you can impersonate the user as much as you want. This is the state of nearly all Web-based login systems today, but it can can be improved upon quite a bit by some cryptography. I'll get to that next.

1.By contrast, the major security feature on "do not duplicate" keys is often the stamp that says "DO NOT DUPLICATE" (the capital letters are what make it mandatory.2.) Sometimes, but not always the blanks are restricted, but obviously the stamp has nothing to do with that.

2. In this document, the keywords "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT", and "MAY" are to be interpreted as described RFC 2119.

3. Note to advanced readers, don't bother me about timing analysis. I'll try to write that up later.

UPDATE: In the comments, Chris WalshByrd reminds me that someone actually has copied a Diebold key from a picture on a web site. I haven't seen the relevant picture, but I suspect it's a lot better than your average picture on a TV, which tend to be taken from funny angles and be fairly low resolution.


Although I agree with the majority of your post, it may be more possible to copy a physical key with an image than you might think. Check out this article for a recent example:

I was involved in the copy-Diebold-key-from-photo demo. It was indeed a higher-resolution picture than you would get just seeing a key on TV. It was also a relatively simple key.

Leave a comment