What combination locks teach us about encryption weakness

Last week, an interesting story made the rounds on social media about a researcher named Samy Kamkar who discovered a flaw in Master-brand combination locks and was able to open the lock in eight tries or less. It’s a great discovery and is of particular interest to security professionals because it teaches us about encryption, the concept of brute-force attacks and weaknesses in implementation.

First, let’s start with combination locks.

A standard Master-brand combination lock has 40 numbers on a wheel. It’s unlocked by turning the dial to the first number, second, then third. In total, there are 64,000 possible combinations on a lock of this type. I chose 10 random combinations and timed myself on the lock to see how long it would take for me to rotate through them. It took me about 12 seconds per combination so to try all 64,000 possibilities, it would take me up to nine days of non-stop working the lock to guess the correct combination. In cryptography, this is called a brute force attack — trying every single possible combination until the one that works is discovered.

Is there an easier way?

Yes, it is often easier to attack the implementation of the cryptography instead of the crypto key. In other words, rather than trying all 64,000 possible combinations, one would look for a flaw in the way this combination lock is designed that will allow an attacker to get the combination much quicker.

Samy Kamkar was able to find the combination of a lock by observing the resistance caused by internal locking mechanisms touching each other. From there, he was able to find a weakness and devise a way to reduce the number of required attempts from 64,000 down to less than eight.

The same type of attack is used against cryptographic algorithms and the Master Lock crack is a very good analogy to help us understand how this works. Cryptographic keys are similar to a combination lock: they have a key that is used to lock (encrypt) and unlock (decrypt). A particular cipher has a key strength — think of this as how many different numbers a combination lock has. A standard combination lock has three different numbers, ranging from 0–39 so the total number of possible combinations are 40³ or 64,000. We can improve the key strength by adding one more number to the mix, meaning one would have to rotate the dial and select four numbers to unlock. This dramatically increases the strength — instead of 64,000 possible combinations, we now have 2,560,000 possibilities.

Cryptographic algorithms employed to encrypt data use the same basic concept. In the DES standard, a symmetric-key algorithm, the key length is 56-bits long, giving it 7.2x10¹⁶ possible combinations. For perspective, let’s look at the most common algorithms along with a combination lock.

AES-256 has an astronomically high number of combinations! This is what the number looks like in standard notation:

110,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

That number is more than the number of atoms in the known universe! Just like you wouldn’t want to try 64,000 combinations on a combination lock, you don’t want to (or can’t) try every possible combination on data encrypted with AES-256. Samy Kamkar circumvented key strength in a combination lock by attacking the implementation; the same is done in encryption algorithms.

If you think about the end-to-end flow of encrypted data, there are many links in the chain: software that encrypts the data, the password (or shared secret), data transmission and software that decrypts the data. The encryption algorithm is clearly the strongest link in the chain. A weak password can shatter the strongest encryption, as can poor implementation of the algorithm and coding errors. All lead to significant vulnerabilities in encryption and, when found, can be exploited.

Examples of some common vulnerabilities that circumvented very strong encryption:

This is just a sampling — there are the BEAST and CRIME vulnerabilities and many others that can circumvent even the strongest encryption. Just one coding error or missing patch can put your business or data at risk.

Cryptography is a complex concept and can be hard to fully grasp. However, it’s important to keep in mind that strong encryption is not a silver bullet to securing data and other factors must be considered when architecting a secure environment. In addition to attackers defeating controls, also consider the ability to completely circumvent controls, just as Samy Kamkar has done with a combination lock.

Originally published at www.csoonline.com on May 19, 2015.