10
$\begingroup$

I want to encrypt some data(text/voice/video) but it is essential that the size of the cipher data remains the same as the plain data.

Which techniques can I use, and how secure are these techniques as compared to the ones which increase the size of the data?

$\endgroup$
  • 5
    $\begingroup$ Can 16 bytes of extra data be sent, in or out of band, once per file/session/stream? $\endgroup$ – Stephen Touset Jan 22 '16 at 4:26
  • $\begingroup$ @Stephen: My requirement only says the size of plain data and cipher data should be the same but I would like to hear more on what you suggest. $\endgroup$ – Jay Jan 27 '16 at 2:58
  • 2
    $\begingroup$ If you can store an initialization vector (typically 16 bytes) per encryption, this becomes trivial (use any stream cipher with a unique IV). However, the IV must be available to the decryption process. This IV can be stored separately from the encrypted data, or in some cases it can be inferred through context. $\endgroup$ – Stephen Touset Jan 27 '16 at 20:25
8
$\begingroup$

The standard answer to this question is format-preserving encryption (FPE). FPE is a class of techniques that allow you to encrypt data while preserving some of its format (which can include its length).

In terms of security, most FPE schemes are deterministic, which means they do not achieve the standard IND-CPA notion of security. However, for high-entropy message distributions this is probably not an issue (ymmv). If your ciphertext can't be even one bit longer than the input plaintext, you don't have space to include a random IV or tweak, so randomization is out of the question unless you get tricky with your protocol.

FPE schemes usually do achieve a security notion called "strong indistinguishability from a random permutation", or SPRP.

For an example of FPE being used in a network protocol, see this paper on network protocol obfuscation.

$\endgroup$
3
$\begingroup$

Any cryptosystem in which the size of the ciphertext equals that of the plaintext is necessarily deterministic, and thus can only be secure if each key is used to encrypt only one message.

$\endgroup$
  • 3
    $\begingroup$ You can get around the problem of CPA impossibility using deterministic nonce-based encryption, if there is some public but non-repeating value that you can use as a nonce (e.g., timestamp, hard disk block number) $\endgroup$ – Mikero Jan 22 '16 at 5:48
  • 5
    $\begingroup$ "is necessarily deterministic..." ... or stateful. $\endgroup$ – SEJPM Jan 22 '16 at 13:25
2
$\begingroup$

Which techniques can I use?

You can use a system like the ones used for the encryption of credit card numbers: AES (for a good grade of encryption) + FPE (for preserve length).

Have a look at “A Synopsis of Format-Preserving Encryption” by Phillip Rogaway (PDF)

$\endgroup$
2
$\begingroup$

There are many block-cipher modes.

CBC for example works only on full blocks of plaintext and produces ciphertext as a multiple of the block size, it is therefore not applicable to your case.

CTR transforms a block-cipher into a stream-cipher, which produces a ciphertext that has the same length as the plaintext. This mode requires the use of a nonce as an IV. If no such nonce is used and the key doesn't change, an attacker may deduce the contents of the plaintexts only by observing multiple ciphertexts because of the many-time pad.
The nonce doesn't have to be secret, but it has to be used only once per key. Usually, this nonce is sent along with the ciphertext, but this would increase the encrypted data, which is not applicable in your situation.
Another way is to have a stateful encryptor, which manages a counter. For every encryption, it would increment the counter, write it back to disk and use the value as a nonce for the next message. If two parties are communicating with the same key, one party may use only odd nonces and the other only even nonces. This is secure and applicable, but requires state at the encryptor.

While Format-Preserving Encryption (FPE) is a general primitive of achieving this sort of encryption where the ciphertext has the same size (and character set) as the plaintext, it is not widely implemented or used.

Ciphertext stealing (CS) is another alternative based on block-ciphers to produce ciphertext of the same size, but is easier to implement than FPE. Those are usually defined as extensions to non-streaming modes for block-ciphers. The Wikipedia page shows examples for ECB and CBC modes with ciphertext stealing. They can operate deterministically like FPE and the many-time pad attack as in CTR mode is not applicable. The only problem is that ciphertext stealing is only possible for plaintexts larger than a single block when the IV is static.

CS example for ECB:

enter image description here

Conclusion

Deterministic encryption as with FPE and (ECB/CBC)-CS enables you keep the same ciphertext size as plaintext size, where FPE additionally enables you to keep the same character set. Since those are not randomized, an attacker might be able to compare the ciphertexts of multiple plaintexts to determine whether the same plaintext was previously sent.

If a state is possible, then CTR or another streaming-mode is likely the better option as it provides randomization.

$\endgroup$
1
$\begingroup$

Which techniques can I use?

The most ideal option is to use synchronous-stream ciphers. They are not only fast, but also let you retain the plaintexts length. The best pseudorandom number generator I know is AES-CTR.

How secure are these techniques as compared to the ones which increase the size of the data.

It completely depends on the algorithm. The only advantage of the ones that increase the ciphertexts lenghth is that it hides the plaintext length, which doesn't make much difference in cases like yours.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jan 26 '16 at 18:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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