Topic: How long would it take to brute force 256 bit AES passwords (Read 49232 times)

NVM. 

Agreed smartassery wasn't useful or necessary.  Still I take issue with the bolded point.  It seems you are still looking at each element in isolation.  No you can't brute force a 12 digit password with your GPU farm is key stretching is done.  Say bcrypt w/ workload of 12 or pbkdf2 with 100,000 iterations.  Each of these key stretching methods add roughly 16 bits of entropy.  So say you could brute force a single SHA-256 hash of a random 8 digit password in a day.  By using key stretching it would take substantially longer.  Instead of a single SHA-256 hash per password it is now 100,000 hashes per password so the 50% time is now measured in decades not days.  

The key point is that using all 5 elements (a,b,c,d AND e) together can make brute forcing a password computationally infeasible.  Only doing part of it is insecure.   Sure a longer password is better but a 12 digit password on a list of previously cracked/leaked passwords is far less secure than an 8 digit one which needs to be exhaustively brute forced.

TL/DR version:
You can't exhaustively brute force* a properly salted 8 digit password which has been hashed using bcrypt(12) or pbkdf2(100000).  

* brute force being an exhaustive search of all possible combinations.  This would exclude dictionary based attacks as the password is not found on any list of weak/compromised/cracked passwords.

I did— but no need to be a smartass about it— especially since you're drawing the wrong conclusion.

The existence of this rainbow table _proves_ the feasibility of brute-forcing that entire space for a single salt. I _happened_ to have a rainbow table, but for the point I was making I might have well said that I brute-forced a single password of that size on my GPU farm.

So sure, the salt means the attacker couldn't lower their costs through precomputation, but if you have high value data (e.g. a bitcoin private key they _know_ has a lot of funds assigned to it) then they really could search such a large space unless you had a quite costly KDF.

And I agree in combination your advice is good, I'd just prefer that you hadn't repeated the 8 characters == good myth, which is terrible advice in isolation as it's normally applied.

Did you miss the bolded part?  Or did I misunderstand you and you have a rainbow table of all  9,967,884,244,759,920,000,000,000,000,000,000,000,000,000 combinations of a 12 digit passphrase and 64bit salt values?  I guess "desk" is the name of the planet which you converted into a supercomputer. Sweet.  I will start using 128 bit salt values (only those larger than 2^64-1) and make that precomputation worthless.  Now if you have a solar system sized computer and started precomputing MD5 hashes millions of years before it was invented well then you might have me there.

The components of security fit together to support the other elements. Looking at only one element is dubious.   While you may have a rainbow rable of MD5 hashes you don't have quadrillions upon quadrillions of rainbow tables one for each of the those password sets and a unique 64bit salt.

You're saying a number of good things mixed with absolutely terrible things. I have exhaustive 12 character (alphanumspace) md5 rainbow tables sitting on a disk here.

With a fast KDF you need a fair bit more to be sufficiently strong.  And you certainly can't count on a user constructed string being sufficiently random really at any length.  People can't reason about entropy, and they can't reason about attackers that can do a billion attempts per second per gpu and have powerful statistical models.

Well now I can brute force it pretty easily ;-)

Just as a point of reference ... last I checked (a couple months ago) the total number of hashes performed by the Bitcoin network since 2009 is only about 2^68.  Think about thousands of GPU mining rigs doing billions of hashes per sec for a few years... that's enough "guesses" to break 68-bit key 50% of the time...

Therefore, 64-bits is crackable in a year only with extraordinary resources (barring weaknesses being discovered in AES).  Anything beyond that -- 96 bits, 128 bits, etc -- is arguably going to be safe for decades, even with extraordinary advances in computing speed.  

Unfortunately, most user-created passwords contain far less than 64 bits.  Though, you can offset it quite a bit with key-stretching -- if you slow down guessing speed by a factor of 65,000, that's kind of like adding 16 bits of entropy to the passphrase.  

256 bits of entropy is not possible on any budget, but OP was asking about 64 bits.

With an unlimited ($700T) budget it could be cracked in less than a day with a very large number of GPUs or ASICs.  The lead time on hardware would be the longest part.


With a much smaller budget ($50M) you could have 10,000 ASICs at 50M/s and crack it in about a year.

256-219 = 37, and 2³⁷ is 137,438,953,472, so a mere 137 billion supernovas.  But a supernova leaves a lot of matter behind, presumably a direct conversion of matter to computation would reduce the number of stars needed somewhat.  On the other hand, hashing or decrypting takes more computation than merely counting.  At any rate, it won't be happening while any of us are alive, so it seems silly to quibble about how many millions, billions or trillions of stars we would need to destroy to crack a password.

This is why Armory uses RAM-heavy key stretching for its wallet encryption.  When you create a new Armory wallet, it will test the speed of the system it is running on, and will usually require at least 2MB of RAM, and however many hashes it can do in 0.25s.   This is essentially scrypt -- each thread an attacker uses to guess a decryption passphrase will require 2 MB of dedicated RAM, and will have have a non-trivial amount of hashing to do.  The RAM requirement makes it infeasible to execute on a GPU -- you might get a modest speed up, but not orders of magnitude (because all threads would have to use super-slow global memory instead of super-fast local/shared mem).  If your system is fast enough, it could require 32 MB -- then the attacker would be better off with an 8-core CPU than a GPU.

To answer your question about brute-forcing:  if someone creates a truly random 256-bit encryption key -- it's not possible.  Bruce Schneier showed (via thermodynamics) that if you had perfect computational efficiency, you'd need the power of something like 40 trillion suns in order to crack one perfect 256-bit key (actually that sounds like of low, to me... maybe he was talking about hash collisions...?  I don't know, look it up).  That doesn't take into account how many gazillion years it would take to consume and apply that energy.

The weakness is the password, so as others keep harping -- a strong password, on an encryption scheme that has solid key stretching is the way to go.  For instance, someone contacted me recently to ask if there was a way to recover their Armory password.  It turns out, a completely random 5-char password would take over 100 years for him to crack on his own system (for default settings of the Armory wallet)... considerably more if the password was longer.  But when he told me how simple his password was, I was able to write a script to help him find it in 12 hours...

Suppose my budget is 700 trillion dollar.

How long would it take to brute force this AES encrypted password: f0e4c2f76c58916ec258f246851bea091d24d4247a2fc3e18694a61b1816e13b ?

The user's question was about AES but key strengthening can be used to make your brute force example infeasible.

Lets use the example of 1 hour on a high end rig to brute force all 8 digit passwords using a SINGLE SHA-256 hash.
Using a Key derivative function one could make the stored hash (or key for AES) not the output of a SINGLE SHA-256 but the output of 50,000 SHA-256 hashes.  At that point (if we use your 1 hour example) the cost is now 50,000 hours or say 6 month using 10 high end rigs (40+ GPUs).

The TL/DR I added sums it up better

A typical mining rig can brute force 30 billion passwords a second, cracking all eight-character passwords in just a few hours: http://blog.zorinaq.com/?e=43. Note, if you have stolen a list of 1000 hashed passwords and you just need to crack one, this reduces the problem from 4 hours to minutes, even if all passwords are full-strength random eight character length. Salting doesn't increase the difficulty if the salt is known.

The problem isn't with the algorithm or it's key space, it's the size of the typical password someone creates. Upper and lower characters plus number is 62 possible characters. Add in some typical type-able characters (such as .?!@#$%..) and you've got somewhere around 80 possible characters to check in each position. However, smart crackers do not just "brute force", they look for memorizable passwords people would actually, such as "ugly#duckling333", "Strong.1234", by combining dictionary phrases, along with using massive lists of leaked real passwords (these dictionaries of words and passwords can be millions long, and can already be pre-hashed into rainbow tables).

The SHA256 algorithm hashes 64 byte blocks (with some padding included), and outputs 32 byte hashes. Anything less than 40+ character passwords using all type-able characters is not utilizing the full strength of SHA256.  If you are using a password keeper creating huge-ass passwords it is not unreasonable to use passwords like this to prevent cracking:

`#l}
F2oCA:lsLZ"P+fU3Js6l@]ie9
'"5E!'MuZD&Y0PO:Oy}1u}QCZ1UI

The issue with AES-256 isn't in brute forcing strong passwords.  If you password is strong (not on any dictionary, longer than 8 char, mixed symbols, uses a large random salt) it can't be bruted forced at any reasonable cost.  If it is 12+ char includes all 4 symbol classes or simply is a random string it can't be brute forced at any cost.

The issue with AES-256 is it is a very faster cipher.  For weak (or marginal) passwords it can be bruted forced.  How complex of a password is vulnerable depends on the resources available to the attacker and how long they are willing to to wait.  

So if we consider a weak password to be one that (at least in theory) could be compromised by a dictionary, modified dictionary, or brute force attack using a computing on the magnitude available:
1) anything found in a standard dictionary or leaked/common password list (various lists usually in the tens of millions of pwd range).
2) anything with less than 8 characters.
3) anything all lower case with less than 10 characters.
4) anything not encrypted using 64bit or larger salt.
5) anything which has less than 3 substitutions from something listed above (p@ssword! vs password)

The reality is end users likely don't know if their password is strong or not. So developers should prevent users from hurting themselves.  As a developer you can implement a large salt and could require a minimum of 8 characters (don't impose special char requirements).  At that point brute force and precomputation are off the table; so the largest risk comes from dictionary or modified dictionary attacks.  There are lists of millions of previously compromised passwords.  If the password used is on one of those lists it can be found in a matter of minutes.  If you are paranoid about your user's security you could check their password against a list of known compromised passwords.  An alternative would be for someone to develop a webservice which took a hash (HMAC) or all known/weak/compromised passwords.  Users could send a HMAC hash of their potential password and get a "known" or "good" response.  

One further step you could take is key stretching using a key derivative function. The bitcoin wallet does this.  Rather than simply use the passphrase it takes multiple iterative hashes of the password (generally thousands of tens of thousands).   So instead of key = passphrase it is key = SHA256(SHA256(SHA256(passphrase))). This increases the length of time necessary to try one key and thus reduces the throughput of the attacker.   Understand that if user's password is very weak (under 6 char or on a dictionary list) this is unlikely to help because even 2000x a 1 sec search is unlikely to stop an attacker.  

The key stretching function (hash) used by the wallet is SHA-256 which is well optimized due to this thing called mining.  Security could be enhanced by replacing the key strengthening function with another one (say bcrypt of even PBKDF2 using SHA-512 or RIPEMD).

http://en.wikipedia.org/wiki/Key_derivation_function
http://en.wikipedia.org/wiki/Key_stretching
http://en.wikipedia.org/wiki/PBKDF2
http://en.wikipedia.org/wiki/Bcrypt

TL/DR:
It depends. Using a combination of:
a) require at least 8 digits (makes brute force prohibitively expensive)
b) use a large (64bit+) random salt (prevents precomputation attacks)
c) check password against known/compromised password list that hackers are likely to be using (prevent quick dictionary based attacks)
d) use key strengthening (reduces the attackers throughput by a couple orders of magnitude).
e) use an algorithm other than SHA-256 in the KDF to prevent "re-use" or mining research

question makes no sense, because there is no direct proportion between entropy and brute force strength.

this:
-------------------------------------------------------------------------beeb--------------------------------------------

has 25bits. gl brute forcing it.

Depends - what's your budget?

How long would it take to brute force a 256 bit AES password with a password entropy of 64bits and above?