Schneier on Security

Roger • September 28, 2006 7:25 PM

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