Why does DES use a block size of 64 bit? Why do we use 64 bit as block size for the DES algorithm? Is there a reason not to use another block size, for instance 72 bits?
A minimum block size is required for a block cipher mode of operation to be considered secure. If the block size is too small then issues may arise.

Many modes of operation for instance use an IV that has the same size as the block size. If the block size would be smaller then a randomly generated IV could repeat. This will happen quickly especially if many messages are encrypted using the same key.

Worse, a mode such as CBC uses the last ciphertext as vector for the next step, so the ciphertext could repeat as well, which means that the ciphertext could leak information about the plaintext. For counter (CTR) mode the counter could start to repeat, which could lead to a complete loss of confidentiality of the plaintext message.

So using a block cipher with a small block size will lead to security issues, even if the block cipher itself is considered secure.



On the other hand a block should not be too big. Larger block sizes require a more complex cipher and likely require more internal state. This is especially a problem if space is an issue, and space always is for hardware implementations of the block cipher.

Also note that modes of operation always require at least one operation of the full block cipher for the last bytes of the message. So if 1 byte is encrypted the full block cipher still needs to be executed for that single byte. Many modes of operation output a multiple of the block size, so there may be additional storage / communication overhead for larger block sizes (on top of the larger IV). 

So using a block cipher with a larger block size will increase the memory requirements and as well as the CPU and storage overhead required for the ciphertext.



To simplify calculations, enhance memory efficiency (alignment) and so forth, many computer algorithms perform operations using powers of two. Although it would probably be possible to specify a block cipher as an algorithm of 65 bits the algorithm and implementation would be tricky to design correctly. Ciphers are generally specifies using byte boundaries and preferably using powers of two.

Furthermore, it makes sense to make the (encoded) key size and the block size match up. That way it is easy to encrypt one key with the other. A DES key consists of 56 bits and 8 parity bits. That means that a 64 bit DES key can be directly encrypted (wrapped) by another DES key, without requiring any mode of operation.

AES-192 - which has a key size of 192 bits and a block size of 128 bits - is awkward to correctly use because 192 is not a multiple of the block size of 128 bits.



In the end the block size is selected by the designers with the above three points in mind. The block size is therefore a compromise between security and efficiency.



Modern ciphers do not use a block size of 64 bits anymore; most cryptographers would consider 64-bit block ciphers outdated. They may not be broken, but the 64 bit block size makes them insecure in many situations. Single DES is of course considered broken, mainly because of the small effective key size.

AES has a block size of 128 bits, as this was mandatory for every AES candidate during the AES competition. But even 128 bits is sometimes considered not that secure anymore. Counter mode encryption and many authenticated ciphers that rely on it have limitations, mainly when the 128 bits are used for different purposes (a 64 bit random nonce and 64 bit counter, for instance).

So other block ciphers even use a larger block size. Threefish (which is part of Skein, one of the SHA-3 candidates) uses a block size of 256 bits. This helps it being used as a tweakable block cipher within the Skein hash algorithm.

With Blowfish using 64 bit block size, Twofish using 128 bits and Threefish using 256 I guess you can see where we're heading. That said, a block size of 256 / 512 bits may be large enough for most purposes, so this trend to larger block sizes will likely not continue forever.



Note that many modern CPU's have been designed with 64 bit and SIMD operations and may be more efficient for larger block sizes and / or larger internal state. So a smaller block size may not always be more efficient; for instance SHA-512 is commonly both more secure and faster than SHA-256 on a CPU with an AMD64 instruction set, especially for large messages.