Let's Code About Bike Locks(nbviewer.ipython.org)
nbviewer.ipython.org
Let's Code About Bike Locks
http://nbviewer.ipython.org/url/norvig.com/ipython/Fred%20Buns.ipynb
7 comments
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".
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.
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.
Unfortunately, the locks are not configurable.
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.)
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.)
Oh, my mistake! Mine doesn't have that ability, and if you make that assumption, the article is accurate. I didn't know some could do that.
So, the best way to use a lock like that would be to pick a non word sequence. And regardless of the combinations these locks and all their derivatives are very easily opened even if you don't know the combination.
I once destructively opened a friend's U-Lock in about 60 seconds. (The key broke, didn't have copy.)
I took a 10 dollar hack saw and sawed through the main bar of the lock (not the U).
It was like a hot knife through butter.
I took a 10 dollar hack saw and sawed through the main bar of the lock (not the U).
It was like a hot knife through butter.
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.
You should always have two different locks anyway.
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/
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
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
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.
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.
> 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.
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.
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.
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.)
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.)
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
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.
It's like a timing attack.
The locks are not precisely made. If you put tension on them, then in theory, it should be evenly distributed into the four notches in the shaft which mate with the dials. But in reality, one of the notches hogs all the tension, due to imprecise machining. You can turn the dials and feel for which one it is; when you find it, you have defeated that dial. It is now open, and so there are three left to attack the same way.
That's effectively how picking a pin-tumbler lock (most locks that use a key) works too. Put some torque on the tumbler, then push on each pin to find the one with the most resistance. Push that one up until it takes a set. Repeat until the lock opens.
There's ways around that. Simply put notches that don't go all the way through the dials and you've effectively defeated that method of attack. Kinda like trying to rake a lock with spool pins.
"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.
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.
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
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
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.
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.
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).
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).
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.)
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.)
[deleted]
There's an improved algorithm that finds a better lock, one that can do 1,410 words: https://blog.glyphobet.net/essay/2770
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"
> "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"
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.