# Low complexity implementation of a small blocksize cipher (< 64 bit)

Searching for "small blocksize cipher" finds a number of discussions on the topic, mostly refering to FPE.

This one in particular suggests using AES as the round function of a Feistel network.

The problem is on some embedded devices, the use of AES is too complex, so a tradeoff between cipher strength and complexity is required.

In searching for a Feistel based cipher with low complexity, the TEA cipher seems a good choice, but uses 64 bit blocksize.

For a sub 64 bit block of data, say 44 bit, tweaking TEA by masking the output of each Feistel round with a 22 bit mask (0x3FFFFF) seems to work correctly.

The question is, does masking in this way break the TEA algorithm? (other than weakening due to a smaller blocksize)

-
Have you looked at present leightweight block cipher with 64 bit block size? –  curious Feb 15 '13 at 10:27
I think PRESENT is optimized for hardware implementations. I don't know whether there's a variant with a 44-bit block size. If you're OK with a 64-bit or larger block size, Skipjack and RC5 are also worth a look: they're very convenient for embedded microprocessors. –  D.W. Feb 15 '13 at 18:24
@curious Thanks for the tip on PRESENT, i can think of several applications where that would be useful. Unfortunately here am constrained to 44-bits. –  TheLazyEngineer Feb 16 '13 at 13:04
@D.W. thanks, my eyes were lighting up reading about RC5...very simple, should be easy to do a 44-bit version, but.... patented until 2015. –  TheLazyEngineer Feb 16 '13 at 13:04

This will probably be OK. It does have some non-trivial side effects/caveats:

• The effective key length is reduced to 86 bits. Only the low 22 bits of each of the 4 key words will matter, so only 88 bits of the key material are relevant. Then, there are known equivalent-key properties of TEA that further reduce the effective key length to 86 bits.

• A 44-bit block width is uncomfortably narrow. Most modes of operation will have security weaknesses if you encipher more than about $2^{22}$ blocks of data. Even if you encrypt a fraction of that much data, there's still a chance of problems: if you encipher $b$ blocks of data, there's about a $b^2/2^{45}$ chance of some sort of problem.

• Due to the equivalent keys, TEA is not suitable for building hash functions.

Have you considered using something other than a block cipher? Maybe a stream cipher? What are your needs?

-
If D.W. had not before, I would not have voiced the opinion that the proposed scheme is probably OK. But now I simply can second that. –  fgrieu Feb 15 '13 at 16:29
I would consider the $2^{22}$ block limit as a deal breaker, to be honest. That means you can barely encrypt 20MB of data before having to change IV's. But of course it depends on usage. Also, isn't the probability of "problem" more like $1 - e^{- b^2 / 2^{45}}$? I'm thinking of the birthday paradox and probability of a collision, though that doesn't apply for all modes of operation. –  Thomas Feb 15 '13 at 17:19
@Thomas, yes. I agree with everything you wrote. On your question: Yes, $1 - e^{-b^2/2^{45}}$ is a more accurate estimate. However, if $b$ is much less than $2^{22}$, then $1 - e^{-b^2/2^{45}}$ is approximately equal to $b^2/2^{45}$ (using the approximation $e^{-x} \approx 1-x$ when $x>0$ is much smaller than 1). –  D.W. Feb 15 '13 at 18:22
Thanks for the responses. The application transmits a standalone 44-bit message (incl seq no and status bits) approximately every hour. Effectively in ECB mode. The cipher will be a software implementation a 16-bit microprocessor. The main constraint is limited memory. Speed is not a major issue. There will be at most 7 different keys ever used, all generated by me. Based on the transmit frequency, the device will generate less than 2^17 blocks over its lifetime. –  TheLazyEngineer Feb 16 '13 at 13:05
@D.W. I had concluded that a block cipher would be better than a stream cipher because of its avalanche properties. AFAIK, with a stream cipher, bit 13 (for example) could only influence bits 13 to 44. –  TheLazyEngineer Feb 16 '13 at 13:06