> CBC mode does require > random nonces, other modes may be fine with even sequences as long as > the values are not reused.
I disagree that CBC mode requires random nonces, at least based on what NIST has published. They only require that the IV (not the nonce) must be unpredictable per [1]:
" For the CBC and CFB modes, the IVs must be unpredictable."
The unpredictable IV can be generated from a non-random nonce including a counter:
"There are two recommended methods for generating unpredictable IVs. The first method is to apply the forward cipher function, under the same key that is used for the encryption of the plaintext, to a nonce. The nonce must be a data block that is unique to each execution of the encryption operation. For example, the nonce may be a counter, as described in Appendix B, or a message number."
