Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 19 Mar 2011 06:01:49 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: GSOC - GPU for hashes

Hi Lukas,

On Sat, Mar 19, 2011 at 02:22:05AM +0000, ?ukasz Odzioba wrote:
> I'm interested in the following tasks:
> 
> JtR: GPU for slow hashes
> JtR: GPU for fast hashes

Sounds great.

> I would appreciate an additional information about them.
> For now I've got these questions:
> Q1) what have to be computed on GPU (check every possible combination
> paralelly)?

For slow hashes, just the hashes themselves need to be computed on GPU,
for multiple candidate passwords in parallel.  The candidate passwords
will be generated on the main CPU, and the GPU-computed hashes will be
checked against those loaded for cracking on the main CPU as well.

For fast hashes, we'll need to discuss this.  One approach would be to
move more of JtR's core code onto GPU - part of candidate password
generation and hash comparison to be done on GPU.  Another approach
would be to make asynchronous and parallelize those things across CPU
cores, such that while the GPU is busy computing hashes the CPU is busy
checking the previous bunch of hashes and generating new candidate
passwords.  Each of these has pros and cons.

> Q2) do you have any prefferences about technology (I would prefer cuda)?

Ultimately, the code will need to run across a variety of GPUs from
different vendors, not just NVidia.  This means multiple technologies
or/and OpenCL.  However, a CUDA-only implementation is within
consideration for a student's GSoC 2011 project.  It will be a step
forward compared to where we are now.

Some work being done on DES S-boxes will assume AMD GPUs being
programmed at a low level, though.  This is definitely not CUDA.  But
like I said, we may use CUDA too, and another person may do the AMD
specific stuff.

> Q3) I'm not getting the difference between slow and fast hashes, whats
> all about or where i can found this type of information?

"Slow" hashes are those that implement multiple iterations of a
cryptographic primitive for computation of just one hash.  The various
modern Unix crypt(3) flavors are an example of these.

"Fast" hashes are those that rely on a single computation (or very few
computations) of a cryptographic primitive.  NTLM is an example.

There are also some "inbetween" hashes, which we may approach in either
way.  The traditional DES-based crypt(3) is an example, with its 25
iterations of modified-DES.  25 is a small number, so these hashes are
pretty fast; just not as fast as those that have no iterations at all.

JtR's current on-CPU candidate password generation and hash comparison
code can only do up to tens of million of hash computations per second.
For a hash type where the GPU will "only" compute, say, under 1 million
of hashes per second, we can use JtR's code as-is.  However, for a hash
type where the GPU is able to compute, say, 100M+ of hashes per second,
we have to use a more complicated approach (as mentioned above), or the
task will be mostly CPU-bound.

> Q4) what hashing functions have to be implemented?

There are lots to be potentially implemented (all those supported by JtR
with the jumbo patch normally, and then more, which gives about 50),
but no specific requirements on which of these to implement this summer.
We're yet to decide on this, and our decision may depend on what we're
reasonably able to do (and achieve good efficiency), and on demand.

I would suggest that we consider all of the slow hashes (there are
relatively few of these - maybe around 10) and a few most popular of
the fast ones (NTLM, raw and salted MD5, raw and salted SHA-1, etc.)

I hope this clarifies things for you.  Please don't hesitate to ask any
further questions you might have.

Thanks,

Alexander

Powered by blists - more mailing lists

Your e-mail address:

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.