Password Cracking in 2010 and Beyond

Question

I have looked a bit into cryptography and related matters during the last couple of days and am pretty confused by now. I have a question about password strength and am hoping that someone can clear up my confusion by sharing how they think through the following questions. I am becoming obsessed about these things, but need to spend my time otherwise :-)

Let's assume we have an eight-digit password that consists of upper and lower-case alphabetic characters, numbers and common symbols. This means we have 96^8 ~= 7.2 quadrillion different possible passwords.

As I understand there are at least two approaches to breaking this password. One is to try a brute-force attack where we try to guess each possible combination of characters. How many passwords can modern processors (in 2010, Core i7 Extreme for eg) guess per second (how many instructions does a single password guess take and why)? My guess would be that it takes a modern processor in the order of years to break such a password.

Another approach would consist of obtaining a hash of my password as stored by operating systems and then search for collisions. Depending on the type of hash used, we might get the password a lot quicker than by the bruteforce attack. A number of questions about this:

1. Is the assertion in the above sentence correct?
2. How do I think about the time it takes to find collisions for MD4, MD5, etc. hashes?

And finally, regardless of the strength of file encryption using AES-128/256, the weak link is still my en/decryption password used. Even if breaking the ciphered text would take longer than the lifetime of the universe, a brute-force attack on my de/encryption password (guess password, then try to decrypt file, try next password...), might succeed a lot earlier than the end of the universe. Is that correct?

I would be very grateful, if people could have mercy on me and help me think through these probably simple questions, so that I can get back to work.

Answer 1

As I understand there are at least two approaches to breaking this password. One is to try a brute-force attack where we try to guess each possible combination of characters. How many passwords can modern processors (in 2010, Core i7 Extreme for eg) guess per second (how many instructions does a single password guess take and why)?

As you observe, this depends on the algorithm used. SHA1 is a common (though poor) choice, so let's consider that.

The best SHA1 implementations in software claim as little as 5.8 cycles per byte on 1024 byte blocks; let's be generous and assume that it's as efficient on a single 512 bit block; that would imply 371.2 cycles per block, or equivalently, per password guess. On your suggested processor, which Wikipedia claims does 147,600 MIPS, that's very optimistically about 400 million guesses per core per second, or a little under 2.3 billion per second for the whole processor. Note these are wildly optimistic, but should be in the ballpark, at least.

Another possibility is dedicated hardware: this claims to run on an FPGA, do 82 clock cycles per block, and run at 350mhz - which doesn't sound impressive at only 4.2 million guesses per second, until you consider that at only 14,500 gates per core, you can build a lot of these in the size of a Core i7.

Also bear in mind that a good password hashing scheme will hash the password repeatedly - hundreds, or even thousands of times - which inflates the amount of work you have to do by the same factor.

All of this is somewhat irrelevant, however, if you don't have access to the password hash - which you often wouldn't. In that situation, you're limited by the rate at which you can make guesses, and a well designed system will easily detect your brute-force attack, and cut you off, making the size of the password somewhat irrelevant.

Another approach would consist of obtaining a hash of my password as stored by operating systems and then search for collisions. Depending on the type of hash used, we might get the password a lot quicker than by the bruteforce attack. A number of questions about this:

Is the assertion in the above sentence correct?

Not exactly. You seem to already assume you have the password hash in the first question. A brute force attack is searching every possible password - they're not two distinct things.

How do I think about the time it takes to find collisions for MD4, MD5, etc. hashes?

There are currently no known practical preimage attacks for MD5 or SHA1. I'm not sure about MD4, but nobody in their right mind should be using it now!

And finally, regardless of the strength of file encryption using AES-128/256, the weak link is still my en/decryption password used. Even if breaking the ciphered text would take longer than the lifetime of the universe, a brute-force attack on my de/encryption password (guess password, then try to decrypt file, try next password...), might succeed a lot earlier than the end of the universe. Is that correct?

Correct, which is why good crypto systems don't encrypt messages directly with a password-generated key, but rather use other systems like public key crypto, requiring the attacker to first get your private key (which ought to be difficult in the first place), then attempt to crack the password on that.