13

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 find a decent flow-chart-like description of how the encryption of the first block works. I remember I had one from a course at Uni, but of course, it's nowhere to be found.

Achraf Almouloudi
  • 756
  • 10
  • 27
wvdschel
  • 11,800
  • 14
  • 41
  • 45
  • 22
    If the answer is "yes", then the AES standard is a fundamental failure. – skaffman Jul 10 '09 at 15:18
  • 4
    Focus on figuring out how to steal the key rather than decrypt the file. You'll get farther with that in a week. – Michael Jul 10 '09 at 15:19
  • Then I'm hoping it is :) – wvdschel Jul 10 '09 at 15:20
  • Stealing the key is not an option, that would defeat the purpose of the challenge. – wvdschel Jul 10 '09 at 15:22
  • 15
    Hold your friends nuts in the fire until he gives you the key. The universe will not last long enough for you to break AES. – skaffman Jul 10 '09 at 15:23
  • Hey, he "challenged [you] to crack a file". Stealing the key is a perfectly valid approach. What if the Ultra crowd had had your attidude in WWII? We'd be writing all this in German. – MusiGenesis Jul 10 '09 at 15:31
  • 2
    im getting confused here, is AES a hashing algorithm or encryption? – Petey B Jul 10 '09 at 15:35
  • 6
    Do you by any chance have a significant other that's been leaving unexpectedly from your home while you attempt to solve this problem? – John Rasch Jul 10 '09 at 15:35
  • @PeteyB: It a symmetric encryption algorithm – skaffman Jul 10 '09 at 15:36
  • 1
    Not a chance you'll crack it. – Jon Tackabury Jul 10 '09 at 18:13
  • 1
    Did he encrypt it with his own functions? If he isn't too keen on encryption he might have encrypted it using ECB mode. If this is the case, open the cryptotext in MSPaint and see if you can see the image. http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation#Electronic_codebook_.28ECB.29 – clemahieu Jul 10 '09 at 19:35
  • This question appears to be off-topic because it is about cryptography, which is more appropriate elsewhere on the Stack Exchange network. – templatetypedef Oct 23 '13 at 08:08
  • This question appears to be off-topic because it is about security or cryptography and doesn't include a programming problem. – Duncan Jones Dec 04 '13 at 15:16

10 Answers10

36

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.

Eli Bendersky
  • 263,248
  • 89
  • 350
  • 412
  • 7
    Heck, forget the PhD, you may be in contention for the Fields medal if you figure this out ;-) – David Z Jul 10 '09 at 15:41
  • 7
    But hurry, you can only get the Fields medal if you are 40 or younger. ;-) – starblue Jul 10 '09 at 17:55
  • 79
    Who wants a PhD or a Fields medal... Stack Overflow would give you a 'gold badge' if you do it! – Mark Feb 11 '10 at 18:34
  • PhD for what? secretly auction the code, a rich country/organization should buy it right away at least for a $1B for counterintelligence usage. – D.Snap Apr 11 '16 at 06:18
8

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.

tanascius
  • 53,078
  • 22
  • 114
  • 136
5

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

Graphics Noob
  • 9,790
  • 11
  • 46
  • 44
5

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

Will Vousden
  • 32,488
  • 9
  • 84
  • 95
3

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'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.

BoltClock
  • 700,868
  • 160
  • 1,392
  • 1,356
abelenky
  • 63,815
  • 23
  • 109
  • 159
3

Good topic.

Interesting how fast is tech and science evolving. Recently I read this NSA related article: http://www.hpcwire.com/hpcwire/2012-03-19/nsa_employs_cutting-edge_supercomputing_for_domestic_surveillance.html (from 2012 March 19th, less than 3 yrs after the original question in this post).

Much of the data is encrypted though, and that’s where the supercomputing comes in. To extract the information, the NSA had to employ brute force algorithms, and that required a lot of computing power. Bamford reports that the Multiprogram Research Facility was built at Oak Ridge National Laboratory to house a supercomputer for such work. That facility, known as Building 5300, spanned 214,000 square feet and cost $41 million to build back in 2006. While the unclassified “Jaguar” supercomputer was being deployed on the other side of the Oak Ridge campus, the NSA was installing an even more powerful system in Building 5300. Writes Banford:

The NSA’s machine was likely similar to the unclassified Jaguar, but it was much faster out of the gate, modified specifically for cryptanalysis and targeted against one or more specific algorithms, like the AES. In other words, they were moving from the research and development phase to actually attacking extremely difficult encryption systems. The code-breaking effort was up and running.

According to Binney, a lot of foreign government data the agency was never to break (128-bit encryption) might now decipherable.

How efficiently NSA is doing this, I guess will be quite difficult to know for normal mortals like us (hey, it's NSA! :-) )

Still we should consider that they are not planning in breaking 1 key but a huge number of them... So breaking a 128-bits AES message seems not anymore science fiction or theoretical math.

Jorge
  • 1,317
  • 1
  • 11
  • 6
2

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.

AlbertoPL
  • 11,479
  • 5
  • 49
  • 73
2

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)

CraigTP
  • 44,143
  • 8
  • 72
  • 99
1

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.

jpc
  • 11
  • 1
0

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.

Michiel Buddingh
  • 5,783
  • 1
  • 21
  • 32