You have old_passwords=1 in your my.cnf. This could be because you used one of the my-small.cnf, my-large.cnf etc. templates provided with your MySQL distribution.

This KBA provides information about how you can upgrade passwords from old_passwords.

Solution

The problem with old_passwords is that this variable makes the password hashing algorithm compatible with that of MySQL 4.0 which was released several years ago and is not likely to currently be in use anywhere. With old_passwords you get a 16 hexadecimal digits (64 bit) hashing of your passwords, whereas with "new passwords" you get 40 hexadecimal digits (plus extra "*") leading to better password encryption. You can read more about it on the manual.

How do I upgrade to new password format?

You cannot merely put a comment on the "old_passwords=1" entry in the configuration file. If you do so, the next client to connect will attempt to match a 41 characters hashed password to your existing 16 characters entry in the mysql.users table. So you need to make a simultaneous change: both remove the old_passwords entry and set a new password. You must know all accounts' passwords before you begin.

Please note that old_passwords is both a global and a session variable. To work out an example, assume the account ‘webuser’@’localhost’ enters with ‘123456’. Please see the following:

root@mysql-5.1.51> SET SESSION old_passwords=0;
Query OK, 0 rows affected (0.00 sec)

root@mysql-5.1.51> SELECT PASSWORD('123456');
+-------------------------------------------+
| PASSWORD('123456')                        |
+-------------------------------------------+
| *6BB4837EB74329105EE4568DDA7DC67ED2CA2AD9 |
+-------------------------------------------+
1 row in set (0.00 sec)

root@mysql-5.1.51> SET SESSION old_passwords=1;
Query OK, 0 rows affected (0.00 sec)

root@mysql-5.1.51> SELECT PASSWORD('123456');
+--------------------+
| PASSWORD('123456') |
+--------------------+
| 565491d704013245   |
+--------------------+
1 row in set (0.00 sec

So, the PASSWORD() function consults the old_passwords session variable.

To upgrade ‘webuser’@’localhost’‘s password please perform:

root@mysql-5.1.51> SET SESSION old_passwords=0;
Query OK, 0 rows affected (0.00 sec)

root@mysql-5.1.51> SET PASSWORD FOR 'webuser'@'localhost' = PASSWORD('123456')

You can check the password entry on the mysql.users table.

The above steps sets a 41 characters password hash for that account. Now, the next time the client wishes to connect, it must know in advance it is to expect a new password, otherwise it will encode a 16 characters hash, and try to match it with the new 41 characters hash. Now please perform:

root@mysql-5.1.51> SET GLOBAL old_passwords=0;
Query OK, 0 rows affected (0.00 sec

This will apply to all new connections made from that moment on (not affecting any existing connections). So, make sure you have updated passwords for all accounts.

To summarize, please don’t forget to set old_passwords=0 in the my.cnf file. It's better to completely remove the entry altogether.