The ABC’s of Password Cracking: The True Meaning of Speed

November 30th, 2020 by Oleg Afonin
Category: «GPU acceleration», «Tips & Tricks»

When adding a new encryption format or comparing the performance of different password recovery tools, we routinely quote the recovery speed expressed in the number of passwords per second. But what is the true meaning of password recovery speeds? Do the speeds depend solely, or at all, on the encryption algorithm? What’s “military grade” encryption, and does it guarantee the security of your data? And why on Earth breaking AES-256 encryption takes so vastly different effort in different file formats? Read along to find out.

If you aren’t familiar with password cracking, I recommend reading What is Password Recovery and How It Is Different from Password Cracking first. Before we start discussing the differences in encryption, let us first talk about what you need to launch the attack.

More often than not, in order to break an encryption password you’ll need access to the entire file or document. In many cases, the encryption metadata (which includes the password hash, salt value, and sometimes additional encryption parameters) is stored in the beginning of the document in the file header. As a result, for most file formats you can extract the encryption metadata (sometimes referred as simply “hashes”, although there is more than just hash values stored in the encryption metadata). However, there are several exceptions to this rule.

One notable exception would be the RAR3 and RAR4 formats. To crack passwords, you’ll need almost the entire content of the archive and not just a tiny hash from the file header. There are other formats where you’ll need to decrypt and validate a certain block of data in order to verify the password. Even if both the encryption algorithm and the hash function are the same, such formats will always be much slower to break due to additional computations required to validate the password.

The password verification method is not the only thing affecting the speed of the password recovery attack. There are formats allowing several million password combinations per second, and there are formats where you are limited to single-digit speeds.

The numbers don’t tell the whole story

Almost everyone makes use of AES-256 for encryption, yet some formats are multiple orders of magnitude slower to break than others. Why are the speeds so different? The differences are caused by the different hashing and encryption algorithms as well as the vastly different numbers of hash iterations required to verify the password. In Microsoft Office encryption evolution: from Office 97 to Office 2019 we demonstrated it using the different generations of encryption used in Microsoft Office tools over the years.

Does it get any slower than that?

The longer it takes to break a password, the more secure your data is. Is there a theoretical limit on how secure your data can be? Most manufacturers assume that the user expects the encrypted document to open or the locked device to unlock in approximately 0.3 seconds. However, this time is measured on what they consider to be average hardware for the use case, meaning that newer and faster computers will unlock the document much faster than that.

Most manufacturers use a single CPU core and inefficient coding to verify the password. By utilizing all available CPU cores and thoroughly optimizing the code, we’ve been able to increase the speed of attacks by the factor of 10 to 25 compared to the time it takes the original manufacturer to validate the password. The use of a dedicated GPU accelerator further increases the recovery speed by the factor of 20 to 250 depending on the format.

Manufacturers know about the issue, and attempt using several countermeasures. For some formats, the number of hash iterations (what’s that?) can adapt to the speed of the current hardware. For example, Apple employs a different number of hash rounds to encrypt macOS user passwords. VeraCrypt allows users manually specifying the number of hash iterations, while some password managers do this automatically on the user’s behalf.

How many passwords can I try before being locked out?

Speaking of file encryption, the number of passwords you can try is unlimited. Our tools routinely crunch through hundreds of billions password combinations before finding the only one that works. If, however, you are attempting to unlock and iPhone or attacking an online service, you may be locked out much sooner after a handful of attempts.

Is there two-factor authentication for data encryption?

Encryption with two-factor authentication (where the second authentication factor is provided by a remote service) is commonly used in DRM to protect books, music and videos from copying. We’ve almost never seen encryption 2FA in common data formats. While theoretically possible, the implementation would require the ability to interact with a remote party just to gain access to your data, which is not everyone’s cup of tea. One example of 2FA-based protection is OneDrive Personal Vault, which, on the other hand, is not encryption.

Some algorithms are faster than others

You might be wondering about which formats are slower and which are faster to break. In What is Password Recovery and How It Is Different from Password Cracking, we are discussing this very thing. Microsoft Office before Office 2007, the legacy ZIP and PDF encryption are examples of extremely weak encryption. Today, Tally ERP 9 Vault is a good example of almost non-existing protection.

Much stronger encryption is used in many modern products. Microsoft Office 2013 and 2016, RAR archives, TrueCrypt, BitLocker and VeraCrypt are good implementations of strong encryption.

Interestingly, not every manufacturer is interested in strong protection even within a certain class of products. In Breaking Encrypted Virtual Machines: Recovering VMWare, Parallels, and VirtualBox Passwords, we made a point that some encrypted virtual machines might be broken much faster than the rest of the pack. We’ve seen the recovery speed of some 19 million passwords per second for Parallels VMs.

The true meaning of speed

So 19 million passwords a second is “a lot”, and 10 passwords a second is “very slow”. I get that. Well, not really. How much time, exactly, will you need to break this password? Or that one? Or let me as it this way: how long a password can you break in a day? A week? Two weeks perhaps?

You’re not going to like the answer: “It depends”. The deciding factor is the number of password combinations we’ll have to try before finding the right one, and the number of passwords per second we can try on a given system. In May the [Brute] Force Be with You! , we discuss these exact issues in detail.

Salt anyone?

In It’s Hashed, Not Encrypted, we discussed the value of salt. What if someone wanted to take a shortcut, calculating a massive number of hashes corresponding to some 10 million most common passwords? Or maybe a billion passwords that had ever leaked? Wouldn’t it be easier to simply look up the hash string in such a list? Or how about stealing a list of hashes and looking for some of the most common passwords in that list by their hash values?

Fortunately, none of these attacks work in real life. To mitigate these threats, hashed passwords are “salted” by appending a string of some unique random data to each password. The result of this transformation is a salted hash of the password. To verify a salted hash, one needs the password itself and the corresponding salt value. The salt is not a secret, and usually stored along with the hash. Salt values stored in a separate database (or on a separate physical server) are called “pepper”. With rare exceptions, all major manufacturers use salt when encrypting stuff or protecting online accounts.

Pure brute force vs. smart attacks

The speeds above are only valid for pure brute force attacks. For the attacker, incrementing the next password to try is the simplest math resulting in the fastest recovery speeds. Brute force is one of the best optimized attacks when it comes to using GPU acceleration with a large number of parallel computing cores.

On the other hand, pure brute force attacks are rarely effective. They only allow recovering very simple passwords (or average-length passwords for some of the weaker formats). We discussed the limitations of pure brute force attacks in May the [Brute] Force Be with You!

Many types of passwords (such as simple dictionary-based passwords or passwords combining one or several common words with typical alterations) can be broken much faster by using other types of attacks using dictionaries, mutations or scriptable rules. All of these smart activities don’t require additional CPU cycles; the smarter the attack, the more additional CPU cycles it takes compared to pure brute force. As a result, a smart attack based on complex scriptable rules may work several times slower compared to a pure brute force – yet still delivering the result much faster.

The iPhone backup password

I simply love iPhone backups because they are great in a very unique way. In The Most Unusual Things about iPhone Backups, I talked about how Apple made iPhone backups extremely slow to attack. Even hardware-accelerated attacks deliver the speeds of just about 10 passwords per second. A single-core, CPU-only algorithm requires approximately 15 seconds to try a single (!) password to an encrypted iTunes backup.

What about the iTunes app? The app can check the password in less than a second. Is it a trick? It’s exactly the one: iTunes verifies the backup password on the connected iPhone instead of using your computer’s resources, and the iPhone has access to a different verification algorithm not available from outside the device.



Elcomsoft Distributed Password Recovery

Build high-performance clusters for breaking passwords faster. Elcomsoft Distributed Password Recovery offers zero-overhead scalability and supports GPU acceleration for faster recovery. Serving forensic experts and government agencies, data recovery services and corporations, Elcomsoft Distributed Password Recovery is here to break the most complex passwords and strong encryption keys within realistic timeframes.

Elcomsoft Distributed Password Recovery official web page & downloads »