3
$\begingroup$

Suppose that the key generation is insecure; each key bit is independently generated, but the value of each key bit is '$1$' with probability $0.90$. These keys are used in AES. What is an efficient attack against these weak keys.

The only thing I know is that a randomly chosen key has a lot of $1$s. But from this I don't know how to continue. Can someone give some hint on how to continue?

I have read here but I don't understand.

Improve this question
$\endgroup$
3
  • $\begingroup$ my first approach would be try a bruteforce: write your own key-generator that respects the probabilities of bits distribution, and try to decrypt your ciphertext. This approach is naïf, of course, but you should cover quite easily the "most probable" keys. $\endgroup$
    – ddddavidee
    Commented Nov 13, 2014 at 8:24
  • 2
    $\begingroup$ Note that the notion of "weak keys" has usually a different meaning in crypto. DES has weak keys: these are keys that will result in the block cipher itself providing less (or even no) security. AES in contrast does not have "weak keys". Your only option is to perform a weighted brute force attack; the algorithm itself hasn't become weaker by choosing specific key values. I would call this AES with keys that contain lower entropy. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 13, 2014 at 12:32
  • $\begingroup$ This should also make the link you've provided easier to understand. This is about the key schedule itself, i.e. if AES actually has a weak key schedule that compromises the block cipher itself. That's different from low entropy keys as you mention in your question. $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 13, 2014 at 12:37

1 Answer 1

Reset to default
4
$\begingroup$

You could do a brute force attack where you simply try the keys with highest Hamming weight first (those with the most ones). I am not sure if you would call this attack practical but at least it would be much more likely to succeed quickly than brute force when the key is selected uniformly at random.

Just consider the key of all ones, and assume we are using AES with 128bit keys. The probability of picking this key is $0.9^{128} \approx 10^{-6}$. One in a million may not sound very good but in contrast with uniformly random keys the probability would be $0.5^{128} \approx 10^{-39}$. The probability of picking one of the 128 keys with just a single 0 in it would be even better. So you might not have search very many keys to be likely to find the right one.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes. An easy statistical calculation shows that if for $j$ increasing from $0$ to $13$ we try the $128!/(128-j)!/j!$ keys with $j$ zero bits and $128-j$ one bits (using encryption of some known plaintext), we'll find a key with odds about $59.6\%$, and less than $2^{57.8}$ AES encryptions. With $j$ up to $8$, our chances to find a key are still a fair $9.7\%$, with effort less than $2^{40.5}$ encryptions. With $j$ up to $5$, $0.93\%$, with effort less than $2^{28.1}$. $\endgroup$
    – fgrieu ♦
    Commented Nov 13, 2014 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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