Modern encryption tools employ strong encryption with multiple hash iterations, making passwords extremely difficult to break. The November article “What is password recovery and how it is different from password cracking” explains the differences between instantly accessing protected information and attempting to break the original plain-text password. In that article, I briefly mentioned GPU acceleration and distributed attacks as methods to speed up the recovery. In this article, I’ll discuss the two acceleration techniques in more detail.

Why do we need GPU acceleration?

Literally, we need GPU acceleration to break passwords faster. How much faster, exactly, depends on several things: the type of the video card (more on that later), the number of video cards installed, and the algorithm that was used to convert the password into a binary 128-bit or 256-bit encryption key.

If you have not yet read the “What is password recovery and how it is different from password cracking” article, you may want to review it for the basic theory of password cracking. Most types of data protection today implement encryption. The encryption algorithm protects data with a 128-bit or 256-bit Media Encryption Key (MEK, sometimes also referred as a Data Encryption Key, or DEK), which is long enough to make brute-force attacks out of the question.

With the binary media encryption key out of the reach of today’s brute force algorithms, one must target something else instead. The media encryption key itself is either directly produced from the user’s text-based password or encrypted with the user’s text-based password. The majority of plain text passwords have significantly lower entropy compared to 256-bit or even 128-bit media encryption leys.

Recovering the original password is often the only way to access the data. While makers of password recovery tools are trying to break password as fast as possible by trying increasing numbers of password combinations per second, makers of data encryption tools are doing exactly the opposite in order to slow down attacks. This is often achieved by increasing the number of rounds (recursive calculations of a hash function) that is used when processing the user’s input and turning it into an encryption key.

However, there is light at the end of the tunnel. Manufacturers of data protection tools cannot increase the protection indefinitely; there is only so much time the user is willing to wait for a password-protected document to open or an encrypted volume to mount. As a result, manufacturers profile their data protection algorithms so that the data can be accessed in about 0.3 to 1 second on an average (or below-average) system. Particularly important is the fact that all common data protection algorithms only use the system’s central processor (CPU) when it comes to verifying the password. Which brings us to the next point.

What is GPU acceleration and how does it work?

As demonstrated earlier, the speed of a single CPU is not enough to break many types of passwords. With hundreds of thousands or even millions hash iterations used to slow down the recovery, attacks running on a CPU alone can only break the simplest passwords. Additional computation power is urgently needed to break passwords in reasonable time.

At the same time, today’s power-hungry video cards ship hundreds of dedicated high-performance cores working in parallel. High-end and mid-range video cards manufactured by NVIDIA and AMD can render complex 3D scenes in real time; something that a bare CPU would struggle with.

This is how we arrived to the idea of using video cards to accelerate the recovery. GPU acceleration offloads computational-intensive calculations from the computer’s CPU onto the highly scalable video cards. Featuring several hundred GPU cores, a single video card can deliver the speed far exceeding the metrics of a high-end CPU. Depending on which video card is installed and what type of encryption we are dealing with, one can expect the recovery speed to raise some 50 to 250 times faster compared to CPU-only benchmarks.

Asynchronous GPU acceleration

If you have more than one video card installed, Elcomsoft Distributed Password Recovery can use up to 32 dedicated video cards at the same time.

What if those video cards running at different frequencies? Or what if they are different video cards altogether? This is where asynchronous GPU acceleration comes into play. With asynchronous acceleration, the password recovery tool can break jobs into smaller pieces, and feed every piece to a given video card. The asynchronous scheduler does not have to wait for a given part of the job to complete before feeding the next piece in line once one of the video cards finishes its slice.

In layman terms, heterogeneous GPU acceleration allows using multiple video cards of different makes and models, effectively utilizing existing hardware and squeezing the last bit of performance out of every supported component.

EDPR can utilize all GPU cores in mix-and-match scenarios if the video cards are made by different manufacturers. Whether you have a mix of AMD and NVIDIA boards or just want to make use of your computer’s built-in Intel HD Graphics cores, all of these can be used together to speed up the recovery.

How fast is GPU acceleration?

The “how fast…” is a million dollar question. GPU acceleration is only as fast as the video card (or video cards) installed in the computer. However, a video card that is fastest in 3D games or one offering real-time ray tracing is not necessarily the best for password recovery.

Long story short, there are no password recovery algorithms that would utilize the ray tracing acceleration units found in NVIDIA’s RTX series video cards. As a result, a NVIDIA GeForce GTX 1660 Super will break passwords at almost the same rate as a GeForce RTX 2060 Super with nearly double the price.

So how fast is GPU acceleration, exactly? These are the bare numbers:

What do the number mean, and how strong a password can you break with a single GTX 1660? We’ll use a password calculator to estimate the time required to break some types of passwords.

Attacking an encrypted Microsoft Office 2013 document with a single video card results in approximately 2900 passwords per second, or about a million (1044000) password combinations an hour.

A very simple (I would even say, unrealistically simple) password composed of only 5 characters (lower case letters and numbers only) has 60,466,176 possible combinations. Brute-forcing such a simple password with a GPU would only take about 58 hours. This very same password would take about 1.5 years of brute-force attacks using a CPU alone.

A weak password containing 6 characters including lower and upper case letters and numbers (but no special characters) has 56,800,235,584 possible combinations. This password would take 6.3 years to break on a single GPU.

An average password of 7 characters of the same group would take 385 years of brute-force attacks to break.

Distributed computing

385 years sound like an awful lot for a single-GPU attack. In other words, this is not a feasible attack to run. Granted, smart attacks including dictionaries, double dictionaries, prefixes, postfixes, mutations, scripted rules and whatnot do a great job when it comes to breaking passwords of ordinary Joe and Jane. They won’t do such a great job when attacking passwords of a seasoned hacker. In other words, we need more speed.

I already talked about multi-GPU acceleration; let’s do that and build a 4U rack server with as many as 8 GPUs. Great; this server will only take 48 years to break that password instead of 385! The next logical step is adding more of the same servers to the rackmount. If you use Elcomsoft Distributed Password Recovery, you can use up to 10,000 servers to your distributed network.

Cloud attacks

The linear scalability approach works great if you already have a data center equipped with up to date hardware. If, however, you were to build a dedicated data center from scratch, you may be shocked with the final bill. Hardware and maintenance costs, electricity and air-conditioning bills (you’ll have to pay for, and dissipate, some 1500W per computer) will add up quickly.

For those who require the fastest recovery speed without the hassle of building and maintaining a dedicated data center, we recommend considering offloading parts of the load the cloud. Using a cloud service means you’re getting a high-performance distributed network without having to build your own data center.

Using a cloud services (currently, Elcomsoft Distributed Password Recovery supports Amazon and Microsoft Azure clouds) offers a number of benefits over a static infrastructure. You can quickly add computing power on demand by renting additional instances, and quickly scale back once the job is done. With up to 16 GPUs per instance, you can build a network as fast as you need while keeping the costs under control.

Building a distributed cloud network is easier than you might think. Read Breaking Passwords in the Cloud: Using Amazon P2 Instances for details.

Conclusion

Even the fastest distributed network of 10,000 8xGPU computers will choke when trying to brute-force a .docx file protected with a 12-character password such as “JoeSmith1956”. However, this very same password can be broken easily with a simple hybrid attack in less than 2 minutes. This, however, is a very different topic.