Wednesday, October 7, 2009

Picking Locks

Picking Locks - Sheva Apelbaum

A year a go I got a new bike and a 4-disc, 6-digit combination lock.  A few weeks after getting it, my dad opened it told me the combination and then locked it around my bike’s seat post.
Then I  promptly forgot the combination.

When I asked my mom if she remembered it, she said no, but he suggested that I try some of my favorite combinations (Fibonacci numbers). Sadly, none of them worked.

So there I was, unable to ride my bike to school because I couldn't open the lock.  I asked my dad if we could contact the manufacturer for help opening the lock or just send it back and ask for a replacement.  My dad, who does software engineering and computer security, said that he had a better idea. Instead, he suggested I should figure out the combination by myself.  At first, I thought that would be impossible, but then he told me about the “brute-force search” method.

With a little bit of experimentation (I wrote on my whiteboard all the combinations for a simple 2 dial 3 digit lock).

I came up with the following formula for calculating the number of combinations for any lock:
clip_image002[4]

Where:
NC = Number of combinations
UN= Upper disc value (the number of digits on the disk)
ND= Number of discs in the lock
In my case the lock has 4 discs and each one has a 1-6 number range.  After plugging the numbers into the equation, I got
 clip_image002[1]

So, in order for me to open the lock, I would have to try up to 1296 combinations. Wow, that's a lot of combinations!

After thinking about this problem for a while,  I figured that if I try 500 combinations a day, I would be done in 2.5 days. I told my dad about my plan and he suggested that before actually trying the combinations, I should write them down and check them off as I go along.  He also suggested that instead of writing all of them down by hand, I should use a spreadsheet.  When I tried creating all 1296 combinations manually on a spreadsheet, I found out that this was also going to take a lot of time (and I would probably make some mistakes along the way).

So I asked my dad to help me write a computer program (you can download the Combination Number Generator here) to generate all the lock numbers and help track them as I tried each one.  The program is written in Microsoft Excel (you will need to enable Macros in order to use it) and it quickly calculates and outputs all possible lock combinations (see sample combination table below).

Dial-1
Dial-2
Dial-3
Dial-4
6
6
6
6
6
6
6
5
6
6
6
4
6
6
6
3
6
6
6
2
6
6
6
1
6
6
5
6
Sample Combination Table

I generated the spreadsheet and every day after school (before going to bed), I spent 20 minutes going through the list of combinations.  I started with the lowest number range (1111) and worked my way upwards.  Finally, on the third day, after spending 45 minutes turning dials I found my combination.
That was a very satisfying moment!

I have to admit that when I first started the search for my forgotten combination, I didn’t think that I’ll be able to find it.  But after finding it, what I can say with certainty is that brute force search works.  All it takes is patience and the right tools.

1 comment:

  1. This is what I've heard, too, especially when relating to police-work (detective work). It can take years and years to solve a crime, but by using this method you can have success. Now, let me see, where did I put my keys...?

    ReplyDelete