7

The question says everything, knowing that a pdf is protected using standard Adobe password encryption that comes with Acrobat Pro (which as far as i know is AES 128) how much would it take to bruteforce a key which is known to be 20 characters long and that the charset is A-Z, 0-9? Please assume for calculation a modern GPU rig, or a GPU cluster from for axample Amazon AWS.

  • 2
    How will you choose your 20 characters, each character at random or is the 20 character string perhaps a pass phrase? – Dick99999 Jun 19 '14 at 6:12
  • 1 second for a computer that can do 36^20 tries per second, but longer than Earth's age for an hypothetic 1 exa-AES128-OPs computer grid. – Xenos Jun 19 '18 at 15:09
18

A-Z and 0-9 means 36 possible characters. 20 such characters imply 3620 possible keys. That's approximately equal to 2103.4.

The biggest brute force effort currently known publicly was for a 64-bit key (for RC5, but the difference between RC5 and AES is not important here); it is described here. It took almost five years and a lot of contributors; the peak cracking rate was equivalent to what 30000 top computers of that time could do. Of course, this was a decade ago, and computers have become faster, but not to the point of closing the gap from 264 to 2103.4: we are talking about a problem which is 725 billion times harder.

GPU would not be a very efficient platform for AES-breaking; the most cost-effective system would be CPU with AES-NI opcodes. Note, though, that an AES key is a sequence of 128, 192 or 256 bits; not a sequence of characters. Therefore, your characters are probably transformed through some kind of hashing into an AES key, and the hash function computation will probably be more expensive than the AES invocation itself. Depending on the used hash function, GPU may become competitive again. In any case, we are talking about, at best, a few billions of keys per second and per GPU. One billion of such GPU would produce a lot of heat... and would still need billions of seconds to get through (one billion of seconds is 30 years).

So the only realistic answer to your question is: forever. An key of the format you describe (20 characters in an alphabet of size 36) will not be cracked through brute force. Brute forcing such a key would not make sense: even if it was technologically feasible (which assumes more resources than is available to the biggest governments or corporations currently existing), it would cost a lot more than whatever the key is protecting. For instance, if I owned the millions of billions of dollars involved in the process, then I would simply buy the USA wholesale (top corporations, government,... including a complete national debt buyout)(that is, if it took my fancy to actually own the USA, which is, when you get down to it, a weird idea).

(In all of the above I am using the American "billion", i.e. one thousand millions, not one million millions.)

  • So you are saying that even in 10, 20 or even 30 years it won't be feasable without a HUUuuugeee amount of money? – David 天宇 Wong Nov 23 '15 at 9:55
  • "known publicly" Liked how you phrased that! – Tim Jul 17 '16 at 16:10
2

Well lets take an average processor speed, not too fancy, cracking approximately at 22,004k/s a PDF document. Assuming you are only bruting a-z0-9A-Z with out spaces, special characters, etc.

It would take approximately 1 septillion years. or 1.0306281275164522e+24 years 33 days 7 hours 30 minutes and 54 seconds

The amount of password combinations you would potentially have to test is (7.159713505559651e+35 password combinations)

Again I am assuming we are NOT using any GPU, Amazons AWS, etc. We are using an average processor. If you use GPU or AWS, this would SIGNIFICANTLY speed up your cracking. You can play with the numbers at this. site.

I hope this answered your question.

  • 1
    thanks and great link !! haha I put 999 characters ualphanumericsymbol and it told me "FOREVER MAN.. IT WOULD TAKE INFINITY YEARS" HAHAHA – securityaddict Oct 28 '14 at 4:14
  • 1
    "...approximately 1e24 years .... and 54 seconds" ?! – TripeHound Aug 26 '16 at 8:45
0

Regarding how long it would take, if we use a tool like crunch to generate the wordlist to use for cracking said PDF file, the output would be this:

[root@yokai ~]# crunch 20 20 ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
Crunch will now generate the following amount of data: 11388113619364347904 bytes
10860551471104 MB
10606007296 GB
10357429 TB
10114 PB
Crunch will now generate the following number of lines: 2299123893656354816

With this we can see just how much data would have to be processed in such a brute force attack. Safe to say that without knowing more about the password used, and without making any specific generation modifiers to narrow down the possible passwords, it will never be crack in this lifetime by pure brute force. Maybe not even in the next 10-20 lifetimes.

There is however, a random chance approach where the very first password could be the correct password. Say like if you used linux for the attack, you could script a tool to attack with randomly generated full passwords.

#!/bin/bash

PASS_GEN="$(tr -dc 'A-Z0-9' </dev/urandom | head -c 20)"

echo "$PASS_GEN

while [ "$something" != "$something_else" ]
do
      try_password
done

Of course only the "tr" command is the real functioning command in this bash code but you get the idea. It is possible, however improbable, to generate the correct password very quickly.

0

AES128 uses exactly 128bit key length, 20 chars is a password not a key, the key is created from the password, as is the initialization vector(a bit like a key extension in some ways, for use in CBC mode AES) There are many methods to generate the key and IV from the Password and the better ones also toss in some salt, however the key generation is not part of AES.

The answer is a mean time of 2127 and maximum 2128 attempts.

Assuming CBC mode (a very popular and secure mode) the attempts per second will vary wildly with the length of the document as you must decrypt the whole file and check to see if it is gibberish, separately for every key. All 128bit sequences are valid AES keys and will "decrypt" the document, however all but one will produce bad decrypted data.

The encryption block is 16 bytes. Assume the PDF is only 16 bytes, and the GPU is decrypting at 32GiB/s [ 235 B/s ]. (I saw a similar number somewhere for gpu AES performance) That is 231 decryptions per second (assume the CPU can also parse for gibberish output that fast) So a mean of 2127/231 = 296 seconds, and max 297 seconds, which is 2.5e21 years mean, 5e21 max. 21 zeros is a whole lot of zeros. Divide the load among one million devices and it is 2.5e15 years or 25 million millions. And then you have AES-256.

Then again you may also get lucky and find it is the first key you try. Powerball lottery odds are one in 300 million. The odds of hitting the correct key in the first 1.7e13 years is 1 in 300 million [with a single machine], with a million machines that time drops to 1.6e7 or 16 million years

  • 1
    Why would you have to decrypt the whole file? Why not just decrypt the first block or two and look for the magic header or whatever is being used? PDFs have a magic header. – forest Jun 19 '18 at 9:40
  • Ah yeah that helps somewhat in the specific case of the original question, however the header code is 4bytes/32bits and a block 128bits so there will still be[128-32=96] 2^96 false positives that need full decryption. It also doesn't change my specific calculations as I based them on a file that is only one AES block in size. – Max Power Jun 19 '18 at 10:13
  • The IV should not be created from the password, it should be random. Also, as Tom's answer covers, what matters is the entropy in the password, which is only about 103 bits. – AndrolGenhald Jun 20 '18 at 20:04
0

The only attack that doesn't take millions of years requires a lot of money.

  • Custom build a 32 nm AES cracker
  • Build 50 chip plants to make these chips
  • Spend a year making chips
  • Build a giant cluster of systems
  • Run the cluster for 1 year

Note that the R&D cost on the chip will be anywhere from $50-$250 million, the plants will be $1-2 Billion each and the operating costs will be in the Billions. Also note, we are using 32 nm because a <20 nm solution would multiply the costs by 5 times easy. Realistically, getting all the parts and people for 50 plants would put a great strain on GLOBAL chip making.

  • The PDF contents better be worth it then! – user81147 Jun 19 '18 at 10:23

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.