Schneier on Security

Roger • June 15, 2005 10:03 PM

> Interesting noone came up with numbers like 401 and 403 (HTTP response codes).

401 and 403 are pretty funny ("unauthorized" and "forbidden"). If you only keep your lunch in your briefcase you could also go with a more philosophical 417 "expectation failed". However these 4xx codes are technically incorrect since at this point the client entity has sent a properly formed request! You should have 200 ("document follows") or maybe 204 ("no content").

Seriously, when I need to generate random numeric codes for stuff like this, I have a little Perl script which generates random numbers of the correct length, then tests them against /usr/dict/words to find which ones can be converted to a valid word (or multiple valid words if a 0=space is included) via the mapping on a phone keypad.

This isn't perfect of course. It gives a biased distribution because 1 never occurs, numbers that mainly turn into rare letters (e.g. 5) are probably less likely to occur, and certain patterns are impossible. A histogram of output frequencies looks like a binomial + big spike for 0 frequency (impossible outputs) rather than flat, although I think the bias will be much less than picking the word first and then turning it into a number. In exhaustive tests with 4 digit numbers, I get a measured entropy of 11.4 bits versus a theoretical 13.3, so it's not too bad. (Nearly all of the entropy loss is from 7249 values that never occur at all.) Measured entropy/wanted entropy declines as PIN length increases because the number of really long words declines sharply, so for 7 or more digits it's better to split it up. At any rate, it gives me a way of easily having lots of long, random looking, unrelated numeric codes that are much closer to full strength than, say, using your birthday.

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.