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.