Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Tue, 11 Jun 2013 10:37:22 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Parallella: scrypt

Rafael -

I notice that you have edited the project description as we had
discussed off-list:

http://www.google-melange.com/gsoc/project/google/gsoc2013/lordrafa/22001

It now says "In this project I will add Epiphany support to scrypt code
using a Parallella board."

This is OK, although I hope you will have time to do more than just that
during the summer.  Further tasks (stretch goals) may include: Litecoin
mining code both using Epiphany and not, FPGA programming (both for
scrypt/Litecoin just because we have the Zynq chip anyway, and for other
JtR "formats" where an FPGA is of more benefit - such as descrypt),
another/further attempt at using OpenCL to program for Epiphany.

For now, though, let's in fact focus on scrypt.  We do not yet have any
scrypt code in JtR, so your first task is to add such support using the
host CPU.  To do this, please use this encoding syntax:

https://www.gitorious.org/scrypt/scrypt-unix-crypt/blobs/master/unix-scrypt.txt

and my revision of Colin Percival's original implementations
(reference, somewhat optimized, and heavily optimized x86 SSE2
intrinsics) as attached to this message (this includes implementation of
the above encoding syntax as well).

My escrypt includes a defeat_tmto feature.  For your project, please
keep it disabled - that is, set defeat_tmto = 0.  This feature is a
work-in-progress and it's not part of scrypt proper.

(BTW, there's still much room for attack-specific optimization -
bringing more parallelism down to instruction level - but that's out of
scope of your project, at least until after you've implemented scrypt on
Epiphany.  I think there's sufficient parallelism in one Salsa20 core to
fully use Epiphany, and we're limited by the 32 KB of local memory, so
bringing more parallelism to instruction level is not helpful for
Epiphany.  However, it is likely helpful for modern x86-64 CPUs.)

You need to create a JtR format out of this.  Please take a look at
c3_fmt.c and dummy.c in the JtR tree for some samples.  I mention
c3_fmt.c because it simply uses crypt(3), whereas my escrypt tarball
provides a similar function.  While normally we'd decode the ASCII
strings back to binary on loading of hashes to crack, and work on the
binaries then, for scrypt this does not matter much.  It's so slow that
the time wasted on ASCII-encoding will be negligible.  c3_fmt.c also
supports OpenMP with glibc's crypt_r(3), and my escrypt also provides an
MT-safe function - so you may do things similarly (to include OpenMP
support too).

Please try to complete this within a week.  Then your next task will be
to experiment with scrypt time-memory tradeoff (still on the host CPU):

http://www.openwall.com/lists/crypt-dev/2013/03/21/1

and then to bring the actual scrypt computation (making use of TMTO as
needed) to Epiphany (in a revision of the JtR format - maybe a new
format name, so that both host and Epiphany versions could be invoked
from the same build of JtR).

I expect that you will need help with the TMTO - please feel free to ask
for it when you get to that point.

Frankly, I only expect sort of reasonable performance with very low
memory settings for scrypt - much like Litecoin's 128 KB (at which the
increase in computation is only about 2x).  Thus, for practical use, the
JtR/host format is far more important than the JtR/Epiphany format.  (We
generally don't have to use TMTO on host, but we do on Epiphany.)  The
primary reason why we even bother to implement scrypt on Epiphany is for
Litecoin mining (where we know that scrypt's memory setting is only 128 KB,
which is sort of acceptable for Epiphany).  Thus, for the Epiphany part
of the project to potentially make any practical sense at all, you do
need to proceed to implementation of Litecoin mining.  For the Epiphany
part of the project to potentially make any practical sense for JtR in
particular (rather than merely for Litecoin mining, which is not exactly
a JtR task), you do need to proceed to implementation of other formats
(beyond scrypt) on Parallella (both chips) - I suggest descrypt (because
it'd make good use of the FPGA and reasonable use of Epiphany, and also
because it's not perfect on GPUs yet, unlike e.g. most things
MD5-based).  So please try to allocate half the summer to those highly
desirable stretch goals.

Please let me know if you have any questions or/and comments.

Thanks,

Alexander

[ CONTENT OF TYPE application/x-gzip SKIPPED ]

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ