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