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.

I've had many questions on Stackoverflow on how to minimize the output of a cipher - during encryption of course - to the same size as the input. Obviously this is possible for a single block of plaintext, but it gets harder when the plaintext size is larger than one block. Using a stream cipher is possible, but you would need some kind of IV, and some place to store or derive the input data for the IV.

For now I am just looking for answers regarding confidentiality (authentication/integrity may be disregarded). Furthermore, I would like to focus on input that is bit or byte aligned and cannot be compressed. Obviously it would be nice to have obviously distinct results when using a different plaintext, even if it starts or ends with blocks of identical data. The key size should be manageable, say a maximum of 64 bytes.

Currently I presume that the best result can be achieved using a stream cipher and a nonce encoded to the minimum of required bytes. So then the encoded nonce would be the only overhead.

Note that I am very much aware that the solution space may be empty. In that case I very much would like to have this confirmed.

share|improve this question
2  
That's Format Preserving Encryption. See e.g. this and this –  fgrieu Feb 22 '13 at 14:07
add comment

1 Answer

up vote 3 down vote accepted

As @fgrieu mentioned, what you're after is FPE. The papers he linked deal with FPE on a very small domain, but it looks like you're interested in encrypting longer strings.

For that, you need a wideblock cipher. Unlike traditional blockciphers, these typically allow different input lengths, which is a plus. They meet your criterion of not revealing shared (pre/suf)fixes. Examples (any of which will be secure): EME, EME2, HTCR, HEH, TET, PEP. Tracking down a good implementation might be problematic; I don't know any off hand. Some, including EME/2, are patented (but can be liscenced under "reasonable, non-discriminatory" terms). Depending on the mode, they operate at roughly half the speed of standard encryption algorithms.

In terms of providing confidentiality, a result by Bellare and Rogaway ("Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography") shows that you get it for free as long as you can guarantee that all plantexts are distinct (e.g., they already have distinct sequence numbers encoded into them somehow). The only information these ciphers leak is plaintext length, and whether or not a plaintext is repeated.

You said authenticity was not a concern, but perhaps it's worth noting that you can get this fairly cheaply if the plaintext contains some type of redundancy that you check upon decryption.

Finally, these algorithms are tweakable ciphers, which means the take an additional input, called the tweak. You can use (meta)data from any accompanying headers as the tweak (or just used a fixed string). Again, if the tweak is distinct each time, then you have confidentiality even if a plaintext is repeated. But at that point it might be easier to, e.g., take a 64-bit nonce from the headers and use that as the high-order bits of a counter-mode IV.

share|improve this answer
add comment

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.