I want to encrypt data and protect its integrity and confidentiality. However, I cannot increase the length of the data.

Are there any cipher modes of operation which provide confidentiality and integrity protection without increasing the length of the ciphertext?

-
To clarify: You want a transformation that detects modification but doesn't enlarge the ciphertext? That's impossible, since you need some form of redundancy to get detection. The closest you can get with length preserving encryption is that any change to the ciphertext will produce an unpredictable, random looking plaintext. But those transformations are not stream ciphers. –  CodesInChaos Mar 6 '14 at 12:46
@CodesInChaos looks like a valid answer to me. Care to post it? –  mikeazo Mar 6 '14 at 13:05
If data is sizable and has structure (e.g. text, raw output of some sensor..) then with overwhelming odds it can be compressed; we then can then use a mode giving confidentiality and integrity without increasing the data length (there are pesky details to make the data exactly match the original length when using some modes, but nothing that can't be solved). This won't work for all inputs, of course. –  fgrieu Mar 6 '14 at 13:27
I'm curious as to why the length cannot be increased. I can see that being an interesting theoretical question, but in practice I just don't see this being a real constraint. Sure, it might require some extra work to change some things (a protocol, database, or something along those lines). So, if this is indeed a hard requirement, I'd be interested in hearing more about your application. –  mikeazo Mar 6 '14 at 13:31
Compression can't work for random keys stored as raw data, e.g. an AES-192 key stored as 24 bytes. For 3DES keys stored as 24 bytes but really of 168 bits, you can use the 24 low bits to give significant integrity protection (that's sometime done and used to be prescribed), and use encryption on top of that. For RSA keys, things will depend of the format; some a very compressible. In short: that depends on your key, and what's allowed by the storage for it. Also: you obviously need extra storage for the key of your integrity and confidentiality scheme. –  fgrieu Mar 6 '14 at 13:43

If the data to protect has no built-in redundancy at all (for example, has each of its bit determined by fair coin toss), there is no way to protect integrity without expansion (Proof sketch: there are as many distinct possibilities for valid plaintext as there as possibilities for valid enciphered-and-protected data, hence every possible enciphered-and-protected data must be acceptable by the verify-and-decipher operation).

If the data to protect has some built-in redundant part (like, a fixed header of 16 octets), then we can remove it, use normal authenticated encryption, and restore the redundancy after the verify-and-decipher step. Variant: if we are certain that some lossless compression scheme will shrink the data enough (e.g. the plaintext is 2227 symbols restricted to 246 possible values, each coded as an octet, allowing to encode that plaintext as 2211 arbitrary octets by mere conversion from base 246 to base 256, making room for 16 octets), we can compress the data before applying the authenticated encryption, and expand after the verify-and-decipher step.

If the data to protect has some built-in redundancy that we have no way to turn into compressibility but can nevertheless characterize (like, plaintext is the result of applying Bzip2 compression to about one page of sensible English text), we have the option to use Format preserving encryption (that is, in the context, a block cipher with the block size equal to the data size, that implements a key-dependent, random-like, reversible transformation of the whole data). Any alteration of the ciphertext (other than replacing it with a known-valid ciphertext) will make the whole deciphered plaintext random, and we can reliably detect that (with a Bzip2 decompression algorithm hardened against rogue input, followed by even the most basic validation that the output contains a large-enough proportion of English words). Notice however that we loose something on confidentiality: contrary to the previous solution, the same plaintext will always be enciphered to the same ciphertext, which sometime is unacceptable, and does not match the modern goals of a cipher.

-

One more option. Suppose you know that the plaintext has redundancy (due to some message formatting or something), and you know how to verify that its redundancy is correct (e.g., to check the formatting), but you don't know how to compress it or how to remove the redundancy.

Then a reasonable solution is the following:

• Encrypt the message with a length-preserving encryption scheme such as CBC encryption with all-zeros IV and ciphertext stealing (I would not recommend using counter mode or a stream cipher).

• Then, apply a public random permutation or a length-preserving all-or-nothing transform.

• Finally, encrypt the result with the same length-preserving encryption scheme, but with a different independent key.

On the recipient side, you can undo this (decrypt, undo the permutation or all-or-nothing transform, decrypt), then check the formatting/redundancy. If the formatting/redundancy is valid, accept the message as valid and not tampered with.

(You might even be able to skip the first step, and just apply a public random permutation followed by encryption with CBC mode. But the above might be more robust.)

Even better would be to use a variable-length length-preserving block cipher (pseudorandom permutation), if you can find one. (For instance, some schemes for format-preserving encryption might be suitable.) But the above is a pragmatic engineering solution that should be good enough if you can't find a variable-length block cipher of the right length for your messages.

I'd expect this approach will provide as much integrity as is possible, given the assumptions I outlined. (I mean this only in an engineering/heuristic sense; it is not something I have proven mathematically.) It is also pretty easy to code up and apply. Therefore, this may be an attractive approach in practice.

-
Do you know of any candidate length-preserving AONTs? $\;$ –  Ricky Demer Jun 17 '14 at 20:26
I would be quite surprised if the public random permutation method has to work. $\:$ In particular, although I don't see a way to argue the existence of such schemes, any sufficiently malleable length-preserving encryption scheme would be a counterexample to the claim that the public random permutation version of your option provides "as much integrity as is possible". $\;\;\;\;$ –  Ricky Demer Jun 18 '14 at 1:48
@RickyDemer, I've updated my answer to provide a construction that you might like better. If provable security is a goal, a better construction is likely to be $E_{k_2} \circ P \circ E_{k_1}$ where $P$ is a public random permutation and $E$ is a length-preserving encryption scheme. (Then even in the case where $E$ is merely xor with a constant, i.e., $E_k(x)=k \oplus x$, then it can still be proven to provide reasonable security, as this devolves to the Even-Mansour construction, which offers provable security guarantees.) –  D.W. Jun 18 '14 at 2:06