2
$\begingroup$

I understand the general idea of IND-CPA, however I fail to understand why the messages the adversary chooses have to be of same length. I guess that with variable length messages there would always exist a successful attack and therefore CPA security would not exist. Can anyone guide me into a direction on how such an attack would look like?

$\endgroup$
1
  • $\begingroup$ One does not want to impose the requirement that schemes need to hide the message length (because that would probably end up being suuuuuuper inefficient). $\endgroup$
    – SEJPM
    Jul 19 '17 at 8:31
6
$\begingroup$

Here is an outline of such a distinguisher would work; if you submit a one byte plaintext, then the resulting ciphertext length will follow some probability distribution (with many ciphers, it will be one fixed length; we'll consider the more general case where it is probabilistic); for this probability distribution, we'll have some $N$ where the probability of the length being less than $N$ is $\ge 0.75$.

So, we submit two plaintexts; one consisting of 1 byte, and the other consisting of $N+1$ random bytes. If the ciphertext corresponds to the short plaintext, the ciphertext will be of length $< N$ with probability $> 0.75$; if the ciphertext consists to the long plaintext, the ciphertext will be of length $< N$ with probability at most $\frac{1}{256}$ (can be shown by the pigeon-hole principle); hence just looking at the length of the ciphertext can serve as the distinguisher.

Obviously, one way to get around this approach would be to pad out all encrypted messages to a fixed length (and have an arbitrary length bound on plaintexts). However, this sort of thing is expensive in practice; the leaking of the plaintext length is generally considered acceptable.

$\endgroup$
2
  • $\begingroup$ Very good answer. I get the idea but don't understand it fully. Can you go into a bit more detail why you chose N + 1 for the long message and how this works out to be the 1/256 probability? Thank you very much! $\endgroup$
    – Gilrich
    Jul 20 '17 at 8:40
  • $\begingroup$ @Gilrich: I specifically said that the long message was 'random', that is, randomly chosen out of the $256^{N+1}$ possible messages of length $N+1$. We assume that the encryption method is invertible; that is, for any ciphertext, there is at most 1 plaintext message that can map to it. There are $\sum_{i=0}^N 256^i = (256^{N+1}-1)/255$ ciphertext messages of length $N$ or shorter; hence the probability that a random long plaintext message can map to a ciphertext message of length $N$ or shorter must be less than $1/255$ (I said $1/256$, well, that's a minor error) $\endgroup$
    – poncho
    Jul 20 '17 at 17:21

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.