The block size of a symmetric cipher will generally be in the neighborhood of the key length. You can imagine the problem if you had a 128-bit key but an 8-bit block size -- for each of the 256 possible inputs you would have only 256 possible outputs. There would be multiple keys that produced the same mapping and you could produce every possible mapping with only 65536 keys. So the block size needs to be near the key size. Making it larger than that wouldn't make it any more secure but would make it slower.
This doesn't sound right to me. There are 256! permutations of the set {0, 1, 2, 3, ..., 255}. 256! is much bigger than 2^128, so I see no reason that each key cannot produce a unique mapping.
> So the block size needs to be near the key size
Note that AES-256 has a 256 bit key, but the block size is 128 bits, which is not near the key size.
I believe that the main constraint on block size is that a small block limits the length of messages you can safely encrypt with a given key. If the bad guys see a lot of cipher text encrypted with the same key, they have a better chance of a successful attack. What "a lot of cipher text" means depends on the block size. The bigger the block size, the more cipher text is needed to constitute "a lot of cipher text".
A smaller block also gives you less room to maneuver when designing modes of operation; for instance, it can be tricky to implement CTR with a 64 bit block --- the convention is to split the block into "counter" and "nonce", and you need enough space for the counter that it can't conceivably wrap.
This may be a stupid question, but why is there a convention to split?
I saw that in set three of the crypto challenge, as well, and wondered.
Is it so that you can always start counting at zero when re-starting the application, as long as you're randomly picking a new nonce?
And if you just picked a random counter value at each restart you might get very unlucky and at some point reuse a counter value, so by this convention you're separating counter values belonging to different restarts?
Conventions and usage vary by setting, but yes, it's to prevent nonce reuse.
A typical scenario might use a single encryption key for many different messages. A simple strategy is to allocate 64 bits to a message counter and 64 bits to a block counter. For each encryption you can increment the message counter by one. The block counter starts at zero and increments for each block of the message.
Note that this imposes hard limits on both the number of encryptions you can perform with this key (2^64) and the number of blocks a message can contain (also 2^64). As long as we respect these limits, we're guaranteed never to reuse a nonce.
If we use a random 64-bit nonce in place of the message counter, the picture changes a little. Due to the birthday paradox, we can now expect a collision in around 2^32 encryptions, which is a little close for comfort.
Fortunately, we can tune the bit allocations based on the needs of the application. So a reasonable strategy might be to bump the random message nonce to (say) 96 bits and leave 32 for the block counter. This still allows individual messages of around 64GB.
Of course, parameters like these should be considered implementation details for 99% of application developers. The best thing to do is to use a high-level library like NaCl that makes reasonable choices and then abstracts them away.