4

Background:
I have been working on an Android application that stores data in a local database as my pet project. Lately, I have decided that I want to password protect the application and encrypt the database. Now, I am aware of the complexities of encrypting the database on the fly and have (given the expected usage pattern of my application) decided to just encrypt the whole database file rather than try to store encrypted column value or the like. Thus far I have implemented a system that will prompt for a password on every application launch or whenever the user navigates away from my activity (to account for the user pressing the home key and the application not being killed in a timely manner).

Currently, I am trying to decide how exactly to go about hashing the password and where to store it. Given that everything must be stored on the device, I am basically treating the password hashes and salt as already compromised as anyone who has spent 10 minutes reading can root a given device and access my database / preferences.

I have developed what I think should still provide very strong security given the above assumptions. I wanted to get some feedback from the community to see if my solution is viable or if there is a better way.

My idea is to generate 10 different random salt values on the first run of the application. These values will be stored with the actual final password hash in the application preferences (rather than in the database). Note that there will only be one password and it is used for both user authentication and database decryption. Whenever a challenge is presented, the password will be hashed as follows:

  1. Cleartext password is hashed.
  2. Hashed password is run through the same checksum algorithm that is used for standard UPC barcodes. This will result in a value between 0 and 9 (inclusive).
  3. This checksum digit will be used as an index to the array of salt values. This single salt value will be appended to the current hash.
  4. The new hash + salt value will then be hashed and steps 2 - 3 will be repeated.

I figure doing this process for 5 iterations would give 5^10 different salt combinations alone and should make any type of rainbow attack practically impossible. Once the final hash has been verified correct, it can be used to decrypt the database.

Now, I realize that this sounds like overkill for a simple cellphone app. It is. But, this being my pet project, why not?

Question:
So, after that wall of text, is this approach reasonable or is there a better way? I think, with this in place, the weakest link would be an in-memory attack or am I mistaken? Any feedback is greatly appreciated.

Thank you in advance.

-cheers

MysteryMoose
  • 2,211
  • 4
  • 23
  • 47
  • 1
    hashing more than once is pointless due to collisions - see http://www.youngcoders.com/php-articles/16159-encryption-safety-collisions.html I wholeheartedly support your approach to seek a more secure method - I wish more devs did - but be aware that it's a really big subject and some things are non-intuitive. – Basic Dec 15 '10 at 00:25
  • Hm, collisions are definitely something I had not considered in-depth. I came upon this whole scheme (in the shower, comically enough) after reading http://www.owasp.org/index.php/Hashing_Java as well as an article on this very site which advocated iteration (can't seem to find the link, though). Am I missing something? – MysteryMoose Dec 15 '10 at 00:55
  • Basiclife's advice is completely contrary to that given by any authority in cryptography. Key-strengthening, which for a cryptographic hash function means iterating thousands of times, is vital to prevent brute force attacks. Also, on average, half the bits of a cryptographic hash change for every bit of input. The hashes do not converge to a limited set of values. – erickson Dec 15 '10 at 09:38

5 Answers5

5

I don't get it. If you are encrypting the database, why do you need to store a hash of the password anywhere?

Derive an encryption key from the password, which is stored in the user's brain, using something like PBKDF2. Use it to encrypt the database.

When the user wants to decrypt the database, prompt them for the password. Derive the key from it again, and decrypt the database.

You store a password hash for authentication purposes. But this is encryption, not authentication.

Suppose you have a hash function that takes salt, a number of iterations, and a password as input, and returns a hash as output: byte[] hash(byte[] salt, int count, char[] password). Randomly generate one salt on the first run of the app, and hash the newly chosen password. Store this salt and the resulting hash in the application preferences. Then randomly generate another salt, and hash the password with it. Use the resulting hash as the database encryption key, but store only the new salt in the application preferences.

Later, when a user wishes to use the app, prompt for the password, and use the first salt to hash it. If it matches the stored hash, the user has proven that they know the decryption password. Hash it again with the second salt, and use the resulting key to decrypt the database.

This subsequent derivation of an encryption key might be what you meant; I am trying to make that step explicit, in case you intended to use the password directly as an encryption key. Having two different salts, one for authentication, and another for encryption, will allow you to use the same password for both purposes, safely.

erickson
  • 265,237
  • 58
  • 395
  • 493
  • Perhaps I was unclear as to the nature of the application itself. There are two parts to the process. The first part is standard user validation. This is in place for two reasons. One, to allow access to the application (which does not necessarily mean decrypting the database) and, two, to verify that the key supplied is actually correct. I do not what to try to decrypt the database with a bad key and then get an exception when I try to call open() on the database (which will be garbage). I basically don't like that the password and salt are just sitting there. – MysteryMoose Dec 14 '10 at 23:43
  • @phobos51594 - Okay, that makes a lot more sense. However, I still recommend using PBKDF2 to "hash" the password. Just use different salts for encryption and for password validation. Using a large salt (16 bytes) will thwart rainbow tables. Using many iterations (several hundred or a few thousand shouldn't be too slow on a mobile device) will prevent a brute force attack. (Salt and iterations are the parameters to the PBKDF2 algorithm.) – erickson Dec 15 '10 at 00:05
  • P.S. Not sure if it's available on Android, but if the JCE provides a "PBKDF2WithHmacSHA1" `SecretKeyFactory`, you can use that, as shown [here.](http://stackoverflow.com/questions/992019/java-256bit-aes-encryption/992413#992413) – erickson Dec 15 '10 at 00:08
  • Ok, thanks for the input. Have been deciding exactly which algorithm to use. Would you mind elaborating a bit more on what you mean by "Just use different salts for encryption and for password validation"? As I am envisioning things, the user password would go through multi-salting procedure (for lack of a better term) that I have laid out and that final hash value would be used to decrypt the database (assuming validation passes). I this poor practice for this sort of thing? – MysteryMoose Dec 15 '10 at 00:14
  • I'd also add that a long salt is only a deterrent if you're trying to come up with a "generic" rainbow table - in which case, I agree completely. If you're targeting a single device, the length of the salt is irrelevant as it can be extracted by a root user and simply appended/prepended to the PW being hashed. – Basic Dec 15 '10 at 00:56
  • 1
    @phobos51594: Don't use your homebrewed scheme - just use PBKDF2. This is exactly the situation it is designed for - it assumes that the attacker will have access to the salt and derived key (or "hash" - in this case, they amount to the same thing). It is designed to make bruteforcing computationally infeasible. – caf Dec 15 '10 at 03:51
0

What I do is use the record ID of the database row as the salt. You could hash the id of the row and use that for a zestier salt.

If you only have a dozen or so passwords, it seems approximately similar in security to what you are already doing. But if you have hundreds or tens of thousands, it becomes infeasible to calculate one dictionary table for every ID.

Brian Topping
  • 3,235
  • 28
  • 33
  • Hm, definitely something to keep in mind for future projects requiring multiple logins. However, this is a cellphone app and there will only be a single password. In addition, the entire database file will be encrypted at the time of password entry. – MysteryMoose Dec 14 '10 at 23:45
  • You;re assuming an Id exists for the record but we're talking about hashing _before_ the DB is decrypted - so presumably this auth is stored in a file or similar - I suppose you could use line number as a salt if users are never deleted :) – Basic Dec 15 '10 at 01:12
  • Right. I guess in my domain fixation on server-based apps, I didn't consider that this was a single password encrypting an entire database rather than protecting passwords themselves, which this solution does a good job at. – Brian Topping Dec 15 '10 at 01:22
0

Ok... Assuming your hashing method is not weak, it doesn't matter if the salt is known - Salt is simply so that 2 users with the same password have different hashes - and a casual inspection of hashes wouldn't result in identical passwords being obvious. Salt should be unique per user.

Assuming the (malicious) user has root, there's absolutely NOTHING you can do to prevent them compromising your app except encryption - specifically the user could theoretically get your binary, decompile it to work out how it authenticates users, bypass it and then just follow the decryption mechanism - And since the encryption key is not related to user PW in your scenario, it has to be stored SOMEWHERE - and if the app can read it, so can root

The only truly secure approach would be to have a single-user (or at least single-password) which related to the DB encryption key.

Aside from that, the best you can hope for is to make it sufficiently difficult for a malicious user that it' not worth their time.

Basic
  • 26,321
  • 24
  • 115
  • 201
  • There is only a single password and that password will, after verification, be used to decrypt the database. The salt in this case is to complicate any type of attack where the hashes are precomputed. – MysteryMoose Dec 15 '10 at 00:03
  • whatever mechanism you choose to calculate the salt can be duplicated by the pre-computed hash approach - I can see a benefit for having the salt be device/app-specific so that what breaks one device won't break another - but if you're picking from 10 salts using a formula, that formula can be extracted and duplicated - so the pre-computed hashes would simply take that into account. You haven't increased the password set space at all... – Basic Dec 15 '10 at 00:07
  • eg if **password1** resulted in the use of *salt1*, **password2** resulted in *salt2*, etc... and I wanted to break your app by brute-force, I'd simply extract the N salts and use the same mechanism when computing my hash tables. (Edited: should've been salts not hashes) – Basic Dec 15 '10 at 00:09
  • One other consideration - since this is presumably going on a mobile device, you _could_ perform the authentication remotely - eg phone home with a username/password/deviceId (using a suitably secure comm method) and what you get back if the un/pw is correct is the DB encryption key for your device. This would make your app online-only and would require server(s) maintained by you... You could then prevent brute force attempts based on device id by rate-limiting your auth server responses. pre-computed hash tables would then be useless – Basic Dec 15 '10 at 00:10
  • Oh and one final thought - It would be just as much effort to brute force a salted password as it would be to brute force the DB encryption key... – Basic Dec 15 '10 at 00:14
  • I see your point that the use of a salts would follow a linear progression for a given input. You are correct in that it does not really increase my search space, just makes it take that little bit longer to compute each entry in the rainbow table. However, won't each iteration have a multiplicative effect on the time required to compile such a table within reasonable accuracy? E.g. wouldn't two iterations take longer to compute (per key) that one (though no necessarily twice as fast)? – MysteryMoose Dec 15 '10 at 00:46
  • Oh, and I considered online verification but that was not really feasible given my current means. – MysteryMoose Dec 15 '10 at 00:47
  • I see where you're coming from and I have to say that I'm not an encryption expert (just an aspiring amateur) - so we're reaching the limits of my knowledge. That said, as I understand it the only additional complexity you're adding is that each iteration would require the evaluation of your function to determine which salt is used. Whilst this _is_ more computation, it's trivial compared to calculating the hash itself - so we're now talking about fractions of a % more time to generate the rainbow table - which seems like little benefit for a significant loss in readability/maintainability – Basic Dec 15 '10 at 00:54
  • Fair enough. We are well beyond my knowledge but I am always learning. There would be the added time of running the checksum, as well, but that is still trivial I am now seeing. Perhaps I would be better served implementing a stronger algorithm and just iterating over that. Though, the point of the exercise was not to be uncrackable (nothing is) but to make it as difficult as possible. – MysteryMoose Dec 15 '10 at 01:02
  • Agreed - have a look at the link I posted in a comment on your Q re: collisions. As I understand it, picking a better hashing mechanism (not MD5! http://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities) will give you much better results than almost anything else you can do. I initially tried double-hashing and double-encrypting but ppl far wiser than me have proven that this usually weakens rather than strengthens the security. Hashes are already deigned to achieve all the goals you want - second guessing often results in more problems than it solves unless you're a skilled matematician... – Basic Dec 15 '10 at 01:08
  • Yeah, it looks like I have a lot more reading to do. I wish I could choose two answers. This discussion has been amazingly helpful, thank you. – MysteryMoose Dec 15 '10 at 01:14
0

Even with 10 salt values you are still technically vulnerable to rainbow table attacks. All they have to do create 10 rainbow tables each using your salt. It will take them sometime to generate all new rainbow tables, we are talking days or weeks. Once they have the tables though the can use it against all the users who downloaded the application. If you store a unique salt per password that would require them to go through the whole process for every password, which is a lot of work for just one password. The question is would someone want to go through all that trouble to get one password. Here is a good post about storing passwords "You're Probably Storing Passwords Incorrectly"

Patrick
  • 651
  • 6
  • 14
  • This is not a single pass process. Notice the iteration. With each iteration a new salt is added. Not to mention that the salt is randomly generated on the first run and would be unique for each device. – MysteryMoose Dec 15 '10 at 00:07
0

I cannot spot any major weakness in this scheme. However, it does not add any security over best practice salting; i.e. generating an storing a new per-user salt each time the user sets or changes their password.

This scheme does add an extra point of attack. If there is a weakness in the way that the salts are generated (e.g. predictability), then it is likely to be easier to exploit if you restrict yourself to 10 salts all generated at the same time. That might give an attacker more leverage to guess what the likely salts are, and hence create rainbow tables.

But the main problem with your approach (IMO) is just the complexity.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216