Make implementation of Challenge-Response more compatible to Keepass 2

[PhilippC]

As the author of Keepass2Android I was looking into implementing the Challenge-Response functionality as in KeepassXC. While I like the idea of using the Master seed as "challenge", I am not so happy with the implementation of Challenge-Response. To explain why, here is a short overview of the key generation in Keepass 2 (by Dominik Reichl) which is used by Keepass2Android as well:

Keepass2:

pbPassword = CryptoUtil.HashSha256(StrUtil.Utf8.GetBytes(strPassword))
pbKeyFile = LoadKeyFile(...)
pbCustomKey = challengeResponse //for example when using KeeChallenge Plugin in keepass 2
//CompositeKey concatenates the data of ALL IUserKey objects
pbAllData = pbPassword + pbKeyfile + pbCustomKey
pbRaw32 = CryptoUtil.HashSha256(pbAllData)
pUserKey32 = kdf.Transform(pbRaw32)
pbCmp = MasterSeed + pUserKey32
pbHmacKey64 = h.ComputeHash(pbCmp);

KeepassXC, with the naming conventions from Keepass 2

pbPassword = CryptoUtil.HashSha256(StrUtil.Utf8.GetBytes(strPassword))
pbKeyFile = LoadKeyFile(...)
//CompositeKey only concatenates password + keyfile but not challengeResponse
pbAllData = pbPassword + pbKeyFile
pUserKey32 = kdf.Transform(pbRaw32)
pbRaw32 = CryptoUtil.HashSha256(pbAllData)
//challengeResponse is added later, where no plugin can modify the computation in Keepass2
pbCmp = MasterSeed + challengeResponse + pUserKey32
pbHmacKey64 = h.ComputeHash(pbCmp);

In Keepass 2, it is very common for Plugins to add elements to the Composite Key. These elements are objects of KcpCustomKey or custom classes implementing the IUserKey interface. The data of all these elements are concatenated and transformed. When I added support for KeeOtp or KeeChallenge in Keepass2Android, I did exactly this, which was very simple.

In KeepassXC, the challengeRespose is not concatenated with password and (potentially) key file. Instead, it is prepended to the hashed and transformed key. This cannot be implemented for Keepass2 by a plugin, so the current KeepassXC implementation will not be usable for Keepass 2 users, and nobody can change this by developing a plugin. It also requires some pretty intrusive code changes if I want to implement this in Keepass2Android which I believe are not necessary if KeepassXC would offer (at least as an option or better as the default) to concat the challengeResponse to the pbAllData.

If I didn't miss any important reason to integrate the challengeResponse at this point in the processing, I suggest you make the key computation more compatible to other Keepass implementations. Please let me know what you think so I can plan further development on the feature for keepass2android.

[droidmonkey]

Yikes, this is not good. Fixing this will also require backwards compat for users who are currently using KeePassXC with Yubikey with an option to "fix" their encryption for portability.

[droidmonkey]

For the record, the offending code is located here down to line 125.

The main issue is challenge response keys are treated separately from normal keys in the CompositeKey::rawKey() function which is called right before the key transformation occurs. We should also be performing the challenge-response and adding that data to the rawKey() return value for use in KeePass2Reader.

The best way to clean this up is to "initialize" the composite key first by issuing a challenge-response with the master seed, then using that stored result to compute the rawKey later. This has the added benefit of not having to re-issue a challenge response every time you save the database.

We need to maintain the old way the final key is computed to allow existing users to open their databases. This should be tried first, if it succeeds we issue a stern warning to the user with a "YES"|"NO" choice to convert their composite key to the new format. If it fails, we use the KeePass2 method as described above.

Alternatively, we can leave this broken in the current KeePassReader2 and fix this when we implement KDBX4 format. @PhilippC do you support kdbx4?

[phoerious]

We do need to re-issue a challenge every time we save the database, no matter how we calculate the final key. Otherwise we lose any benefit we have from our implementation over the KeeChallenge implementation. The master seed changes every time, so does the challenge response.

I also don't like trying the old way first. There is really no way of knowing how the key was computed and trying several methods multiplies the time it takes to decrypt a database. My database takes about a second on my fastest computer, and on my slowest (my phone) about 5-10. Trying a different method first, would make it two seconds (and 10-20) for absolutely no security gain.

I'd rather suggest going the way VeraCrypt did. They have a checkbox "TrueCrypt mode" which allows me to open legacy TrueCrypt containers. We only need to do a better job at letting users know they have to check this box and not forget it every time or come here and complain their databases won't open anymore.

[phoerious]

Thinking about it, we could do it like that:

1. We add a tiny checkbox somewhere for activating legacy mode. When the user tries to open a database with their YubiKey, we show a dialog asking them if they want to enable legacy mode with an additional checkbox "don't bother me again". If the user chooses "yes", we check the box for them.

2. When saving a legacy database, we show another message, asking the user if they want to convert the database and informing them that the old format will be removed in the future.

3. A few versions down the road we remove support for the legacy format and add an FAQ entry telling users to temporarily use an older version for conversion if they habe a legacy database.

[TheZ3ro]

I think that's the best thing to do, but I will also consider fixing this for the KDBX4 format so every new (converted) database will use the new mode and not the legacy one

[phoerious]

KDBX4 is a completely new format, so there is no reason to implement legacy support for KDBX4 databases (although it would probably not even be much extra code).

[droidmonkey]

its a natural and easy way to fix this issue to only support the keepass2 method of key transform in kdbx4.

[phoerious]

Could you check out 2b6f6f5 please and give feedback if everything's alright with that implementation?

[phoerious]

Update: I re-implemented my fix to make it more compact and fix a few KDB(1) test issues. KeePassXC now uses the transform seed as a challenge instead of the master seed for KDBX4: eb62e7d

[PhilippC]

glad to see the update on this! I don't have a Yubikey at hand for testing, but from the code it looks like I can make this work with Keepass2Android.

Just one thing: You are testing for KDF == AES to decide how to calculate the master key. Is this actually the best way? You can have AES and still use kdbx4 (e.g. when using custom plugin data).

[phoerious]

This is how we determine which format to write. If the user chose AES-KDF, then we write as KDBX4, otherwise KDBX3. I wonder if that could break things if someone opened such a DB in KeePassXC and saved it. It would at least have the effect that the DB will be saved as KDBX3, possibly losing KDBX4-only features. But then, how do you actually determine which format to save in if not the KDF? Let the user choose explicitly? How does KeePass handle this? I don't see an option there either. The only selection I can make is between the two KDFs.

[droidmonkey]

AES KDF is perfectly valid in kdbx4. We may have to add an interlock to make sure we are never going backwards (ie kdbx4 -> kdbx3). The checks.for Argon2 KDF and a couple others only apply to kdbx3 to kdbx4 up conversion.

[phoerious]

That's not entirely true. If you select AES, then a KDBX3 is saved. And the user should have a way to go back in case they need the old format for compatibility and what not.
Also checking for AES in the transform method was the sleekest way to implement this, because the KDF is the only information available to that method. The CompositeKey class doesn't even hold a pointer to the database, so even if we save information about the format version there (which would make sense), the transform method wouldn't have access to that. We could pass the version as a parameter, but then every caller would need to have that available. In theory, this should be easy, but until we refactor the database saving and loading logic to be an atomic, self-contained class, it's not that trivial.

[phoerious]

I solved the problem. AES-KDF is now supported for KDBX4 and saving a KDBX4 database with AES-KDF doesn't convert it back to KDBX3 anymore. Please check out my latest commit on the KDBX4 branch.

[PhilippC]

I wanted to implement Challenge-Response in Keepass2Android finally, but unfortunately I am getting an invalid key. So I wanted to do a custom build of KeepassXC to add some debugging output for comparison of intermediate results. Unfortunately I am getting the same error as reported in
#1185 (comment):

CMake Error at C:/msys64_3/mingw64/share/cmake-3.10/Modules/FindPackageHandleStandardArgs.cmake:137 (message):
  Could NOT find LibGPGError (missing: GPGERROR_LIBRARIES)
Call Stack (most recent call first):
  C:/msys64_3/mingw64/share/cmake-3.10/Modules/FindPackageHandleStandardArgs.cmake:378 (_FPHSA_FAILURE_MESSAGE)
  cmake/FindLibGPGError.cmake:23 (find_package_handle_standard_args)
  CMakeLists.txt:321 (find_package)

I have installed a clean MSys2 and followed the setup instructions for the build-environment. I also tried to install a few additional packages, so the output of pacman -Ss libgcrypt is now

$ pacman -Ss libgcrypt
mingw32/mingw-w64-i686-libgcrypt 1.8.2-1 [Installiert]
    General purpose cryptographic library based on the code from GnuPG (mingw-w64)
mingw32/mingw-w64-i686-libgpg-error 1.27-1 [Installiert]
    Support library for libgcrypt (mingw-w64)
mingw64/mingw-w64-x86_64-libgcrypt 1.8.2-1 [Installiert]
    General purpose cryptographic library based on the code from GnuPG (mingw-w64)
mingw64/mingw-w64-x86_64-libgpg-error 1.27-1 [Installiert]
    Support library for libgcrypt (mingw-w64)
msys/libgcrypt 1.8.1-1 (libraries) [Installiert]
    General purpose cryptographic library based on the code from GnuPG
msys/libgcrypt-devel 1.8.1-1 (development) [Installiert]
    Libgcrypt headers and libraries
msys/libgpg-error 1.27-1 (libraries) [Installiert]
    Support library for libgcrypt

Do you have any additional hint on how to solve this?

[phoerious]

Try deleting and recreating your build folder. Make sure the terminal you have opened has the Mingw64 environment, not the Mingw32 or Msys environment. If it still doesn't work, try setting CMAKE_LIBRARY_PATH to include the path to libgpg-error. You should probably also uninstall the msys/ packages, they might interfere with the mingw -w64-x86_64-* packages. You also don't need any of the mingw -w64-i686-* packages if you only want to build for 64bit.

[PhilippC]

it turned out that cmake was selecting my Visual C++ compiler instead of gcc in msys. Build is now working.

[trevorbernard]

I'd be happy to test this integration. Has it been incorporated into PhilippC/keepass2android yet?

[jpdionne]

Interested in testing too! I just got a yubikey neo and this is the feature who brought me to the beta tester group.

[PhilippC]

please see PhilippC/keepass2android#4 for updates on this. Unfortunately I don't have lots of time these days to work on KP2A :-(

[droidmonkey]

@phillippc do you have a branch or PR you are using? I am an Android programmer as well and can assist in debugging if you like.

[PhilippC]

I finally released a first version, see PhilippC/keepass2android#4 (comment)

[sinistersnare]

Hello, this issue was mentioned on the KeePassXC FAQ. Is this resolved? If so, then the warning can be removed.

[phoerious]

Yes, it is, but only for Keepass2Android.

[PhilippC]

I would suggest to relax the warning stating that it works for kdbx4 databases with keepass2android.