Let me begin by asking you a question. Why exactly are we supposed to use strong random passwords? Your answer is likely to be that, it is to make it hard for an attacker to guess the password. In other words, let’s say you set the password for your online banking account to be a random 8-digit string. There are in total 108 possible 8-digit strings, and since each digit is random, an attacker should ideally go through every possible 8-digit password to narrow down on the right password. If each trial takes 10 seconds, then cracking the right password could take almost 2000 years to guess your password.
Unfortunately, in reality, a hacker might be able to crack your password within just a few hours, even if every digit in your password is entirely random. The attacker could gain information about your password from unusual channels and squash the number of possible passwords from 108 to, say, just a few thousands. This might sound unintuitive, but read on for an illustrative example.
Consider a combination safe with a 6-digit secret combination. Ideally, an attacker needs to try all 106 possible combinations to crack the right one. Does that hold in reality? No, says the CEO of Sparkfun Electronics, Nathan Seidle, an electronics and puzzles enthusiast. Recently, he showed how to easily narrow down the combination space of SentrySafe Model MS0100, a dial safe with 6-digit secret combination, from a million combinations to just a few thousand combinations.
Here is a quick review of how a dial safe works. It consists of three internal discs — Disc A, Disc B, and Disc C. The secret 6-digit combination is divided into three 2-digit numbers AA/BB/CC, corresponding to the discs A, B, and C, respectively; let’s call them the disc combination numbers. Roughly speaking, each disc has a deep notch, and if the dial is turned clockwise to AA, then anti-clockwise to BB, and then clockwise to CC, the notches get aligned, and the safe opens. If you are interested in knowing further details on how a safe actually works, check out this video.
Squashing the Number of Possible Combinations
Since the combination is a 6-digit number and each digit can take any of the 10 values, there are in total 106 possible combinations. Let’s assume that an attacker can perform one trial in 10 seconds. It could take almost 116 days for the attacker to narrow down on the right combination. That is actually a decent level of security. However, as Nathan Seidle explains, there are a few tricks that can reveal enough information about the secret combination, to drastically reduce the the number of possible combinations.
Non-uniqueness of the combination: It is crucial that only one unique combination works on a safe. However, due to manufacturing imprecisions, combinations that are +/- 1 for any of the three 2-digit disc combination numbers can also open the safe. For example, if 839025 is the right combination, 839125, 839124, 828926, etc. also open the safe. Thus, each 2-digit number is equivalent to its two neighboring numbers. Hence, effectively, there are only 33 x 33 x 33 possible combinations, as against 100 x 100 x 100 combinations.
Invalidity of certain combinations: Recall that the right disc combination number corresponds to the position of a deep indent on the disc. It turns out, an attacker could learn the disc combination number of the outermost disc, namely Disc C, just by a simple physical examination. In order to avoid this, the discs are designed to have camouflaging shallow indents that are hard to distinguish from the actual notch, through the physical examination. However, the flaw in the design is that there are only 12 indents, instead of 33 indents. Clearly, the disc numbers that do not correspond to the indents can be ruled out. This leaves us with 33 x 33 x 12 combinations.
Imperfect camouflaging of the secret combination: The deepest indent on Disc C, i.e., the notch, happens to be skinnier than the other indents, again due to a design imperfection. By detecting the position of the skinniest indent, it is possible to identify the disc number CC. Hence, the number of possible combinations is down to 33 x 33 x 1.
33 x 33 x 1 combinations can be tested in just less than 3 hours!
Computing Systems Give Away Secrets
Like in the case of a safe, many systems have secrets hardcoded within (in the form of a hash, for example); otherwise, how else will the system know which passwords to authenticate and which ones to refuse. And, unfortunately, whenever we hardcode a secret into the system, the system is likely to emit information about the secret in one way or the other.
For example, consider a password-based login system. Typically, the system keeps a record of the hash of your password. Every time you try to login by entering a password, it computes the hash of the entered value with the stored hash value. If they match, the system lets you in. The ideal properties of the hash function is that, it should not reveal anything about the password. However, popular hash functions, such as, MD5, SHA-1, etc. are not as secure and can leak undesirable information about the password.
Non-uniqueness of the password: If the hash function does not create unique hash values, then multiple passwords can have the same hash value. In that case, multiple passwords can pass the system.
Invalidity of certain passwords: Let’s say, a hash function always hashes passwords that are even numbers to even numbers and odd numbers to odd numbers. Then, if the hash value is an odd password, the attacker can easily rule out half the password space.
Imperfect camouflaging of the secret password: Let’s say, a hash function is such that the first digit in the hash value is the same the first digit of the password. Although it is crucial that every digit of the password is “perfectly” camouflaged by the hash function, imperfections of the hash functions used in reality can leak away certain parts of the secret.
In general, the return-on-investment of a security measure in an ideal world is not likely the same as it is in the real world. Often, strong security measures strengthen the stronger parts of the system, while the weakest link becomes the primary attack surface for the hackers. Hence, a holistic view of a system is necessary to correctly asses the actual gain of security measures.
Image source: Flickr photo flickr photo by Terekhova shared under a Creative Commons (BY-NC-ND) license