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:
- Is the logic here sound?
- Is this a known theorem that somebody else pointed out a long time ago and already has a name?
- What are some things that can be done to mitigate this?