0

Consider a secure modern block cipher like AES/Serpent/Twofish.

I hear everyone say that the complexity is $2^{128}$ for a 128 block cipher. But isn't the weak link the actual hashed and salted password? Any brute force should be targeted at it?

By my rough calculations $2^{128}$ = $84^{20}$, so any proper password composed of all available keyboard characters shorter in length than 20 is a weakness?

The problem seems to only grow with 256 ciphers: $2^{256}$ = $84^{40}$.

So does this mean there is no point using AES256 if you don't plan to have a password 40 characters long or use keyfiles? Could someone please clarify?

Simon Johnson
  • 3,216
  • 16
  • 20
Mark Litovsky
  • 33
  • 3

2 Answers2

3

Most protocols use a randomly generated key (TLS, for example) that spans the full keyspace of the cipher, so 128-bits in the case of AES-128.

For other uses where the cipher key is directly obtained from a plaintext password a propper key derivation procedure should be used. One standard for this is PKBDF2 which, in simple terms, computes the cipher key by repeated application (tens or hundreds of thousands of iterations) of a hash function to slow down the calculation in order to make brute force attacks impractical.

Imagine a key derivation function that consisted of just two applications of a hash function and compare this to deriving a key from a single hash function application. In this case it is twice as computationaly expensive to mount a bruteforce attack on the password, and this corresponds to an extra bit of the password key. In this way it is possible to "trade" time for key bits.

  • Why is PKBDF2 not used in software like Truecrypt? They use whirpool and ripemd instead. They even offer sha512. – Mark Litovsky Oct 26 '13 at 16:30
  • @TruthSerum: I would say to slow down brute-force attacks. Hundreds of thousands of iterations is still only equivalent to using three characters longer password (Assuming the characters are chosen from set of 84 like OP). – user4982 Oct 26 '13 at 16:52
  • 2
    @MarkLitovsky - PBKDF2 is used in Truecrypt. The user-selected hash algorithms you refer to are used as the underlying hash in PBKDF2, and also in Truecrypt's PRNG. It's worth mentioning, however, that Truecrypt only uses 1000 PBKDF2 iterations, which is far too few. – hunter Oct 26 '13 at 17:15
  • @hunter Thanks for the info, now that I went looking I found it in source. Why is 1000 far too few? – Mark Litovsky Oct 26 '13 at 22:30
  • @MarkLitovsky: This paper Stronger Key Derivation via Memory Hard Functions looks scrypt, bcrypt and PBKDF2 password-based key derivation algorithms at the cost of cracking different password lengths. You can see that the cost of breaking password increases very much according to the number of PBKDF function iterations. Although, some PBKDF2 specs allow 1000 as minimum iteration count, that count appears nowadays too small as the intent has been that the iteration count is increased as the time goes on. – user4982 Oct 27 '13 at 10:53
  • @MarkLitovsky - directly from wikipedia: "When the standard was written in 2000, the recommended minimum number of iterations was 1000, but the parameter is intended to be increased over time as CPU speeds increase." I've heard it said that the number of iterations should (roughly) be doubled every year. 100000 or a million iterations these days is common. Of course, nowadays, things like scrypt offer better protection. – hunter Oct 27 '13 at 18:01
1

Indeed, if an AES key is generated out of the password only by a fast and well-known algorithm, it is a problem. It is mitigated as follows:

  • keys are instead generated by a (pseudo) random number generator (RNG);
  • if RNG is not available, a longer passphrase is used, not a short password;
  • an intentionally slow key generation algorithm is used.

The first option is however the best one.

Dmitry Khovratovich
  • 5,647
  • 21
  • 24