Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20050918234241.GA3888@openwall.com>
Date: Mon, 19 Sep 2005 03:42:41 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: 2 Qs on performance and benchmarking

On Sat, Sep 17, 2005 at 07:03:14PM +0200, Christian Karpp wrote:
> in a previous mail I read
> > John's 1M c/s at traditional crypt(3) (on PPC G5 1.8 GHz or P4 3.6
> > GHz) roughly translates to:
> > 1M * 25 * 64 / 3 = 530 Mbps at 3DES

(This came from a private e-mail exchange we had with Christian.)

> Q1: How does this estimation break down for other CPU types / clock 
> speeds? i.e. How will the "1M c/s" number vary?

For the same CPU type, John version, and build, the c/s rate is almost
proportional to CPU clock rate.  For different CPU types, John versions,
and builds (especially different make targets), it varies widely.

"1M c/s at traditional crypt(3)" for a single CPU is regarded as very
good performance presently, although the best reported to me so far is
1.6M c/s (for a PPC G5 at 2.7 GHz - with the AltiVec code indeed).

The fastest Intel P4s (3.6 GHz) achieve up to 750k c/s at traditional
crypt(3) with the MMX code and up to 1M c/s with the not-yet-public SSE
code.  Modern AMD CPUs achieve similar performance, except that they're
better at MMX (compared to SSE).  PMMX/P2/P3 are roughly 50% faster
(yes, that's right) than P4s per-MHz (but the SSE code, when released,
is going to cure this to some extent).

Alphas have traditionally been among performance leaders for John's
implementations of DES-based hashes, per-MHz.  For example, a 21264A
at "just" 667 MHz would do over 400k c/s at traditional crypt(3).
Unfortunately, their available clock rates are not very high by present
standards.

You are likely to see much lower c/s rates for other processors
currently in use and/or for non-optimal John builds.  If you would run
John on a server installed several years ago (perhaps with a 32-bit OS
userland, even if the CPU is in fact 64-bit), you'd be lucky to have it
achieve over 100k c/s at traditional crypt(3).

For non-DES-based hashes supported by John (including with contributed
patches), x86 CPUs at high clock rates typically outperform the
(otherwise better) RISC/VLIW architectures.  For example, P4 3.6 GHz
achieves almost 10k c/s at FreeBSD-style MD5-based hashes (which are
1000 iterations of MD5 compression function each, plus some overhead)
with the code currently in John.  The current lower-clocked non-x86 CPUs
are unlikely to cross 5k c/s at this test.

> Q2: Is there some further documentation on john's benchmarking 
> available?

Currently, no.

> e.g. What's the difference between real c/s vs. virtual c/s? 

(This is referring to the output of "john --test" on most systems.)

The "real" c/s rate is whatever rate has been achieved in the test.

The "virtual" c/s rate is calculated in virtual (processor) time rather
than in real time.  That is, it's an estimate of the rate which would be
achieved under no other load on the system.

On an unloaded system, the real and virtual rates should be almost the
same.

> How do the results map to Mbps, etc.

Strictly speaking, it is not entirely correct to "map" John's c/s rates
to Mbps for the underlying block ciphers or message digest functions.
The higher-level algorithms that John implements don't always require
full implementations of the well-known/standardized underlying ciphers,
and, in the case of DES, it's a modified-DES that is implemented.  More
importantly, the amount of "overhead" specific to the higher-level
algorithms or to the key setup (which is performance-critical for
password cracking!) is very far from negligible.  For some hash types,
such "overhead" may even account for most processing time.

However, it is OK to calculate "virtual" Mbps rates like this for rough
comparisons against other implementations (both software and hardware)
for which only Mbps figures are available.

Such "mappings" are obviously very different for the different password
hash types that John supports.

> And, some info or links for further 
> reading about the algorithms bechmarked would be nice as well.

It is important to distinguish between algorithms - instructions on how
to calculate a given mathematical function - and functions being
calculated.  There exist multiple algorithms (an infinite number of
them, actually) to calculate the same function.

For John, this distinction is very practical.  Much of John's great
performance (yes, I am very humble) is attributed to its use of
algorithms different from those originally used to describe the password
hash types that John cracks.  For some hash types, John even uses
different algorithms on different processor architectures.

Anyway, as it relates to your question, I only have a handful of
references available.

There's David Hopwood's "Standard Cryptographic Algorithm Naming" which
actually includes the algorithms:

	http://www.users.zetnet.co.uk/hopwood/crypto/scan/

Click on the "PassphraseHash" link in the frame at the left.  Here's a
direct link to the appropriate webpage:

	http://www.users.zetnet.co.uk/hopwood/crypto/scan/ph.html

but you probably want to view it as intended, within the frames-based
interface.

Unfortunately, this project appears to be inactive since 2002 and
David's e-mail address given on the website is outdated.  I was not able
to contact him with my (minor) corrections.

Niels Provos and David Mazieres' bcrypt (the Blowfish-based password
hashes) is described in their paper:

	http://www.usenix.org/events/usenix99/provos.html

The traditional DES-based crypt(3) is described in this historical Unix
v7 manual page:

	http://plan9.bell-labs.com/7thEdMan/vol2/password

To get an idea of how John implements DES (on most processor
architectures and for most DES-based hash types), you should read Eli
Biham's paper:

	http://www.cs.technion.ac.il/~biham/Reports/cs0891.ps.gz

You should then check out Matthew Kwan's webpage on the same topic:

	http://www.darkside.com.au/bitslice/

Hope this helps.

-- 
Alexander Peslyak <solar at openwall.com>
GPG key ID: B35D3598  fp: 6429 0D7E F130 C13E C929  6447 73C3 A290 B35D 3598
http://www.openwall.com - bringing security into open computing environments

Was I helpful?  Please give your feedback here: http://rate.affero.net/solar

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.