Breaking AES encryption using decrypted data

Question

After a discussion about encryption, a friend of mine challenged me to crack a file he encrypted using AES with a 128bit key.

I know the file was originally a GIF image, so it should start with 'GIF8'. I'm wondering if it is possible to derive the password from this knowledge in a reasonable time (ie. a week or less).

Stealing the key in any way other than analyzing the encrypted file is not possible, as it defeats the point of the challenge.

If so, pointers would be welcome. I failed to found a decent flow-chart-like description of the encryption flow of the first block. I remember I had one from a course at Uni, but of course, it's nowhere to be found.

Answer 1

Good luck with that!

Answer 2

According to Wikipedia:

In cryptography, the Advanced Encryption Standard (AES) is an encryption standard adopted by the U.S. government. The standard comprises three block ciphers, AES-128, AES-192 and AES-256, adopted from a larger collection originally published as Rijndael. Each AES cipher has a 128-bit block size, with key sizes of 128, 192 and 256 bits, respectively. The AES ciphers have been analyzed extensively and are now used worldwide, as was the case with its predecessor, the Data Encryption Standard (DES).

In otherwords, 128 bit keys with this algorithm were developed by the US Government, and are used by worldwide.

You think you're going to break it???

On the basis that the file begins GIF8???

What are you thinking?

Answer 3

Think about this: If you could derive the password by just knowing the first cleartext-letters, how many encrypted messages would be worthless? How many letters/emails start with "Hello", how many of them have a standard (and known) signature (especially in companies). They would be all flawed. And in protocols you know a lot of cleartext-information, too. Encryption would be worthless.

Answer 4

wvdschel, while I certainly wish you good luck, consider that if you solve this problem you'll be probably entitled to a Ph.D in computer science or mathematics. AES was designed to be extremely difficult to break (i.e. in the exponential order of the amount of bits) even if you know some minor details about the encrypted file.

Any attack that can lower the complexity from about 2 to the power of the bit-length of the key somewhat will be a great breakthrough. In the past, such attacks on DES (that merely lowered its strength by a few times) won their authors wide acclaim.

Read up on linear cryptanalysis of AES.

Answer 5

You might stand a chance if he hasn't used Cipher-block chaining; see the image in the Wikipedia article pointed to by the link. Other than that, the comments you've received are spot on.

Answer 6

The only way to attempt to break the AES encryption is to use linear or differential cryptanalysis. Now, this is still extremely difficult to do!

Even for DES, which is deemed weaker, it took 50 days to break the encryption using linear cryptanalysis. A guy named Matsui in 1994 used 2^43 plaintext-ciphertext pairs. And this is only with 56 bits (which is the number of bits DES uses, or at least used at the time).

That is way more than the week or less you propose, and honestly I think it would take too many years for you to figure this one out, even with the knowledge that it has GIF8 in it.

Answer 7

This is highly unlikely to be achieved, not just of AES, but of any decent modern encryption algorithm due to (amongst other things):

Cipher-Block Chaining (whereby the results of the encryption of the previous "block" are used in the encryption of the next "block")

and also:

The Avalanche Effect (The avalanche effect is evident if, when an input is changed slightly, the output changes significantly)

Answer 8

If you're going for brute force then I hope you've got a supercomputer and a time machine

Assuming that one could build a machine that could recover a DES key in a second (i.e., try 2^55 keys per second), then it would take that machine approximately 149 thousand-billion (149 trillion) years to crack a 128-bit AES key. To put that into perspective, the universe is believed to be less than 20 billion years old.

Wow!! Approximately a 149 trillion years to 1 second proportion.

Also consider that any method of recovering the key faster than a brute force attack is considered a "break," and AES has not been broken.

Your best bet is to do some rubber-hose cryptanalysis

http://en.wikipedia.org/wiki/Rubber-hose_cryptanalysis

Answer 9

You'll never be able to break the AES 128 bit key.

If the key comes from a password, then you have a chance at a dictionary attack or brute-force attack on the password.

Answer 10

While any attempt to break AES will most certainly be futile, here's a nice, friendly explanation of the algorithm itself:

http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

Answer 11

Yeah, unless the implimentation is incredibly bad (you can find other encrypted data using the same key and IV that you know the plaintext of) you're basically hosed. Your best bet is to try to work it around the back, either get the key from the user somehow OR try and bruteforce keys and IV's (good freaking luck) using a known cleartext:known ciphertext.