Schneier on Security

Roger • June 16, 2005 11:45 PM

@jammit:
“Even I can open a four digit combo on a bike lock in a few minutes.”

Assuming you’re talking about brute forcing rather than feeling the correct positions (which is often possible on cheap bike combination locks), you’d have to be fairly lucky to do 4 digits in “a few minutes”. There are ten thousand equally likely combinations, so although you might get lucky and hit it early, on average you will need to try 5,000. From a quick experiment I find I can manage 2 to 3 combinations per second but only for a few seconds, it soon drops to about 1 per second. That means on average you should take over an hour, and might take up to 2 3/4 hours.

However, if you have a simple way of recording the swept keyspace (e.g. counting), and the bike is parked in the same spot each day, then you don’t have to do it all at once. This fact (due to the inability to change the combination) is enough to make me avoid these locks even for a cheap bike.

This, incidentally, brings to mind what is in my mind a serious design flaw in briefcase locks. Most briefcases have two thumbwheel style combination locks, each with usually 3 wheels. The two locks are operated totally independently, which presumably makes them easier to assemble but also means the average difficulty of brute forcing is not a strong 0.5 * 10^6 (say, a week to brute force even with 24 hr shifts) but instead a puny 2 * 0.5 * 10^3 (about a quarter of an hour). Furthermore the latter attack can be parallelized (one person trying each lock), which happens to reduce the average time by 1/3.

It might be argued that stronger locks are irrelevant since the case can be forced open with a screwdriver or bodily carried away and opened at leisure. However briefcases are usually used to protect documents, and in document security it quite often happens that an undetected theft is far more serious than one which is quickly detected. With locks this weak it would be possible to undetectably open the case, copy documents and put everything back the way it was in any of a variety of scenarios. Furthermore, it shouldn’t be hard to fix. If the sliders of the two locks are connected internally by a simple rigid bar, it wouldn’t be possible to open either lock until both are correct. (The bar would need to be stiff enough that you couldn’t feel a small amount of “give” when one only of the locks is on the correct combination.)

Roger • June 18, 2005 1:30 PM

@Probitas:
Actually, your briefcase password is two 3 digits strings, which is 500 times weaker than one 6 digit string.

@Dan:
Oh, OK. The one I tried timing myself with, you couldn’t turn the wheels while there was pressure on the slider.

@Erik N:
A nice problem. I found a solution–not a closed formula, unfortunately, but a reasonably efficient algorithm, a type of greedy algorithm. Basically I keep an array of all 1,000 triplets, each pointing to a list of the remaining digits with which they have not yet been used. I then build my sequence list incrementally, as follows: take the last three elements of the list, and look up which digits have not yet been used for that prefix. For each of these digits, form a tentative new triplet, and find which of these would give the greatest number of candidates at the next step. If several are equally good, pick one at random. If none of them give any, then we have backed ourselves into a dead end; start again. If you get up to 10,003, run a test to see if the answer is correct.

This algorithm frequently gets the list around 9,900 items long before stalling and having to restart; after about 200 ~ 500 attempts (taking a couple of minutes), it gets one which works. Multiple distinct answers are possible and are distinct beyond a mere relabelling of digits. I can send you the program if you want to give it a go.