Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <20161106140653.GA12390@openwall.com>
Date: Sun, 6 Nov 2016 15:06:54 +0100
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Cc: apingis@...nwall.net
Subject: DES-based crypt(3) cracking on ZTEX 1.15y FPGA boards (descrypt-ztex)

Hi,

A couple of weeks ago, we merged into bleeding-jumbo this pull request
by Denis:

https://github.com/magnumripper/JohnTheRipper/pull/2307

with some implementation detail described here:

http://www.openwall.com/lists/john-dev/2016/10/12/1

This implements descrypt aka traditional DES-based crypt(3) hash
cracking on ZTEX 1.15y quad Spartan-6 LX150 FPGA boards.  Some of you in
here have these or compatibles (such as the US clones of the originally
German ZTEX boards).  Most of these boards previously worked as Bitcoin
miners, and were then resold on eBay and such at a fraction of the
original price.  Those we bought for development cost us between 100 EUR
(lately) and 250 EUR each (earlier).  They became rare on eBay now, but
I guess some asking around in cryptocurrency forums will do the trick
since there were a lot of those boards around, and only a fraction ever
reached eBay.  ZTEX itself does not sell them anymore.

As implemented by Denis, the "descrypt-ztex" format supports "mask mode"
(with on-device mask), hybrid modes (where you add a mask on top of
another mode, referring to the previous mode's generated portions of
candidate passwords with the "?w" mask), up to 2047 hashes per salt
(with on-device comparator) so up to a few million hashes loaded total
perhaps (given a good salt distribution), and it can work with one or
multiple ZTEX boards at once.

I think it's the first time this combination of features is implemented
on FPGA.  Previous descrypt crackers on FPGA were single-hash, didn't
allow easy customization of the candidate password sets being tested,
and were not integrated in a generic password cracker.

Performance is up to about 740M hash computations per second (with room
for further improvement).  This is slightly less than the best speeds
achieved by oclHashcat on current high-end GPUs, which apparently
achieves around 900M on GTX 1080 (and more with overclocking), so we're
being a bit late to introduce this.  The main advantage of using ZTEX
boards for this is their lower power consumption, at ~40W per board (vs.
~200W or more for a high-end GPU), and indeed that some of us and you
might already have these.  There's lower purchase cost, too, but this is
offset by the GPUs being usable for many more hash types rather than
just descrypt.

I just got around to testing Denis' contribution yesterday, and it works
as intended for me (with one board for now, although Denis also tested
with 3 boards at once).

In terms of software dependencies, it needs libusb and that's about it.
Denis tested it on Windows and Linux.  My test runs below are on Ubuntu
12.04, 64-bit.  I replaced the board serial number with X's. ;-)  (It
may be useful to have this serial number printed when you're working
with multiple boards.)

At build time, you need to ensure you have libusb installed (including
development subpackage) and build with "./configure --enable-ztex" (much
like you would have built older cgminer for use of these boards back
when Bitcoin mining on FPGAs was a thing).

First run after board power-on:

$ ./john -form=descrypt-ztex -mask='?a?a?a?a?a?a?a?a' pw-fake-unix
SN XXXXXXXXXX: ztex_reset_cpu(0) returns -4 (LIBUSB_ERROR_NO_DEVICE)
SN XXXXXXXXXX: firmware uploaded
SN XXXXXXXXXX: uploading bitstreams.. ok
1 device(s) ZTEX 1.15y ready
SN: XXXXXXXXXX productId: 10.15.0.0 "inouttraffic UFM 1.15y" busnum:2 devnum:34 
Using default input encoding: UTF-8
Loaded 3269 password hashes with 2243 different salts (descrypt-ztex, traditional crypt(3) [DES ZTEX])
Warning: Slow communication channel to the device. Increase mask or expect performance degradation.
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:06  0g/s 0p/s 744201Kc/s 1080MC/s aaaaaaaa..ae\aaaaa
0g 0:00:00:17  0g/s 0p/s 737140Kc/s 1059MC/s aaaaaaaa..ae\aaaaa
0g 0:00:00:23  0g/s 0p/s 738982Kc/s 1102MC/s aaaaaaaa..ae\aaaaa
0g 0:00:00:31  0g/s 0p/s 738780Kc/s 1101MC/s aaaaaaaa..ae\aaaaa

As you can see, JtR loads those hashes and seems to run sanely, at
decent speeds, but there's a spurious warning (the mask here is fine as
it is; perhaps this is a bug for Denis to fix).  Since testing this mask
(all printable ASCII) against this many different salts would take a
long time even at this speed, I interrupted.  A similar test on just one
hash can be seen to make some progress:

$ ./john -form=descrypt-ztex -mask='?a?a?a?a?a?a?a?a' pw
1 device(s) ZTEX 1.15y ready
SN: XXXXXXXXXX productId: 10.15.0.0 "inouttraffic UFM 1.15y" busnum:2 devnum:34 
Using default input encoding: UTF-8
Loaded 1 password hash (descrypt-ztex, traditional crypt(3) [DES ZTEX])
Warning: Slow communication channel to the device. Increase mask or expect performance degradation.
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:04 0.00% (ETA: 2017-02-15 07:38) 0g/s 711722Kp/s 711722Kc/s 711722KC/s aaa3Iaaa..ae\3Iaaa
0g 0:00:00:30 0.00% (ETA: 2017-02-17 15:01) 0g/s 739400Kp/s 739400Kc/s 739400KC/s aaaw<1aa..ae\w<1aa

As you can see, with 1 hash it'd complete in about 3.5 months (and
that's worst case), which is consistent with the reported speed:

95^8/740/10^6/86400/30 = 3.46

With 3 boards, you can do it in a month - and without a huge power bill.

Now let's give it a hint that first and last letter are "t":

$ ./john -form=descrypt-ztex -mask='t?a?a?a?a?a?at' pw
1 device(s) ZTEX 1.15y ready
SN: XXXXXXXXXX productId: 10.15.0.0 "inouttraffic UFM 1.15y" busnum:2 devnum:34 
Using default input encoding: UTF-8
Loaded 1 password hash (descrypt-ztex, traditional crypt(3) [DES ZTEX])
Warning: Slow communication channel to the device. Increase mask or expect performance degradation.
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:06 0.61% (ETA: 19:00:07) 0g/s 744201Kp/s 744201Kc/s 744201KC/s taaa)Uat..tae\)Uat
0g 0:00:00:26 2.61% (ETA: 19:00:17) 0g/s 736814Kp/s 736814Kc/s 736814KC/s taaa5q1t..tae\5q1t
0g 0:00:01:12 7.21% (ETA: 19:00:18) 0g/s 736199Kp/s 736199Kc/s 736199KC/s taaa+'rt..tae\+'rt
testtest         (user)
1g 0:00:01:24 DONE (2016-11-05 18:45) 0.01182g/s 739057Kp/s 739057Kc/s 739057KC/s testtest..t###d1st
Use the "--show" option to display all of the cracked passwords reliably
Session completed

Worked.  Now an even more specific mask ("tes" and 5 lowercase letters),
but many hashes (and salts), where we only expect to get one of them cracked:

$ ./john -form=descrypt-ztex -mask='tes?l?l?l?l?l' pw-fake-unix
1 device(s) ZTEX 1.15y ready
SN: XXXXXXXXXX productId: 10.15.0.0 "inouttraffic UFM 1.15y" busnum:2 devnum:29 
Using default input encoding: UTF-8
Loaded 3269 password hashes with 2243 different salts (descrypt-ztex, traditional crypt(3) [DES ZTEX])
Warning: Slow communication channel to the device. Increase mask or expect performance degradation.
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:02  0g/s 0p/s 542659Kc/s 799708KC/s tesaaaaa..tesaaaqa
0g 0:00:00:14  0g/s 0p/s 580490Kc/s 821512KC/s tesaaaaa..tesaaaqa
testtest         (u2781-des)
1g 0:00:00:26  0.03835g/s 0p/s 583101Kc/s 842663KC/s tesaaaaa..tesaaaqa
1g 0:00:00:31  0.03216g/s 0p/s 580654Kc/s 836678KC/s tes####a..tes####q
Warning: passwords printed above might be partial
Use the "--show" option to display all of the cracked passwords reliably
Session aborted

This works too.  (I interrupted the run shortly after the password got
cracked.)  The speed dropped to 580M, presumably because the mask covers
too few candidates.  With a less restrictive mask (and one hash, so we
get it cracked soon anyway):

$ ./john -form=descrypt-ztex -mask='?l?l?l?l?l?l?l?l' pw
1 device(s) ZTEX 1.15y ready
SN: XXXXXXXXXX productId: 10.15.0.0 "inouttraffic UFM 1.15y" busnum:2 devnum:29
Using default input encoding: UTF-8
Loaded 1 password hash (descrypt-ztex, traditional crypt(3) [DES ZTEX])
Warning: Slow communication channel to the device. Increase mask or expect performance degradation.
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:02 0.70% (ETA: 18:02:11) 0g/s 693044Kp/s 693044Kc/s 693044KC/s aaaaijna..aaysijna
0g 0:00:00:31 10.99% (ETA: 18:02:07) 0g/s 740595Kp/s 740595Kc/s 740595KC/s aaaattwi..aaysttwi
testtest         (user)
1g 0:00:01:30 DONE (2016-11-05 17:58) 0.01104g/s 739285Kp/s 739285Kc/s 739285KC/s testtest..####qmst
Use the "--show" option to display all of the cracked passwords reliably
Session completed

We're back to full speed.

Finally, a hybrid mode test.  Use "incremental" mode to generate first 4
characters in a smart order, and mask mode for the other 4 characters.

(Also, I didn't clean out john.pot from the previously cracked password,
so that one was not loaded here - as you can see it's "Remaining 3268".)

$ ./john -form=descrypt-ztex -inc=alpha -min-len=8 -max-len=8 -mask='?w?l?l?l?l' pw-fake-unix
1 device(s) ZTEX 1.15y ready
SN: XXXXXXXXXX productId: 10.15.0.0 "inouttraffic UFM 1.15y" busnum:2 devnum:36 
Using default input encoding: UTF-8
Loaded 3269 password hashes with 2243 different salts (descrypt-ztex, traditional crypt(3) [DES ZTEX])
Remaining 3268 password hashes with 2243 different salts
Warning: Slow communication channel to the device. Increase mask or expect performance degradation.
Press 'q' or Ctrl-C to abort, almost any other key for status
0g 0:00:00:10  0g/s 0p/s 745784Kc/s 1067MC/s loveaaaa..loveaays
0g 0:00:00:15  0g/s 0p/s 740910Kc/s 1072MC/s loveaaaa..loveaays
pinkfloy         (u1273-des)
1g 0:00:00:18  0.05497g/s 0p/s 739285Kc/s 1064MC/s loveaaaa..loveaays
1g 0:00:00:23  0.04317g/s 0p/s 737519Kc/s 1087MC/s loveaaaa..loveaays
bluefish         (u947-des)
2g 0:00:00:29  0.06870g/s 0p/s 736204Kc/s 1124MC/s loveaaaa..loveaays
2g 0:00:00:36  0.05515g/s 0p/s 739285Kc/s 1072MC/s loveaaaa..loveaays
blueeyes         (u1774-des)
3g 0:00:00:40  0.07457g/s 0p/s 738473Kc/s 1085MC/s loveaaaa..loveaays
mattingl         (u2361-bigcrypt:1)
4g 0:00:01:09  0.05787g/s 0p/s 735400Kc/s 1046MC/s loveaaaa..loveaays
lissabon         (u2310-des)
password         (u2-des)
blowfish         (u946-des)
jeanette         (u660-des)
bluebird         (u363-des)
pinkfloy         (u1273-bigcrypt:1)
maryjane         (u297-des)
poohbear         (u102-des)
12g 0:00:03:19  0.06022g/s 0p/s 735570Kc/s 1054MC/s love####..luku####
Warning: passwords printed above might be partial
Use the "--show" option to display all of the cracked passwords reliably
Session aborted

Indeed, these passwords are easier crackable with a wordlist, but this
is just a test.

The reported ranges of candidates being tested look off (stuck at "love"
for the first 4 chars here).  I guess this is not fully implemented yet,
and I recall Denis mentioning related implementation difficulties to me.
But it shouldn't hurt actual cracking.

It's somewhat surprising to see the full speed at this test at ~735M,
with only a 4-char alphabetic mask, whereas we had only 580M with the
5-char alphabetic mask on a test above.  Maybe there's some easy code
fix for that other scenario to get it to run at full speed as well.

I also ran a quick test to make sure that all passwords that are
supposed to be cracked actually are - that test passed.

Overall, things look good to me.  Thank you for working on this, Denis!

Alexander

Powered by blists - more mailing lists

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