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