There are several well-regarded block cipher modes for authenticated encryption which have made their way into standards and protocols: [CCM](http://en.wikipedia.org/wiki/CCM_mode), [EAX](http://en.wikipedia.org/wiki/EAX_mode), [GCM](http://en.wikipedia.org/wiki/GCM_mode), [OCB](http://en.wikipedia.org/wiki/OCB_mode), …

If I am designing a new messaging or storage protocol which requires both confidentiality and authenticity of the data, how do I choose between these modes? I am specifically interested in the case of whole-message encryption and integrity verification (as opposed to block storage).

I'm after answers like “pick whichever of X or Y is easily available in your programming environment”, or “padding for this mode is delicate to implement, but it is more robust to a broken RNG”.

(This is in the spirit of [AES CBC mode or AES CTR mode recommended?](https://crypto.stackexchange.com/questions/6029/aes-cbc-mode-or-aes-ctr-mode-recommended) for modes that provide confidentiality only.)