Are there public slow-but-strong algorithms out there that resist brute-force attacks better?

Question

I'm reading that AES uses 4x4 bytes (4*4*8 = 256 bits key) matrix for performances matters (since it's a requirement for common standard encryption algorithms), but are there implementations with choosable key size for this particular algorithm, so I can make brute-force attacks harder with a good password ?

Also, if I'm worried that I can't make user use good passwords (it's a shame, but lets imagine that), can I make an algorithm deliberately slow to make brute-force attacks infeasible with weak passwords, but really secure ?

Could we one day make users switch to key files instead of passwords to completely forget about brute-force, even with the potentially theft of those keys ?

Answer 1

Bruteforcing the AES algorithm itself (i.e. trying all possible keys to encrypt or decrypt some blocks to see if they give the right result in a known-plaintext attack or similar) is not really a problem, even in the 128-bit key version.

(This takes on average 2¹²⁷ tries. If you can try 2³⁰=10⁹ AES-keys per second, it will still take around 5·10²¹ years, much longer than the universe existed, and any life will exist. Parallelizing this makes it faster, but there is some limit, too ... if you can calculate on 10⁹ processors in parallel, it still needs 5·10¹³ years ... about three times the estimated age of the universe until now.)

So, the attackable point is not bruteforcing the AES key, but bruteforcing the derivation of a key from a password. And here is where we have to enforce our design. You should not use the password directly (maybe with padding) as an AES key. Instead, use a slow password derivation function, and incorporate some salt.

NIST proposes the PBKDF2 construction based on iterated calling of some fast hash function. Setting the iteration number high enough will make it slow enough. PBKDF2 is easily parallelizable on GPUs, which makes brute-forcing slightly faster than we would wish, though.

Other alternatives might be bcrypt, or the newer scrypt.
These are firstly slow hash functions for secure password storage, but I think one can also reuse their output as a key for AES or any other symmetric cipher of the right key size. (You just have to think of a protocol to transfer the salt.)

Answer 2

The way to solve this problem is to use a well-chosen function for deriving the key from the password. You should use PBKDF2, bcrypt, or scrypt to derive the key from the password, and set the number of iterations to make them very slow (e.g., to make them take 100-200 milliseconds on your machine). Once you've done that, you don't need to make any changes to AES. This is an elegant way to solve the problem: you decouple the problem of making password search hard, from the problem of building a secure encryption algorithm.