Let's say that I have a system where one of the security requirements is preventing users from choosing a password that matches their username.  Usernames are not case sensitive but the passwords are.  The passwords are stored by the server using a secure hashing function that cannot be reversed.

When the account is created both the username and password are initially available in plaintext to the server for comparison.  We can compare them in memory (while disregarding case) to see if they match and instruct the user to choose a different password if they do.  Once this check is satisfied the password is securely hashed for storage while the username is stored in plaintext.  No problems meeting the requirement here.

When the user wants to change their password, or it is being changed for them, the server can retrieve their username record and compare it to the newly chosen password value (again ignoring case) to see if it matches.  No problems meeting the requirement here either.

However, the system also allows username changes.  During this ID change process the user hasn't necessarily provided their password in plaintext to the server.  They may have done so when they authenticated, but the server isn't going to keep that password stored in plaintext just in case they decide to change their username.  So the plaintext password is not available to check for a match against the newly chosen username value.

In an attempt to meet our requirement the server can use the same secure hashing function to hash the new username and compare it to the recorded hashed password.  If they match then the server can instruct the user to choose a different username.  However, since the username is not case sensitive this check might fail when it is arguably true.  If I submit "PwdRsch1" as a new username choice and my password is "pwdrsch1" then the system will allow it since the hashes won't match.  I -- or worse, an attacker -- could then later successfully authenticate with a matching username and password of "pwdrsch1".

We could force the username to lowercase before hashing and checking it against the password, but then the reverse scenario is possible.  The username would be checked as "pwdrsch1" against a password of "PwdRsch1" and allowed since these don't match.  But later I can successfully authenticate with a matching username and password of "PwdRsch1".

What reasonable options do I have to reduce this risk of a password matching a username that is not case sensitive?

The only sensible way to get what you want is to ask for the password when a user changes their username.  This way the server always has the information needed to conduct an accurate comparison between the username and password during a change, and prevent matches.

As sensitive operations - such as changing passwords, or in your case usernames - should require a password anyways (to limit the damage of XSS), this shouldn't be a problem.

Your only other alternative is to try every possible case combination, hash it, and compare that to the stored hash when a user changes their username.
