Why doesn't CTR mode require blocking?

I've been reading a bit about block cipher modes and I have a relatively straightforward question regarding CTR. In essence, I was hoping you guys would be kind enough to validate my understanding of things.

As I understand it, CTR does the following:

1. Take the first output of the nonce (let us assume an incrementing int for our purposes)
2. Encrypt the nonce with the key. CTR requires that the key and the nonce be of identical size.
3. Perform some lossless operation between encrypted nonce and a portion of plaintext (e.g.: XOR)

4. Increment nonce

Here's what I don't understand. CTR is supposed to transform a block cipher into a stream cipher, but don't you still have to operate block-by-block for step 3?

What am I missing?

-
"CTR requires that the key and the nonce be of identical size" No. The nonce size corresponds to the block-size, but the key-size is completely independent. For example AES-256 has 128 bit blocks (and thus nonces) but a 256 bit key. –  CodesInChaos Nov 5 '12 at 12:48
@CodesInChaos, When you say "block size", are you referring to the encryption of the nonce with the key? In other words, for AES-256, we use two 128-bit nonces? I'm afraid I don't follow... –  blz Nov 5 '12 at 14:02
The nonce is incremented as a counter and each counter is encrypted separately, which means each keystream block is independent of the other (you can jump to, say, the 3847th block by incrementing the initial counter by 3847 without having to compute any previous keystream blocks). –  Thomas Nov 5 '12 at 19:17
@blz With AES-256, we encrypt each 128-bit nonce with a 256-bit key. The block size of AES is 128 bits, in all variants. The key size varies between 128, 192, 256. –  Paŭlo Ebermann Nov 5 '12 at 20:25
Yeah, it is another question. Have a look at my answer to a similar question. Also have a look at What is the effect of the different AES key lengths?. –  Paŭlo Ebermann Nov 6 '12 at 20:45

While you do operate block-by-block when generating the pseudorandom stream, the actual encryption step (i.e., the XOR) is bitwise, and therefore does not require the message to be padded.

For example, the message "Hello" will be processed as follows (pseudocode):

byte stream[16] = AES(Key, Nonce);
byte plaintext[5]  = "Hello";
byte ciphertext[5];
for i from 0 to 5:
ciphertext[i] = plaintext[i] XOR stream[i];


The remaining bytes of the pseudorandom stream, beyond the length of the message, are simply discarded.

-