Aegis
Aegis copied to clipboard
beemdevelopment
Dynamically decide KDF parameters and consider implementing caching
TL;DR: Hardcoded KDF values violate NIST guidlines; they are supposed to be set based on device speed. While you are at it, implement KDF caching using Argon2's "server relief" to drastically increase the cost of brute-forcing the vault backups.
Key Derivation Functions attempt to squeeze additional security out of low-quality secrets by increasing the computational cost of a brute force attack. The amount a key can be stretched is ultimately limited by usability requirements. The industry standard practice of hardcoding of specific values technically violate NIST's KDF guidelines:
The iteration count shall be selected as large as possible, as long as the time required to generate the key using the entered password is acceptable for the users.
Industry hasn't done much about this because increasing KDF values would represent a major expense for service providers and a DoS attack vector. Part of the rethink done for the password hashing competition was to formalize a technique in which clients would perform the majority of the work for server. Argon2 calls this "server relief" and is provides an error-resistant API.
While Aegis doesn't have a client/server model, abusing caching can be used to increase the cost for offline attackers while maintaining a good user experience. The simplest example/implementation of KDF caching would be to set a very high KDF iteration value for the backup vault and cache an intermediate value within the apps' private storage area. The user would only experience a high KDF wait time during the initial setup and when restoring from a backup. This wouldn't do much against a root exploit, but it can increase the cost of other attacks by 10-100x.
The following KDF run times roughly align with user perception/delay tolerance:
- 100ms - 200ms app closed
- 1s - 5s phone reboot
- 1m-10m initial setup/sync or restoration from backup
The first tier provides marginal security gains to a narrow group of high-risk users, like protesters without enough op-sec experience to setup work mode. The additional complexity is only justifiable if key material is already being flushed from memory to help mitigate side channel attacks.
The second tier delay should be masked using an animation that also communicates that the delay helps increase security. The third tier cache isn't needed for on-device functionality and can be run as a background task. Users can be expected to tolerate restoring from backups for much longer than normal, as long as you provide accurate feedback on how long the task will take.
Edge cases in which restoring to a new device would take over an hour or when the new device just doesn't have enough memory can be handled by entering the private key by scanning a QR code or manually entering a mnemonic.
Hardcoded KDF values violate NIST guidlines
Do the NIST guidelines actually specifically suggest this anywhere? Going from your quote of the guidelines to this conclusion is quite a stretch.
That said, I like the idea of dynamically adjusting the KDF parameters based on the specs of the device Aegis is running on. This has also been touched on before in this issue: #114. However, the problem is that Android poses strict memory usage limits on apps. Both scrypt and Argon2 are deliberately memory-hard KDF's. With Java implementations, we quickly run into OOM crashes if we increase the KDF parameters. This a bit less of a problem with Argon2, because it permits tweaking the memory-hardness parameter and CPU-hardness separately. Either way, switching to a native implementation of the KDF would be required in order to be able to meaningfully increase the KDF parameters. See #302 for some existing work on this.
Is this something you'd like to work on? Once the switch to a native KDF implementation is done, we can look at dynamically deciding the KDF parameters. And finally, whether we need to cache some of the KDF calculation locally on the device in order to improve the user experience when unlocking the app.
In the end though, you shouldn't have to count on the cost of the KDF to protect your weak password. Setting a strong password is the only way to know you'll always be safe.
Edge cases in which restoring to a new device would take over an hour or when the new device just doesn't have enough memory can be handled by entering the private key by scanning a QR code or manually entering a mnemonic.
I think there is some misunderstanding here as to how TOTP/HOTP authenticator apps work. There is not a single secret key from which all OTP secrets can be restored. Since the other issue you created mentioned cryptocurrency wallets, I think being used to having the ability to restore your wallet with a single mnemonic phrase is where this confusion comes from. With TOTP and HOTP, each service that you set up 2FA for generates a shared secret that is communicated to the device through scanning a QR code. Aegis stores the secret (and the other parameters used to calculate the code) and encrypts these secrets at rest with a user-provided password. See: https://github.com/beemdevelopment/Aegis/blob/master/docs/vault.md.
Hardcoded KDF values violate NIST guidlines
Do the NIST guidelines actually specifically suggest this anywhere? Going from your quote of the guidelines to this conclusion is quite a stretch.
It's all in section 5.2 and annex A.2.2 of SP 800-132. They go on at some length on the topic without giving actionable advice, which is probably why everyone ignores it. Compliance to standards is enforced via unit testing, which realistically can only check if the minimum iteration count is met.
But anyone who actually cares about this knows that PBKDF is a joke. The standard needs to be updated to adopt Argon2, provide actionable advice based on UX research, etc.
Both scrypt and Argon2 are deliberately memory-hard KDF's. With Java implementations, we quickly run into OOM crashes if we increase the KDF parameters. This a bit less of a problem with Argon2, because it permits tweaking the memory-hardness parameter and CPU-hardness separately. Either way, switching to a native implementation of the KDF would be required in order to be able to meaningfully increase the KDF parameters.
Is this something you'd like to work on? Once the switch to a native KDF implementation is done, we can look at dynamically deciding the KDF parameters. And finally, whether we need to cache some of the KDF calculation locally on the device in order to improve the user experience when unlocking the app.
If I could get a job (even a research position) working on this issue, I would get NIST to adopt Argon2, setup a competition for the fastest Argon2 library, and provide native ports to every major software ecosystem. I have dreams of collaborating with OpenBenchmarking.org to track the speed of various devices, etc, etc, etc. Then I wake up and go back to work : /
In the end though, you shouldn't have to count on the cost of the KDF to protect your weak password. Setting a strong password is the only way to know you'll always be safe.
You yourself criticized andOTP for not using a KDF. I believe the added engineering effort is justified, given how weak pins and passwords are.
I think there is some misunderstanding here as to how TOTP/HOTP authenticator apps work.
I lived through the transition to hierarchical crypto wallets and I understand that TOTP tokens are essentially shared secrets.... I'll jump on Matrix later.
So, WRT edge cases in which restoring or syncing on devices that don't have enough power to compute the KDF in a reasonable amount of time: the backup vault would be encrypted to both a password that has been stretched through the KDF and a random key generated by the device.
That being said, this really should be an edge case. The constraints used to specify maximum values should be data driven ... I'll think about a way to derive those values that doesn't involve cooking up an alternative to GeekBench : p
In the end though, you shouldn't have to count on the cost of the KDF to protect your weak password. Setting a strong password is the only way to know you'll always be safe.
This comment has been on my mind, so let me try again: using randomly generated keys is the only way to know that you'll always be safe. By definition, passwords either do not provide enough bits of entropy or are subject to reuse/forgetting/fat fingering. I haven't had the time required to quantitatively answer how much extra protection a given KDF gives users, but it's limited to a constant time addition that erodes as technology improves.
It's all in section 5.2 and annex A.2.2 of SP 800-132.
These recommendations seem based on the assumption that PBKDF2 is going to be used. As already discussed, dynamically deciding the KDF parameters is a different story when using a memory-hard KDF.
You yourself criticized andOTP for not using a KDF. I believe the added engineering effort is justified, given how weak pins and passwords are.
Of course I criticized them for that. There's a big difference between 1) not using a KDF at all and 2) already using a KDF, but not squeezing the last bit of performance out of a device to improve the parameters a bit. Anyway, I've already said that I'd be on board with some of the idea's proposed here, but I think we disagree on the priority. If you'd like to prioritize this, get cracking on some patches.
So, WRT edge cases in which restoring or syncing on devices that don't have enough power to compute the KDF in a reasonable about of time: the backup vault would be encrypted to both a password that has been stretched through the KDF and a random key generated by the device.
Where would users store this random key? Assuming we do this, now users need to remember a password and keep a key safe somewhere. That doesn't sound very user friendly.
This comment has been on my mind, so let me try again: using randomly generated keys is the only way to know that you'll always be safe. By definition, passwords either do not provide enough bits of entropy or are subject to reuse/forgetting/fat fingering. I haven't had the time required to quantitatively answer how much extra protection a given KDF gives users, but it's limited to a constant time addition that erodes as technology improves.
When I say "strong password", I'm implying that is was generated randomly. If it wasn't generated randomly, it wouldn't be strong, so I don't think we disagree there.
These recommendations seem based on the assumption that PBKDF2 is going to be used. As already discussed, dynamically deciding the KDF parameters is a different story when using a memory-hard KDF.
The assumptions in the NIST guidelines apply equally to any on-device KDF caching values (tiers 1 & 2) as those can be device specific. I agree with you that the backup KDF settings need to factor interoperability into the equation. However, while Scrypt conflates memory and time hardness as a single parameter, Argon2 does not. The parameters for an Argon2 protected backup will be subject to much bikeshedding, so let's focus on implementing tiered caching and Argon2 first and worry about idealized values later 😸.
There's a big difference between 1) not using a KDF at all and 2) already using a KDF, but not squeezing the last bit of performance out of a device to improve the parameters a bit.
Fair! I'm just trying to explain the fuller security model. FWIW, I really appreciate your honest responses as they underscore how researchers and standards bodies could better support implementers.
Anyway, I've already said that I'd be on board with some of the idea's proposed here, but I think we disagree on the priority. If you'd like to prioritize this, get cracking on some patches.
FAIR! 🤣 I'm going to see if BitWarden and 1Password will provide hard data on devices and migration statistics. Maybe they will pay me to build some hashing cost models.
So, WRT edge cases in which restoring or syncing on devices that don't have enough power to compute the KDF in a reasonable about of time: the backup vault would be encrypted to both a password that has been stretched through the KDF and a random key generated by the device.
Where would users store this random key? Assuming we do this, now users need to remember a password and keep a key safe somewhere. That doesn't sound very user friendly.
I'm fine with using backup/sync services that rely on a user generated pin/password as long as they are backed by a HSM that can limit brute force attacks (such as Google's Android backup service). Backups/syncs to those services would be encrypted to both the user generated password and the device generated backup key. Access to either of those keys would be sufficient to decrypt the backup.
I still need to sit down and do the math before I can make any informed recommendations about the trade-offs. I just don't think it makes sense to restrict KDF values based on Android's platform minimum of 416 megs of ram when the cheapest phones I can find in my market all have at least 2GB of RAM.
But we have to assume user error on password input anyway ... you have already had at least one person in chat swearing they input their password correctly. I'm just suggesting reusing that escape hatch here as well.
When I say "strong password", I'm implying that is was generated randomly. If it wasn't generated randomly, it wouldn't be strong, so I don't think we disagree there.
That's the definition of an encryption key, not a password. Humans can't remember long random strings without lots of unreliable memory tricks that require waaaay more effort than a paper backup. There are shades of grey between random strings and low-entropy passwords, but we went down that rabbit hole with brainwallets.
Argon2 doesn't need a lot of memory to be useful. Just enough to be larger than L1/L2 and possibly L3. Even the largest CPUs only have 32MiB of L3 per group of cores. 48MiB of state would be guaranteed to overflow the L3 cache and go out to memory. Even 4MiB would be plenty to overflow L2 and start contented L3 on a Ryzen.
I use a password manger for the backup password and bio to unlock, though a pin would be nice. The backup password is long and random. KDF doesn't matter, it's not getting broken no matter how fast the hash is. A pin on the other hand would benefit from KDF since it's meant to be short.
Argon2 doesn't need a lot of memory to be useful. Just enough to be larger than L1/L2 and possibly L3.
The Argon2 RFC recommends 64 MiB for memory constrained devices, double the per-application minimum memory allocation specified by the Android Compatibility Definition Document. 🤷