Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)

share|improve this question
    
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
add comment

1 Answer

up vote 4 down vote accepted

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?

share|improve this answer
    
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
2  
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
2  
@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
    
@D.W. Thank you, that makes sense. –  Thomas Feb 15 '13 at 18:40
    
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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