Which password-based encryption method should I use in Java 6? It should be as strong as possible, but work with the default security policy file (not the export restricted one which you have to download and install separately)?
My recommendation: You should try to avoid using password-based encryption, if you can possibly avoid it. In particular, password-based encryption tends to be insecure, in practice. The problem is that it is rare for users' passwords to have enough entropy to resist dictionary attack. Therefore, if you need encryption, you probably don't want to use password-based encryption, if there's any alternative.
A better solution is to give users a key, and use the key to encrypt or decrypt.
If you don't follow my recommendation: If you absolutely must use password-based encryption, here are some suggestions to reduce the risk somewhat:
If you're getting the sense that password-based encryption is a headache to use securely, your sense is absolutely accurate.
First read @D.W.'s answer, it is full of good advice. Then, if you still want to do password-based encryption, consider the following:
Note that password hashing mechanisms are usually not covered by cryptographic laws and export regulations, since they do not "hide" data. I then recommend that you just include an implementation of bcrypt in your code, e.g. jBCrypt which is written in Java, OpenSource with an easy license, and reasonably compact (one source file). You would need to alter the code a bit, because that implementation wants to use strings, whereas you want raw bits; thus, do the following:
(I usually prefer bcrypt over PBKDF2 for the reasons explained there, but PBKDF2 is not bad either, so if you really want PBKDF2 (or need it for compliance reasons), then go for it.)
Important: doing the encryption properly, and adding a MAC, can be botched in a surprisingly high number of ways. You are warmly encouraged not to do it yourself. However, the following method should be safe:
And, remember: never, never, NEVER reuse the salt value for two encryption instances (whether they use the same password or not). Always use