Briefcase Locks

I like trying to describe technical concepts to non-technical people. Everybody deserves (and needs!) a basic understanding of the things they use and rely on every day. One of the most important things you use online is your password – or hopefully many different passwords.

I’m not sure if anybody actually still carries a briefcase in 2013, but I remember my father had a briefcase a long time ago with combination locks that consisted of 3 dials. These dial locks are actually a great physical analogy for how passwords work. In this post, I will try to leverage this analogy to explain what makes a password “strong” and how criminals crack passwords.

A Single Dial Lock

In order to start thinking about the security of a dial lock, let’s first simplify by considering a lock that only has a single dial on it.

This dial has the digits 0-9 on it, which means it has 10 different positions. If an adversary stole your briefcase – or maybe just had access to it while you stepped away for a few minutes – how long would it take him to break into the briefcase?

Let’s assume the adversary can only open the briefcase by entering the correct combination; we’re not going to consider smashing the lock open or x-ray vision or anything like that.

Clearly, this single dial lock doesn’t offer much security, because the adversary can simply try every single one of the 10 possible settings of the dial. Actually, the adversary probably won’t need to try all 10 possible settings, because he may find the correct setting by chance much earlier. For the purpose of this article, I’m only going to deal with the worst case scenario: trying every single possible setting in order to open the lock.

In security terms, we call these 10 unique settings the search space, because these are all the possible settings that the adversary may need to try. If the adversary can try one setting per second, then it will take him at most 10 seconds to break into a 1-dial lock like this.

How does the security change if we introduce a second dial?

Intuitively, you might expect that doubling the number of dials would double the strength of the security. Actually, the strength is increased 10 fold! Here’s why: for each possible setting of the first dial (which takes 10 seconds to test), there are also 10 possible settings for the second wheel. Therefore, there are 10 x 10 = 100 possible combinations (a.k.a. search space) between the two dials.

The adversary now needs to try as many as 100 combinations in order to open the briefcase. Under the same 1 combination per second assumption, the adversary needs 1 minute 40 seconds to open this lock. So by adding just one more dial, we increased the adversary’s time by a factor of 10.

How Many Dials Is Enough?

Finally, let’s consider a real 3-dial combination lock – the kind you can actually buy.

The total number of combinations is now 10 x 10 x 10 = 1,000, which is once again a 10 fold increase just by adding 1 more dial. The adversary now requires as many as 1,000 attempts to open a 3 dial lock, which would take 16.7 minutes. This still doesn’t seem very secure, does it? We can already see that no matter how many dials we add, it will always be possible for the adversary to open the lock if he is willing to dedicate enough time to it. How do we even define what “secure” means in this context?

In order to reason about whether the security is “strong enough”, we need to introduce a concept that security experts call a threat model. A threat model is a description of the adversary: who he is, what motivates him, what tools and skills he has, what value he places on the target, what level of access he has to the target, etc. Threat modeling is an important part of reasoning about security. For example, a company may be worried about outsiders trying to gain unauthorized access to their computers, but they may also be worried about insiders who are in a position to abuse the authority that they have. In order to think about security, that company needs to consider each of these threat models separately.

For the briefcase, let’s consider two threat models. The first threat model is that the adversary may try to open the briefcase while the owner is not paying attention. Let’s say the owner gets up to use the restroom and leaves his briefcase behind, giving the adversary a short window of time during which he tries to open the briefcase before its owner comes back. If the adversary can open the briefcase, retrieve the contents, and then close the briefcase, then the owner may not immediately realize that the theft has happened.

The second threat model is that the adversary may steal the briefcase outright. Under this model, the owner notices the theft quickly, but the adversary has the benefit of virtually unlimited time to try to open the briefcase.

With these two threat models in mind, we can begin to reason about various scenarios. For example, if the briefcase only contains credit cards, then the second threat is minimized: the owner will notice the missing briefcase and cancel the cards immediately. In this scenario, the lock only needs to delay the attacker long enough so that the owner can contact the credit card company.

But what if the briefcase contains the secret formula for Coca Cola? If the adversary steals the briefcase in this scenario, he has the entire rest of his life to try combinations until he opens it. Is there an adequate amount of security in this scenario? We know the lock can only delay – not prevent – the adversary’s inevitable opening of the briefcase. Maybe we could make the delay really long… like 100 years? That would probably exceed the lifetime of the adversary, thus keeping the secret formula safe. Of course maybe he hands it down to his child. Can we delay the adversary by 10,000 years? How many dials would that take?

A Few Light Maths

We can answer these questions using a little high school algebra.

We already know that we can add more and more dials to the lock in order to increase its strength. We’ve already seen that each lock increases the strength by a factor of 10, due to the fact that each dial has 10 possible settings. Generalizing, we can write the number of possible combinations as 10ⁿ , where n is the number of dials. For example, if we build a lock with 6 such dials, the total number of possible combinations is 10⁶ = 1 million. At 1 second per check, that would delay the adversary by about 11.6 days.

The question at hand is how many dials (the n in our equation) are needed to delay the attacker by 100 years? There are about 3,155,973,600 seconds in a century. We can write this equation as 10ⁿ = 3155973600. For the math impaired out there, we can solve for n by taking the logarithm (base 10) of both sides: log₁₀ (10ⁿ ) = log₁₀ (3155973600). This simplifies to n = log₁₀ (3155973600). Now you can break out your calculator to solve for n.

Wait, you just want me to tell you the answer? Ok, fine, n is approximately 9.5 dials. We don’t have half dials, so we’ll have to round up to an even 10. A briefcase lock with 10 dials on it would delay an adversary from opening it by over a century! You can use the same math to figure out how many dials are needed to delay the adversary for 10,000 years, but I’ll save you the trouble: it’s about 11.5. So with only 12 dials, we could construct a combination lock that would take over 10,000 years to open.

If you glazed over during the unpleasant math-y stuff, please at least take away this:

• With 3 dials, we delay the attacker by a matter of minutes.
• With 6 dials, we delay the adversary by a matter of days.
• With 12 dials, we delay the adversary by a period longer than the written history of human beings on Earth.

In other words, as we add more dials, the search space starts to grow very, very [shockingly!] quickly.

Passwords

This is getting to be an elaborate analogy… where was all this headed?? Oh yeah, passwords.

I hope you already see how the briefcase lock is like a password. Each letter in your password is like a dial. Instead of setting each “dial” to a number from 0 to 9, you set each character in your password to a letter, number, or special character. Just like the briefcase lock, an adversary can try all possible combinations of these letters, numbers, and special characters in order to guess your password.

We already said the search space for the briefcase lock is 10n. We know that n is the number of dials. But where did the 10 come from? Recall that it is the number of settings on each dial. So for our password, we need to count how many different possible values there are for each character. Let’s start with the 26 alphabetic characters and 10 numeric digits. That’s a total of 36 possible values for each character of our password. If we pick a random 8 character password, then the search space is 36⁸ . This is a seemingly big number, 2,821,109,900,000, nearly 3 trillion possible passwords.

How fast can an adversary go through the search space of possible passwords in order to crack this password? There are many possible threat models here – there’s that term again – but it can range from very, very slow (a few checks per day) to extremely, absurdly fast 350 billion checks per second. In the latter scenario, an adversary can try every single one of our 3 trillion possible passwords in about… 8 seconds. Yikes.

We saw with the briefcase dials that we only had to add a small number of dials in order to get a dramatic increase in the size of the search space, and thus a dramatic increase in security. Can we do the same with passwords?

Let’s improve our password by adding mixed case letters, and let’s throw in some special characters: @, #, $, %, &, *, ? and !. That increase the number of possible characters in our password from 36 to 70. Let’s also double the length of our password from 8 characters to 16 characters. This new password has a search space of 70\ :sup:16. This is such a huge number that it makes the previous example look like a joke: 332,329,310,000,000,000,000,000,000,000. That’s close to 1 nonillion possible passwords! That number is so freakishly big that neither you nor I has ever heard the word nonillion used in conversation.

We already said that the adversary can check 350 billion passwords per second. At that rate, it takes him 30,088,871,774 years to check all of these possible passwords in our new search space. This is such a huge span of time that it’s hard to relate it to anything we humans know of, but here are a few ways to imagine it.

30,088,871,774 years is:

• 6 million times longer than the written history of human beings.
• 150 times older than dinosaurs.
• 3 times longer than the estimated age of the universe.

So it’s a big number, mmkay?

Conclusions

So what have we learned about passwords?

Well, first of all, there’s a very good reason why many passwords have minimum lengths and require numbers and special characters. Due to the exponential growth of the search space, just a few simple requirements can make the difference between easily crackable passwords and completely uncrackable passwords. And although we can see that no password is literally uncrackable, we see that we can make our password long enough and random enough to make cracking preposterously unlikely.

We can also see that security relies not just on mathematics and large numbers; we also need to consider threat models. If we pick a different threat model, then the whole situation changes. Sure, the sun will burn out and the universe will die of heat death before anybody can guess your really strong password, but nobody needs to guess it if you write it on a post it note and put it on your monitor.

In order to reason about security and what level of security is “good enough”, we must first define the threat that we wish to secure against.