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.

  • 1
    Why not use One-Time-Pads? If your campaign-state fits into 40bits you could as well enumerate levels (or sth. similar). Assign the levels fixed passwords (e.g. "bootcamp" or "frog"). If your game gains attention the level passwords will appear on cheat-websites anyways. – marstato Mar 15 '16 at 18:27
  • Why limit the password length to 8 characters? – Steve Sether Mar 15 '16 at 18:39
  • 1
    @SteveSether As is written in the question: "Longer passwords are far more tedious to write down and key in." – Damian Yerrick Mar 16 '16 at 15:22
  • 1
    A simple XOR OTP is vulnerable to the kind of tampering the OP is concerned about. pencil+paper hacking. Realistically, any modern cipher that supports 32 bit blocks would fit the attacker model, since getting the key is going to be trivial which is MUCH easier than attacking the cipher. Hell, you might even publish the method you used just to take the fun out of "hacking it". An early custom crafted OS at MIT had a "crash system" command for this very purpose. – Steve Sether Mar 16 '16 at 16:25
  • 1
    @MichaelKjörling The attacker model is "bored gamer who likes crossword puzzles". It's not "average developer who might be discouraged by something non-obvious". – Steve Sether Mar 16 '16 at 16:54

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.

  • This paper claims to usually achieve better bounds than the Thorp shuffle. ​ ​ – user49075 Mar 15 '16 at 18:46
  • Beware of patents. RC5 is a patented algorithm, and I'm unsure when it expires. Check if the algorithm is still patented. – Steve Sether Mar 15 '16 at 19:00
  • US Patent 5724428 was filed in 1995 (after the publication of RC5, so that should be a US-only patent) and, as far as I know, patents expire 20 years after being filed, so it should be expired. But, of course, I am not a lawyer and certainly not a lawyer specialized in patent law. – Thomas Pornin Mar 15 '16 at 19:07
  • You're right. The patent expires in the US 20 years after the filing date. I wouldn't be as confidant about patents in other countries. – Steve Sether Mar 15 '16 at 19:30
  • @SteveSether - I think the US is the only country that allows filing of post-publication patents. In other countries, once you publish the work (or ship a product based on the work) without a patent, the work is in the public domain and can never be patented. So Thomas P is saying that it can't be patented in other countries. – Neil Smithline Mar 15 '16 at 22:42

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.