0

I'm often told that encryption forces processors to "make a pause" when performing the math to decrypt a hash, which is why brute forcing can take so long. I don't understand what it means for a processor to "make a pause" nor how a string of numbers could force that pause. Can anyone explain this using as much plain English as possible?

I recognize I might not be throwing all these terms around in an accurate way – my computer science and mathematical fundamentals are weak at best.

  • 3
    It does not make a CPU pause. It uses complex and slow calculations is I think what the author of whatever you read meant. Or they were just plain wrong. – Vitaly Osipov Feb 18 '16 at 22:22
3

Your question sounds a little vague to me, so I can think of two things you might mean by forcing it to pause:

A programmed pause - in the event that you don't have access to the password hashes, and you're just trying to type a password into the device, the device can just arbitrarily wait a certain amount of time before telling you whether you succeeded or not. This amount of time may increase with each unsuccessful attempt, though commonly the first few times have little penalty, due to human tendency to mix up password or type things incorrectly. If someone has access to your password hashes, and is using their own software to test all combinations (a brute force attack), then they don't need to include that pause, and it will have no effect.

Computationally expensive password checking - certain hashing strategies require a LOT of computation* to verify the the password is correct. These are intentionally used for password checking because you can't write your own software to bypass this. While it may seem like it would be a bad idea to force your users to wait for this expensive computation, having to wait one whole second actually isn't that big of a deal for the valid user, but it's a huge deal when dealing with a person who is trying to guess the password by brute force, as that penalty is incurred for every single incorrect guess they make. I should mention that while this may seem to just be a pause from the user's perspective, from the computer's perspective, it's a massive amount of work, which just doesn't happen to have any visible results drawn to the screen.

*a lot of computation compared to the few milliseconds that most operations take - actual delay may only be a second or so, depending on hardware.

3

I think you make be confusing a couple of concepts, and are asking specifically about password hashing, correct?

Password hashing, when done correctly, introduces a work factor, meaning that it takes some time to compute a hash, not strictly that a "pause" as you describe it, in involved though it does result in the end user perceiving some delay, which could be interpreted the same way.

One additional correction of note: A hash is one-way. There is no opportunity for decryption. So, if you have a hash of a password, and want to figure out what password was used to create that hash, the way that you do it is to use the same hash function, and to submit candidate passwords, and compare the resulting hash to the hash that you have, to see if they match. This is what websites (for instance) typcially do. In very simple terms, when you create an account, you're asked to provide a password, which is hashed, and the hash is stored. When you come back to log in again, you enter your password again, the website hashed what you have given it, and compares that to the hash it has stored. If they match, you're authenticated. If not, you're asked to try again.

So, the problem with a simple hash function is that its fairly easy to create the hashes of many candidate passwords very very quickly. So when the attacker steals a password hash from a database, he can then create hashes from a dictionary of possible passwords and compare the resulting hashes to the stolen hash to figure out what the password is at a staggering pace. For many common hash functions, he can try literally billions of possible passwords each second.

The fix for this, which I think you're alluding to in your questions, is the work factor that I mentioned, which is generally implemented as iterations. So when a password is submitted for hashing, it isn't hashed once, but 10,000 times, or 100,000 times, or 1,000,000 times. This means that when an attacker steals this hash, he too has to hash each of his candidate passwords just as many times in order to figure out if candidate is in fact correct. So now you've limited his possible tries from billions per second, to billions divided by 10,000, or divided by 100,000, or by 1,000,000. Much more expensive for him, and much less likely that he'll get far enough down his list of possible password to find the actual password.

In practice it's a bit more complicated that this. You have to factor in details such as salts, computational hardness vs memory hardness, and other such variables, but in general, at a high level, this is mechanism by which make attacking password hashes difficult.

  • Well done examples with good advice. Excellent inclusion of "get as far down the list of possible passwords." Thank you. – Anti-weakpasswords Feb 21 '16 at 20:25
2

I think there are two things you might have heard to give you that idea.

First, a good hash algorithm for password storage is designed to take long time to brute force. This is however not accomplished by making the processor pause. On the contrary, it is accomplished by making the processor work a lot.

The hash algorithm is designed to require a lot of computations (and therefore a long time). To bruteforce a hash you need to run the hash algorithm billions of times, and if the algorithm is good that should take years even on a good computer. But that is years of active computing, not pausing.

For more on password hashing, please see this article, especially the section on slow hash functions.

Second, you might have heard that on many login systems will not accept any number of attempts at entering a password without forcing you to pause, so as to prevent you from brute forcing the password. This has nothing to do with encryption. Also the processor does not pause. It is just that whatever you are logging into (it might be a remote server, or it might be an integreated circuit in you iPhone) refuses to test your credentials because it is programmed that way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.