2

Just an idea I had, and I am sure there is a lot of material about this subject, so I am looking for a pointer as to where I can find more information.

My idea is this...

When storing a password in a database, it is common to store it as a hash. This is weak against rainbow tables, which is mitigated by adding salt, and is also weak against brute force attacks.

I am thinking that it is possible to store the hash, modified with a small random string...

Using md5

mypass -> 2b643a4d56186389d84dbb3a9a483e99

If you have the hash, the password can be found by simply hashing all possible passwords, and comparing the hash, so...

// append a random 3 character string of a-z characters, we can use "xth" for this example
mypassxth -> 02a2247c788681af6ce1bb5fa66dd4c0

The random string is never stored, never shared, and only resides in memory on the server at the time of storing the hash.

This makes lookup of passwords less efficient, because the server must check any incoming requests by brute forcing the partly complete input against the stored hash, which in this case would mean an upper bound of 17576 (26^3) checks to validate the password.

It would also make brute force attack much harder in this case, an upper bound (assuming a-z only) of 5429503678976 (26^9) rather than 308915776 (26^6).

I guess it is like using a very small salt, that is not stored anywhere, requiring brute forcing during lookup operations.

Assuming I am not completely missing something obvious that makes this not work, can someone tell me what this concept is called, or point me somewhere where I can read about it?

Billy Moon
  • 123
  • 3
  • 2
    The problem with your code is that your server-side brute force function needs somewhere between 1 and 17576 iterations to exit successfully (has variable cost). This is not anything like how some inherently slow KDFs that @TerryChia mentioned in his answer function, by introducing a known and non-variable cost to using them. – TildalWave Apr 01 '13 at 13:41
  • While @TildalWave is certainly right, it _is_ a useful evasion technique used by malware, since the key will be nowhere in the binary itself. – forest Dec 12 '17 at 06:36

1 Answers1

10

Seriously, don't be a Dave and roll your own crypto.

Use a proven KDF such as PBKFD2, bcrypt or scrypt to hash your passwords. See this great answer for more information on how to securely hash passwords.

For your scheme, mypass is essentially no longer your password. mypassxth is. An attacker has no problems just bruteforcing the password with his nice little GPU as you are using MD5. This has NO bearing on an attackers ability to bruteforce your password, and just makes password hashing that much more computationally expensive for your servers.

If you are using a good KDF like bcrypt instead of MD5 for password hashing, this scheme will add a lot of additional load on your servers with very little gain.

Community
  • 1
  • Well, the password is no longer `mypass` and becomes `mypassxth` - which is the point - to make a stringer password, which is still usable. People prefer to have a shorter password, like 8 characters, and if the system can make it as string as an 11 character password, surely that is a good thing no? As far as I can tell, it does have a bearing on the attacker's ability to brute force it, because it increases the length of the password, which makes it harder to brute force. Is there something I am missing? – Billy Moon Apr 01 '13 at 13:41
  • it seems that `bcrypt` and `scrypt` are solving the same problem space, but much more efficiently, and with more concerns thought out. Thanks for the links - I am learning. (not implementing any of my own crypto, just trying to understand more about it). – Billy Moon Apr 01 '13 at 14:10