MHB How Many Tests to Break DES and AES Encryption by Brute Force?

[Sudharaka]

Hi everyone, :)

Here's a question I encountered in one of my computer science classes.

• How many tests are necessary to break a DES encryption by brute force attack?
• What is the expected number of tests to break a DES encryption by brute force attack?
• How many tests are necessary to break a 128-bit key AES encryption by brute force attack?
• What is the expected number of tests to break a 128-bit key AES encryption by brute force attack?

And here's my answer. I just want to know whether you think it's correct. It seems ambiguous to me what is meant by necessary and expected in these questions. I hope I did it correctly but want some confirmation. :)

My Answer:

The number of bits in the key of the DES algorithm is 64. However only 56 bits are used in encryption; giving a total number of $2^{56}$ keys. Therefore the expected number of tests to break a DES encryption by brute force is $2^{56}$. However DES has the property that the compliment of the plaintext gives the compliment of the ciphertext under the compliment of the key. That is if the encryption is given as, $c=E(p,\,k)$ then, $\neg c=E(\neg p,\,\neg k)$. Therefore in each test (each application of the decryption algorithm) we can take the compliment of the plaintext that is produced and check whether it makes sense. This means instead of running the decryption algorithm $2^{56}$ times we only need to run the algorithm $2^{56}\div 2=2^{55}$ times. Hence the necessary number of tests to break a DES encryption by brute force is $2^{55}$.

Both expected and necessary number of tests to break a 128-bit AES encryption by brute force is $2^{128}$. This stems from the fact that the AES encryption scheme does not have the complimentary key weakness as the DES algorithm. So each key will have to be tested separately applying the decryption algorithm over and over again.

 

[Sudharaka]

Hi everyone, :)

Here's a question I encountered in one of my computer science classes.

• How many tests are necessary to break a DES encryption by brute force attack?
• What is the expected number of tests to break a DES encryption by brute force attack?
• How many tests are necessary to break a 128-bit key AES encryption by brute force attack?
• What is the expected number of tests to break a 128-bit key AES encryption by brute force attack?

And here's my answer. I just want to know whether you think it's correct. It seems ambiguous to me what is meant by necessary and expected in these questions. I hope I did it correctly but want some confirmation. :)

My Answer:

The number of bits in the key of the DES algorithm is 64. However only 56 bits are used in encryption; giving a total number of $2^{56}$ keys. Therefore the expected number of tests to break a DES encryption by brute force is $2^{56}$. However DES has the property that the compliment of the plaintext gives the compliment of the ciphertext under the compliment of the key. That is if the encryption is given as, $c=E(p,\,k)$ then, $\neg c=E(\neg p,\,\neg k)$. Therefore in each test (each application of the decryption algorithm) we can take the compliment of the plaintext that is produced and check whether it makes sense. This means instead of running the decryption algorithm $2^{56}$ times we only need to run the algorithm $2^{56}\div 2=2^{55}$ times. Hence the necessary number of tests to break a DES encryption by brute force is $2^{55}$.

Both expected and necessary number of tests to break a 128-bit AES encryption by brute force is $2^{128}$. This stems from the fact that the AES encryption scheme does not have the complimentary key weakness as the DES algorithm. So each key will have to be tested separately applying the decryption algorithm over and over again.

Our professor told that "expected" means the average value. So basically the expected number of tests needed to break a DES encryption is $2^{55}$ and for AES it's $2^{127}$.

 

[Sudharaka]

Hi everyone, :)

Here's a question I encountered in one of my computer science classes.

• How many tests are necessary to break a DES encryption by brute force attack?
• What is the expected number of tests to break a DES encryption by brute force attack?
• How many tests are necessary to break a 128-bit key AES encryption by brute force attack?
• What is the expected number of tests to break a 128-bit key AES encryption by brute force attack?

And here's my answer. I just want to know whether you think it's correct. It seems ambiguous to me what is meant by necessary and expected in these questions. I hope I did it correctly but want some confirmation. :)

My Answer:

The number of bits in the key of the DES algorithm is 64. However only 56 bits are used in encryption; giving a total number of $2^{56}$ keys. Therefore the expected number of tests to break a DES encryption by brute force is $2^{56}$. However DES has the property that the compliment of the plaintext gives the compliment of the ciphertext under the compliment of the key. That is if the encryption is given as, $c=E(p,\,k)$ then, $\neg c=E(\neg p,\,\neg k)$. Therefore in each test (each application of the decryption algorithm) we can take the compliment of the plaintext that is produced and check whether it makes sense. This means instead of running the decryption algorithm $2^{56}$ times we only need to run the algorithm $2^{56}\div 2=2^{55}$ times. Hence the necessary number of tests to break a DES encryption by brute force is $2^{55}$.

Both expected and necessary number of tests to break a 128-bit AES encryption by brute force is $2^{128}$. This stems from the fact that the AES encryption scheme does not have the complimentary key weakness as the DES algorithm. So each key will have to be tested separately applying the decryption algorithm over and over again.

Our professor told that "expected" means the average value. So basically the expected number of tests needed to break a DES encryption is $2^{55}$ and for AES it's $2^{127}$.

 

[Nono713]

Our professor told that "expected" means the average value. So basically the expected number of tests needed to break a DES encryption is $2^{55}$ and for AES it's $2^{127}$.

Remember that without further information on the key you are trying to find, you can only assume it has been chosen uniformly from the key space (from $[0, 2^{56})$ and $[0, 2^{128})$ respectively) so after trying half the keys you should expect to have found the correct one with probability $\frac{1}{2}$. In probability theory, the expected value is a synonym for the average value (or, perhaps, it is the opposite :p)

If you go on to study advanced cryptography, the reason you fall back to a uniform distribution will be formally explained in more detail than you would have ever hoped :) (it comes from the way security properties are defined, and that the uniform distribution constitutes the global maximum of all probability distributions under a very well-defined metric, which makes it essential to properly calculate worst-case security bounds - specifically, it is the maximum-entropy distribution of all continuous distributions).