3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "non-uniformly distributed" does not seem to give much of foot hold to me. The work on related key attacks was made possible by carefully studying the AES key schedule. Just saying that something is not well distributed and work from there is not going to give you any results. Note that the related key attack still has a complexity of $2^{96}$ for one key out of $2^{35}$ so it isn't very practical when AES is used to achieve confidentiality. It just makes it somewhat harder to use AES to create other primitives such as hash functions and PRNG's. $\endgroup$ – Maarten - reinstate Monica Oct 2 '14 at 20:53
  • $\begingroup$ If you assume that your hash function is a PRF, then I don't think it really matters, besides the obvious brute force vector. What you seem to be hinting at is that there might be some special "weak" keys in AES that you could be stuck with if you sample from a low-entropy distribution? But the hash function would map your given low-entropy distribution onto a still low-entropy, but uniformly chosen distribution over the key space. So even if things are "close" in the password space, they will not be in the key space. $\endgroup$ – Travis Mayberry Oct 2 '14 at 22:26
  • $\begingroup$ @TravisMayberry I was using the term "uniform distribution" in the technical sense, i.e., all keys are equally likely. The standard PRP security definition assumes this property of the blockcipher key, and I was wondering if anyone had looked at the question of what happens when this assumption is violated (aside from related key attacks). $\endgroup$ – Seth Oct 3 '14 at 0:41
  • $\begingroup$ @owlstead This is not my area, but it seems to me that key scheduling attacks would be well in-scope here. For example, consider generating an AES-256 key by appending 178 zeros (or whatever) to a uniformly random 80-bit string. The result would (arguably) have enough entropy to be border-line secure against brute-force attacks, but it's my understanding that the key scheduler wasn't designed to handle this level of abuse. $\endgroup$ – Seth Oct 3 '14 at 0:54
  • $\begingroup$ @Seth: If my understanding is correct, even in the hypothesis you describe, we do not know an attack better than brute force; and that holds even if we allow the attacker to define how the key is expanded (without loss of entropy). I'm not sure of that, but still turned it into a tentative answer. $\endgroup$ – fgrieu Oct 3 '14 at 7:49
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

AES was designed to behave like an ideal cipher. An ideal cipher has no weaknesses when used with a non-uniformly distributed key (beyond that inherent in the non-uniform distribution of the key). Therefore, if AES does indeed meet its design goals, there are no shortcut attacks on AES that exploit special properties of AES, when using non-uniformly distributed keys.

There are some limited results which show that AES does not fully meet the goals of being an ideal cipher (the related-key attacks on AES-192 and AES-256), but their complexity is so high that they don't matter in practice. Therefore, they probably don't endanger your use case.

So, there are some reasons to believe that AES probably does not have any significant weakness, when used with a non-uniformly distributed key, assuming the key has sufficient min-entropy.

That said, usually using a non-uniformly generated key is not considered great practice, as it exposes you to unnecessary risk (even if the risk is small). It is better to use uniformly generated keys if possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.