2

Suppose a user uses a password to log in to their PC. When the user logs in, the PC applies a cryptographic function to the password and compares the ciphertext to the stored ciphertext of the known password (this cryptographic function can be "hard," in order to make brute-force attacks difficult). An attacker has gained physical access to the machine, including the stored password ciphertext -- so of course they have access to all unencrypted files on their machine, but the attacker wants to get the password as well (perhaps knowing the user's password will help them guess the user's password on other services, among other things).

It seems like there is a theorem that gives an upper limit on how long the attacker can be delayed in brute-forcing the user's password. If N is the number of passwords in the complexity space that a real user is likely to choose from, and t is the maximum time that a user is willing to wait for the cryptographic function to hash their login password, and R is the ratio of the speed of the attacker's hardware to the speed of the user's hardware, then the maximum time for the attacker to brute-force the user's password is N*t/R.

For example, if there are 10 million passwords with the complexity of the password that the user is likely to choose from, and the user is willing to wait 3 seconds to log in after typing their password, and the attacker's hardware is 100 times faster than the user's hardware, then the maximum time for the attacker to brute-force the password is 10,000,000*(3 seconds)/100 = about 3.5 days.

Unfortunately, this seems to be an upper limit that is independent of what hardware or what cryptographic function you're using. There's always going to be a limit on how complex people will make their own passwords, there's going to be a limit on how long of a delay people will tolerate when logging in, and a well-funded attacker will always be able to get hardware many times faster than what an average user is using (if only by buying 100 laptops identical to the user's laptop).

So, a couple of things:

  1. Is the logic here sound?
  2. Is this a known theorem that somebody else pointed out a long time ago and already has a name?
  3. What are some things that can be done to mitigate this?
Improve this question

2 Answers 2

Reset to default
1

Your logic is sound, and is the basis for algorithms like PBKDF2. These increase the cost of a brute force attack to the point where it becomes infeasible for all but the smallest of dictionary attacks.

Improve this answer
4
  • True, but the conclusion here is that PBKDF2 (or any other "slow" algorithm) doesn't really help you, does it? Because if we assume the user won't tolerate a PBKDF2 delay of more than 5 seconds, and the attacker's hardware is 100 times faster than the user's computer, it will only take them 5-6 days to check all possible passwords against the hash stored on the hard disk.
    – Bennett
    Commented Jul 17, 2018 at 19:24
  • Ah, I understand now. You’re assuming an upper limit of 10 million passwords, which is simply a space so small that it can be brute forced in finite time. That’s why people implement password complexity requirements; to guide users to choose from a broader search space. But most requirements are poor; length is the primary way to improve entropy. PBKDF cannot improve a weak password.
    – John Deters
    Commented Jul 17, 2018 at 22:28
  • Yes that was intended as a sample number. But there's always going to be an upper limit on password complexity, beyond which users can't use them (without writing them down). Is there a number that used as a rule-of-thumb as the number of passwords that are sufficiently non-complex that human users will agree to use them? Even with password complexity requirements, you're going to hit a limit on how many passwords to choose from. (That is the justification for PBKDF after all -- even with strong requirements, there's a finite number to search through, which is why PBKDF has to be slow.)
    – Bennett
    Commented Jul 18, 2018 at 22:49
  • PBKDF is designed to thwart an attacker who steals a password database containing millions of records from affordably cracking them all. It also slows down online password guessing attacks. It won’t stop a dedicated one-on-one offline guessing attack.
    – John Deters
    Commented Jul 19, 2018 at 10:53
1

True for one password but another case is where 100,000+ accounts are obtained via an attack and it is desired to crack the passwords for sale on the dark web. In that case the security is reasonable good.

TO be secure according to NIST the salt must be secured separately from from the hashed password with an HSM or another secure server.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .