Storing user passwords

[gepard-me]

Currently in Hercules there are 2 ways to store user passwords in database:

• unsalted one-round MD5 hash (bad)
• plain text (arguably unacceptable)

I've done little research on storing passwords in safe manner these days, and it looks like bcrypt is generally recommended and widespread solution. It also has ready to use implementations in many languages, most importantly PHP and C.

I think we should provide a way to store passwords in a way that is considered safe. MD5 maybe was good enough several years ago, but with increasing computing power it no longer is.

[MishimaHaruna]

MD5 is indeed broken, especially if unsalted. There are even preimage attacks available (i.e. http://link.springer.com/chapter/10.1007%2F978-3-642-01001-9_8).

bcrypt seems like a good idea. Unlike MD5 and SHA-1, there is no implementation in MySQL, but that's not a critical issue, security comes first, and neither of those two algorithms is secure enough for storing passwords.
If we switch to bcrypt, we might perhaps consider offering a command-line tool to crypt strings, for the users' convenience (i.e. when they set up a new server, they will probably want to replace their s1/p1 passwords. While with MD5 it was trivial - UPDATE login SET user_pass = MD5('foo') WHERE account_id = 1, with bcrypt it no longer is.)

Another thing we should consider (unless we make bcrypt optional) is to get in touch with the most prominent Control Panel software authors to make sure they implement the new encryption algorithm in a timely manner. We don't want to drive away users because there's no easy way to manage their players' accounts.

An implication of the algorithm change is that old passwords (if stored in MD5 format) will be no longer valid, and it won't be possible to batch-convert them. Thus, we might want to offer a way for the server to convert them on the first successful login. (And this is, as of today, outside the HPM capabilities, as far as I know.)

The reason why we're currently allowing plain text passwords is because of the clientside (salted) hashing of passwords with certain versions of the login packet (see login.c:check_password() and packets 0x01dd, 0x01fa, 0x027c.) I don't see many solutions to this, other than using reversible encryption instead of hashing - as terrible as it may sound (but still better than plaintext.)

[gepard-me]

Ok... Thanks for pointing all this out. Here's the list of potential issues and possible solutions (proposed by you, and few more from me).

1. Setting up interserver password
   • Solution A: Provide command-line tool to calculate bcrypt hashes. It doesn't seem really convenient to me (need compiling), especially compared to other solutions (read on) or web-based calculators like https://www.dailycred.com/blog/12/bcrypt-calculator
   • Solution B: Embed bcrypt calculator into login-server console. Pretty straightforward. No need to for extra builds.
   • Solution C: Make login-server ask user for password for S accounts if they're not set in database. Make SQL schema creation script insert S account with empty password. Add hardcoded check against empty passwords (in case plain-text passwords are enabled).
2. Moving from plain-text passwords to bcrypt hashes
   • Solution A: Batch-convert them with console command.
   • Solution B: Batch-convert automatically.
   • Solution C: Convert only on successful user login.
3. Moving from MD5 hashes to bcrypt hashes
   • Solution A: Batch-convert to bcrypt(md5(password)) by bcrypting existing md5 hashes (either with console command, automatically, or on succesful login).
   • Solution B: Keep md5 hashes until successful login, then update with bcrypt hash.
4. Control Panels
   As far as I know, great majority is using flux-cp. Original flux-cp is not compatible with rAthena. There is a fork of it, by Xantara, upgraded for rA (https://github.com/missxantara/fluxcp-ra) , but it's not compatible with Hercules. Honestly, I think we (HerculesWS) should just fork it and keep it up to date with emulator. This isn't a lot of work.
5. Speed
   bcrypt is slow, much slower than md5 (that's also why it's so good against attacks). While I was testing it on my home PC I got following results:

rounds time (ms)
 4         1 
 5         2
 6         3
 7         7 
 8        14
 9        29
10       56
11      112
12      224
13      447
14      893

I'm gonna test more as soon as I prepare Linux build.

Now, there are two factors to be taken into consideration when choosing work factor (number of rounds):

• CPU time you are willing to pay for one password hashing
• number of concurrent login attempts

I suppose the second figure is usually rather low, unless you restart your server in peak hours. Even with 100 concurrent login attempts and 50ms per hash, it can delay user login by max 5 seconds. Anyway, that 50ms will imply different number of rounds depending on computing power available. So I guess there should be some kind of benchmark available to help determine number of rounds based on time limit imposed by user.

[MishimaHaruna]

About (1.A), I was thinking of a command line tool in src/tools (to easily compile with make tools), but the other options sound better, good idea there. Login server will already have the encryption functions defined, so both (1.B) and (1.C) sound good. Though, (1.B) won't be available for those who disable CONSOLE_INPUT, while (1.C) may be made available for them.

About (2), A and B are better from a security standpoint (why keep the unencrypted passwords, potentially for a very long time), but they may take a long time to complete in case of a big database, which may make option C more viable in certain cases.

About (3), I feel that bcrypt(md5(password)) may decrease security. If I'm not mistaken, there are only 2^128 ~= 3.4E+28 possible MD5 hashes, while the possible passwords are much more than that:

• We can assume all the password characters are in the [32..126] range of the ASCII character set. This gives us 126-32+1 valid values for each character.
• The minimum length of a password (normally - it is possible to edit the client to decrease that) is 4 characters
• The maximum length of a password (according to packets that carry plaintext passwords, such as 0x0064, 0x0277, 0x02b0) is 24 characters. Or 27, if we consider packet 0x0825 (used by the new clients without the integrated login interface)
  If all the above assumptions are correct, and my spreadsheet application can handle those numbers correctly, this means there are SUM(95^i) forall i in [4..24] ~= 2.95E+47 possible passwords (old clients), or SUM(95^i) forall i in [4..27] ~= 2.63E+53 possible passwords. One can argue that the cardinality of the codomain of the bcrypt function is much smaller than those figures, but it still is larger than the md5 one (2^128 for the salt + 2^184 for the password hash.)
  Because of that, I'd rather prefer to convert them on the first successful login.

About (4), it is really unfortunate that there's no control panel that works out of the box on Hercules. We really need to do something about that (but it's better to discuss that elsewhere, as it'd go off-topic here.)

About (5), should we make it configurable (And perhaps provide a sane default value)? If we do, we need to warn the users that they should never change the value once they set it, or things will break.

[saithis]

Suggestion for (5): How about making it configureable, but save the used number of rounds for each account. On each login it is checked if the config value matches the saved value and if it doesn't match, rehash the password and save it with the new number of rounds. So the admin can change it without breaking the login for all accounts.

[gepard-me]

About your concerns for (3.A), I'm not really sure if they're justified. I found 3 topics related to the issue:

• http://crypto.stackexchange.com/questions/2945/is-this-password-migration-strategy-secure
• http://crypto.stackexchange.com/questions/2840/how-did-linkedin-salt-all-their-passwords
• http://crypto.stackexchange.com/questions/2831/whats-the-reason-for-applying-the-hash-twice-when-hashing-with-salt
  and looks like there are no problems with that approach (stating that md5ing should not cause noticable entropy loss). All in all one of main goals of bcrypt is key strengthening, so it doesn't really matter if initial key (either plain pass or md5(pass)) is kinda weak.

About (5), in case you change work factor old passwords (with different number of rounds) will continue to work, since that number is stored inside hash. They can't be rehashed to new factor without providing password though. You can even use higher number of rounds for some accounts (server, GM) that are most likely to be targetted first in case of security breach and lower for regular accounts.

[MishimaHaruna]

Hmm, I'm not sure who those people from the stackexchange topics are, so I can't really know whether they're security experts - but I agree with the point that bcrypt(md5(password)) is far better than keeping md5(password) entries.

We can set it up so that those hybrid bcrypt(md5) entries are eventually replaced with bcrypt(password), when the user logs in. If we use bcrypt(md5) on existing md5 databases and bcrypt(password on existing plaintext or new ones, we'll need in any case to have the login server able to handle both, so it's a no brainer to have it detect if it should re-encrypt a password. (i.e. an algorithm like the one in the last flowchart from this example case)

About (5), that is really good news. Thanks for clarifying.

[gepard-me]

Preview of new console commands:

• bcrypt hash PASSWORD - calculates bcrypt hash of PASSWORD using login-server configuration settings (number of rounds)
• bcrypt benchmark TIME_LIMIT - calculates time required to hash one password with various number of rounds, starting from 4, which is minimum, up to the point it would exceed TIME_LIMIT in miliseconds.

Example output:

bcrypt hash password
[Status]: bcrypt hash: 'password' => '$2y$12$vUv9wv3xCU4ttZYKWnYcTOjfl08WDeWleHKUHiqResw/aQoOpc9xi'
bcrypt benchmark 1000
[Status]: bcrypt benchmark:  4 rounds -     2 ms
[Status]: bcrypt benchmark:  5 rounds -     5 ms
[Status]: bcrypt benchmark:  6 rounds -     9 ms
[Status]: bcrypt benchmark:  7 rounds -    19 ms
[Status]: bcrypt benchmark:  8 rounds -    14 ms
[Status]: bcrypt benchmark:  9 rounds -    28 ms
[Status]: bcrypt benchmark: 10 rounds -    55 ms
[Status]: bcrypt benchmark: 11 rounds -   112 ms
[Status]: bcrypt benchmark: 12 rounds -   223 ms
[Status]: bcrypt benchmark: 13 rounds -   448 ms
[Status]: bcrypt benchmark: 14 rounds -   893 ms
[Status]: bcrypt benchmark: done

[gepard-me]

Branch for #74: https://github.com/HerculesWS/Hercules/compare/bcrypt

[Yommy]

I suggest to also salt the encryption using the login name.

[MishimaHaruna]

@Yommy I don't think using the login name as an additional salt would give any security improvements, as bcrypt already uses a random salt on every password (so that if two users have the same password, their hashes won't be the same.)

[Status]: bcrypt hash: 'test' => '$2y$12$fW9jbe9qX1B9XjTl1wkMie8cpVts776KheGTYdWZcokww6JLkBLK.'
bcrypt hash test
[Status]: bcrypt hash: 'test' => '$2y$12$xnDgQe/RS05XWm/yZFTtkuBgc4o517cEqg5p4Hvq1KHzu1YwuNXpC'
bcrypt hash test
[Status]: bcrypt hash: 'test' => '$2y$12$rtcI2SXQkV2g6rirNh3QSeESpoIxcbIy8ijE7iDKaUQT.QjW.IqMC'

@piotrhalaczkiewicz What do you think of auto-detecting the password store method during password validation (i.e. calling password_guess_store_method on login), so that a partially transitioned database would still be usable? (and perhaps offering a configuration option to disable this behavior and force password checks to only use the configured password_store_method.)
Would that be worth the effort? It might help decreasing the downtime when converting all passwords to bcrypt, for servers with a large user base (assuming they're using an external tool to convert the passwords, rather than the login server's console command)

[Schwierig]

@MishimaHaruna We used bcrypt to encrypt a 60k heavy userbase in one project. If the rounds aren't set too high you should only have a minimal downtime.
And since the rounds don't matter when verifying the password you can just let the automated script run in ~4 rounds and advice the user to change their passwords to ensure an even better security with around 15 rounds or so.

[EPuncker]

is this issue dead? :(

[vthibault]

Just to let a note somewhere.
Basically, the MD5 hash stored in the database is as secured as the plain text one currently.
Let me explain : you can connect on the server without even reversing the MD5.

• Case of a plain password
  You have a plain password
  You connect in game using packet 0x64
  Success.
• Case of a hash password
  You have a hash password
  You connect in game using packet 0x01dd using the hash.
  Success.

So basically, from my point of view, the md5 hash is as secured as plain password so we should really have another encryption method, any news on this branch ?

[EPuncker]

@piotrhalaczkiewicz is on hiatus :/

[MishimaHaruna]

Yes, md5 hashes are useless. It's not as easy as you describe, since only plain-text passwords are accepted if the server is storing hashed passwords in the database.

            if( sd->passwdenc != 0 && login_config.use_md5_passwds )
            {
                login_auth_failed(sd, 3); // send "rejected from server"
                return 0;
            }

That was originally written because the packets 0x01dd, 0x01fa, 0x027c don't send a raw md5 hash of the password, but they salt it with a challenge string received from the server (well, I believe they do, I've never tested them on a client, so please correct me if I'm wrong), so it's not directly usable (or at all) to login if you only have the md5 hash stolen from a database.

But, in any case, I agree that the main point stands - MD5 is insecure and we should stop using it.

The main reasons why this branch is stalled are:

• If we complete it, we also need to add support for it in FluxCP before merging this to master, else it'll become unusable.
• There are some performance concerns with bcrypt, making a server an easier victim of a DoS attack. I don't have any figures to show because I have yet to benchmark this, but considering how slow bcrypt is (and for a reason), I feel there will be a need for better anti-DoS/DDoS measures, especially if we're going to enable this by default, or make it the only password encryption method.

[vthibault]

If I remember correctly you can can omit to request a key from the server, in this case the key is never generated and so the md5 hash will not be salted.
But in all cases you're right it will fail to pass the condition you quoted so I was wrong :)

[poporing]

is the project of bcrypt is dead?

[LiamKarlMitchell]

How about this?
https://github.com/trusch/libbcrypt

I've added a pull request that adds support on windows.

Client would have to send the password over in plaintext, unless someone can mod it to bcrypt on that end. Unless you want to bcrypt a md5 hash but that seems silly...

Lib usage:

std::string hash = BCrypt::generateHash(password, 10);
BCrypt::validatePassword(password, hash);

Adding bcrypt on fluxcp should be simple enough.

password_hash ( $password, PASSWORD_BCRYPT, [ 'cost' => 10 ] );

Notes on php:

• Maximum password length of 72 characters.
• PHP Defaults to BCRYPT from PHP 5.5.0 onwards, but could change in future versions so being explicit.
• Output always a 60 character string or FALSE on failure.
• You can store this as bytes and save some space but prefer simplicity.

[SombraRO]

@csnv
@guilherme-gm

I think the emulator is about time to have a feature like this