Has there been any cryptanalysis of AES under a non-uniformly distributed key? The standard security property demanded of a blockcipher is that it be a pseudo-random permutation; i.e., given a uniformly random key, the blockcipher should be computationally indistinguishable from a random permutation under a chosen-plaintext or chosen-ciphertext attack.

However, what if the key is randomly selected from a non-uniform distribution? Has there been any research in analyzing the security of AES (or any other well-known blockcipher, for that matter) when the key is instead chosen from some other distribution? Clearly low-entropy distributions would permit brute-force attacks, but it seems there's a pretty big gulf between keys for which brute-force attacks are infeasible and uniformly distributed keys.

My question is motivated by the observation that encryption keys are frequently derived from passwords or other low-entropy sources by hashing them (perhaps with a salt, which itself may or may not fall into the hands of an attacker). The hashing may expand the key to the required length and deter brute-force attacks, but cannot introduce entropy into the result. (Edit: My question isn't about scenario in particular, it's just an example of when a non-uniform key distribution could happen in practice.)

I am aware that there has been work on related-key attacks, but to my knowledge the results aren't directly applicable to this question.
As far as I know, NO, there has not been any cryptanalysis of AES under a non-uniformly distributed key. That holds even if we let the adversary decide what the non-uniform distribution is. Of course we should adjust the expected difficulty of attack according to the entropy remaining per the distribution; but typically, hashing a low-entropy password looses negligibly few entropy.

Further, the scenario that motivates the question has a low-entropy key hashed then the result (known as a derived key) used as the AES key. Indeed that leads to a non-uniform distribution of the AES keys, but that distribution is unrelated to the structure of AES, thus it is highly implausible that an attack on AES can take advantage of that non-uniform distribution.

The closest thing to what's asked is related-key attacks, but (as stated in the question) such attacks do not apply in the scenario that motivates the question. See in particular Alex Biryukov and Dmitry Khovratovich's Related-Key Cryptanalysis of the Full AES-192 and AES-256 (in proceedings of AsiaCrypt 2009). Quoting their adversarial model:


  The related-key attack model is a class of cryptanalytic attacks in which the
  attacker knows or chooses a relation between several keys and is given access to
  encryption/decryption functions with all these keys. The goal of the attacker is
  to find the actual secret keys. The relation between the keys can be an arbitrary
  bijective function R (or even a family of such functions) chosen in advance by
  the attacker.




In the scenario that motivates the question, the best general attack is typically enumerating the low-entropy key (approximately from most likely to least likely), applying the key derivation algorithm (or hash) for each, then testing if this is the right AES key based on known or low-entropy plaintext. That is slowed, to a large (but often insufficient) degree, by using a purposely slow key derivation algorithm, such as scrypt, or the lesser bcrypt or PBKDF2.