# Distinguish messages

Since i cannot comment on questions, I give my own:

If a secret key encrypt algorithm can encrypt messages of arbitrary length and the encrypt algorithm is probabilistic then: suppose the adversary selects two messages of different length, $||m_0||=n$, $||m_1||=l$ and $n<l$. She gets back a ciphertext $c$. How can she tell which message was encrypted? Cause I thought that since the encryption is probabilistic the length of $c$ might as well be $n$ (which is not likely, but just to show that $c$ can have any length), while message $m_1$ was the one encrypted. Right? or very wrong?

-

Now, suppose you have the two messages $||m_0|| = l_0$, $||m_1|| = l_1$ and $l_0 << l_1$ (say $l_0 = 1 \, bit$ and $l_1$ is very large $>10G \, bits$). If you receive a ciphertext shorter than $l_1$ you know that $m_0$ was encrypted. I think you can see, that an encryption algorithm, that produces ciphertexts longer than $l_1$ when you only encrypt a single bit, is very inefficient.
 Thank you. "Now, suppose you have the two messages $||m_0||=l_0$, $||m_1||=l_1$ and $l_0<10Gbits). If you receive a ciphertext shorter than$l_1$you know that$m_1$was encrypted." I guess you meant$m_0$in this last sentence? – Thom Oct 31 '12 at 1:01 Yes, of course. I will edit my post. – Ekris Oct 31 '12 at 9:53 How do I know how big$l_1$should be? And what is the chance of$m_0$being encrypted in a ciphertext longer than$l_1$? – Thom Oct 31 '12 at 16:45 This was only an example and there will be no secure encryption scheme that stretches the ciphertext very much. BUT if you really get an encryption scheme that stretches the ciphertext there must be any step in the algorithm description where the length is defined and at this point you can attack. – Ekris Oct 31 '12 at 18:35 I want to show that it is not secure when the messages are of different lengths. My thought was this: suppose that the encryption of a single bit cannot be longer than$p(n)$, what do we know about a message of lets say length$p(n)+n$? My idea was to let the adversary select$m_0 \in \{0,1\}$and$m_1 \in \{0,1\}^{p(n)+n}$. – Thom Oct 31 '12 at 19:14 show 1 more comment For most schemes, the length of the ciphertext reveals the length of the plaintext, or reveals the approximate length of the plaintext. (For instance, the length of the ciphertext might be the length of the plaintext plus 128 bits, or the length of the plaintext rounded up to the next multiple of 128 bits plus another 128 bits, or something like that.) Thus, if$n$and$l\$ are different enough, it's easy to distinguish simply by looking at the length of the ciphertext.