When would we need a bigger IV than 2 bytes when the IV is derived of a master key?

Question

As an example, let's take a simple situation where AES-256-CBC with IV + MAC is used to encrypt a given plainText to offer both authentication and prevent identical cipherTexts.

iv.mac1.cipherText(plainText)

The keys are derived using HMAC for simplicty (alternatively could be HKDF)

masterkey = [32 random bytes];
encryptionKey = hmac_sha256(masterkey,'encryption_key');
mac = hmac_sha256(masterkey,'mac_key');
ivInput = [2 random bytes];
iv = hmac_sha256(masterkey,ivInput);

Would this already deliver enough 'randomness' for almost any messaging system, since with 2 bytes the chance of arriving at an identical cipherText with an identical message would already be around 0.002% (1/(256*256)*100)?

(256 possibilities per byte, 2 bytes used for IV)

Answer 1

Would this already deliver enough 'randomness' for almost any messaging system, since with 2 bytes the chance of arriving at an identical cipherText with an identical message would already be around 0.002% (1/(256*256)*100)?

Actually, with 100 messages, there are $\binom{100}{2} = 4950$ pairs of messages, and so the expected number of pairs of messages with identical IVs (which is not precisely the same as the probability that there will be two messages with the same IV) is circa 0.0755.

And, for any such pair of messages with identical IVs, it would leak (at the very least) whether or not the first 16 bytes are identical.

I am of the opinion that a 7% probability of leaking this amount of information is too high, even if you are limited to encrypting only 100 messages (and many systems will end up encrypting far more)