Repeated NONCE in CTR mode

Question

My understanding is that, in CTR mode, the NONCE must be unique because, if a NONCE is reused, multiple plaintexts will be XORed with the same value and this gives an attacker leverage to decrypt the data.

If you have a situation where it is hard to guarantee that the NONCE will always be unique, but you have a fast (whatever that means in your context) encryption implementation, can I take away the leverage that repeated NONCES give by adding an additional encryption step the normal CTR mode process?

E.g. replace

AES256(key, NONCE) XOR Plaintext

with

AES256(key2, (AES(key1, NONCE) XOR Plaintext))

I understand I loose CTR mode's ability to work with arbitrary length plaintexts (which is fine for me, I'm happy working in blocks), and that I have doubled the amount of encryption I need to do, but I think this retains the advantages of CTR mode (as opposed to ECB mode) while gaining some protection against repeated NONCEs.

Is this approach valid? Is there a lighter way to gain some protection against repeated NONCEs?

I am focusing on CTR mode because my communication channel is not necessarily reliable and I worry about the need to "resync" if I use any of the chained modes.

Answer 1

This would be better than simply CTR if your nonces do collide, but it is still not very good.

Suppose you use the same IV for two messages $m_0||m_1||...m_n$ and $m_0'||m_1'||...m_n'$ where all the $m_i$ are 128-bit blocks. Each block is XORed with the same keystream value as the corresponding block in the other message. They then pass through AES, the same as in ECB mode. If any $m_i=m_i'$, they have the same ciphertext, so the cipher leaks information about the message.

SIV mode would be closer to what you are looking for. It should be approximately as fast, though it does require two separate passes over the data. In the case of nonce reuse it leaks the equality of the (complete) messages, but no further information.