Can we still use 64-bit block ciphers?

Question

After thinking a lot about 64-bit block ciphers, I ask a question here.

Most proposed block ciphers these days seem to have a block size of at least 128-bits.

Also, I know that when using a 64-bit block cipher with an operating mode (e.g. CBC or CTR), there is a high probability of a collision when about $2^{32}$ blocks of data are encrypted (by the birthday bound).

This is where my troubles begin. I'd love to hear your thoughts on these.

1. I think there is no problem if 64-bit block ciphers are used in devices or protocols that process small amounts of data, such as embedded devices. Encrypting $2^{32}$ blocks of data on such a device is practically unlikely. In particular, I know that short message processing speed was judged to be important in the recent NIST LWC project (Ascon selected as the final algorithm).

2. If the key changes frequently in the protocol itself, I don't think there will be any problems. For example, changing the key every time we encrypt $2^{16}$ blocks of data.

3. I think it's okay to use 64-bit block ciphers in environments that value efficiency. Even if there is a fast 128-bit block cipher, a well-crafted 64-bit block cipher (PRINCE, PRIDE, Midori, etc.) is expected to be faster (AES with AES-NI support may be faster than 64-bit block ciphers).

4. We may have to worry about quantum security (64-bit block ciphers are seriously weak), but I don't think we would consider applying 64-bit block ciphers in an environment where we have to worry about quantum security.

Answer 1

1. I think there is no problem if 64-bit block ciphers are used in devices or protocols that process small amounts of data, such as embedded devices.

Embedded devices can still be pretty fast. I'd say that you would be relying on system security rather than algorithm security. If the algorithm would not have any problems then system security would be less of a problem.

Encrypting $2^{32}$ blocks of data on such a device is practically unlikely.

Two things: 1. citation required. It depends on the system. Furthermore, this assumes that after $2^{32}$ blocks of encryption there suddenly is a problem. That's not correct; the chance of a collision is relatively high before that (depending on the mode of operation of course).

In particular, I know that short message processing speed was judged to be important in the recent NIST LWC project (Ascon selected as the final algorithm).

This is not good reasoning, you're trying to balance security vs efficiency here. Given the question, I'd say that this is trying to excuse any possible problems. This is indicative of the whole way that you ask these questions.

---

2. If the key changes frequently in the protocol itself, I don't think there will be any problems. For example, changing the key every time we encrypt $2^{16}$ blocks of data.

You'd have to integrate a counter that is increased before you do any block encryption, and usually such a thing is not present. The system has to e.g. account for broken packets and such that require a repeat of previously send messages and such. Again, these are requirements put on the system, and the reason they are required is because the block cipher is less secure.

---

3. I think it's okay to use 64-bit block ciphers in environments that value efficiency.

It really seems you've already made up your mind. That's OK, but just asking for confirmation isn't useful.

Even if there is a fast 128-bit block cipher, a well-crafted 64-bit block cipher (PRINCE, PRIDE, Midori, etc.) is expected to be faster (AES with AES-NI support may be faster than 64-bit block ciphers).

Yes, there may be more efficient ciphers than 128 bit ciphers for very small message sizes. On systems with AES-NI I would not expect that this kind of efficiency plays any part though, so I'm not sure why you'd include that.

Note that it is perfectly possible to encrypt a message smaller than the block size using a 128 bit block cipher.

---

4. We may have to worry about quantum security (64-bit block ciphers are seriously weak), but I don't think we would consider applying 64-bit block ciphers in an environment where we have to worry about quantum security.

That depends on what data you're trying to protect. Blanket statements like these are not useful at all as they are reversing the reasoning: we're using a 64-bit block cipher so quantum security is moot. That's not the way the world works, sorry.

Conclusion

I'm not saying that 64-bit block ciphers are not or cannot be useful. I'm however 100% certain that the method of reasoning used in the question isn't useful at all. It basically reasons for 64-bit block ciphers and then asks for a blanket confirmation. If 64-bit block ciphers are considered then a use case specific risk analysis should be performed.

Answer 2

I think there is no problem if 64-bit block ciphers are used in devices or protocols that process small amounts of data, such as embedded devices. Encrypting $ 2^{32} $ blocks of data on such a device is practically unlikely.

There are lots of embedded devices where encrypting $ 2^{32} $ blocks is very common. Think about Wi-Fi or Bluetooth chipsets. It's very common to underestimate the amount of data that will be sent over a connection, and WEP had a giant vulnerability because of that (its nonce was very small).

Also, $ 2^{32} $ blocks is not some magical limit where security suddenly gets much worse. The chance of collision increases as more blocks are encrypted.

In particular, I know that short message processing speed was judged to be important in the recent NIST LWC project (Ascon selected as the final algorithm).

You're assuming that a 64-bit block cipher is somehow more performant for small messages than the alternatives. Whether that is true is highly dependent on the system and the hardware.

If the key changes frequently in the protocol itself, I don't think there will be any problems. For example, changing the key every time we encrypt $ 2^{16} $ blocks of data.

This requires keeping extra state and it requires more key management that must be tested. It also may require an expensive rekey operation more frequently for security. If your concern is embedded devices, this may be impractical, since rekeying is not always possible (think EMV cards, which definitely can encrypt that much data).

I think it's okay to use 64-bit block ciphers in environments that value efficiency. Even if there is a fast 128-bit block cipher, a well-crafted 64-bit block cipher (PRINCE, PRIDE, Midori, etc.) is expected to be faster (AES with AES-NI support may be faster than 64-bit block ciphers).

That may be your opinion, but I tend to disagree. In many environments, including many embedded devices (e.g., Wi-Fi and Bluetooth chipsets, EMV cards, and transit cards), AES is used and is standard. Oftentimes, those devices have some sort of hardware instructions for it, so it's going to outperform virtually everything else.

Even if you don't have AES hardware instructions, you have alternatives to 64-bit block ciphers such as stream ciphers like ChaCha20 (or ChaCha12) or AEADs such as Ascon. Implementing Ascon also gets you a cryptographic hash and other goodies effectively for free, since they all use the same permutation. Unless you absolutely need a block cipher (and if you're using CBC or CTR, you probably don't), those can be fast, secure alternatives that can provide 128-bit or better security using a simpler design without the downsides of a 64-bit block cipher. Simpler designs (given equivalent security) are good because they reduce the risk of unintentional (and possibly security-sensitive) error.

I'm not saying that there are absolutely zero cases where a 64-bit block cipher is the right choice. I'm just saying that with reasonable forethought about the implementation and design of the system, there are very frequently better alternatives.