How are GPUs used in brute force attacks?

Question

I have read that GPUs can be used in brute force attacks? But how can this be done and is there a need for any other hardware devices (hard disks for instance)?

Note: I'm more interested in web application security, but I don't want to put on blinders. I'm sorry if my question is ridiculous for you, but my hardware background isn't very good. I just know how basic components work together and how to combine them.

Since I can't comment: As a for instance, I could calculate around 33 million MD5 hashes per second using John the Ripper with the CPU, and around 11.8 billion hashes per second using OclHashcat and the GPU. I tested this recently as part of a security class assignment. — chris, Mar 21 '16 at 20:33

score 56 · Accepted Answer · answered Mar 21 '16 at 20:04

56

I'm choosing to assume you're asking why it's a risk rather than how to hack.

GPUs are very good at parallelising mathematical operations, which is the basis of both computer graphics and cryptography. Typically, the GPU is programmed using either CUDA or OpenCL. The reason they're good for brute-force attacks is that they're orders of magnitude faster than a CPU for certain operations - they aren't intrinisically smarter.

The same operations can be done on a CPU, they just take longer.

answered Mar 21 '16 at 20:04

Phil Lello

1,122
10
15

Thank you! I don't want to know how to hack, I just want to understand the idea. So, the software used is convincing the GPU that it is working on a computer? – Mahmood Muhammad Nageeb Mar 21 '16 at 20:16
17

@MahmudMuhammadNaguib It uses the GPU for a non-graphics operation - which tends to be allowed by design these days (it used to be creative hackery). The process is initiated by a normal program. – Phil Lello Mar 21 '16 at 20:21
Thank you! This is very creative, and these people are real hackers! Do you think companies will modify the design in the future, so GPU's can't be used for this purpose, and is this possible (as graphical operations include some mathematical operations, too)? – Mahmood Muhammad Nageeb Mar 21 '16 at 20:27
19

@MahmudMuhammadNaguib Absolutely not! While they can be used for brute-forcing the same capabilities can be used for tons of other useful things. The trend is that GPUs are getting better and better at doing things that aren't strictly speaking graphics. And this trend exists because they are being exploited more and more to do that stuff. – Bakuriu Mar 21 '16 at 20:34
@MahmudMuhammadNaguib I think the trend is to add GPUs onto the die with the CPU to support highly-parallel non-graphical operations. I don't see how it would benefit GPU manufacturers to limit non-graphics opertions. I'm a little out of my niche here though. – Phil Lello Mar 21 '16 at 20:34
I see, I respect specializations. – Mahmood Muhammad Nageeb Mar 21 '16 at 20:40
18

Just to underscore @Bakuriu's comment, the CUDA API was created by nVIDIA especially to enable developers to use their GPUs for non-graphics purposes. They strongly encourage the creative uses of their GPUs because they hope to sell more of them as computer performance accelerators. It should not be considered hacking, this is all now mainstream use of GPUs to perform massively parallel computations. – John Deters Mar 21 '16 at 22:07
9

Since we're talking about Nvidia, look up some pictures of their Tesla cards--"[These are built solely for computing, so many of these don’t even have a video output](http://blog.goldenhelix.com/mthiesen/i-want-a-gpu-for-computational-analysis-which-one-should-i-get/)". People who work with them will be used to the idea, but a video card with no output ports on the back of it just looks so cool and different to me. – Mathieu K. Mar 21 '16 at 22:51
@MahmudMuhammadNaguib Why would you deliberately prevent a GPU from being able to process things that aren't graphics? The fact they're called "G"PUs is just historical inertia. – user253751 Mar 22 '16 at 02:13
1

@MahmudMuhammadNaguib Or to use an analogy: you're watching people throw plastic bottles out of car windows, and you're asking why we don't modify the design of windows so only biodegradable rubbish can pass through them. – user253751 Mar 22 '16 at 02:16
@immibies Who said I would? I am just discussing! And I have mentioned that this is very creative, and that these people are real hackers! – Mahmood Muhammad Nageeb Mar 22 '16 at 09:25
1

I'd just like to point out that this is the reason GPUs are considered superior for bitcoin mining - they excel at performing a basic repetitive task in a massively parallel format, like sending an update to each individual pixel on an HD monitor. – David L. Mar 22 '16 at 10:26
1

The real answer for why GPU manufacturers wouldn't even consider limiting this use of their hardware is because it wouldn't make anything safer. GPUs are generally available and easy to install on a general purpose computer, which is their prime attractiveness, but custom ASICs can be built that are even faster and, so long as there aren't other considerations at play (like scrypt and memory usage) aren't out of line on cost - which is why most Bitcoin mining these days has moved to custom ASICs. – Jason Mar 22 '16 at 14:10
Besides cryptography and graphics, doesn't anything in computing require mathematical operations? – DDPWNAGE Mar 23 '16 at 05:05
3

@DDPWNAGE Its not mathematical operations GPU's are good at; it is a particular kind of mathematical operations (ones that parallelise really well). Most computing doesn't do much with this kind of operations -- most of say a email program, or a webserver is squential code full of branchs and conditions -- these run best on the CPU. – Frames Catherine White Mar 23 '16 at 05:36
5

They are actually usually *slower* at doing the mathematical operation in question, not *faster*, in that it takes more time for them to do one mathematical operation, they just do *more of them at the same time*. GPUs win via parallelism, not via speed. On a batch of jobs, they can be faster, and cartographic attacks often rely on checking ridiculously large number of combinations of possibilities. – Yakk Mar 23 '16 at 16:49

score 51 · Answer 2 · 2016-03-23T12:02:41.313

People have given great answers here that directly answer your question, but I'd like to give a complementary answer to explain more in depth why GPUs are so powerful for this, and other applications.

As some have pointed out, GPUs are specially designed to be fast with mathematical operations since drawing things onto your screen is all math (plotting vertice positions, matrix manipulations, mixing RBG values, reading texture space etc). However, this isn't really the main driving force behind the performance gain. The main driving force is the parallelism. A high end CPU might have 12 logical cores, where a high end GPU would be packing something like 3072.

To keep it simple, number of logical cores equals the total number of concurrent operations that can take place against a given dataset. Say for example I want to compare or get the sum the values of two arrays. Lets say length of the array is 3072. On the CPU, I could create a new empty array with the same length, then spawn 12 threads that would iterate across the two input arrays at a step equal to the number of threads (12) and concurrently be dumping the sum of the values into the third output array. This would take 256 total iterations.

With the GPU however, I could from the CPU upload those same values into the GPU then write a kernel that could have 3072 threads spawned against that kernel at the same time and have the entire operation completed in a single iteration.

This is handy for working against any data that can, by its nature, support being "worked on" in a parallelizable fashion. What I'm trying to say is that this isn't limited to hacking/evil tools. This is why GPGPU is becoming more and more popular, things like OpenCL, OpenMP and such have come about because people have realized that we programmers are bogging down our poor little CPUs with work when there is a massive power plant sitting in the PC barely being used by contrast. It's not just for cracking software. For example, once I wrote an elaborate CUDA program that took the lotto history for the last 30 years and calculated prize/win probabilities with tickets of various combinations of all possible numbers with varying numbers of plays per ticket, because I thought that was a better idea than using these great skills to just get a job (this is for laughs, but sadly is also true).

Although I don't necessarily endorse the people giving the presentation, this presentation gives a very simple but rather accurate illustration of why the GPU is so great for anything that can be parallelized, especially without any form of locking (which holds up other threads, greatly diminishing the positive effects of parallelism).

Perhaps the next logical question then: Why do CPUs have so few cores in comparison to GPUs? Is it simply a consideration of space? — Dan, Mar 22 '16 at 11:17
@DanPantry The simple answer is because each CPU core is much more complex than a GPU core. GPU cores are designed to perform lots of (comparatively) simple operations, with lots of them happening in parallel. CPU cores are generally far more complex, and -- broadly speaking -- the tasks they are doing are much harder to (easily / successfully) run in parallel (because of problems with synchronizing between cores). — TripeHound, Mar 22 '16 at 12:01
So, was your lotto program successful into avoiding getting a job? — Mindwin, Mar 22 '16 at 12:40
@Mindwin Sadly, no. Even using the 500 series GTX to run my program, I calculated that I would die before it finished crunching all the possible combinations of 5 line tickets (my decided max budget for tickets), so instead I opted to become an armchair expert on stackexchange and occasionally loiter at the local mall with a sign that says "will code for food." — , Mar 22 '16 at 12:45
@DanPantry Most general computing problems cannot be easily parallelized. CPUs are designed to be general purpose, so they are faster for most things. Graphics and code cracking problems tend to be easily parallelized so GPUs are a nice fit. GPUs take longer to setup and submit individual operations, but then they can be computed in parallel faster (see SIMD). The GPU tradeoffs and advantages would not work well for most computing problems. — Justin Meiners, Mar 22 '16 at 21:51
@JustinMeiners thanks for emphasizing this. I tried to convey this in the 5th paragraph but you've done a better job. — , Mar 23 '16 at 00:48

ferit · Answer 3 · 2016-08-22T09:22:07.537

13

You don't need any other device, just a suitable GPU, and a software. For example, cRARk can use your GPU to brute-force rar passwords. And oclhashcat can use your GPU to brute-force lots of things.

Why GPU's are much more faster than CPU in cracking? Because cracking is something you can run in parallel (You can use every single core for trying different passwords at the same time) And GPU's have lots of cores which can be used in parallel.

For example: GeForce GTX980 Ti, which is a high end GPU, has 2816 cores. While no PC CPU has more than 16 cores (Highest I know is 72-cores but for supercomputing and server purposes).

But why CPUs have a little amount of cores compared to GPUs? Can't they make CPUs with lots of cores? Of course they can, but it is not beneficial. Because generally it is not possible to process in parallel like graphics. Many software has to process sequentially, and even if they can process in parallel, it is not common to write a software for parallel processing, because it is harder for developers.

See the graph below:

Assuming that averagely %50 of the processing can be parallelized, speedup is only 2x with 16 cores. So increasing core numbers has very diminishing returns for CPUs.

edited Aug 22 '16 at 09:22

answered Mar 21 '16 at 19:58

ferit

459
3
13

Thank you! But how I can run this software on my GPU, and how this software is able to make my GPU execute programming instructions? – Mahmood Muhammad Nageeb Mar 21 '16 at 20:02
1

You don't need to do anything extra, just download the tool, and run. If you don't know how to run, then you should read documentation of the tool, like any other tool. There is no difference. – ferit Mar 21 '16 at 20:05
1

The 3 answers are very good, I got something of each. Don't care to downvoters! – Mahmood Muhammad Nageeb Mar 21 '16 at 20:33
(CPUs do have more than 16 cores - even Intel Xeons go above that, Sparc M7 is at 32.) – Mat Mar 22 '16 at 12:14
Well, actually they are for servers, not for PC's. But yeah I should update my answer. – ferit Mar 22 '16 at 12:51

Criggie · Answer 4 · 2016-03-23T02:02:36.750

At work we have special servers which solve "computationally hard routing problems." Each host is fairly well-specified with four sockets and quad core xeons, so 16 physical cores and HT on top of that. Call it 32 cores.

Each box has a PCIe expander chassis, and in there are multiple higher-end NVidia GPUs, and the big PSUs to power them. Since each graphics card has about 2000 CUDA cores, that works at around 30,000 CUDA cores per host.

So if we hand-wave and call a CUDA core the equivalent of a CPU core, this server is the same as a thousand servers running on normal CPUs. Much fudging there because CUDA cores are no good at some tasks, but very good at others.

Imagine solving the traveling salesman problem by enumerating all possible routes and pick the best one. Or enumerating all possible chess moves from the current board, and pick the single move that leads to the highest chance of a success for your next move.

Don't need no stinkin' heuristics when all possible answers have been calculated! And that is the definition of a brute-force attack.

+1, you can drop a tesla or two into a standard machine and have a supercomputer. — , Mar 23 '16 at 01:29

score 3 · Answer 5 · answered Mar 23 '16 at 22:39

You may want to see this link https://www.iacr.org/archive/ches2006/09/09.pdf. The advantage of a GPU is to parallelize the massive discrete logarithmic computations needed to crack a cryptosystem.

Abstract. Cryptanalysis of symmetric and asymmetric ciphers is computationally extremely demanding. Since the security parameters (in particular the key length) of almost all practical crypto algorithms are chosen such that attacks with conventional computers are computationally infeasible, the only promising way to tackle existing ciphers (assuming no mathematical breakthrough) is to build special-purpose hardware. Dedicating those machines to the task of cryptanalysis holds the promise of a dramatically improved cost-performance ratio so that breaking of commercial ciphers comes within reach. This contribution presents the design and realization of the COPACOBANA (Cost-Optimized Parallel Code Breaker) machine, which is optimized for running cryptanalytical algorithms and can be realized for less than US$ 10,000. It will be shown that, depending on the actual algorithm, the architecture can outperform conventional computers by several orders in magnitude. COPACOBANA hosts 120 low-cost FPGAs and is able to, e.g., perform an exhaustive key search of the Data Encryption Standard (DES) in less than nine days on average. As a real-world application, our architecture can be used to attack machine readable travel documents (ePass). COPACOBANA is intended, but not necessarily restricted to solving problems related to cryptanalysis. The hardware architecture is suitable for computational problems which are parallelizable and have low communication requirements. The hardware can be used, e.g., to attack elliptic curve cryptosystems and to factor numbers. Even though breaking full-size RSA (1024 bit or more) or elliptic curves (ECC with 160 bit or more) is out of reach with COPACOBANA, it can be used to analyze cryptosystems with a (deliberately chosen) small bitlength to provide reliable security estimates of RSA and ECC by extrapolation3 .

score 2 · Answer 6 · answered Mar 21 '16 at 20:06

A GPU brute forcer is simply a PC with one or more high-end GPUs in. It runs some form of password cracking software, which is optimised to use the specialised GPU processing power for high performance mathematical operations on large numbers.

It usually needs a relatively high power PSU, because graphics cards are fairly power hungry, and a large hard drive can help with some tasks, such as holding large dictionaries for attacks to use.

All it does is hash things very quickly, whether from dictionaries, or from generators which output sequences of characters to cover the whole keyspace. It then compares the results of the hashing with a target hash, which has usually been recovered from a system under attack.

score 2 · Answer 7 · answered Mar 24 '16 at 15:16

All very technical answers but to put it a more real world context.

When you have a simple job to do say beeping your items at the supermarket till and paying for them is it better to have one checkout or 1024? Sure one checkout will work, and you can make it really sophisticated with lots of tricks to speed up things so it performs better than a normal one. But at the end of the day people can only work so fast and shoppers often slow things down. Therefore loads of tills it better.

Conversely when you have a very difficult job to do like surgery. Is it better to have one really skilled surgeon backed up by a small but good team or an army of butchers who are good at what they do, but can basically only chop stuff up?

How are GPUs used in brute force attacks?

7 Answers7