Is there a practical way to crack an AES encryption password?

Question

I heard that the fastest method to crack an AES-128 encryption, or and AES-256 encryption is by brute force, which can take billions of years. But I can't help thinking there's got to be a faster way. Because the AES encryption scrambles the data contained in a zip file, the password could be found by unscrambling that data correctly. Say if a portion of the data in the file is known, for example a string at the end of a file, or a header containing an expected sequence of bytes in a known file type. Then by comparing the scrambled bytes with the 'expected' unscrambled bytes, the password can easily be determined by computing an algorithm that converts those bytes because both the scrambled bytes and the unscrambled bytes are known. Only the formula is unknown. However, the condition for this type of cracking is that the zip file contains known file types which have a determined data format and places certain data in certain locations in the file. For instance, a 3ds file always starts with a header containing the bytes "4D4D".
Hence a list of possible passwords to rearrange the sequence begin to be narrowed down as the cracking progresses. So is this method plausible? or is there something wrong with it, like maybe the actual address of the bytes in the zip is different from the address in the unzipped file.

Answer 1

Yes, in the question's situation, a password-recovery attacks is entirely reasonable.

The question considers a (partially) known plaintext attack, where e.g. some header of the encrypted file(s) is known, for a file encrypted with AES, where the key has been determined from a user-supplied password. In this scenario, it is not important to consider the expected number of AES operations for brute-force search of the AES key ($2^{127}$ for AES-128, $2^{255}$ for AES-256) because that's not the best (nor a credible) attack strategy.

The reasonable attack strategy is password cracking: try passwords, approximately from most to least likely to have been chosen, and for each attempt decryption up to the point where known plaintext is reached, and move on to the next password if this test fail. Attack cost will depend on:

1. How the password was chosen. Users vary widely on that, and 123456 will be easier to find than MdSm2aZ!t&5u*Z5. That varies widely with the context, and motivation of users. See the obligatory XKCD.
2. How the password is transformed into an AES key. A password-based key derivation function should be used here, parametrized so that it adds a sizable cost.

The cost for an attack grows roughly as $2^E$ times the cost of the PBKDF (assuming that dominates the cost of testing a password), where $E$ is the password entropy in bits. For example, if the password is 6 random decimal digits ($E=\log_2(10^6)\approx19.9\,\text{bit}$), and the PBKDF + plaintext testing uses 0.1 second of CPU time (300000 CPU cycles @3GHz), a competent attacker will use an average of $10^6\times10^{-1}/2=50000\,\text{s}<14\,\text{h}$ of CPU time to find a password, that is less than 2 hours of wall clock time with a single 8-core PC, minutes for a powerful adversary.

Answer 2

No.

AES isn't know to fail in even huge amount of plaintext-ciphertext pairs. Even if you were able to encrypt anything you like and get result back, you wouldn't be able to learn key (in feasible amount of time).

Basically saying, those formulas can be so complex on modern computers that it becomes sufficiently complex that best way is trying every possibility.

Hence a list of possible passwords to rearrange the sequence begin to be narrowed down as the cracking progresses.

Changing one variable changes everything in result. You don't even have enough storage to store even 1% of possibilities of results. Best possibility is still trying every key.

That being said, usually implementations might have some weaknesses. And usually password itself is weakest point (if there is password), not anything else. So if it was encrypted using password, best bet is that hopefully password is weak.

Answer 3

If something is known about the way that the password might have been generated, and the padding method is known - then it may be possible to crack the password without even knowing anything about the plaintext. See How do I detect a failed AES-256 decryption programmatically? for a working example based on AES-256-CBC.

Answer 4

In a simple substitution cipher, like rot13 or ceaser, you would be correct; known plaintext would reveal details about the "key". However AES isn't like that in that its nth byte of cipher text is not solely derived from the nth byte of zip file and a key. How much else is input into a given byte depends on the mode of AES, but suffice to say with accepted modes it's at least all bytes that have gone before, the iv, the key, and adjacent bytes in the block.

put simply: It's probably rare to know enough of the plaintext to break encryption without knowing all of the plaintext, thus mooting the need to break anything. Oh, and to guess you (typically) have to redo the whole encryption, so guessing the remainder is relatively slow, even in the case of a single unknown appended log line on a known log.

Answer 5

The AES standard is theoretically unbreakable in non-trivial time, hence why everyone is using it.

Brute force would be a bad idea, since a 12 digit password with no symbol have 3.9087701e+20 combinations.

Your best bet is a dictionary attack with a good set of rules and a massive massive dictionary. I recommend the RockYou database.