How is the keystream actually generated in AES CTR 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)
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 &lt; 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).