Why you can't recover your KeePass password

It was a pretty vexing problem I faced; not only had I forgotten my password for the KeePass password manager, but the developer of this tool had made a concerted effort to drastically slow down my efforts when repeatedly guessing what my password could have been via a technique called brute-forcing.

What peeked my curiosity though, is why it wasn’t feasible to recover the password via brute-forcing? Or by a dictionary attack for that matter. The following shows how KeePass intentionally slows down the process that is required to run in order to decrypt the stored credentials, and thus determine if the password is correct.

You can explore these steps further with a small tool I wrote.

1. Reading the Database’s Header

Before asking the user for their password, KeePass first reads all the relevant data from the database’s unencrypted header. This data is then used during the following steps to authenticate the key and decrypt the database’s body.

Signature 1                 Signature 2         File Version
0x00000000                  0x00000000          0x00000000

Fields
Type ID                      Data Size           Data
0x04 = Master Seed           0x00000000          0x00...
0x05 = Transform Seed        0x00000000          0x00...
0x06 = Transform Rounds      0x0000000000000000  0x00...
0x07 = Encryption IV         0x0000              0x00...
0x09 = Expected Start Bytes  0x00000000          0x00...
0x00 = End of Header 		

Using the KeePasswd tool you can view the header of a KeePass database by calling the following:

$ keepasswd -file "C:\ExampleDatabase.kdbx" -header

Master Seed: 681576DF73AC6AE38A21494AF04723E1968168EE08CC4D1893F72D3F309E42BF
Encryption IV: 5B61F08E5BDD401F72C0C43DA15E2700
Transform Rounds: 6000
Transform Seed: C723515A30197B562906A32BBC371FC8C9433DA589A499FF59587A62EC8F3055
Expected Start-Bytes: A45D4E050BF15F3F66B357E1BDC86343C75D6A72CE976665C6E341D2EE015ADC

2. Create the Composite Key

The process starts by creating a master key from all of the keys provided by the user (generally a password, key-file and/or Windows User Account). This is achieved by appending the bytes of the SHA256 hash for each of the keys into a single composite, which is then hashed with with SHA256.

byte[][] keys = {
    Encoding.UTF8.GetBytes("Example"),
    ...
};

byte[] compositeKey;
using(var stream = new MemoryStream())
{
    foreach(byte[] key in keys)
    {
        byte[] hashedKey = (new SHA256Managed()).ComputeHash(key);
        stream.Write(hashedKey, 0, hashedKey.Length);
    }

    compositeKey = (new SHA256Managed()).ComputeHash(stream.ToArray());
}

The resulting composite key is then passed to the next process.

3. Transformation of the Key

The key transformation stage is rather clever in that it transforms the key many times to slow down the whole authentication process; thus reducing the feasibility of guessing the password via dictionary or brute-force attacks.

This process works by using the AES algorithm, with the Transform Seed (taken from the header), to transform each 16 bit half of the 32 bit key by the amount of times specified in the Transform Rounds header field.</p>

var rijndael = new RijndaelManaged
{
    Key = Header.TransformSeed,
    ...
};

ICryptoTransform crypto = rijndael.CreateEncryptor();
for (ulong i = 0; i < Header.TransformRounds; ++i)
{
   crypto.TransformBlock(compositeKey, 0, 16, compositeKey, 0);
   crypto.TransformBlock(compositeKey, 16, 16, compositeKey, 16);
}

transformedKey = (new SHA256Managed()).ComputeHash(compositeKey);

As with the last step, the result of this transform is hashed using SHA256, which is then passed to the next part of the process.

4. Seed the Key

The resulting transformed key is now joined to the Master Seed (taken from the header) and then hashed with SHA256 once again to produce the seeded master key that is ready to be used for decrypting the database’s body.</p>

byte[] masterKey;
using(var stream = new MemoryStream())
{
   stream.Write(Header.MasterSeed, 0, Header.MasterSeed.Length);
   stream.Write(transformedKey, 0, transformedKey.Length);

   masterKey = (new SHA256Managed()).ComputeHash(stream.ToArray());
}

5. Compare Decrypted Stream with Expected Bytes

The last part of the process is to decrypt part of the encrypted stream (situated after the KeePass file’s header) and then compare the first few bytes with the ExpectedStartBytes header field.

If the decrypted bytes match the bytes stored in the header field then the password is correct and the rest of the stream, containing the user’s data, can be decrypted.

var rijndael = new RijndaelManaged
{
    Key = masterKey,
    IV = Header.EncryptionIV,
    ...
};

ICryptoTransform decryptor = r.CreateDecryptor();

int startBytesLength = Header.ExpectedStartBytes.Length;
byte[] decryptedBytes = new byte[startBytesLength];

var cryptoStream = new CryptoStream(databaseFileBodyStream, decryptor, CryptoStreamMode.Read);
cryptoStream.Read(decryptedBytes, 0, decryptedBytes.Length);

bool isPasswordCorrect = areBytesEqual(decryptedBytes, Header.ExpectedStartBytes);
Console.WriteLine("Password is " + (isPasswordCorrect ? "Correct" : "Wrong"));

Finally

The whole process at the time of creating the database is configured to take approximately 1 second on the host’s machine, which adds up to a considerable amount of time when you’re trying to guess thousands of passwords.

To see the whole process in action with the KeePasswd tool you can call the following:

$ keepasswd -file "C:\\ExampleDatabase.kdbx" -passwords test1,test2,test3

The password is 'test2'