How does one write a MySql query to do a search on (for example) a username, when the username has been AES encrypted with a key and an IV?
I can't find examples of how to write the query.
Of course one has to decrypt the entire dataset and then filter it. Doesn't this cause memory problems?
This is not advisable. Having to decrypt the whole data-set will be slow and memory expensive. You will want to find a reasonable way to encrypt the data without using a separate IV for each username, then encrypt the username you want to find and search for the cipher-text. This will allow you to use indexes and search for only the one username you are interested in.
Alternatively you may consider using hashing in addition to the sorting encrypted username. HMAC the username with a password only known to the server and store in the DB. Then when you want to find a user, hash his username as well and find using the hash. Admittedly this allows some information leakage, for example attacker will be able to see users with the same usernames (you rpobably don't want these anyway). However he should not be able to use any hashtables or even guessing without knowing the HMAC key.
PS: A way you may want to deal with the IV may be: During registration (or username change) choose IV common for the entire server. Encrypt using this IV. If the first block (16 bytes for AES) already are in the database, increment the IV by one and try again. Store the highest increment. During search, try all possible IVs (from the basic one up to the highest increment used).
