We know they're not hashed because you can ask to have your password mailed to you. They could still be encrypted, as encryption is reversible, making it possible to decrypt and mail the password.

And that's a quite bad idea, encrypted or not. Sending the plain text password by unencrypted mail does not make anything better.

There is another, generic way to solve the "I lost my passwort" problem. It only requires that the user has a valid email address. It works with any hashing algorithm, the harder the better:

1. Provide a "lost password" form that requires the user to enter its account name. To make it harder, you may also ask for the mail address currently stored in the database.
2. The handler for the "lost password" form searches for the user, something like SELECT userid, mail_address, user_name FROM users WHERE login=? AND mail_address=?.
3. If that does not return exactly one user, skip to the "lost password" form answer.
4. Generate a random number or string, about 100 byte of base64-encoded noise should be sufficient.
5. Store that random number in the user record as password update key (UPDATE users SET password_update_key=? WHERE userid=?), and send it out in an email adressed to the mail address stored in the database. Preferably, put the key in the URL for the "update lost password" form explained below.
6. The mail template should contain a note NOT to click on any link in the mail unless you have lost your password. It should also instruct the user to click on the URL or copy it into the browser's address line to set a new password.
7. Return an HTML page stating that a mail has been send out if the data entered was correct. (Note that you don't leak any information about the correctness of the login name or the mail address entered here.)
8. Provide a second "update lost password" form, with fields for the password update key, the login name, mail address, new password, new password repeated.
9. If a password update key is provided in the URL for the form, copy it into the password update key field.
10. The handler for the "update lost password" form compares the two new password, and repeats jumping to the form until the password and the repeated password are identical.
11. The handler salts and hashes the password, with the hardest hashing algorithm currently available.
12. The handler now atomically checks login, mail address, and password update key; updates the password, and invalidates the update key. Something like UPDATE users SET password_hash=?, password_update_key=NULL WHERE login=? AND mail_address=? AND password_update_key IS NOT NULL AND password_update_key=?.
13. Again, the handler answers with a page not leaking any information. Something like "if the data you entered was correct, you can now login using your new password" and a link to the login form.

A little detail that should be added is an expiry date for the password update key. It should be set to the current timestamp plus a short interval (8 hours, or a day, perhaps two days, depending on how fast emails are usually transported to your users, maybe 1 hour in an intranet environment). It is set when the update key is generated, and it should be included in the WHERE condition for the update statement (... WHERE ... AND update_expire_timestamp > NOW()). This prevents that users have a change request pending for ages. Technically, it does not hurt much. But without the timeout, an attacker could try to guess the code for ages and eventually succeed. With the timeout, the attacker has only a short time for guessing. After that, even a valid code is refused.

Another detail is that now the mail address is the "key to the kingdom". You don't want to allow simply changing it, perhaps because the user did not log out and a "black hat" tries to change it. Changing the mail address should require a confirmation code send to the old mail address, and a second confirmation code send to the new mail address, using a process very similar to changing a lost password.

Of course, there will be cases when users lose access to their old mail address before they can update their account. For that, you have the technical support people who can judge if a change request is legal and manually edit the mail address.

In intranet environments, email addresses rarely change, so you can omit the mail change procedure and rely only on tech support. Even better, you often have a central user directory (e.g. Active Directory or some other LDAP system), providing all user data, including the mail address. Just store LDAP "handle" of the user in the user table.

Even better, often the LDAP systems also store the central password, and allow your application to verify it (e.g. by appempting to login to the LDAP system using the credentials entered into the login form). (Single sign on.) This way, you can completely get rid of the password field in the database, and of all lost password problems, and make it Somebody Else’s Problem. And, as we all know, the "Somebody Else's Problem field" is much simpler, more effective, and "can be run for over a hundred years on a single torch battery."

Alexander