Let's Code About Bike Locks

http://nbviewer.ipython.org/url/norvig.com/ipython/Fred%20Buns.ipynb

by platz • 11 years ago

93 30 11 years ago

nbviewer.ipython.org

patcheudor• 11 years ago

Just like every other barrel combination lock, these are trivial to compromise. For me, trivial equals not needing any tools and opening it quickly enough to not draw any attention in a public space. Recently someone locked their bike to my fence with one so I figured it was fair game since it was on my property & fastened to my fence. The combination was "FUSE." The first thing that popped into my head was "short fuse" so I put the lock back on and spun the tumblers.

megablast• 11 years ago

You should always have two different locks anyway.

rplnt• 11 years ago

Doesn't matter, had bolt cutters. While it's easy to open most of these combination locks, it's always faster just cutting through it. So two locks won't help at all if one takes under five seconds to get through. One proper lock that can't be cut with smaller cutters and a hope is all you need. Hope that someone with a bigger cutter, pneumatic one, or an angle grinder won't come/

emhart2• 11 years ago

Combination locks that use letters/characters/non-numeral-glyphs have been around for an astoundingly long time, what's interesting about the word lock, though, is that they start with words, then make the dials.

https://www.google.com/patents/US6621405

The patent goes into detail - and is actually super easy/enjoyable to read - but the goal was to have a letter lock that maximized the number of real words that could be spelled from the available letters provided on the dial rings. So, a wordlist is generated under some parameters (such as word length) and then the rings are generated from that word list.

It's basically exactly what the author is doing, but in reverse.

The goal of the word lock was to increase the available keyspace of real words in a letter lock, thus increasing the security of those users who will buy a letter lock regardless. They do a number of other things right mechanically as well. Whether or not a bike lock is the best medium, I wouldn't say, but wordlock silently improved the security of a specific user base that greatly prefer convenience to security. That's awesome.

hackmiester2• 11 years ago

Unfortunately, the locks are not configurable.

kazinator6• 11 years ago

The better ones certainly are. I have one.

When the lock is open, you can rotate an inner cylinder (not accessible while the lock is clasped) to a position which allows the outer rings of the dials to be moved to change the code.

Bought at a Canadian Tire store in Richmond, British Columbia. (See, even available in Canada.)

norvig• 11 years ago

Very nice find on the patent, emhart. Thanks! It looks like the patent is the same as my `greedy_lock`, except that at each tumbler "the entire word list is scanned"; this is worse than scanning just the words that make it through the previous tumblers. Also, I was a noob at lock terminology; I should replace "dial" with "tumbler".

emhart2• 11 years ago

Thanks. I hadn't yet arrived at the greedy lock portion when I posted the above, but I finished the article soon after and absolutely loved it. The other thing worth noting is that while it sounds like there was some regional bias toward Fred Buns at your store, they should have different combinations of dials/letters on some of their locks. Also, also, some should be reconfigurable, which leads me to the challenge:

Optimal combination of dials in the circumstance that the dials can be rearranged.

& Don't sweat dial/tumbler, dial is more specific anyway, tumbler is the generic word.

aaronharnly• 11 years ago

Great post, lucidly written as always.

With the last part about "FRED BUNS", doesn't feel a bit like he's committing a variant of the Texas Sharpshooter fallacy[1]? (That's the old saw about the Texan who takes a bunch of shots at a barn, then walks up and paints a target to encircle them.)

While the chances of "FRED BUNS" may be slim, the chances of /some/ pair of words being present in adjacent lines is much better. How much better? Uh, I'll let you know once I'm not on my phone and not lazy...

[1] https://en.wikipedia.org/wiki/Texas_sharpshooter_fallacy

kazinator6• 11 years ago

That sounds more like birthday paradox: like the surprise that two people in a crowded room have the same birthday.

Of course, that paradox is related to the Texas sharpshooter. Why? Because you find the pair with the same birthday (say Bob and Alice) and then form a hypothesis that it must be hard to find someone with the same birthday as Bob, so, gee, that is surprising.

zellyn• 11 years ago

https://www.goodreads.com/quotes/649893-you-know-the-most-am...

kazinator6• 11 years ago

The lock makes 1118 words (according to my word list). You might say that this lock is only 11.18% as secure as a 4-digit lock with 10,000 combinations.

What? It's exactly as secure; there are four dials with ten symbols. Wait, of course, Norving means dictionary words. Well, don't constrain yourself to dictionary words! You wouldn't use a dictionary word for your gmail account, right? Configure the lock for some arbitrary four-letter combination.

(There is still value in that over a lock with digits embossed on its dials, because some people can memorize a four letter combination which isn't a word more easily than four random digits.)

Here is another thing: you can configure a WordLock such that your chosen key word is something meaningful, but must be assembled in a row other than the "home row" to open the lock. That improves the security somewhat in the situation when you stick to code which is a word (as defined by Norvig). You have one more secret: the offset of your word.

If your offset keyword is such that gibberish occurs in the home row, then a naive search of meaningful words on the home row will not open the lock, so there is a "security through obscurity" element at play here too against (non-wirecutting) brute force attackers who don't know about this trick.

You might as well then memorize that home row gibberish, and use the original offset word as only a mnemonic to recover the gibberish if you forget: you can assemble the original word, and then rotate the dials in parallel until the lock opens.

lnanek2• 11 years ago

The article claims you can't set the combination word, so probably assumes it is always a valid dictionary word preset by the manufacturer. That said, the WordLock web site says you can change the combination, and obviously you can on similar locks that have numbers instead of letters, so really the author probably just didn't know how.

kazinator6• 11 years ago

I know about this limitation, and I suspect it is only true for some "low-end" models of the WordLock.

I have one and it is configurable. For a while I used ROOT as the code, ha!

I have seen ones which are immutable. They featured thinner cables and smaller locks. (Maybe there are more hefty WordLocks which are also not configurable; I don't know.)

jthomas5545• 11 years ago

Just to be silly.. These locks are not secure and you do not need to know the word. I have known how to do this on these types of locks since I was 12 which is no 26 years ago. https://www.youtube.com/watch?v=BcGJpVEq56Y

jchrisa• 11 years ago

It's like a timing attack.

girvo• 11 years ago

You can heard the other kid whisper the word to him at https://youtu.be/BcGJpVEq56Y?t=86 -- I am curious if the method does work however.

Someone• 11 years ago

"I happen to have handy a file of four-letter words (no, not that kind of four-letter word)"

And yet, I spot such a word in many of the high-scoring combinations (hint: it appears near the word 'CUTE')

It would not surprise me if the makers of these locks had a list of forbidden words.

shabble• 11 years ago

I've known some systems that exclusive "offensive" words/substrings, occasionally leading to the ol' Scunthorpe Problem[1].

Personally, I feel the opposite should be enforced. If you make the password vile enough, people should be less willing to tell it to other people :)

[1] https://en.wikipedia.org/wiki/Scunthorpe_problem

tgb2• 11 years ago

Another interesting kind of lock I've seen are some masterlocks that give you a "joystick" of sorts and you make passwords by moving them in the for cardinal directs, for example your password might be up up down down left right left right. What's interesting is that A) you can set your own password and B) they claim no upper bound on the length of your password!

My first thought was "impossible!" and I tried to disprove it. I set it to a long password and tried to unlock it by, say, doing all but the last stroke assuming it was just dropping the strokes after a point. No luck. Same for dropping the first stroke. Etc. But sure this mechanical system has a small finite number of possible sufficiently distinct states and so would only be able to use small password lengths?

Of course! But it's apparently being much smarter about it than I had anticipated: sure, my long password can (presumably) be opened by a shorter password. But that shorter password is apparently unrelated to the long one. They must be taking a mechanical hash of the password!

Here's the lock: http://www.masterlock.com/personal-use/product/1500iD But I wouldn't recommend buying one. They were too bulky and got stuck in the locker at my gym and had to be cut off.

JoshTriplett• 11 years ago

Have you tried transposition of motions in a short combination? In particular, have you tried swapping the first direction with every direction in the short combination? Have you tried a combination consisting entirely of the same direction, and shortening or lengthening that?

Because one possible (bad) implementation would be an MxN grid with a specific point as the unlock coordinate. A slightly less bad implementation that doesn't permit trivial transpositions would be such a grid plus a long internal pad that modifies the direction (realdir[i] = userdir[i] + lockspecificdata[i%LEN]%4).

tgb2• 11 years ago

Unfortunately I don't still have the lock to try that. I was also looking around and found this video: https://www.youtube.com/watch?v=aPKVMTGqTQo which is quite illustrative of its internals as well as this patent https://encrypted.google.com/patents/US6718803 which seems to be for it. And it looks like you're right! The "hash" appears to just be the pair (x,y) where x is the net motion right and y is the net motion down. This is pretty worrisomely bad! In particular the example password I gave at the start would be equivalent to having no password at all!

If I were to try to make this more secure, my first guess would be to have a varying number of pins on each of the four wheels, particularly having the top/bottom and left/right pairs being coprime to each other. Then there'd be a much larger number of possible positions, though I'm not sure if this would make it hard to configure the password.

(And actually, the pair (x,y) is taken mod 5 (I think), just to make it worse.)

glyphobet• 11 years ago

There's an improved algorithm that finds a better lock, one that can do 1,410 words: https://blog.glyphobet.net/essay/2770

glaberficken• 11 years ago

Apparently not! =) but good try

"Update 15 Jun 2015: Someone was wrong on the internet and this time it was me! Astute readers will notice that a tiny off-by-one bug in my implementation (see the fifth revision) led it to generate a lock with three tumblers with eleven letters each, and one tumbler with ten letters.

The new best lock from this implementation only generates 1,161 words, leaving Norvig’s solution the best still:

Lock: ABCDLMPRST AEHILNORUY AEILMNORST ADEKLNOSTY"

Let's Code About Bike Locks

Related Stories