Encryption key generation performance

A question for cryptography experts. Imagine we have a conceptual Notes.app:

• There are notes (title|content) stored as AES-256 encrypted strings
• Application has to present a list of all notes (titles) in a list on its main window
• Every title|content is encrypted with a key, generated from a password and a salt
• Let's imagine the key generation algorithm takes ~80ms on a mobile device to generate a key

With the following conditions, it would take almost 1 second to decrypt 10 note titles. But what if there are lots of notes?

My 2 pennies on the problem: Encrypt all notes with different initialization vectors, but also with identical salt. That would allow me to generate a decryption key only once and decrypt lots of notes fast.

The question: doing so we would end up with lots of different notes, encrypted with an identical key. Does that somehow compromise the security of AES encryption? Is it possible that knowing there's a bunch of files with not just identical password, but also identical salt somehow makes it possible to crack the encryption?

Thanks for your thoughts

-

The password hashing business is about turning a password (which is weak, by definition) into a sequence of bits suitable for storage (password verification token) or use as an encryption key (in which case we are doing password-based key derivation). In order to tolerate the use of passwords, we have to follow some strict rules:

• Use slow hashing with a lot of iterations (that's easier said than done, so don't get creative and use a well-studied standard like bcrypt or PBKDF2).
• Never ever reuse a salt value for another password instance. Indeed, if two passwords are hashed with the same salt, then attacking one will allow attacking the other "for free".

However, once you have turned the password into a key, you can use it as any key. If your encryption system is not laughably frail, there should be no problem with using the same key to encrypt many files. In the case of something AES-based, this implies, indeed, a new IV for each file. The properties of that IV depend on the actual encryption mechanism; AES-CBC requires a random, uniform, unpredictable IV, while some newer modes like GCM only need a non-repeating IV and thus work well with a simple counter.

Note that many password-based encryption scheme use a salt-and-iterations system to hash the password into a sequence of bits containing both the key and the IV. Such systems cannot be used for more than one file; otherwise, you will reuse the IV, and that's a deadly sin (usually worse than reusing a salt, which is already quite bad). If you want to reuse the key resulting from the password hashing, then you MUST generate a new IV for each encryption run.

Also, note that if two files are encrypted with the same password-derived key, chances are that their headers will include the salt (you have to put it somewhere, so that it is available for decryption), so you will leak the information that both files are protected with the same password, and thus have the same source. Depending on your context, this may or may not be a problem for you.

Other people have found it convenient to use the simple expedient of storing their ten files into a single Zip archive and encrypting that as one file. Depending on your context, this may be applicable (or not), and is much simpler to implement without botching the crypto layer. In general, designing your own encryption format and assembly of algorithms is a path fraught with perils, and you cannot know whether you did it right or not (security is not functionality: it cannot be tested).

-
Thank you for your answer, Tom. This is some great information. You are indeed right, i am using password-salt based key deriviation, but currently every file (or record) has a different salt, stored within the file header. I am not worried that cracking one file (record) will open access to the rest. What i AM worried though is that all of these files, encrypted with the same key, will have some sort of statistical weakness that will make cracking the password even easier than with having just a single encrypted file. Should i be worried about that? – Marius Feb 9 '14 at 14:51
If such a statistical weakness exists, then the encryption system you are using is broken and you should not be using it. – Tom Leek Feb 9 '14 at 16:57
Tom, i have no idea if it exists - that's why i ask. I'm talking about standard AES-256. If i have N files with same encryption keys, but different IVs - does it help a hacker in some way other than saying "all of these files have the same password"? – Marius Feb 9 '14 at 17:03