Will varying plaintext compensate for a fixed initialisation vector? This is a follow-up question to Relative merits of AES ECB and CBC modes for securing data at rest.

I need to store encrypted Personal Account Numbers (PANs) in a database. The only encryption option I have available is CFB mode with a fixed (0x00) IV. I can choose my cipher, and have chosen AES-256.

Encryption and decryption are performed without the need for the application to 'know' the key, which is stored securely 'elsewhere'. 

For the sake of this exercise, the PANs are 16-byte numbers (16 decimal digits); the attack I'm currently addressing is theft of a copy of the database, with all the encrypted PANs, any of which can be repeated.

I fully understand that the use of a constant IV is a weakness, but this is beyond my control.

Will any of the following options mitigate the weakness?:


I have an 8-byte binary clock available whose contents change once every microsecond or better, and which repeats every ~130 years. I prepend this clock to the plaintext PAN before encryption, and discard it after decryption.
The same, except that I prepend and discard two copies, to complete the first 16-byte block.
I generate 8 bytes of random data and prepend.
I generate 16 bytes of random data and prepend,


Specifically, I should like to know:

a. Are 16 bytes sufficient while 8 are not?

b. Are random bytes sufficient while the µsec clock is not?

c. Do these options completely compensate for the weakness of the fixed IV?



At the risk of flogging a dead horse, some additional comments, following the excellent answers (especially from @D.W.)


I have always agreed to the principle of 'Do not roll your own', but now, even more so.
I think it relevant to point out that these 'messages' never transit, but are only stored 'at rest', and that the attack I'm defending against in this exercise is 'they stole my database'. So I'm not sure what 
D.W.'s chosen plaintext attack is a real eye-opener.
In this scenario (input, charge, store, perhaps retrieve for refund), I'd like to understand better what advantages authentication would bring me.
I'd welcome further comment on using the TOD clock as an IV. Here are some additional details:


The TOD clock is 64-bit integer representing the elapsed time since 00:00 on Jan 1,1900.
The clock is updated in such a way that bit 51 is guaranteed to be updated once per microsecond. Bits 0-51 are the unsigned number of elapsed microseconds.
On faster machines, bits in the range 52-63 are also updated at their corresponding frequencies.
The system in question runs as a single image on a single real machine.
Clock synchronisation is unlikely to set the clock backwards, but let's analyse that case:
If at peak I'm doing 100 encryptions per second (the real number is a lot less), and I assume the slowest clock (1M per second). Let's suppose that the clock gets set back by 5 seconds (I believe that to be extraordinarily extreme. It's GMT, by the way so there's no daylight saving)
Now, I apply the birthday paradox to 1000 encryptions (5*(100+100)) in 5 million; the probability of two or more synonyms is less than 1.3E-7
I recommend that you prepend a random 16-byte prefix.  Prepending a random 16-byte prefix, before encrypting with your CFB mode, will be just as good as using a random IV. The argument is pretty similar to Using CBC with a fixed IV and a random first plaintext block.

If we use CFB with an all-zeros IV and a random 16-byte value prefixed to the message before encryption, as you suggested, we get a scheme that looks like this:

$C_0 = 0$

$C_1 = E_K(C_0) \oplus IV$

$C_2 = E_K(C_1) \oplus PAN$

where $E_K(0)$ is a constant and $IV$ is your random 16 byte value. Since a constant xor-ed with a random value is itself random, the above has the same properties as:

$C_1 = IV$

$C_2 = E_K(C_1) \oplus PAN$

which is the standard CFB construction (with a random IV) with different indices.



Strictly speaking, the 16-byte prefixes don't need to be random.  The above approach is probably secure as long as the 16-byte prefixes are all unique. If you pull 16 random bytes from a well-seeded crypto PRNG, they should all be unique. But I don't trust your other schemes to produce unique values.  Therefore, I don't recommend using any of your other approaches.



Note that while this technique of prepending a random prefix works for some modes, such as CBC or CFB, other modes, such as OFB or CTR are totally broken in such a scenario.