Choice between appending or prepending nonces to ciphertexts

Question

I understand that when using CTR mode it is usually secure to append or prepend the nonce to the resulting ciphertext, whether the nonce is before or after the ciphertext being unimportant.

However, I am making another home-brew protocol (the bad thing that always happens from time to time), which led to the following scenario:

I chose XChaCha20Poly1305, the best AEAD primitive I could get my hands on, as the encryption primitive. I must give up the actual user control of the encryption key, and the nonce cannot be reliably stored persistently, so I chose to generate the nonce randomly. The resulting ciphertext will then be fed into another deterministic encrypter, say AES-CBC with a constant key (burnt into the chip and cannot be changed in the device's lifetime) and zero IV, over which I have completely no control. The final result will then be sent over the wire.

Does the sequence in which the ciphertext is formatted matter? I have no idea whether the device's RNG is broken or not, nor can I choose where to place the authentication tag in relation to the ciphertext.

If it is $$ nonce || Enc(key, plaintext) || tag $$ then in case of a RNG failure, the security is undermined; and if the extra encrypter is broken, the system fails completely. But if it is $$ Enc(key, plaintext) || tag || nonce $$ then the extra encrypter might provide a bit of security or even make most security claims hold, even in case of a RNG failure.

Many limitations are involved here, and this might be complicated question, but I hope someone can shed some light on this question for me.

Answer 1

The order of the tag, the nonce and the ciphertext doesn't matter at all. Any encoding would perfectly fine, since what gets authenticated is the data itself and not the way it is encoded for transport.

Now, if you can't use counters, and you don't trust the PRG, you may end up reusing nonces, no matter how they are encoded.

You should either use a nonce-misuse resistant scheme such as AES-GCM-SIV, or use a KDF to create the nonce from the ciphertext, some output from the PRG, and a secondary key.

Answer 2

You place the nonce first. Why? It has nothing to do with security. It is because it is the first piece of information you have, the ciphertext cannot be created or decrypted without it.

Imagine the following:

You need to encrypt a piece of information, and the recipient needs to decrypt it. You are able to transmit the message in 60s, and the recipient is able to decrypt the message in 30s.

If the nonce is not available to the recipient until AFTER the ciphertext is received, there is no work that can be done until the entire message is received, and the plaintext will be available to the recipient 90s after transmission is started.

If the nonce is available immediately, the recipient can decrypt the message as the ciphertext arrives. Since the decrypt speed is twice the transmission speed, the message should be decrypted almost immediately after the ciphertext transmission is complete. The plaintext will be available to the recipient 60s after transmission is started.

In your case, since you are wrapping the output with CBC (probably), the wrapper can also be decrypted as soon as it is received, putting the nonce at the end would only serve to prevent decryption until the entire message is received.