Cracking a combination lock

I was thinking, how long would it take to crack a combination lock by bruteforcing it?

Assuming a combination lock has

$$40^3$$

different combinations, and it takes about ten seconds for each try. In hours, it would take about

$$\frac{40^3*10}{3600} \approxeq 178$$

hours. This is the worst case scenario having the combo be (39 39 39).

My question is, is there any faster way the lock picker could get the combo without brute forcing it? (And of course getting bolt cutters :-)) Also, is there a way to calculate an average case performance in hours?

1 Answer

Yes

In fact, there are optimizations which cut this time by a factor of $\hat \eta$.

$\hat \eta$ is the diameter of the acceptable error region around any one mark on the dial in units of marks. If you've noticed every time you've gone to the gym or remember back to your days in high school, you didn't need to line up the marks on the dial exactly with the arrow on your padlocks. This means that you can be off by $\frac{\hat \eta}{2}$ marks in either direction and it'll still register for the combination.

Often, $\hat \eta > 1$. This allows a lock-breaker to try every other 2 or 3 (sometimes even 4 marks for low-quality locks).

For example, $\hat \eta = 2.5$

Combination: 10 20 30

Attempt: 12 18 32 SUCCESS

This reduces the number of attempts you need to make to $\frac{40^3}{\hat \eta}$ by rotating the dial by $\hat \eta$ instead of by 1 grade.

Guessing the $\hat \eta$ is a the difficult part, however, you can try optimistic $\hat \eta$ and reduce it every time you exhaust all combinations.

With your new $\hat \eta '$, you can select your starting point to minimize the number of collisions with already tested combinations. For breaking into a physical lock, it is a worthwhile to solve this alignment sub-problem because of how time-expensive testing combinations is. For a virtual example, the alignment problem may take longer than simply checking the collisions again.

You are actually quite likely to have broken into the lock before reaching the actual value of $\hat \eta$ of the lock, assuming you attempt to avoid collisions as described above.

To ensure that you don't test more than is necessary, you need to pick a finite sequence of $\{(\hat \eta_n, \theta_n)\}$ where $\theta_i$ is the starting point on the dial for iteration $i$ such that

$$ \frac{40^3}{\hat \eta_1} + \frac{40^3}{\hat \eta_2} + \dots + \frac{40^3}{\hat \eta_n} \le 40^3 $$

As you can see, this method is does not depend on the number of grades on the dial (therefore the number of combinations doesn't matter).

$$ \frac{1}{\hat \eta_1} + \frac{1}{\hat \eta_2} + \dots + \frac{1}{\hat \eta_n} \le 1 $$

If your initial guesses aren't optimistic enough, you can pick more optimistic ones later to more closely approach $1$ in the above sum. Once you've picked a final $\{\hat \eta_n\}$ such that the sum meets or exceeds $1$, you've performed more tests than trying all combinations in the standard bruteforce manner. If you still haven't cracked the lock by now, you may have poorly chosen your $\hat \eta$s.

Picking $(\hat \eta_{k+1}, \theta_{k+1})$ given $\{(\hat \eta_k, \theta_k)\}$

We want to maximize the area of coverage under this new hypothetical $\hat \eta_{k+1}$

Let $m$ be the number of marks on the dial,

$$ f(\hat\eta, \hat\eta_i, \theta, \theta_i, m) = \begin{cases} 1 & |\theta_i + n\hat\eta_i - \theta| \le \hat\eta,\text{ for any } n \in \left[0, \left\lceil \frac{2\pi}{m\hat\eta} \right\rceil\right] \\ 0 & \text{ otherwise } \end{cases} $$

$f$ defined above is a density function. It's $1$ when $\theta$ on the dial is already accounted for under the new choice of $\hat\eta$ given a previous $(\hat\eta, \theta)$, $0$ otherwise.

Below is the optimization problem, when solved, that gives us a best $(\hat\eta_{k+1}, \theta_{k+1})$ to pick next for the fewest collisions:

$$ \min\limits_{\text{w.r.t. } \{(\hat \eta_k, \theta_k)\}} \sum^k_i \sum^{\left\lceil \frac{2\pi}{m\hat\eta_{k+1}} \right\rceil}_j f(\hat\eta_{k+1}, \hat\eta_i, \theta_{k+1} + j\hat\eta_{k+1}, \theta_i, m) $$

Average case time complexity

To have a meaningful answer to this, the $\hat \eta$ of the specific lock would have to be known. If it's known, a majority of the method isn't used and we simply check $O(\frac 1 {\hat \eta})$ combinations. If it's not known, then we need to have knowledge of the domain of lock quality (all possible locks and all possible $\hat \eta$s they could have and with what probability). This is infeasible at this time.

In this answer, I use $\{a_n\}$ as a short-hand notation for a finite sequence of length $n$ with $a_i$ as elements for $1 \le i \le n$. This normally should be interpreted as a set with a single element. Notation used for simplicity and reduction of symbols in an already symbol-rich answer.