Deterministic nonces in CTR mode

I want to encrypt a file with AES in CTR mode. I have a 256 bit master key and the file. Given these, the encryption must be deterministic, so I can't use a random nonce in the usual way. Fortunately the master key will be unique¹.

My original plan was to simply set the nonce to 0. Assuming no collision happens when deriving the 128 bit AES key from the master key, this should as secure as conventional CTR, where the nonce is prepended to the message.

An alternative plan is to also derive the nonce from the master-key. This seems to offer two advantages:

1. It makes key-nonce pair reuse more unlikely, since now they have 256 bits and not just 128
2. It prevents some kinds of known-plaintext attacks, since the attacker now doesn't know the content of the counter-stream, effectively turning the nonce into some kind of secondary key.

Is there a problem with either scheme? Is the second scheme better than the first?

¹ assuming the 256 bit hashfunction I use is collision free

-
There is already a question about the first scheme, so this question is mainly about the second scheme. In particular how it compares to the first scheme. – CodesInChaos Apr 16 '12 at 12:54
One problem with constant IV is that it enables multi-target attacks. When using AES-128 an attacker you can break all messages encrypted with this scheme with $2^{128}$ work and break one random message cost only $2^{128}/t$ for $t$ known ciphertext. So I'd avoid constant IVs with 128 bit keys, but 256 bit keys it doesn't really matter. – CodesInChaos Oct 29 '13 at 8:04

1 Answer

Assuming that you can indeed guarantee that the keys will never be reused, both schemes should be secure.

The only requirement for the nonce in CTR mode is that it must be unique (and, if used directly as the initial counter value, not equal to any intermediate counter value used in the past or in the future). If you're only encrypting one message with a given key, the nonce $0$ is as unique as any other.

As you correctly note, your second scheme provides somewhat less information to an attacker who can guess some of the plaintext. (Reading between the lines in your question, I'm assuming you're not planning to store the nonce along with the ciphertext, but to re-derive it from the master key on decryption.) Whether it's "better" is hard to say — it only makes a difference if the cipher you're using is broken, and at that point it will depend on just how it's broken — but it's at least unlikely to be worse.

-
The AES key will be as unique as random 128 bit numbers are. It's derived from the hash of the plaintext file, optionally combined with a password. – CodesInChaos Apr 16 '12 at 10:16
Pardon for asking, but how are you going to get the hash of the plain text file before you have decrypted the cipher text? It's obviously not a good idea to append a deterministic hash of the plain text to the cipher text, since it will trivially reveal information about the plain text. – Henrick Hellström Apr 16 '12 at 10:41
@HenrickHellström You need to get that hash for an outside source, typically it's part of the download link. This is a scheme similar to freenet's CHK or tahoe-lafs immutable files. – CodesInChaos Apr 16 '12 at 11:57
@HenrickHellström How does a hash trivially reveal information about the preimage? (For a hash with "good" properties such as SHA256) – MartinSuecia Apr 16 '12 at 12:00
@MartinSuecia: Well, for instance the hash will not change if the plain text doesn't change, so the adversary will know if the file at the other end has changed or not. This is a piece of information that a properly used confidentiality mode will hide (with the exception of information about the maximum length of the plain text). – Henrick Hellström Apr 16 '12 at 12:05