What does counter mean in Counter (CTR) Mode? Is it the same as nonce?

As asked above, what does "counter" mean exactly? Is it the same as nonce?

Also, the book Network Security Essentials (6ed.) from William Stallings states, "Typically the counter is initialized to some value and then incremented by 1 for each subsequent block (modulo $2^b$, where $b$ is the block size)". What does this statement mean exactly?

what does "counter" mean exactly?

Counter per Wikipedia definition;

In digital logic and computing, a counter is a device that stores (and sometimes displays) the number of times a particular event or process has occurred

In CTR context; it is used to produce different inputs for the encryption, then the output is x-ored with the plaintext to produce a ciphertext. It is usually performed by incrementing, though one can use LFSR, too.

Is it the same as nonce

No, it is not the same as the nonce ( number used once)

The CTR mode combines nonce and counter, as the input to the cipher. The input is combined from two parts;

• nonce part; typically generated randomly per encryption session or by use of counter/LFSR.
• counter part; initially set zero, then incremented for every block encryption

With these we can have, randomized encryption and each block can produce a different output under the same key if we are using a PRP like AES ( PRF part is more complex and actually CTR is defined for PRFs since there is no need for the inverse)

"Typically the counter is initialized to some value and then incremented by 1 for each subsequent block (modulo $2^b$, where $b$ is the block size)". What does this statement mean exactly?

Consider that we have 64-bit nonce and 64-bit counter;

 nonce              counter
9237AF71A232BC82E4 0000000000000000

First block uses 9237AF71A232BC82E40000000000000000 as input, then the subsequent block uses as

 nonce              counter
9237AF71A232BC82E4 0000000000000001
9237AF71A232BC82E4 0000000000000002
9237AF71A232BC82E4 0000000000000003
9237AF71A232BC82E4 0000000000000004
 ...                   ...
9237AF71A232BC82E4 EFFFFFFFFFFFFFFF
9237AF71A232BC82E4 FFFFFFFFFFFFFFFF
 ...                   ...
9237AF71A232BC82E5 0000000000000000 ???

If you can encrypt $2^{64}$ blocks you will reach the end of the counter, depending on the case this can be dangerous.

• If you continue from 0 counter 9237AF71A232BC82E40000000000000000 then you will have a nonce-reuse (two-time pad) issue in the CTR mode; confidentiality is lost. An observer can execute a manual crib-dragging even an automized one

  • A natural language approach to automated cryptanalysis of two-time pads

• If you continue increment than 9237AF71A232BC82E50000000000000000 you may hit another input that can turn into the two-time pad, too.

Stop there; actually, stop way before there if you use PRP instead of PRF.

Notes on different usages of the nonce IV term;

• NIST definition uses counter as the whole input for the encryption.

• Wikipedia makes a distinction. I've preferred Wikipedia's definition, In the GCM case, NIST uses IV and counter separately.

• Lindell&Katz, on their book, uses IV as the $3n/4$ part of the block size and $1/4$ as for the counter. The encryption is defined as $y_i := F_k (IV || \langle i \rangle)$ They show that if the IV is uniformly selected then the IV reuse is a negligible event. Therefore CTR mode is CPA secure.

No, the nonce and the counter are certainly distinct terms.

• The nonce is a unique value per message.
• The counter is a unique and sequential value for multiple blocks of the same message.

The nonce can be calculated in any way as long as it is unique. Usually it is either fully randomized, or it is sequential, starting at zero or one.

Although the counter is often specified as separate from the nonce in protocols, implementations usually have a counter that is the same size as the block size. In that case the nonce is part of the most significant bits of the starting counter.

This is reflected by the part of the book that you quote:

Also, the book Network Security Essentials (6ed.) from William Stallings states:

"Typically the counter is initialized to some value and then incremented by 1 for each subsequent block (modulo $2^b$, where $b$ is the block size)".

What does this statement mean exactly?

Let's assume a 128 bit block cipher such as AES. Then let's say that each byte is displayed by a letter, then you have:

 CCCCCCCC_CCCCCCCC = NNNNNNNN_00000000

where each C is a byte in the starting counter and N is a byte within the nonce. The starting counter is often treated as "IV". Now implementations will increase this initial value modulus $2^{128}$: i.e. when it hits $2^{128} - 1$ the next value will be all-zero.

However, that means that after $2^{64}$ increments your counter will increase the rightmost nonce byte, possibly leading to a duplicate counter value. This means that the application itself needs to keep count how many blocks have been encrypted. The reason for this is that the nonce can consist of any amount of bytes, so it doesn't know when the nonce is affected. In other words, the implementations don't know when an overflow into the nonce occurs or when counters collide.

Notes:

• In principle any scheme is valid for CTR as long as the counter does not repeat for the same key. Deriving a new key for each message gives you an almost infinite amount of blocks ($2^{128}$ 16 byte blocks for AES).
• Although the counter is not defined to be either big or little endian, big endian counters seem to prevail. I've come across one protocol that used a little endian counter though - WinZip if memory serves me right.
• The nonce may not be the only element that makes the (initial) counter unique, other data elements may be included in the (initial) counter value. Sometimes an identifier for domain separation is included such as an identifier for the receiver.
• NIST goes into detail about how to construct cipher blocks in NIST SP 800-38a, appendix B, noting at the end that counters are basically protocol specific, and that the uniqueness requirement must be tested separately.

A nonce is a (random/pseudorandom) number used only once. And that is the only limitation to which it is subject. Thus nonce is merely a generic term.

In CTR Mode every value is different to each other and (in general) only used once. Therefore the initialization vector and resulting numbers can be viewed as nonces.

(Note: In some cases authors may explicitly make a distinction between CTR-values and nonces. If that's the case, they may have a different definition or more restrictions to consider)