I've been trying to find out how the keystream in AES-CTR is generated, but I can't actually figure it out. Wikipedia and any other sites that "explain" it just say the nonce is padded with the counter and encrypted with the key...

So how does it actually work? (As nitty gritty as possible please)

  • $\begingroup$ What parts are confusing to you? The nonce and counter are used as the 128-bit input and are encrypted under a given key, and the "ciphertext" is used as the first 128 bits of the keystream. To create the next 128 bits of the keystream, the counter is incremented by one and the process repeats, i.e. $C_i = E_k(\text{nonce} + i) \oplus P_i$. $\endgroup$ – forest Dec 8 '19 at 4:37
  • $\begingroup$ @forest Specifically, how the nonce and key are added together. One is a series of bytes, and the other an number. And what does the couter start at value wise? 0, 1 or another number? $\endgroup$ – Legorooj Dec 8 '19 at 4:51
  • 3
    $\begingroup$ A "series of bytes" and a number are the same thing. Just think of the bytes being incremented by one. It's just that we're used to base 10 so we say that after 9 comes 10, rather than "after 0 255 comes 1 0". And it starts at zero in traditional CTR, although with GCM mode, which uses CTR internally, it starts at one. $\endgroup$ – forest Dec 8 '19 at 4:52
  • $\begingroup$ @forest ah ok I see that - but say that the nonce is ABCD, or 65, ..., 68. and the counter is 0001. Is nonce + counter $65666768+0001$? $\endgroup$ – Legorooj Dec 8 '19 at 4:55
  • 1
    $\begingroup$ It can be addition or concatenation. CTR usually concatenates, so 0xabcd and 0x0001 becomes 0xabcd0001 (for 32-bit blocks, at least). The next block would be 0xabcd0002, etc, up to 0xabcdffff. $\endgroup$ – forest Dec 8 '19 at 4:56

How the counter and nonce are related is specified in e.g. NIST SP 800-38A: Recommendation for Block Cipher Modes of Operation Methods and Techniques, Appendix B: Generation of Counter Blocks.

I'll list the second approach, as the first approach - just concatenating all the messages - is stupid and really never used:

A second approach to satisfying the uniqueness property across messages is to assign to each message a unique string of $b/2$ bits (rounding up, if $b$ is odd), in other words, a message nonce, and to incorporate the message nonce into every counter block for the message. The leading $b/2$ bits (rounding up, if $b$ is odd) of each counter block would be the message nonce, and the standard incrementing function would be applied to the remaining $m$ bits to provide an index to the counter blocks for the message. Thus, if $N$ is the message nonce for a given message, then the $j$-th counter block is given by $T_j = N \| [j]$ , for $j = 1...n$. The number of blocks, $n$, in any message must satisfy $n < 2m$. A procedure should be established to ensure the uniqueness of the message nonces.

So in bytes you would have NNNNNNNNCCCCCCCC where each character is one byte, with the most significant byte to the left and the least significant to the right. Here N is a byte or octet which is part of the nonce and C is part of the counter.

For AES this means a 8 byte (random, serial or otherwise unique) nonce and a 8 byte / 64 bit counter part, containing a statically sized, unsigned big endian encoding.

Most libraries simply allow any kind of scheme and will treat the 16 byte IV simply as initial counter value, and start counting as if it was an unsigned big endian 128 bit value (note that the increase operation is very lightweight and doesn't need any special big-number magic, you just increase the byte values right to left). So basically the counter is considered CCCCCCCCCCCCCCCC. This is kind of dangerous if you decide e.g. to have a larger nonce and smaller counter, as you may overflow the counter into the nonce at the left of it. So in that case you must make sure that the message size limitations are adhered to yourself.

Usually the counter part is initialized to all zero bits, so that the overflow happens only when the entire counter space is used up.

In principle NIST will allow any scheme that produces a unique counter for each block (for the same key). However, due to common usage, you'll likely not find many counter schemes that uses little endian. Sometimes the nonce consists of different fields though, and some implementations also accept smaller nonces as input variable, that are then placed at the leftmost side (and the counter starting at zero).

  • 1
    $\begingroup$ Decent answer - but I'd point out that I wouldn't have gotten it if it wasn't for my discussion with forest. $\endgroup$ – Legorooj Dec 8 '19 at 6:21
  • $\begingroup$ Well, if you have points on how to improve it I'm all ears. Do you need more examples of binary representations of the numbers? Because if I improve it for you, I also improve it for others, most likely. $\endgroup$ – Maarten Bodewes Dec 8 '19 at 16:47
  • $\begingroup$ True - I'll suggest an edit soon. $\endgroup$ – Legorooj Dec 8 '19 at 21:44
  • $\begingroup$ Actually the easiest way to improve would be to add a "layman's terms" section at the end, similar to what @forest suggested. That way, it's explained very simply for the ones that don't get the the rest, and for the ones that get the rest, they needn't actually read it. $\endgroup$ – Legorooj Dec 8 '19 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.