6

The KeePass security help page talks about preventing dictionary attacks

To generate the final 256-bit key that is used for the block cipher, KeePass first hashes the user's password using SHA-256, encrypts the result N times using the Advanced Encryption Standard (AES) algorithm (called key transformation rounds from on now), and then hashes it again using SHA-256. For AES, a random 256-bit key is used, which is stored in the database file. As the AES transformations aren't pre-computable (key is random), an attacker has to perform all the encryptions, too, otherwise he cannot try and see if the current key is correct.

The "security against dictionary attacks" apparently lies in the time needed for the N encryption rounds. Now the question:

Is the time needed to compute N iterations of AES really N times the time needed for a single AES encryption, or is there a known, more efficient scheme to compute AES^N(cleartext)?

Adi
  • 43,953
  • 16
  • 137
  • 168
kutschkem
  • 666
  • 5
  • 12
  • A related question was asked here: [Keepass Dictionary Attack Protection Strategy](https://security.stackexchange.com/questions/56220/keepass-dictionary-attack-protection-strategy) – Simon East Sep 08 '17 at 05:49

3 Answers3

8

Performing AES multiple times is not useful. Breaking AES would take infinity if you use a proper key. What KeePass is doing here is making the key derivation from password slower so that a bruteforce attack would take a very long time because for each password the key needs to be re-computed (it's what PBKDF2, Scrypt and Bcrypt try to tackle).

While this may slow down dictionary attacks it won't prevent them. Preventing dictionary attacks can only be done by using long enough, random passwords.

enter image description here

As far as I know (I might be wrong since I'm not a cryptographer), there should not be a faster way to compute AES^N more efficiently than N iterations of AES. The primary reason they are using this algorithm is because it's just really hard (impossible) to make computations more efficient and thus makes it less susceptible to brute-force.

I hope Thomas Pornin will be able to give you more insight on this one.

Lucas Kauffman
  • 54,229
  • 17
  • 113
  • 196
  • On a side note, it will be interesting to see whether we start seeing 'correct horse battery staple' appear in leaked password lists! – Owen Dec 05 '13 at 14:25
  • Well if doing a dictionary attack takes at least as long as brute-forcing the final 256-bit key (or lets say some secure key length), then i would, in my naievity, call it prevented. – kutschkem Dec 05 '13 at 15:47
  • That won't happen...ever. Otherwise it would take several weeks to months to just generate the key *once* from the word. – Lucas Kauffman Dec 05 '13 at 15:53
  • Great post, although I found some of the wording a little confusing. I've suggested some edits which I hope increase the clarity somewhat. Feel free to correct it further if needed. – Simon East Sep 08 '17 at 05:49
6

No. However, your question isn't related to the text you quoted. The actual data (the password database) isn't really encrypted multiple times.

In order to encrypt something with AES-256, you need a 256-bit key. The password MyPass!sAwesome is pathetic for that purpose. The good news is that there's something called KDF (Key Derivation Function) which takes the password and turns it into a the gigantic key needed for the encryption. The slower the KDF is, the more difficult it is for an attacker to compute the final key by trying a large number of passwords. One standard and widely used KDF is PBKDF2.

(Please read How to securely hash passwords? so that the following analogy make more sense)

A KDF usually takes works with a cryptographic hash function, salt, and an iteration count. KeePass chose to write their own own KDF logic and they're making it slower by using 6000 rounds of AES. What they did is simply use AES as their cryptographic hash function, the random 256-bit key as the salt, and the N as the iteration count.

What KeePass documentation meant by "dictionary attack prevention" is really protection against rainbow tables which is done by using secure salts (a random 256-bit key used a salt is pretty secure).

Community
  • 1
Adi
  • 43,953
  • 16
  • 137
  • 168
2

If I understand your question correctly, you're asking if multiple AES encryption operations have a "known optimization". The answer is "no". If there was, it would have to work on the internal rounds of AES, and the defenses created by those multiple rounds would be thwarted quickly. However, just as we know that reducing the number of rounds leads to weaknesses, we also know that increasing the rounds makes it secure (today). The same logic applies in the larger scope of multiple encryptions.

Put another way, if such an optimization existed, it would be a weakness in the underlying cipher. It would imply I could learn more about the internal state simply by asking the algorithm to encrypt the data a second time.

This would not be so certain if KeePass fed the same data into every encryption iteration, but it's not -- the only thing fed into round n+1 is the output of round n.

John Deters
  • 33,897
  • 3
  • 58
  • 112