Note that I'm not saying use SIV. I'm just saying that SIV already does the extended nonce part:

> The AEADs defined in this document calculate fresh AES keys for each nonce.

I guess write an RFC for extended nonce only?