What's the point of the nonce in CTR mode?

Question

Does having a nonce in CTR mode actually improve security (vs. just using 1, 2, 3, etc. - basically a constant nonce of 0)?

As far as I can tell, the best-case scenario security-wise is that the nonce could act as a sort of second key, which would also be shared securely between the communicating parties. But if the underlying block cipher is secure (let's say AES-128), that should be both unnecessary and unhelpful...right?

It seems to me that specifying a nonce only gives a false sense of added security. Am I missing something?

Answer 1

The "nonce" is better known as the Initialization Vector -- with "IV" being the universal short name for that concept. CTR mode works by encrypting the successive values of a counter (CTR stands for "CounTeR"), so the IV in CTR mode is merely the value at which the counter starts.

CTR basically produces a long key-dependent pseudorandom stream, and encryption occurs by XORing that stream with the data to encrypt; in that sense, it is very similar to One-Time Pad, except that the key stream is generated with AES (as a kind of PRNG): this voids the mathematical greatness of OTP, i.e. its absolute security, but it makes the scheme usuable in practice.

Using an IV of value zero is fine... as long as you do it only once. If you reuse a counter value (with the same key) for another run, then you end up with the same thing as OTP where the "pad" is not "one-time". This is a classical break. The idea is that, for a given key, you should consider each counter value as "burnt" whenever you use it. If you do a first encryption run starting with counter value 0, then you will use counter values 0 to, say, 12782 (for instance if the data encrypted that time had length 276525 bytes). If you do not change the key, then you MUST NOT reuse any of the counter values 0 to 12782. The next encryption run with that key ought to start with IV = 12783.

Conversely, sticking to an IV of value 0, always, will be secure as long as you use the AES key only once. This would make sense in an SSL-like protocol, where a connection-specific encryption key is negotiated during an initial handshake, used for that connection, then dropped forever.

---

More generally, most modes of operations for block cipher use an IV (because they have some "running state" which must start somewhere), and the requirements for these IV depend on the mode. CTR can tolerate a fixed IV if you never reuse the key for another run. CBC does not even tolerate that, because a predictable IV can be leveraged for chosen-plaintext attacks.

Answer 2

This is a random guess as I'm not an expert...

To answer the question in the title, "What's the point of the nonce in CTR mode?", I would say that it's to make the protocol stateless. Meaning that both side doesn't need to store any information in order to encrypt/decrypt multiple runs, except the key.

To understand the above statement, let's look at block cipher and some protocol like SSL.

A block cipher is like a function with two arguments, key and input. If you provide the same two arguments (key + input) two times it will always produce the same output.

In SSL, you generate a symmetric key at the beginning that you will use to encrypt/decrypt many different messages. So, one of your argument in the block cipher is already fixed for the whole conversion. This means that you must never repeat the second one or you would produce the same output from the block cipher twice.

Why is it bad to produce the same output from the block cipher twice?

It is bad because it makes you vulnerable to replay attack. If it is ok to produce the same output from the block cipher twice, it means that it is ok for an attacker to resend one of your old message during the conversation and the server will gladly accept it.

So, is this why we need a nonce?

Yes and no.

If you have fixed nonce, you are fine as long as you never reuse the same key with the same counter during the whole conversation which might include many messages. So, both the client and the server need to know the last value of the counter hence they would need to maintain a state.

By using a nonce, we make the assumption that we will never have the same input which is formed by the combination of the nonce and the counter. So, we don't need to maintain any state.