What cipher mode is suitable for independantly decryptable short messages? I'm building a small VoIP client which transmits encrypted audio data via UDP, and some packet loss is expected, so each packet will need to be decrypted separately even if others in the stream don't arrive. I also don't enforce strong ordering of data, since re-ordering is done only if a packet is significantly out of step.

I know some modes like CBC require the previous ciphertext block to be known in order to decrypt the next block, so I don't see that being suitable. ECB is ideal in terms of the "decryptability" requirement, but obviously it's not secure. I figure OFB might be useful, but I can see the implementation being awkward if multiple blocks are skipped.

Are there any modes of operation that suit this kind of scenario, without significant implementation overheads?
Reflex answer: EAX. EAX does encryption and authentication, with minimal space overhead. EAX also has light requirements on the IV: it just needs a non-repeating value, so a simple counter can work. Possibly you already have a suitable counter or time stamp in your packets, that can be used as IV.

About replay attacks: you already expect that some packets will be dropped, or reordered. Be warned that if your protocol tolerates it, then the attacker can force it upon you, mechanically. I suppose that your protocol already includes some sort of frame counter so that you can reject frames which are too old (or too new !) and merge duplicates. That frame counter would work nicely as an IV for EAX.

If you want to do it old-style, use CBC with a random IV (IV must be transmitted along the packet), and then a MAC (HMAC, for instance) computed over the encrypted data (including the IV) and appended to the packet. You will need more code, cryptographically strong generation of an IV for each packet, and space overhead is likely to be higher than for EAX. That's the price of being old-style.