time to crack file-encryption password - more than just iteration

Question

I have often seen that takes x amount of time to crack a certain length password. But this just seems to be the amount of time it takes to iterate through all the possibilities. What about the time it takes to check each iteration to see if it works? Wouldn't that make the process take far longer?

I'm most interested in a situation where there is a file which is believed to be encrypted but by an unknown method . (Not so much interested in web password logins). What is the procedure for trying billions of passwords on this file and how would it impact the total time to decrypt?

Answer 1

Enumerating through all possible password, having each one in memory at some point, is an extremely fast process. One can assume that a simple PC will be able to build one such password per clock cycle and per CPU core. So the PC will enumerate billions of passwords per second. If the figures you see are substantially less than that, then they include the password verification cost as well.

The password verification cost is highly variable. Normally, the system which wants to verify passwords stores salted hashed passwords. If the hash function is SHA-1, then an Intel Core2 x86 CPU, running at 2.4 GHz, will be able to try about 12 millions of password per second (and per core): this is what the speed at which the processor will be able to apply the hash function on each password (the password enumeration itself is less than 1% of that cost). My PC is a quad core, so that's 48 millions per second. I also have a not-too-bad Nvidia graphics card which can do password hashing, actually 160 millions per second with a simple raw SHA-1. At that speed, all 8-character passwords (with uppercase and lowercase letters, and digits) are checked in about a fortnight.

Good password storage schemes use iterated or concatenated hashes, in which the password is hashed thousands of times: this makes password verification thousands of times slower, which does not imply a user-noticeable slowdown, but makes the task much harder (namely, thousands of times much harder) for the attacker.

Answer 2

Yes, it's also an important factor. Making it resource consuming to check password correctness is at least some way to make it harder for the attacker. That's exactly what KeePass does trying to protect against dictionary attacks.

But the problem is, based solely on this measure, you're counting on the fact that the attacker won't just switch to a much faster computer/cracking machine.

It can really help though if you can force some external limits to this process. In fact rate limiting your password checks is a good solution if it's applicable - normally you get 3 tries to "guess" your bank account password and you're locked for some time or indefinitely. Try brute-forcing this.

Answer 3

If I get your question right, it is about brute-forcing a password used for file encryption, rather than cracking a password in a standard collection of hashed passwords. And you may not even know the format of the encrypted file.

It is thus related to the concept of Unicity distance - Wikipedia, and closely related to the previous question here If someone breaks encryption, how do they know they're successful? - IT Security.

I suspect that the time needed to verify the success of a given password is typically very fast for most files with common data formats. But at the other end of the spectrum, if the file is carefully chosen to look very random (e.g. highly compressed and stripped of the typical headers and metadata), it may in fact be arbitrarily hard to verify each password.