Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I'm new to cryptography and its implementations. I'm designing an Android app where an user enters a password to retrieve some encrypted data. After some research on possible solutions I ended up with bcrypt used like so:

User enter Password -> bcrypt(Password) -> key for encryption

And then storing it in the database like so:

SHA256(bcrypt(password)) -> user check (this is stored in DB)

I was planning to use the jBCrypt implementation in Android, but from what I've read bcrypt is extremely slow on mobile phones (over minutes depending on the model of phone/strength selected.)

I know that slowing the hash procedure is the core to the bcrypt algorithm, but it's not acceptable for a user to require 2 minutes to login/decrypt on a mobile device, while the same operation on a normal PC takes seconds. However, if I lower the iteration count on the smartphone, an attacker can bruteforce it on a faster PC. How can I reconcile these two aspects of the problem?


EDIT

I finally decided to try jBCrypt on Android, and I've tested it on several mobile phones I have with different SO versions. I also tested it on my home PC and compiled a table of results:

jBCrypt results on Android vs PC

It seems like a Work Factor of 10-11 would be aceptable while still being reasonably secure. I'll try to implement a NDK solution to see whether I can improve the results. (I'll post results if I end up doing tests.)

share|improve this question
    
Is your 2min vs 0.5 sec ratio for android 2.1 oder on some version with JIT? A ratio of over 300 is insane. –  CodesInChaos Sep 12 '13 at 16:15
    
They were example numbers based on post i've read through internet related with this problem. If you see my first web page the user says 1-2 minutes for a default work factor (10 in jBcrypt), and seing the web on that post answer, on a Core 2 Duo 2.4GHz the same work factor takes 500ms. I dont know the rates, and even i dont know Android version of that user (maybe lower than 2.2 who knows). My idea after start coding that part was about going in the right direction, and all i've read about using bcrypt on mobiles sounds awful. But yes, times are estimated on what i've read –  nsL Sep 12 '13 at 16:36
    
@CodesInChaos you were right about the insane ratio. If you see my edit you can compare the results, and i have to admit i was a bit alarmist. However, for Android 1.6 (<2.1) without JIT, it really gets near 300 ratio (~260). –  nsL Sep 14 '13 at 19:43
add comment

4 Answers

up vote 9 down vote accepted

jBcrypt is a Java implementation. Android apps are written in almost-Java, for an almost-Java virtual machine called Dalvik.

For computing-intensive tasks, especially cryptographic algorithms, Java incurs a typical 3x slowdown compared to equivalent optimized C code: a good Java virtual machine runs a JIT compiler, and the performance of the code will be limited by the constraints which a JVM must operate in (translation from bytecode to native code must be fast and incremental, methods being translated on a per-call basis; and the result must still be appropriate for the garbage collector). Further slowdown can be observed in some specific cases where native code can benefit from extra opcodes provided by the CPU, the typical case being computations on big integers (say, for RSA), because the CPU may offer an "extended" multiplication (64x64->128) that Java code cannot use, due to the lack of a 128-bit integer type in Java.

For a rather thorough experiment in the context of hash functions (not "password hashing", just "hashing"), see sphlib: a library implementing a lot of hash functions, in C and in Java, with "similar efforts at optimizations" (same developer for the whole lot), and including measures on a variety of platform types.

Now, there can be additional slowdowns for Android apps:

  • The CPU of a smartphone is not as fast as that of a PC. Smartphone CPU can go to the gigahertz range, but still do less work per cycle than x86 CPU -- because one of the prime objectives of a smartphone CPU is to save battery. A smartphone must be alive for a full day, while engaging in radio activity, whereas a laptop can have a bulkier battery and only needs to be up for a few hours. Modern smartphones are efficient, but there still is a gap when compared to desktop PC. Let's say an additional 3x factor.

  • Dalvik is not necessarily the best JIT compiler around. The relative lack of raw muscle means that the JIT cannot apply the most complex optimization strategies, because it would make JIT translation of a method too expensive.

  • Up to Android 2.1 (included), Dalvik has no JIT. This is the worst slowdown, that other answers allude to. In Android 2.1 (and before), Java bytecode is interpreted, not translated to native code, and this incurs a heavy extra cost (say 10 to 20 times slower than JIT code). Android 2.2 onwards has JIT.

Switching to PBKDF2 won't change the picture much. If you use PBKDF2, be sure to use SHA-256 (or SHA-1), not SHA-512, because the smartphone CPU is ARM-based and will be quite uncomfortable with 64-bit arithmetic operations that SHA-512 heavily relies upon, thus slowing down your code -- whereas the attacker has a PC, which eats 64-bit operations for breakfast, and will not incur the same slowdown.

Summary: bcrypt will be very slow on Android 2.1 (and previous versions). It will be somewhat fast on Android 2.2, albeit not as fast as a PC (say, between 5 and 10 times slower). PBKDF2, scrypt... do not change this picture in a significant way.


All of this is said about the performance of bcrypt. I did not comment in any way on the proper use of bcrypt-derived secrets for both encryption and password verification. Indeed, when you store "something" to validate a password, you don't what that "something" to be too close to the password-derived key you use for encryption.

One "cryptographically reasonable method" is to compute the password hash with bcrypt or PBKDF2 (with salts and iterations and everything), and then take the output and expand it with a Key Derivation Function into enough key material for your needs. In your context, take the bcrypt output, then hash it with SHA-256. This yields 256 bits. Store the first 128 bits in your database as "password verification token". Use the other half as encryption key.

PBKDF2 makes this process slightly simpler since it is a KDF, so you can ask for 256 bits of password-derived output right away, not needing an additional hashing; whereas bcrypt's output size is fixed to 192 bits, which may not be sufficient for your needs.

share|improve this answer
    
Do you think that using NDK (developer.android.com/intl/es/tools/sdk/ndk/index.html) with bcrypt will speed up performance? Thanks for the suggestion about keys. –  nsL Sep 11 '13 at 15:08
    
Yes, using native code (and NDK is about allowing use of native code in Android apps) will speed up bcrypt by allowing you to use an optimized native-code bcrypt implementation. You will still have the hardware slowdown (smartphone CPU is not as fast as a desktop PC CPU) but it will remove all extra slowdowns due to Dalvik. There again, the same applies to PBKDF2. Note that the NDK pages states that "Applications that use native activities must be run on Android 2.3 or later". This constraint may or may not be a problem for you (for instance, my own phone uses Android 2.2). –  Tom Leek Sep 11 '13 at 15:30
    
Thanks for the 2.3 advice. I'm developing for 2.2+ versions, however if i find out that using NDK really worths (i'll do some test with both JBCrypt and NDK BCrypt) i'd probably move to 2.3+ . Just only 2'4% of users are using 2.2 developer.android.com/intl/es/about/dashboards/index.html (Sorry :D) –  nsL Sep 11 '13 at 15:52
    
Using HMAC-SHA512 may actually be a reasonable choice as it hurts the attacker more than the defender. (GPU-based crackers don't do SHA512.) –  Jeffrey Goldberg Sep 12 '13 at 5:41
    
I'd say the two slowdowns, at best, cancel out: by using SHA-512 on a 32-bit ARM, you are slowed down by about the same factor as the attacker's GPU is slowed down, so it is "neutral". But the attacker can still use his PC's CPU which is not slowed down that way, so the attacker may still get an extra advantage. –  Tom Leek Sep 12 '13 at 14:16
show 1 more comment

It is the same dilemma when configuring a password manager like KeePass across multiple platforms - which platform do you focus on?

Because bcrypt is a key derivation function used to stretch out the otherwise quick process of stepping through predictable human passwords; if you side-step the issue of human passwords, you side-step the performance problem.

Have access to the data governed by a session key. When the session key needs to be regenerated (say, every 24 hours or after a phone reboot) bcrypt(password) or bcrypt(password + master key) is used. During a session, the session key is only secured by non-bcrypt password encryption for speed.

Alternately you can leave the bcrypt() and the associated delay in place and simply improve the User Interface experience for the process.

If the decryption process runs as a CPU-capped background task with a foreground notification marking the decryption status with progress bar and percentage; most users will find that acceptable if the core purpose of the application is security. In fact it might even make them feel the application is more secure than a super-fast decryption would.

Of course if the application's core purpose is not security related, you might want to revisit if it really needs the security enhancement of bcrypt() and associated mobile device delay.

share|improve this answer
add comment

I've been in the same situation. On Android you should be able to use PBKDF2 comfortably. I haven't tested scrypt on a mobile device, but I expect the performance not to be any better than scrypt when generating a hash. Apart from that, instead of taking a SHA-256 you could easily just use PBKDF2 with a SHA-256 HMAC. Remember that PBKDF2 also allows you to set the output length of the hash (preferably you use HKDF-Extract on the output of PBKDF2 instead). So normally taking the SHA-256(pbkdf2(pass)) will be too much.

I would recommend however that you take another PBKDF2(PKBDF2(pass)) and store it in your application as well. That way you can check that, when the user inputs a password and you use PBKDF2 to generate the key (inner PBKDF2) that the key is indeed the correct key before decrypting.

So:

  • password => used to generate key (secret, should not be stored)
  • PBKDF2(password) => used as key to decrypt your encrypted data (secret, should not be stored)
  • PBKDF2(PBKDF2(password)) => used to verify the key before attempting decryption (not secret, can be stored within your application)
share|improve this answer
    
While you can use PBKDF2 with variable output length, you probably don't want to. The way to go is HKDF-Extract on the output of PBKDF2. –  CodesInChaos Sep 11 '13 at 13:27
    
Added that to the answer and linked to your answer on crypto. –  Lucas Kauffman Sep 11 '13 at 13:30
    
"scrypt is certainly not better than bcrypt in regards to speed (after all that's what the algorithm tries to tackle)." I don't get the argument you're trying to make here. The problem here is the relative performance for some algorithms on mobile devices compared to PCs. It's not obvious how different algorithms will fare. –  CodesInChaos Sep 11 '13 at 13:30
    
That was my point actually, his question was if scrypt would perform well on a mobile device and I assume that it will not be any better than bcrypt in the sense that it will still take a significant amount time to generate the hash, which is not good for usability. –  Lucas Kauffman Sep 11 '13 at 13:39
    
Thanks! however if PBKDF2 performance might be similar to bcrypt, doing PBKDF2(PBKDF2(password)) will drive the user nuts. Even with that, seems a good method to know for another scenario different to mobile! –  nsL Sep 11 '13 at 14:49
show 2 more comments

As you acknowledge, you have contradictory requirements. You want bcrypt to be as costly as possible to help defend against off-line crackers, while at the same time you want it to not be prohibitively costly to the legitimate user on an relatively low powered device.

There are two kinds of approaches, both of which you should pursue. Tuning your cost factor (or iterations), and finding a hashing implementation that gets you the best (smallest) Attacker/Defender Ratio.

Reduce the Attacker/Defender Ratio.

The password cracker, Bitweisel, talks about what he calls the "Attacker/Defender Ratio" (ADR). When the Defender is stuck running bcrypt, scrypt, or PBKDF2 in a way that is, say, 1/10th the speed of what the Attacker has available, then the ADR is 10 to 1. In your situation, the Defender is not only on a less powerful device, may also be stuck with compilers that don't do well on these systems.

I don't know enough useful about Android to point you in the right direction, but you should try to find something carefully optimized for its operating environment. Whether that will be bcrypt or PBKDF2, I don't know. Again, you are not concerned (yet) about absolute speed, but about the ratio between your environment and the attacker's.

For example, it may be that PBKDF2 using HMAC-SHA512 is deadly slow for you, but that may be worth it if the use of SHA512 precludes the attacker's ability to use GPUs for cracking. So even though slow, this might actually get you the lost ADR.

Install a copy of ocl-hashcat+ (the fasted cracker out there) to test cracking rates on your desktop computer so that you will have that side of the equation for judging the ADR for different hashing schemes.

Tune your cost factor

PBKDF2, bcrypt, and scrypt all allow you to set work factors. The statement "bcrypt takes two minutes" is fixable by reducing the cost paramater by one (to make it take one minute), or by two (for 30 seconds). With PBKDF2 you set iteration, which scale linearly.

So once you've found the algorithm and implementation that gets you the best ADR, then simply decide what time your users will tolerate. If it's 2 seconds, then tune the cost factor or iterations to get you that two minutes.

share|improve this answer
    
"You want bcrypt to be as costly as possible to help defend against off-line crackers, while at the same time you want it to not be prohibitively costly to the legitimate user on an relatively low powered device." The thing is that a secure & acceptable use in pc (0.5 secs for example) turns into secure & unacceptable use on mobiles (2 minutes). The trick is to find a combination of security & usability acceptable in both systems. i'll have a look to HMAC-SHA512, but based on Tom Leek's comment it maybe be better to use 256 –  nsL Sep 12 '13 at 10:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.