I don't understand the following comment in Chapter 2, p. 37 in the second paragraph under "How It Works":

When I look at the implementation of org.bouncycastle.crypto.modes.SICBlockCipher.java, it simply increments the counter (i.e., the IV) each time a block is processed. I don't see anything that would cause it to treat the 4 bytes of counter and 4 bytes of randomizer any differently. I would think that the wrapping would happen after 2^67 bytes (2^64 times the block size).

I don't think the issue is recycling keys so much as preventing simple random access to blocks in the stream. For example, if your counter overflowed into the randomizer part (i.e., > 2^32), you wouldn't be able to access that block by naively reassembling the randomizer and the count (modulo 2^32). If you handled the carry correctly you could decrypt the block. That has nothing to do with key recycling though.

The problem is that once the counter is exceeded you are modifying the bytes representing IV, consequently you are generating the same stream of bytes that you might be if you had used a different IV from the one you initialized the encryption with. The counter must not be exceeded for this reason.

I'm not sure I understand your answer completely, but I think we are arguing different points. I’ve done some digging in an attempt to find some sort of definitive reference for CTR implementation, and the best I can find seems to be: Dworkin, M., "Recommendation for Block Cipher Modes of Operation: Methods and Techniques", NIST Special Publication 800-38A, December 2001.

http://csrc.nist.gov/publications/ni.../sp800-38a.pdf

Appendix B.2 Choosing Initial Counter Blocks seems to be what I’m after. The first paragraph states the basic requirement: In the first approach it describes, all messages are encrypted sequentially. This is the scenario that I have had in mind. In that case, there is no message nonce. My reading of this paragraph is that you can generate 2^counterBits blocks of output.

The second interpretation (which is what I think you are talking about) is that you want to reuse a key for multiple messages, so you divide the counter into two parts. The first part is a per-message nonce (that is expected to be unique for each message exchanged using that key), and the rest of the bits are incremented. I think your point is that you don’t want to overflow the bits that are incremented into the nonce bits since that could generate a counter block that is used by some other message.

I suppose that another way to look at this is that the first approach is just a degenerate case of the second. That is, if:

b – Block size in bits
n – Nonce size in bits
m – Increment parts in bits

b = m + n

You can send up to 2^n messages containing 2^m blocks of data without repeating a counter block. In the first approach, n=0, so you can send one message containing 2^b blocks of data.

Have I got this right?

CTR was also originally known as Segmented Integer Counter mode. If I remember correctly the original proposal came out of Cisco. There's also quite a good discussion on this mode in "Practical Cryptography".

Your reasoning is basically correct though.