Schneier on Security

D'oh - timeout-lockout feature anyone?

Israel Torres

Similar to guessing someone's answering machine code. No timeout and will validate an imbedded string. Of course there are 99 possible values, it might hang up on you after 1 minute. And you will leave a message with DTMF tones on it unless you get it right away.

It would not be hard to hook 5 solenoids to a serial port, or small ROM and have them automaticaly push the keypad in the sequence - and the device could do it much more accurately and faster than a person.

I'd say you'd be in within 90 seconds.

I just checked it against my car entry code. It is too close to the beginning for comfort!

Interesting. I'm sure many of us have noticed that there are actually only 5 buttons for the 10 numbers, and have conidered the number of combinations. Nice to see some confirmation of the ease of cracking it. The next question is, can the owner of the vehicle disable this method of entry, if he decides the risk outweighs the convenience? I'm guessing not.

@nzruss-
Note that there are at least 5! (=120) different such minimal-length sequences; your car entry code is pretty much guaranteed to be near the beginning of at least one of them.

"can the owner of the vehicle disable this method of entry"

@Josh O
Most vehicles that support this method of entry allow the owner to disable it either through fuse removal or keyed deactivation (like inserting your key into the ignition and traversing a specific combination). Usually a simple google search will allow you to find out what you need to do for your (or your target's) specific vehicle.

Israel Torres

re: my comment above

Talk about poor math; I should have verified before posting. there are 5!^5^4/(5^5)=(120^625)/3125 such sequences, which is around 9.8*10^1295 different sequences, any of which will get your code within the given number of button presses.

To make it even more fun, there are generally two codes that work - the owner-programmed code, and the hard-coded (car specific though) one that you use to program your personal code. I believe that one is actually 5 digits, but it's still in there...

@ Fred P: -----------> Did you click the link?

I just searched for my code _in_the_sequence - which, as the article says, is the quickest way to get in. While the article mentions it could take up to 20 mins to get in, the hits before you get to _my_particular_code_ are minimal (it is near the beginning....) meaning someone would be in after about 30 seconds.

my bad. I didnt understand what you were getting at, but do now. sry.

Not that using that sequence is all that much (in a computer-scientific sense) faster; using one of the de bruijn sequences saves you a factor of five (or more generally, factor-of-length-of-code), so it's a question of 20 minutes vs 100 minutes (3,129 presses vs. 15,625). Both are longer than it'd be convenient and inconspicuous to be sitting there for, but neither is prohibitively long. (Do you leave your car unobserved for more than two hours at a stretch? I know I do.)

Steve

Carjacker hunting is legal in some states. Put one of the higher end models with one of these on the side of the road as your decoy, grab a rifle and some camo's, and you're set.

When rafting my family is always careful to leave a car with keyless entry at the pickup site and lock the keys inside it so that nobody has to bring keys down the snake river. One year the car had a dead battery the day before and we had to jump it. Nobody realized/remembered that this would reset the keyless entry code to the default code rather than the one we had programmed and everyone knew.

We figured this out when we reached the car. So my little brother starts pressing buttons in a pattern that he came up with on the spot in order to try to guess the number. Thirty seconds into the process the door unlocked. My dad, couldn't believe it. My brother said, "Oh, it was easy!" and locks the door and shuts it without grabbing the key. My dad went from impressed to furious in no time at all but my brother repeated his pattern and the door was open again in another 30 seconds. This time we grabbed the keys before he could lock it again.

How hard would it be to hook up a device to run through this automatically? How fast could it go if computer-controlled rather than human-input?

In the worst case, you end up with a device that you push a button on, drop next to the car, and then walk away. Come back in 20 minutes and open the door. Not suspicious unless someone's watching the car for 20 minutes straight and recognizes you.

I do like nzruss's idea of solenoid attacking this. How hard would it be to setup a Treo or Crackberry along with a rack supporting 5 solenoids that could be handheld over the keypad. I bet if you jammed this thing hard enough you could be into ANY car in about 5 minutes at most.

Would be kind of like the lockpick guns that rip through key locks. Ugh.

The key-code is a red-herring.

The real security issues are :
(1) leaving the car where there are thieves
(2) who have unimpeded access.

Each, of course, unfolds to additional issues.

My tiny pea-brain is stuck on the properties of the device in question. Is it always the same device, no matter what car it's installed on? Is the code always 5 digits? Can the authentication properties (code length, behavior when a bad code is tried, etc.) be configured?

The device is usually the same- five buttons, with 1/2 on the first, 3/4 on the second, etc. So, 10 numbers but only 5 buttons.

They are on the driver's side, near the top right of the door, and the buttons run left to right in single file (not like a phone pad).

They are usually on Fords or Lincolns, and are old tech. This means there isn't a timeout or lockout if you try too much and I think there is even a default code depending on the car and year.

@Greg (the other)

Exactly - from an attacker's point of view cracking the code, if it takes longer than a few seconds, is pointless.

Remember that a real attacker is not concerned about causing damage to a car - I've heard of them using those spring-loaded centre punches which are small metal pen-shaped things which you press against an object and they give a sharp click and punch an indentation. Against a car window they quietly shatter the whole window and the intruder is in the car in less than 2 seconds.

The article reminds me of Feynman cracking safes in a very similar way. ;-)

I can't say that I've ever seen a car with a keypad like this, but it sounds like a pretty bad idea.
What's wrong with a keyfob with a RF transmitter on it that unlocks the car?
Here in Australia, all keyless entry systems like this are required by law to use a cycling code so that replay attacks are foiled as well. It's a lot more convenient to carry a button around in your pocket than it is to have to enter an (insecure) PIN on a keypad...

The replies are an interesting case study. You all seem nervous that I can get into your car by trying 3000 or so numbers.

You should be nervous that I can get into your car in 45 seconds by
1) Smashing a window: Inelegant and loud, but it works.
2) Beating the shit out of you and taking your keys: see 1
3) Picking the lock: See also your front door.
4) Slim jim: Slip a bit of metal between the glass and the door and you can open most locks. Some newer cars have a plate in the way, but there is a way in
5) Matched keys: Large makers of consumer locks (even some professional locks) use a limited set of keys. With some patientce and a few drop boxes, it is possible to acquire a full set of keys.

You also need to think when the last time you saw a new car with this feature. It was "whiz bang" in the late 80's, commonplace by the early 90's, and is all but gone now.

So look at this not as a security flaw in the keypad, but in a 'meatspace' error in percieved threats.

Interestingly, a friend of mine was discussing this precise problem last Friday, in the context of computer theory. The basis of this is Euler trails: you have a graph where each node has (k-1) digits, where k is the number of digits in the code; you have an edge from a node to every other node whose first (k-2) digits match the present node's last (k-2) digits. Find an Euler path for that graph, and you have an optimal sequence to input.

I find it odd that I hear about so many topics multiple times within a few weeks of first learning about them--I only learned about Euler trails a day or two before hearing that algorithm.

Several years ago I locked my keys in the car at a gas station. I went to ask the attendant if they had some way to help. No.

Luckily, a guy overheard me and offered to open the door for $10. He just happened to have a slim jim in his trunk. About 15 seconds later I was in the car...

@dhasenan: you might have heard about this type of thing lots of times in the past, but not connected it to things that you knew.

It's just like how you buy a new car, thinking that there really aren't that many of that model, and then you see six of them on the way home.

The human mind is actually very good at making connections, once it is primed to look for them.

Interesting: I discussed this problem 6 years ago at a mathematics summerschool in Italy. No one knew about deBruijn to settle the discussion definitively, it appears he solved the problem in 1946 - nice reference.

One thing ignored so far is that is that usually an attacker just wants to steal _a_ car, not necessarily _your_ car. If they go into a parking garage with a suitably modified keyfob transmitter, if they can reach, say, 20 cars of the same make at a single time, the mean time to entry is reduced by a factor of 20: one minute is a perfectly reasonable time to hang around a garage.

Also, unlike smashing a window, slim-jimming the lock or beating up the owner, there is no physical risk involved, or any visible sign that the car has been, or is being stolen.

The combination of high reward and low risk is the vulnerability here.

No car security system is prefectly safe. Every system has a weakness- cryptographically or otherwise. In addition to being guessable, someone could watch from a distance and record the correct password. Keyless fobs are weak because if it goes off in a pocket, you can record a usable key (since the car will look ahead to remain in synch with the fob). Key locks can be picked, and a slim jim will just about always get you in the door.

If your car is a target for thieves, the only way to give yourself a fighting chance is to use as many different methods as possible, and avoid the easy vulnerabilities. Don't ever use easy passwords, never keep the factory defaults for anything, have a physical lock that must be picked and have its encryption cracked at the same time, and park in a secure area.

Whether you're securing a car, a house, or a network, many of these basic rules of thumb apply. People who use "password" for a password and keep the factory defaults are not few and far between, however basic security is becoming an increasingly valuable skill in today's society.

Please ignore the above comment: on rereading, I see this is not a wireless attack.

@dhasenan and @Matt Schinckel: I've heard this called the "Balalaika Effect". The story goes that some guy had never heard of balalaikas, found out what it was (I forget how and why), and then suddenly started noticing them everywhere. There were balalaikas hung on walls, flyers for balalaika concerts, ads for balalaika lessons, balalaika music on the radio, and so on, that he never noticed before.

It's much easier to grab the person's keyless entry, which is pretty much a standard feature on every new car.

Good places to do this are the gym, bars, and Valet parking.

Yes, yes, reminds me again why I don't own any vehicle with a keypad on the door.

The guys in my old neighborhood could open a car with a screwdriver and about 3 seconds. It broke a window, but quietly.

I tried my 2002 Mountaineer and after the 3rd attempt, I had to wait a while before it would allow me to enter in the correct code.

On the other side of the coin, I heard an amusing story on CBC last night about a British woman whose dog ate the engine immobilizer chip that fell out of her car key. This tiny imbedded access control token made her expensive new car useless unless her dog sat on her lap when she started the car. Once the chip passed through the dog, she had to start the car with a bag of dog feces in her lap until she managed to find the chip and wash it.

The pod cast is at:
http://www.cbc.ca/radioshows/AS_IT_HAPPENS/20060927.shtml

Ummm... you can also just see which buttons have fingerprints on them and cut down the search dramatically.

Ah, this reminds me of the cadillacs with the push-buttons that had only a few dozen (if that) combinations. I think it was in the mid-1990s. I'll try to dig it up and post the details if I can find them again.

== Speed ==
Some people have wondered what is the maximum speed at which this can be done if automated. The limiting factor will probably be the de-bounce circuitry. Push buttons connected to digital electronics have a debounce circuit to ensure that a single button push doesn't "bounce" on its contacts and get registered as several pushes.

The time delay for a debounce circuit is adjustable to cater for the characteristics of the button being used, but typical values are from 10 to 20 milliseconds, or 50 to 100 keypresses per second. Note that this is usually *per key*, so we may get a total of 250 to 500 keypresses per second if we choose a de Bruijn sequence which maximises average distance between subsequent presses of the same key. Testing 500 keypresses per second is almost certainly within the processing rate of the underlying chip, even if it is a very cheap microcontroller. (In operation, our key pressing device device will be fast enough to be audible as a warm/dirty hum rather than clicks or buzzing; somewhere between middle C and B4 -- "B above middle C".)

Thus the maximum time to brute force these locks in an automated attack is likely somewhere between 6.5 and 13 seconds; the average time, of course, is half that.

You would not need a Blackberry or Treo to drive this device. Its operation is so simple that one could probably do it in discrete logic; in practice, one would have a $10 microcontroller plus 5 x $4 driver ICs for the solenoids. The solenoids would be around $5 each. (You could make the device smaller and cheaper by removing the tops of the buttons, putting contacts across their terminals and closing the switches electronically instead of electromechanically; however that gives no speed advantage and creates obvious problems.)

== Design flaws ==
It is not true that rate limiting brute force attacks is a new concept. Both the concepts of rate limiting, and its relationship to the keyspace on an electronic or combination lock, have been understood for decades. The basic idea of introducing a delay after (typically) three incorrect attempts -- as described above for the 2002 Mountaineer -- has been used in computer sytems since at least the late 80's, IIRC (I'm specifically thinking VAX/VMS here). Furthermore it is pretty simple to implement in even a cheap microcontroller.

However it does tend to interact badly with the de Bruijn sequence property, in which every key press becomes an individual password test. For example, suppose we have a 5 digit PIN, and a 30 second lockout after 3 incorrect entries. If someone has been playing with the lock in the owner's absence, the first 3 keypresses of his (correct) PIN will come up as incorrect attempts, and lockout the system, causing it to discard the last two correct digits. With the limited feedback capability available, this will likely result in the user becoming hopelessly confused. To avoid this, we *must* have some sort of "Enter" key [1].

Additionally, this property reduces the number of brute force trials by a factor of approximately 5 times. While this is not a huge factor in these types of analysis, it comes on top of an already extremely weak password space, caused by having only 5 buttons instead of the usual 10. The two effects together reduce the number of keypresses required (for a full brute force search) from a reasonable 500,000 to a piddling 3,129.

In short the desire to fit the interface into 5 buttons instead of the usual 12 has forced algorithmic decisions which cripple the security of this device.

== Consequences ==
It's true that you can open a car just as quickly by smashing the window. However deriving the door code is often going to be better, for several reasons:
* in some cases, it may be useful for the opponent to enter the car without leaving obvious forensic traces;
* once you know the code, you can re-enter the car at any time without needing any burglarious tools;
* to anyone who happens to be looking in the right direction, smashing a window is an obviously criminal act. Operating the automated decoder will closely resemble legitimate entry, unless the witness is standing right beside you;
* most modern cars have deadlocks, so smashing a window does *not* enable you to open a door (cars with deadlocks are also immune to "slim jimming"). You can still grab things sitting on a seat, but entering the car will be rather awkward;
* the keyless entry also disables the alarm, whereas smashing a window sets it off!
* on some models, the keyless entry can optionally also pop the boot (trunk), which otherwise is usually the most secure compartment;
* on some models (mostly after-market immobiliser installs, TTBMK) the keyless entry also disarms the immobiliser.

Note that modern OEM immobilisers are very sophisticated, and are rarely directly defeated by car thieves (unlike aftermarket immobilisers which can often by bypassed if the bonnet/hood can be opened to get access to the engine bay -- although a much slower attack than simple hotwiring). Cars with immobilisers are usually stolen either by towing away the whole car, or somehow obtaining a workable replica of the key. Thus, a combination of a weak keypad and linkage to the immobiliser is a fairly serious threat.

____
1. If I had to fix this by upgrading the firmware without touching the hardware, I'd consider using "chording" as the "enter key". That is, press and hold down two keys simultaneously (probably, any two keys) to indicate that you have finished entering your PIN. This is not difficult to detect in a typical microcontroller, and is probably already detected in order to discard such key presses as an error. That alone will slow the attack by a factor of five times, and more importantly would allow the introduction of rate limiting. Rate limiting would work like this: have a one byte global counter, "tr" for "tries remaining". On startup or after a successful unlock, set tr = 5 (one opcode). At the end of an unsuccessful attempt, decrement tr and jump if zero (a single opcode on many microcontrollers). The jump goes to a 60 second sleep routine (single opcode on many microcontrollers), at the end of which set tr = 1.

These two changes require only very small firmware mods, make almost no visible difference to legitimate users (apart from needing to "Enter" an attempt, a very familiar concept), and slow a full brute force attack run from a few seconds to 52 hours max, 26 hours average.

While one could argue that one should not park their car in an area where thieves reside, I find this argument unreasonable in some situations and hence do not fully agree:

You may not know if the area is known to be crowded with thieves, or not. You may be somewhere by coincidence. You may be stuck due to technical failure. You may be exploring an area. Examples: you check out a new shop, you have to be somewhere for business, you found a new girlfriend, you're travelling from a different place by different transporation after visiting a friend, your car broke down after you bought fastfood at , etcetera. There are many reasons to think of. Now, if you stumble upon such situation it is not reasonable to assume you'd suddenly increase your lock security. Hence, you need to act more pro-active and hence the security measure preventing others to break in your car -or worse, stealing the car- should be as sophisticated as possible.

Ways to defeat keyless and keyed cars:

Keyless cars:
*) Looking over shoulder, camera (fun if you're cop using camera's to watch over the concerned people you're serving).
*) Magnesium often shows the numbers used greatly lowering the number of combinations. The longer the combination and the less the available numbers, the weaker this attack is. As defender, its also possible to circumvent it by leaving your fingerprint on all the buttons (your fingerprints will be on them anyway, no worries).
*) Apparently, the attack described here.

The lack of a timeout isn't justified though as it increases the attack time dramatically in a useful manner. If you are stupid enough to enter your code wrong the first time and have to wait 60 seconds then you will, by having to wait, have learned to be sure to type it in correctly next time. And the next next time. And the next next next time. Even dogs and people using recent Windows versions learn in such way. A timeout time of 60 seconds would greatly increase the time a burglar needs to break in a car: in this situation 3129 - 1 minutes; ~52 hours. Assuming the burglar succeeded and isn't caught while performing this repetitive work he'll fall asleep in your car due to being naturally tired ;). He could spread his work through several days, but it would be so discouraging that it'd be easier to do a dictionary attack (i mean equiv to common numbers, don't know name for that) than a brute force attack, or simply chose a different target.

The fact that there is no 'reset' after 5 numbers being pressed is also quite stupid. I'm not a good programmer, but know this is not hard to implement.

Some may say there are easier techniques. However, this technique requires no tools whatsoever. If a burglar has the time then that is in his advantage. In the case someone passes by (though most people don't give a damn), or a cop passes by, the burglar can simply walk away. As the burglar has no tools with him he doesn't seem like a burglar and could just argue he's wandering around (with a more plausable reasoning though). As currently, burglars usually have tools with them, that is an advantage for the burglar (perhaps makes it harder to prosecute the burglar? I don't know on that one). An eye witness may still catch the burglar though. As you can see, that can work in the advantage of the burglar. Although I bet an airport or shop would start using cameras if this would happen often.

Keyed cars (although also applies to doors, etcetera):
*) Some examples given above I don't wish to repeat.
*) Although it requires some training a picture of a key is enough to recreate a replica. Some people even share pictures of their keys on the Internet. Some are made by high quality digital cameras. How nice of them. Most people have no clue whatsoever how keys work ie. that the look of the key contains its 'password'.
*) Lockpicking. Depending on the lock and experience this is time consuming, but for a well-informed and experienced burglar this is peanuts. However, it does require special tools. Similar to the described attack of subject, lock will be unharmed/reusable, and no traces. I have no experience or knowledge on types of locks used in cars. I do know most locks used in house doors are easily pickable, and that they are bumpable. Speaking of bumping...
*) Bumping. Easy, bumpkey is reusable. Excellent if you are interested in doing this regularly (read: wish to be a professional). It takes 5 seconds. So quick, (usually) doesn't damage lock, almost looks legit. No "normal" forensic traces although research on the lock may (and in some cases is known to) prove the lock was, in fact, bumped. If there's no proof of burglary, you can forget your insurance, at least with the insurance policies I'm aware of. Bugger. As bumping is also silent and doesn't trigger an alarm it is an issue in many popular locks. The lock industry doesn't respond to the issues except for competitors of known brands who developed better alternatives. Requires special tools though. This technique has been uncovered in 2005 and 2006 at various conferences by German and Dutch lock experts.

In short, I'd prefer a car with a hard-to-pick, not-to-bump lock. Which my external doors in house already have. They costed slightly more than the casual locks in the mass-market. Spending money on products by people who made a decent product feels good though.

All that said, having a non-stylish/expensive car and leaving no (viewable) expensive items in your car is probably one of the most simple yet effective ways to discourage burglars from breaking your car thing open. Expensive (sport)cars are useless anyway IMO, I prefer a useful one... but that is a different discussion.

Greg said:

(1) leaving the car where there are thieves

Do you mean like every driveway in the country?

Or you can cut out the buttons, and use electronic relays to "press" the buttons.

@J. You can't bump a wafer lock, it destroys the wafers. All but one car type on the UK market uses wafers, the exception being the Bentley.

Modern cars in the UK have the best security in the world now, I am able to open most houses more quickly without damage. Houses here are broken into by gangs to steal the car keys. Oh, and nothing under 5 years old can be slim jim'd. Last time I checked, only one current model US car type was still vulnerable to it.

There is a spate of unexplained security breaches in modern cars in Holland at the moment. See Barry "Bumpkey" Wel's blog at http://www.toool.nl/blackbag/?p=38 and my theory as to how it is being done, in the comments.

My mother had a car in the 80s, (85 nissan Maxima), with keyless entry using a keypad similar to this. The solution was better than the current ones with just 5 keys. The nissan required pressing an 'enter' key which was either an 'open door' or 'open trunk' button. This type of setup negates the kind of attack where you just press a long stream of buttons until the doors unlock. You would have to modify this attack to hit the unlock button after each possible sequence of 5 buttons. This would take longer but probably not much longer.

V Said:
"Or you can cut out the buttons, and use electronic relays to "press" the buttons."

With a screwdriver you can just pry off the keypad, reach inside and short circuit the wires inside to trip the unlocking mechanism. Takes about 10 seconds and leaves minimal visible damage. You could then repair the damage with a bit of epoxy to make it look good as new.

i have a 1992 merc sable with a quorum security system and i want to disable it because its noisy how do i do it.

Someone needs to read a Ford user manual or two--these keypads lock out after 40 incorrect key presses. There's no way you're going to get through this full list of 3129 digits to open all doors as this suggests.

And this device is still extremely common, particularly with FoMoCo vehicles.

I have aftermarket keypad on used Ford Focus. It was on the car when purchased. I don't have the combo, but want to use the keypad. How can I list all combinations to start my journey?
thanks

Well i just popped the entire unit out on my 1994 ford taurus in my driveway, and shorted two wires right off the back of the unit and it unlocked the drivers side.

I am looking for an aftermarket installer of keypad entry systems in the St. Louis metro east area for a customer to have a keypad installed on his new Chevrolet car. Anyone know where we can have this done?

OMG!!! This really does work. I just did this on my husband 2004 F-150. It took about 10 mins. Alot less time than waiting for a locksmith and alot cheaper also.