0

I'm in a situation where I know that I have to decrypt a file encrypted using AES 256 CBC and I've the following details:

  • I know the first 16 bytes block in plain text
  • I know the IV (static 128 bit IV is being used)
  • I know the encrypted text
  • I don't need to know the exact passphrase, it's enough to recover the 256 bit seed derivated from the passphrase

I think the best way to attack this would be generating rainbow tables. Is this approach feasible? What would you suggest in this situation?

Many thanks!

  • What is the process by which the pass[word|phrase] is being turned into a key? – Xander Mar 12 '15 at 16:46
  • No salted password or anything else - it is already generated as random 32 bytes array using random PRNG, there's no real passphrase – int 2Eh Mar 12 '15 at 16:51
  • Then unfortunately, your task is impossible. If you had all the computing power available in the world, and trillions of years to apply it all directly to this one problem, you would not be able to find the key. – Xander Mar 12 '15 at 16:53
4

Generating rainbow tables is never the best way to attack a single instance. Rainbow tables are precomputed tables: you do a lot of computations in advance, under the hope that you will be able to apply these computations to several attack instances.

Precomputed tables (rainbow or not rainbow, this does not change anything here) all follow the same pattern:

  • During precomputations, you "try" N possible passwords and, for each of them, you apply the relevant cryptographic function (in your case, some sort of hash for password-to-key derivation, then symmetric encryption) and store the result (for a rainbow table the storage costs are lowered, but the CPU cost is unchanged -- in fact, it is somewhat enlarged due to the specifics of the rainbow).

  • At attack time, you look up the observed hash/ciphertext in your table. If the password was indeed one of the N that you processed during the table construction, then the attack works. Otherwise, it does not.

So generating the table costs as much as the worst case of a simple brute force attack: you still pay for hashing all N possible passwords. If you have only one instance to attack, then the direct brute force is cheaper.

In your case, you have some (unspecified) password-to-key derivation scheme h, and what you have to work with is:

    f(p, IV, m) = IV xor AESh(p)(m)

where p is the password, IV is the IV, and m is the first block of the plaintext (the first 16 bytes). If you want to build a precomputed table, then that function f is what you have to evaluate for each password. The resulting table will be applicable only to cases that use the exact same IV and the exact same first block of known plaintext. If either the IV or the known plaintext is different, then not only is the table a poor idea for breaking a single instance, but it also becomes a poor idea in all generality since the table will be usable only once.

A critical point is the h function: the process by which a password is turned into an encryption key. If the h function is a proper password hashing function, the it has a salt, which is generated a new for each password, and this completely defeats precomputed tables, even if the IV and the message are reused exactly.

Even if h is a basic, fast and unsalted hash function (say, a single invocation of SHA-256), then you still cannot reuse existing (rainbow) tables, because you do not have access to the hash output; you only have the ciphertext. The encryption step is sufficient to put your context outside of the contexts for which rainbow tables already exist.

Therefore, if you want to enact your breaking attempts, you will have to implement some brute force mechanism. Roam the Web to gather implementations of AES and of the h function, whatever that hash function is. Put them together in some code that tries potential passwords. Compile, run, be patient.


In any case, such brute force works only insofar as the used password is one of the passwords that you can plausibly try within the limits of your patience. If the AES key is not really derived from a password, but was generated randomly from a cryptographically secure PRNG, then forget it. You won't brute force it.

What you can do depends on the context. For instance, if you have access to a device or system that performs encryption with the key you don't know, but on data that you can choose (a chosen-plaintext attack), then the predictability of the IV (it is always the same, in your description) allows you to perform a brute force on the data (not the key), which, depending on the data, may be very efficient.

  • Thank you very much for your thorough answer! Some comments to add: – int 2Eh Mar 12 '15 at 17:05
  • Thank you very much for your thorough answer! Some comments to add: 1) Yes, the derivation algorithm is absent, it is pure 32 bytes array coming from Yarrow 2) I don't know if this can be of any help, but I know the header of the file, I'd say the first 16 bytes - is it some kind of chosen-plaintext-attack? 3) As said, I know the IV which is static – int 2Eh Mar 12 '15 at 17:10
  • 1
    If you know the plaintext, then it is a known-plaintext attack. For a chosen-plaintext attack, you must be able to choose the plaintext. For once, cryptographers managed to come up with clear terminology. – Tom Leek Mar 12 '15 at 17:12
  • Right, agreed. Sorry for the misunderstanding – int 2Eh Mar 12 '15 at 17:12
  • 1
    @int2Eh Ah, I missed your mentioning Yarrow earlier. So, Yarrow is a CSPRNG, and there are no attacks against AES-256 that match only the conditions you describe. Even the best direct attacks against AES-256 are in fact only theoretical, and cannot be carried out with the computing power available in the physical world. Sorry, if this is all that you have to work with, I think someone is playing a prank on you. – Xander Mar 12 '15 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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