What's the consequence of having a short IV? Is one mode better in that case?

Question

I've read lots about null-length IVs being bad for most modes. In a scenario where passing a 128-bit IV along with each message isn't feasible, how would generating the IV from a smaller passed-along value impact the strength of security?

Each user will have their own symmetric key that does get re-generated periodically (maybe only hundreds or thousands of messages for each key, each message maybe hundreds or rarely thousands of bytes). If I randomly generate 16 or 20 bits, hash that using SHA-256 and use the first 128 bits as an IV, how does that impact the overall security? Is it now in effect 16 or 20 bits?

Would adding additional information – that both the server and the user know – into the hash help? Are there modes that would be better than others for this scenario? I've read about Synthetic Initialization Vector (SIV) mode being resistant even if there's no IV, however from what I understand it generates a tag of the block size which defeats my purpose. Can’t I send the tag and still encrypt, while only losing authentication?

Answer 1

The point of the IV is to prevent the same (key,IV) from ever being used for two different messages in practice. This is an absolute requirement for stream ciphers or block cipher modes such as CTR that are effectively stream ciphers, because re-using the same (key,IV) pair lets an eavesdropper trivially obtain the XOR of two plaintext messages, which means they are effectively decrypted. Other modes behave somewhat differently, but the IV requirements for a mode are generally non-negotiable, and security is broken if they are not followed.

With a smaller IV, the chances of using the same (key,IV) go up dramatically. Hashing a low-bit value as you suggest does not fix this problem at all, as there are only 65k IVs possible with a 16 bit counter.

If your application cannot handle transport of at least 96 extra bits with each message, you should exchange an "IV seed" at the start of your protocol, then each side can use that as the state for a CSPRNG and generate the IV for each packet on its own. Using something like HASH-DRBG is probably simplest, you start with your IV seed, concatenate a counter with value N, hash and use the output as the IV for packet number N. Making this scheme tolerate packet loss while never ever repeating (key,IV) is left as an exercise for the reader; see the ChaCha TLS draft RFC as an example of how packet sequence numbers are used to generate IVs. https://datatracker.ietf.org/doc/html/draft-mavrogiannopoulos-chacha-tls-02