How to use AES-CBC to password-encrypt a small block of stored data

Question

I have a small block of data (16 bytes) that I am required to encrypt, store (in an unsecure, visible location). Later I have to retrieve and decrypt it. I must use AES-CBC and a user-entered password.

After decrypting the data, I need to know if the correct password was used (so I can reject the data if not).

My initial plan:

1. Encapsulate the 16-byte payload in a plaintext frame something like this:

     Frame:
        8-byte random salt
       16-byte data block
        8-byte checksum of salt+payload

2. Generate a random 128-bit IV.

3. Generate a 128 or 256 bit key from the user-entered password.

4. Encrypt the plaintext frame using IV+key.

5. Concatenate the IV and ciphertext frame and store them. [Using 48 bytes of storage.]

Storage size isn't critical: a hundred bytes (or two) is OK, but thousands is probably too much.

My questions:

1. Do I really need a random IV if I salt the data? Prepending 128-bits of random salt to the data is the same as using a 128-bit random IV, right?

2. What should I use for a PBKDF? The application is running on a smallish, slowish embedded system and has rather limited crypto routines available (aes, arc4, des3, sha1, sha256, md2, md5). So, I'll have to roll my own PBKDF. A PBKDF algorithm that runs in one second on an attacker's machine will probably take thousands of seconds on this device -- so let's not get carried away: I need to do the encryption and decrypting in no more than a second or so.

3. Most discussions of using a PBKDF emphasize the importance of including a salt value. That means I also have to store the PBKDF salt along with the IV and the ciphertext, right?

4. I have access to the stored data produced by a previous version of this product (which I'm told uses AES-CBC to do the same thing), but I have no access to source code or the people responsible. The stored data is exactly 16-bytes long. AES-CBC always uses 16-byte blocks, so that must be a single block of ciphertext. That means

   a) They aren't using any salt in the PBKDF algorithm?

   b) They must be using an IV produced by the PBKDF (or a constant IV)?

Answer 1

Do I really need a random IV if I salt the data? Prepending 128-bits of random salt to the data is the same as using a 128-bit random IV, right?

Yes, it should do the job, but if I'm reading your question correctly you don't really have to optimize storage away, but if you want to, I'd rather recommend going with AES-128 and a 128-bit IV which is derived from the PBKDF result (simply split the 256 bits in half).

What should I use for a PBKDF?

This is a difficult question. If possible you should pick a password hashing function from the password-hashing competition winner's portfolio.
If it's not possible you should implement PBKDF2 with SHA-256, because you then get those 256-bits from a single iteration chain which you can use for key and IV. All you can do optimize your defense is to measure the time it takes for your actual encryption code to run and then give what is left to the PBKDF.

Most discussions of using a PBKDF emphasize the importance of including a salt value. That means I also have to store the PBKDF salt along with the IV and the ciphertext, right?

Yes, but as discussed above, you can swap the IV for the salt and derive the IV from the PBKDF output to save space again.

They aren't using any salt in the PBKDF algorithm?

If they didn't prepend a salt to the ciphertext and the payload is always 16-bytes, then yes, there's no way they're using a salt.

They must be using an IV produced by the PBKDF (or a constant IV)?

Again, if you don't see an IV, that means that any of the two options holds with the constant one being significantly worse than the PBKDF derived one.

---

Now that I have actually answered the question, I'd like to point out improvements in your format.

The format:

      16-byte salt
frame:
      16-byte payload
frame-end
      32-byte authentication tag

This way you get a strong salt, which won't yield any collisions and other undesirable outcomes on accident. You can feed it into the PBKDF and get the key and IV (both 128-bit) back for AES-CBC. You use this to encrypt the payload and the payload only. Finally you HMAC-SHA256 the salt, the (temporarily buffered) IV and the payload-ciphertext with the AES-key (yes it's ugly but should be safe) and append this tag to the ciphertext.

This has the advantage, that you don't do hash-then-encrypt which is a worse variant of mac-then-encrypt, you can actually use your salt where it's useful (why was it part of the plaintext in the first place?) and you get strong authentication with overall 128-bit security.