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.