Which block cipher for a very short (40-bit) message?

Question

Question:

I'm trying to encrypt a 32-bit message to produce a ciphertext no longer than 40 bits. Are there vetted block ciphers or other good ways to encrypt very short messages? Are there any well-known ciphers with a block size this small?

---

Context and motivation:

Video games for retro platforms may have a campaign longer than one sitting but no nonvolatile memory for storing the campaign's state. To continue a campaign across a power cycle, the game issues a "password" and has the player enter it next time. This password is a short encrypted message containing the state of a campaign plus some extra bits used to ensure that randomly entered passwords or passwords with a few bits flipped are unlikely to work. For this application, the 32-bit message includes which chapter the player is on, quest flags, money, experience, and the like. A typical password has 8 characters with 32 possibilities (5 bits) per character (digits, consonants, and hyphen), for a total of 40 bits. Longer passwords are far more tedious to write down and key in.

I'm unaware of any well-known cipher with such a short block size. Ciphertext stealing works when is longer than one block but not an exact multiple of a cipher's block size. For example, if there were a 32-bit block cipher, one could encrypt the first 32 bits and then the last 32 bits, which touches the middle 24 bits twice. But as far as I can tell, it doesn't apply to a message shorter than a block. So currently I'm using a homemade cipher (yes, eww) with a structure inspired by XXTEA, with five 8-bit words instead of several 32-bit words. After packing the campaign's state into the first 32 bits, I pad the remaining bits with a constant before encryption and reject passwords where the padding does not decrypt to the desired constant. Is there something better for a 40-bit block than rolling your own?

Encryption and decryption need to run on an 8-bit microprocessor in under a million cycles. I'm worried about online attacks and pencil-and-paper attacks by bored gamers, as have been posted in the "Classified Information" section of Nintendo Power magazine. But I'm not quite as concerned about automated attacks by someone reading the algorithm and symmetric key out of the game's code and using this information to put a password generator on a website, as this would take conscious effort on a player's part to cheat at the game.

Answer 1

The generic name for that kind of stuff is format-preserving encryption. The Thorp shuffle is a nice candidate, provided that you use an adequate round function (e.g. truncated output for a cryptographically secure hash function) and enough rounds, as indicated in the paper.

That being said, with 1 million cycles on an 8-bit computer, it may be hard to run, say, a 64-round Thorp shuffle with a truncated SHA-1 as round function.

Unfortunately, there is no standard, well-studied block cipher with short blocks and good performance on small architectures. On the other hand, your attack model states that attackers won't try really hard, so you don't need absolute crypto-grade security; a construction which is academically weak may still be strong enough for you.

I suggest you skim through this page that lists "lightweight block ciphers" with some analysis. Some of them offer 32-bit block size. What you need is such a block cipher, such as there is a known attack on a reduced number of rounds, thereby indicating that some cryptographers tried to break it, and did not succeed for the full cipher. From a cursory look, at least KATAN, KTANTAN, SIMECK-32, SIMON-32 and SPECK-32 match these criteria; RC5 might also be usable with an adequate number of rounds.