More on attacking combination locks

[1] You could just treat this as if it were a keypad with more buttons.

For example, suppose you can push either one or two buttons at a time on the lock pictured above.

Then you could treat this as a lock with 15 buttons: the five actual buttons and 10 virtual buttons corresponding to the ten ways you could choose 2 buttons out of 5 to press at the same time.

Maybe a lock would let you press even more buttons at once.

I don’t think I’ve ever used a combination that required more than two buttons at once, but in principle you could push up to five buttons at once in the photo above, for a total of 31 possible button combinations.

And since 31 is prime, you could use the algorithm here to generate the corresponding De Bruijn sequence.

If you know how long the password is, you can try the De Bruijn sequence for passwords of that length.

But what if you don’t know the length of the password a priori?.You could try the De Bruijn sequence for passwords of length 1, then length 2, then length 3, etc.

But is there a more efficient way?.If there are k button combinations and the password has length n, then the optimal solution is to start entering a De Bruijn sequence B(k, n) until the lock opens.

If you know the password has length no more than 4, then you could try a B(k, 4) sequence, and if the password is actually shorter than 4, say length 3, you’ll still open it.

But what if you’ve tried a B(k, 4) sequence and it turns out the password has length 5?.You could do better than starting over with a B(k, 5) sequence, because some of the substrings in that B(k, 5) sequence will have already been tried.

But how could you do this systematically?.If you don’t know the length of the password, how could you do better than trying B(k, 1), then B(k, 2), then B(k, 3) etc.

?.Related posts Cracking passcodes with De Bruijn cycles Generating De Bruijn cycles Combinatorics just beyond the basics [1] For this post, I’m assuming the lock will open as soon as you enter the right sequence of buttons.

For example, if the pass code is 345 and you enter 12345 the lock will open.

I don’t know whether these locks work that way.

Maybe you have to turn the handle, which would effectively act as an enter key.

But maybe there’s a way to listen to the lock so that you’ll know when the combination has been entered, before you twist the handle.


. More details

Leave a Reply