- the objective is to protect the confidentiality of the user names from an attacker having read access to the encrypted data, the ability to add usernames of her choice, and nothing else (in particular, no access to the key, even by proxy of a computer or device holding the key, or side channel);
- the IV is randomly chosen for each individual username encrypted (or re-encrypted after an edit);
- the key has been randomly chosen, is not compromised, and is used only for that usage;
then the system using CBC is safe, as far as we know (this follows from IND-CPA security of AES-256 in CBC mode). Notice this is highly theoretical. If an adversary can get remote access to a PC, and unless an HSM or Smart Card is used to hold the key, you have no strong argument that the key did not leak. Even if you use such tamper-resistant hardware to store the key, you have no argument that the adversary could not use that hardware, or otherwise access the plaintext.
Using ECB, the system would be unsafe even with the theoretical hypothesis given. In particular, it would be easy, from the ciphertext, to spot:
- identical usernames:
- usernames identical up to the first 16
- with high confidence, if a username uses more or less than 16
characters bytes (which in turn could be correlated with ethnic origin).
Update: Having the same IV for every user is a classical mistake, and brings back some (but not all) of the weaknesses of ECB. In particular, it is trivial to spot identical usernames; and thus to spot if a given username is present, for an attacker able to add a user with a given username. Depending on the number of usernames an adversary can realistically add, and on the encoding used for user names (which has considerable influence on the difficulty to exactly guess a 16-byte fragment of a username), it would be more or less easy to recover a fraction (or perhaps all) of the usernames.
IMHO, simply put, there is no proper way to encrypt usernames in an online database. Problem is, whoever can use the database to get the usernames will circumvent any crypto there might be; this is not a cryptographic problem. If you only want to give the illusion of security (or, equivalently, do the best you can in an implementation running in a nondescript environment), use CBC or CTR encryption with a random IV for each encryption of a record.