Ah, I see your confusion, and I should have been more careful to forestall it.
That's not what is meant here by a dictionary attack. What you describe is what is defended against by the iteration. The dictionary attack defended by a salt is where a *pre-computed* dictionary of keys for likely passwords is constructed. What the salt does is explode the size of that dictionary, basically making it infeasible to pre-compute the hashes for entries in a dictionary. Otherwise, you could bypass the iteration cost, by distributing the cost over a large number of attacks. Then you just search your dictionary for a key that fits, and do no key construction at all during the attack. Certainly iteration can be expensive! That's the whole point, and why it's not specified how many iterations are appropriate. You select the iteration count to determine how long the key computation should take. But the vast majority of the cost of doing a "rekey"? That would either imply a huge iteration count, or a small amount of data to be re-encrypted. In the former case -- don't do that. In the latter case -- it doesn't matter. Actually, it probably doesn't matter anyway, as rekeying is generally an administrative operation, not part of the overall performance of the system. But since the key is derived on first use, the absolute (clock) time consumed will be relevant there. The default iteration count for SQLCipher is 4000, which is pretty typical. But on slow hardware, I suppose that could be too high. In which case -- set it to a lower value. Typically, 100ms computation time after a user supplies a password is not going to be noticed, while 1000ms will. Balance that against the resources available to an attacker (which will vary by scenario and with the advancement of computing power). On Wednesday, May 11, 2011 5:27:30 PM UTC-7, DanH wrote: > > Salt doesn't prevent dictionary attacks at all. If I know that the > password is an 6-character alpha then I can try all combos of that, > dictionary or otherwise, regardless of how "salted" the encryption is. > > I've seen iteration add considerable overhead. In one SqlCipher > implementation "iteration" was the vast majority of the CPU costs of > doing a "rekey". > > On May 10, 11:13 pm, Bob Kerns <[email protected]> wrote: > > I think you missed part of what I was saying. It's important, so let me > try > > to be more clear. > > > > Each of the two components does a different job. > > > > The salt prevents dictionary attacks, by expanding the space of > dictionaries > > by the size of the salt (say, 2^128 or whatever you use.) > > > > The protection against trial-and-error cracking is where the iteration > comes > > in -- you make it take a long time to generate the final key from the > > password. > > > > The salt isn't (in this context) to prevent plaintext attacks, but > > dictionary attacks, which are EXTREMELY relevant to this case. > > > > Increasing the length of a weak password has surprisingly little effect > in > > the real world. Some, definitely, but not on the scale you'd expect from > > sheer length. And in a lot of contexts, you really can't force users to > use > > such long passwords -- the password I'm forced to use on my phone for > > corporate security reasons is very very close to to rendering my phone > > unusable. > > > > The overhead that the iteration adds to the normal path is generally > > negligible, because it's done on the client side, once. You can tune the > > iteration count to balance the performance requirements vs the security > > requirements. If 100 ms is acceptable, then choose your iteration count > > accordingly, and you will limit the attacker to 10 attempts per second > per > > CPU, which certainly beats 1000 attempts per second per CPU. > > > > On Tuesday, May 10, 2011 8:35:00 PM UTC-7, DanH wrote: > > > > > Of course, hashing a password, per se, doesn't really make it any > > > stronger. And doing things like using a salt don't do much if the > > > concern is simple trial-and-error cracking of a single encrypted > > > message (unless you're relying on "security by obscurity"). Salting > > > does help prevent known plaintext attacks and signature spoofing, but > > > those are not likely to be problems in low-volume messaging. > > > Iterating on an expensive hash can help discourage the trial-and-error > > > cracking attack, but it can add considerable overhead to the normal > > > path, and simply increasing the length of a weak password would be far > > > more effective. > > > > > On May 10, 5:34 pm, Bob Kerns <[email protected]> wrote: > > > > The fundamental problem with starting with a human-managed password > is > > > that > > > > there is not a lot of entropy -- the possible values are not > distributed > > > > over a huge range, compared to what an attacker could try with > > > > trial-and-error. > > > > > > So just doing SHA1 or SHA256 for that matter, is not sufficient for a > > > > strong > > > > key generation algorithm. > > > > > > The first thing you need to address are dictionary attacks, where the > > > > > attacker can pre-compute a large dictionary of keys from likely > > > passwords. > > > > Here, you can inject randomness into the process. What you do is to > start > > > > > > with a large random number, termed a 'salt'. This is not a secret -- > > > you'll > > > > save it away in cleartext somehow, and then combine it with the > user's > > > > password. While the attacker could afford to build a dictionary of > keys > > > > based on passwords, a dictionary of possible salt values + passwords > > > would > > > > be vastly larger. > > > > > > The other thing you need to do is to protect against trial-and-error > > > > attacks. To do this, what you do is make it expensive enough to > compute > > > the > > > > key that an attacker simply couldn't try enough to get anywhere. The > > > usual > > > > way of doing this is to iterate some expensive function -- such as > SHA1. > > > > More precisely, you iterate this: > > > > > > hash = f(hash) > > > > > > where f is some function that is expensive, and does not collapse the > > > > space > > > > of possible values into some smaller set. One way to accomplish this > > > would > > > > be: > > > > f(hash) = hash <xor> sha1(hash). > > > > > > I went with SHA1 above, because I want to tie this to PBKDF2, which > > > Nikolay > > > > referenced. > > > > > > What I outline above is roughly what PBKDF2 does for you. You can > read > > > the > > > > full details in rfc2898 <http://tools.ietf.org/html/rfc2898>, and I > > > > encourage you to do so. I did skip over a lot of detail to focus on > the > > > > motivation and approach. > > > > > > So there are basically two parameters -- the salt (selected randomly) > and > > > > > > the iteration count (selected to make it expensive but not too > > > expensive). > > > > iOS4 uses I believe something like 10000 iterations. Blackberry used > 1, > > > and > > > > was seriously pwned as a result. > > > > > > Together, these compensate for the narrow range of human-generated > > > > passwords. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
