[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20060906184339.GA26520@openwall.com>
Date: Wed, 6 Sep 2006 22:43:39 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: encryption strength vs. the time it takes to find the same password with different key sizes
On Tue, Aug 29, 2006 at 03:24:58PM -0400, John wrote:
> I am trying to better understand this, so please bare with me. Lets say I
> have two hashes I want to crack. Each hash uses the same password. If
> one encryption is with 32 bit. and the other is 64 bit. would cracking the
> 64 bit encryption actually take longer? Even though they both use the same
> length password?
Although others have proceeded to interpret your question in certain
ways and provide answers, I feel that I need to point out that your
question is not correctly formulated and thus might be misunderstood.
I'll try to explain without going into detail and omitting whatever is
not relevant.
There are cryptographic hash functions that take any data as input and
produce hashes as output. The input to these may be of an arbitrary or
a fixed size, but the output hashes are typically of a fixed size.
There are also block ciphers that take blocks of data and a key as input
and produce blocks of encrypted or decrypted data as output. With many
of these ciphers, the block and key sizes are fixed.
For example, MD5 is a hash (or message digest) function accepting inputs
of almost arbitrary length and producing 128-bit hashes. For another
example, DES is a block cipher accepting and producing 64-bit data
blocks, encrypted or decrypted with a 56-bit key. JtR supports a number
of hashes built on top of DES that do or do not propagate the block
and/or key sizes of DES onto properties of these higher-level hashes.
The traditional DES-based crypt(3) limits input passwords to 56 bits and
produces 64-bit hashes on output. The BSDI-style DES-based crypt(3) is
also affected by these properties of DES, but the input is effectively
limited to 56 bits in a more subtle way, not by truncating the password
after 8 7-bit characters. So with it you can have a longer password
that carries up to 56 bits of entropy - which is still enough for most
purposes these days.
Now, 32- and 64-bit _what_ did you mean in your question? Input to
hashes? The hashes? A block cipher's input/output block size? A block
cipher's key size? In your question, you've also mixed hashing and
encryption for further confusion. ;-)
Usually, "encryption strength" refers to key size. If nothing is
encrypted, but rather a password is hashed, the strength is primarily in
the password size and choice - so, according to the message Subject, you
could be speaking of the number of bits of information that a hash
function uses out of an input password (e.g., 56 for the two DES-based
crypt(3) examples, above). However, you could also be speaking of the
hash sizes. Luckily, this does not affect the answer to your question
much - it's the smaller of the two sizes that dictates how many
candidate passwords you have to try before you're likely to find one
producing the right hash. (That's under the non-realistic assumption
that the original hashed password was chosen at random from the entire
keyspace, using a RNG with a uniform distribution.)
> For example: I got thinking that if you used an lowercase
> alpha only password, that is 6 chars long.. so 26^6 possible combos to break
> it.... wouldn't it be the same for each encryption strength?
Yes, it would be the same, and the hash size would not matter much since
26 ** 6 is substantially smaller than 2 ** 32 anyway. (I am using the
"**" notation for power.)
However, if we pick a larger candidate password space, then the chances
that JtR finds a suitable candidate password (not necessarily the
original one) that produces the right hash would be high as it approaches
or exceeds 2 ** 32 candidate passwords tried against a 32-bit hash.
Specifically, for a cryptographic hash function accepting arbitrarily
long inputs and producing 32-bit hashes and for a particular hash
produced with that function of an "unrealistically random" password (as
defined above), the probability of finding a suitable password within
any non-pre-screened 2 ** 32 candidates would be 1-1/e or around 63%.
In practice, CRC-32 was misused for password hashing by "Remote Access"
BBS software:
http://wps.com/FidoNet/FidoNews/1994/FIDO1137.NWS
(search or scroll down to "REMOTE ACCESS - FALSE SECURITY PROMOTION")
and by some BIOSes:
http://www.cgsecurity.org/cmospwd.txt
Other than that, uses of small hash sizes or low effective password size
limitations are uncommon. (Also, CRC-32 is not a cryptographic hash, so
its small size is not the only problem with its misuse.)
--
Alexander Peslyak <solar at openwall.com>
GPG key ID: 5B341F15 fp: B3FB 63F4 D7A3 BCCC 6F6E FC55 A2FC 027C 5B34 1F15
http://www.openwall.com - bringing security into open computing environments
Was I helpful? Please give your feedback here: http://rate.affero.net/solar
--
To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.
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.
