How to enhance randomness of AES?

Question

I'm using PHP to encrypt a string and Java to decrypt it on a remote server. To perform the encryption, I'm using the strategy that can be found here.

My problem is that the strings I encrypt are pretty small and very similar each other. Nevertheless, I'd like a high degree of randomness in the encrypted values.

Just to be clear, at current this is what happens:

$$encrypt(foo1) \rightarrow barA$$ $$encrypt(foo2) \rightarrow barB$$

While I'd like something like:

$$encrypt(foo1) \rightarrow b3SA$$ $$encrypt(foo2) \rightarrow 4FrB$$

How can I enhance the randomness of the encrypted values, by keeping the algorithm I'm already using?

Answer 1

If you are doing things right, then you will get the level of randomness you are after. Translation: you are not doing things right. You use AES with CFB8 mode, which requires a random initial value. The initial value is a 16-byte string which should be generated randomly and uniformly, and a new IV shall be generated for every single encrypted message. Since you need it for decryption, the IV for an encrypted message shall be stored/transmitted along with the said message.

Failure to use a new IV for each message results in a wide range of weaknesses, including what you are witnessing right now (if two strings begin with the same characters, the resulting encrypted strings will also begin with the same bytes).