Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 9 Apr 2006 02:00:14 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: help me understand password cracking

On Sat, Apr 08, 2006 at 03:42:18PM +0000, jay rubin wrote:
> Could you help me understand exactly what it is that john does.
> 
> In the README for pwpump2 it has the statement:
> 
> This is an application which dumps the password hashes (OWFs) from NT's SAM 
> database, whether or not SYSKEY is enabled on the system.
> 
> Okay OWF is one way function.  I really get the feeling that pwpump has 
> dumped from the SAM database the result of the password after it has passed 
> through the hashing algorithm.

That's correct.

> Or has it dumped the algorithm

No.  The LM hash algorithm is the same for all systems which use those
hashes at all and thus it does not need to be "dumped".

> that was used to create the encrypted password?

This is hashing, not encryption.  Although a lot of people refer to
password hashes as "encrypted passwords", that is wrong.

Encryption is typically a one-to-one mapping that is easily reversible
given the encryption key (or a decryption key - with so-called
asymmetric ciphers).  This has nothing to do with most uses of John,
including yours.

Hashing in general may be a many-to-one mapping (there may be
collisions) that does not have to be easily reversible.  Cryptographic
hash functions, such as those used for password hashing, are in fact
meant to _not_ be easily reversible.  With password hashing, it is the
password itself which is hashed.

> Now what does jtr do to decrypt the password?

Strictly speaking, this is not "decryption", but rather finding a
password which would hash to a given value.  In practice, this will be
the original password, but in theory it does not have to be (due to
collisions, another valid password may be found for the same hash).

> Does john know the hashing algorithm

Yes.

> and just pass every canidate password combination through the 
> hashing algorithm until it gets one that matches the dump from pwdump2?

Correct.

There's also a subtle difference (which I've ignored for the above
answers to not confuse you) between hashing algorithms and what I call
"hashing methods".  The former are step-by-step instructions on how to
compute a hash.  The latter are functions (in the mathematical sense)
which map a plaintext password to a password hash, without regard to how
the computation is to be performed.  It is possible to implement the
same hashing method using different algorithms - and John takes
advantage of that.  The algorithms that it uses are different from and
much more effective than those that operating systems, etc. use.  For
example, John computes many LM hashes in parallel - for multiple
candidate passwords - and then uses another special-purpose algorithm
to compare multiple computed hashes against ones being cracked - also in
parallel.  This is why you see ranges of candidate passwords being tried
when you press a key for status.

-- 
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

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.