why is my pbkdf2 implementation so slow (vs. SQLCipher)?

Question

I have written a simple Android App on my Xoom tablet, which simply stores some string notes in a SQLCipher database.

The user is prompted to type in a passphrase which will be used for the database by the SQLCipher lib. This works fine so far and very smooth.

Now I have also implemented a small PBKDF2 algorithm for authentication purposes (in fact, i want to encrypt some other files in the future, wich cannot be stored in a database). But as for now, i only came to check if my pbkdf2 algorithm is correct. I only used the javax.crypto and java.security libs.

Code snippet as follows:

int derivedKeyLength = 128;
int iterations = 500;
KeySpec spec = new PBEKeySpec(passphrase.toCharArray(), salt, iterations, derivedKeyLength);
SecretKeyFactory f = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1");
byte[] derivedKey = f.generateSecret(spec).getEncoded();    

The salt is a 16 byte random number, generated with SecureRandom.

So I hardcoded the key and the salt and compare the the derivedKey for authentication (only a test case!)

My Problem now is, that on my Xoom it lasts about 5 seconds until the deriving function is done, although the iteration is set to 500 only.

AFAIK SQLCipher is using an iteration number of 4000 by default, and it responds instant, if the key is wrong or correct. (if I set the iteration to 4000, it takes at least 15seconds)

The question is, did I implemented that inefficient or is it because SQLCipher is just that good in performance (native NDK functions, etc..)?

Thank you in advance p.s: sorry, my english isnt that great yet!

Edit:

Sorry, I was not clear enough :-)

I know PBKDF2 is supposed to be slow (in specific the iteration amount, to slow down brute force attacks), thats exactly the reason I am asking! I wanted to set the iteration number to lets say 5000 (which is not acceptable, with over 15seconds)

I'm just wondering because, like I said, SQLCipher also uses PBKDF2 (Iteration = 4k, while I am using 500) for deriving a key from a given password. I'm not talking about the encryption with AES in the end, its only about the difference in deriving the key.

Of course it seems legit that SQLCipher is way faster than an self made keyderiving function, but I did not think that it would be this much difference, since SCLCipher's PBKDF2 really works instant!

Greetings!

Nick

Welcome to IT Security StackExchange! I have voted to close this question as it seems like a programming issue instead of a security issue! If a mod agrees with me, it will be migrated to StackOverflow for you. – Pad

well, thank you and sorry for this! :) – Nick

Answer 1

Ok I figured out what the problem was.

If I disconnect the device from my PC it works instant. Also if I reconnect it after that.

Now even with an iteration amount of 5000 and above, the deriving function only needs less than a second!! This is great, since my Xoom isn't the newest of all devices!

May be it is because of the debug mode or something, I don't really know actually!

Anyways, thanks to mr.spuratic. Hope this helps someone in the future :-)

Nick

I've had odd performance problems (high CPU) on a Motorola Android phone. It was triggered by connecting to a PC via USB, even just for charging. The workaround was to enable USB debugging: code.google.com/p/android/issues/detail?id=13130 – Kerbing

Answer 2

OK, that (see below) is not exactly your problem, PBKDF2 is slow but should be nowhere as slow as described with those parameters on that hardware. There are some stats (and tips) here on Android PBE/KDF performance: http://nelenkov.blogspot.com/2012/04/using-password-based-encryption-on.html . SecretKeyFactory performance problems are not unknown: Any way around awful SecretKeyFactory performance with LVL and AESObfuscator? .

SecretKeyFactory is likely using pure Java implementation. SQLCipher has two relevant features:

• it uses OpenSSL, compiled native code (on my desktop OpenSSL's PBKDF2 is nearly 100x faster than a JVM6 SecretKeyFactory version for 2000 iterations, excluding JVM startup time. I haven't compared AES speed, it appears other people find it slow on Android too)
• the 4000 iteration PBKDF2 is only done on database open, after that there's at most 2 iterations for the page HMAC secret (assuming the default configuration, as documented)

Your code seems correct, there should not be such a large (linear?) performance degradation when you increase your iterations. The Xoom should be running a non-ancient JVM with JIT, can you verify the performance problem with other code?

---

PBKDF2 is designed to be slow (see the answer to this question https://security.stackexchange.com/questions/7689/clarification-needed-for-nists-whitepaper-recommendation-for-password-based-ke ) due to the intended key stretching operation. The iteration counter lets you trade off speed for security.

AES was always intended to be fast and is fast (speed comparison PDF, the chosen AES candidate is referred to by its original name Rijndael in that paper).

I assume you are comparing the PBKDF2 computation time directly to the time taken to perform an SQL operation on your SQLCipher database which will almost certainly have been designed to be fast.

You are effectively comparing two different operations with different requirements, hence the speed difference.

Kerbing

Thank you for answering! I think I was not clear enough, please check my edit :) – Nick

OK, gotcha, will update answer . I did some quick testing and I can see that the Java (1.6.x) implementation seems to be ~100 times slower than OpenSSL's PKCS5_PBKDF2_HMAC_SHA1() on my x86 desktop. – Kerbing

+1 thank you very much mr.spuratic. You brought me to the right direction! I figured it out and I will upload my answer. – Nick