Too few rounds of PBKDF2 when encrypting master key with password

[jspilman]

Looks like you are using 100 rounds of PKCS#5 - PBKDF2 here:

private static SecretKey getKeyFromPassphrase(String passphrase, byte[] salt) {
PBEKeySpec keyspec = new PBEKeySpec(passphrase.toCharArray(), salt, 100);
SecretKeyFactory skf = SecretKeyFactory.getInstance("PBEWITHSHA1AND128BITAES-CBC-BC");
return skf.generateSecret(keyspec);
}

Shouldn't this be at least 10,000? At least for devices released in the last few years?

[moxie0]

100 was the maximum back in the G1 days. What we should probably do is benchmark a fixed number of PBKDF2 iterations during the original secret generation step, then pick a target number of rounds that takes 500ms for that device and store that iteration count in a preference.

Want to take that on?

[joeykrim]

I researched the PBEKeySpec iteration count in the AOSP code and found that the MountService.java class, which deals with OBB (Opaque binary blob) encryption, uses 1024 rounds.
https://github.com/android/platform_frameworks_base/blob/master/services/java/com/android/server/MountService.java#L223

Unfortunately, the 1024 iteration count implemented in AOSP is very close to the 1000 iteration count minimum recommended by NIST in the PDF "Recommendation for Password-Based Key Derivation Part 1: Storage Applications" - http://csrc.nist.gov/publications/nistpubs/800-132/nist-sp800-132.pdf

Short excerpt from the NIST documentation "Recommendation for Password-Based Key Derivation Part 1: Storage Applications" says "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. Since the capability of user machines varies (e.g., from a smart card to high-end workstations or servers), reasonable iteration counts vary accordingly. A minimum iteration count of 1,000 is recommended. For especially critical keys, or for very powerful systems or systems where user-perceived performance is not critical, an iteration count of 10,000,000 may be appropriate."

Is this sufficient to to send a pull request using 1024 iterations or do you prefer some benchmarks from various devices to find the iteration counts around 500 ms?

If you prefer some benchmarks, I wouldn't mind creating a small open source Android app that would simply time various iteration counts, which could be used on various devices to gather a rough benchmark list.

[moxie0]

AOSP doesn't have to deal with the compatibility range that we do,
though. On some supported TextSecure devices, 1024 could be too much.
On others, we could likely do much better. I think the best thing to do
is to put a lightweight benchmark in at generation time.

On 07/08/2013 06:34 AM, joeykrim wrote:

I researched this in the AOSP code and found the MountService.java class
which deals with OBB (Opaque binary blob) encryption uses 1024 rounds.
https://github.com/android/platform_frameworks_base/blob/master/services/java/com/android/server/MountService.java#L223

Is this sufficient to to send a pull request using 1024 iterations or do
you prefer some benchmarks from various devices to find the iteration
counts around 500 ms?

—
Reply to this email directly or view it on GitHub
#184 (comment).

http://www.thoughtcrime.org

[richo]

I decided to have a crack at this. Disclaimed, my java fu is very weak and I've not actually played much with android before.

I implemented some stubs to make it reasonably straightforward to start subbing in a method to calculate how many iterations are reasonable, and to rebuild the keys in the case that the assumption has changed.

It's not ready to merge, but feedback would be appreciated: #275

[joeykrim]

@richo Excellent! I've also been experimenting with this feature. I created a small android application to test out and understand how the iterations work on a variety of Android devices. Essentially, I've ended up with a binary search function using an adjustable target range, currently set at 400ms - 600ms, essentially 500ms +-20%.

The application is fully functional and I've been working on tweaking the binary search method to be as quick as possible on older devices as well as newer devices. The difficulty here has been how to find the target time range on an older device without overshooting but yet being able to scale/step up quickly to find the target range on a newer device. For example, some older devices settle around 10,000 or 15,000 iterations in the target time range while a Nexus 10 settles around 55,000 to 60,000 iterations in the same target time range.

If anybody wants to compile and run on an older Android device, I'd be interested in the results or any other feedback!

https://github.com/joeykrim/PBEKeyTester

I'll keep experimenting and work on merging the AsyncTask class into TextSecure

[Prillan]

@joeykrim Shouldn't the time to run be linear in the number of iterations? Or does it deviate to much?
Why not run 15,000 (or something like 10k, 15k and 20k) iterations a few times and extrapolate?

[joeykrim]

@Prillan From the testing I've done, the deviation appears to be too much. The CPU on most Android devices I've tested, other than tablets, is heavily impacted by work from other processes making a linear assumption much more difficult. If there were no other processes running on the device, I think the results might be more linear.

In a previous version, I had the runs incrementing by iterations of 5k, as you suggested, but the deviation is fairly inconsistent and on some old devices, the 5k increment and decrement was too large to hit the target time range causing the search to bounce between 10k and 15k for 30+ seconds.

There is a fine line for finding the right amount of iterations to increment by in order to scale up quickly in large increments to hit the target range on a tablet, such as the Nexus 10 at 60k iterations in 1-2 secs, but also be able to scale up quickly in small increments to hit the target range on a low end device at 10-15k iterations in the same 1-2 secs.

Feel free to grab the app, compile and test on your devices. I'm not sure how much work needs to be done on the algorithm to reach the desired end state.

If @moxie0 has a chance, I'd be interested to see his feedback on whether the binary search with dynamic steps in https://github.com/joeykrim/PBEKeyTester is a good route or if he prefers a different approach?

[moxie0]

This doesn't need to be critically precise, we just want to do better on nice devices without impacting performance on lower-end devices. So I'd recommend just doing one ~15k calculation and then deriving a scaling factor from there. If we set a lower bound that's the same as our current iteration count, then it can't be worse.

If you're seeing a lot of deviation, it looks like that could be because you're doing these calculations in an AsyncTask, which is an extremely low-priority thread. I also don't know how tight that loop is, but those singleton methods on SecretKeyFactory are expensive.