Can prepending "junk" be equivalent to an IV when encrypting using CBC?

We are encrypting a small positive integer (1-1000) with a constant key using AES256 encryption. We are considering two approaches to make this secure; use an initial vector (which we then need to store as well), or just prepend some junk to the integer before encryption (possibly 6 characters, this is the plaintext we might encrypt to store 123: "fI8cW3123").

The second approach seems better to us, (we only store a single value, and "discover" the IV while decrypting), but we aren't cryptography experts. Is this dangerous or less secure?

• Why do you want to do this? Storing and transmitting an IV requires an extra 32 bytes. Why spend time, effort, and energy brainstorming ways to avoid dealing with thirty two bytes? I'm sure you have tons of problems that actually require solving, and I can't imagine that figuring out how to handle thirty two bytes is one of them. Apr 18 '13 at 23:33
• Choose n uniformly from [0,2^118) and then store AES(k,(1000*n)+123). $\hspace{1.7 in}$
– user991
Apr 19 '13 at 1:11
• +1 Stephen In anycase you have to ensure that the IV is a nonce. If you are always using the same key this consideration is critical. Apr 19 '13 at 12:37

If you know that the integer is fixed in size (always in the range 1-1000), then the second approach is fine. Effectively, you still have a random nonce (what you are calling the "junk"); you concatenate the nonce and the integer, then encrypt the result with AES-ECB. This works.

Do make sure that you choose a large enough random nonce. I recommend making it as large as possible, i.e., filling the full remaining width of the block. For instance, if your value is always in the range 1-1000, then it will fit in 10 bits. So dedicate 10 bits to hold the value, and use the other 118 bits for the random nonce (i.e., to encrypt, you generate a random 118-bit nonce, concatenate it with the value, and then encrypt using AES-ECB). At a minimum, you probably want your nonce to be at least 80 bits long, and a bit longer might be a bit better.

Also, make sure that you use a cryptographic-strength PRNG to generate the random nonce.