0
$\begingroup$

From what I understand perfect secrecy means that the probability distribution of the messages are independent of the cipertext, right? How can the one time-pad be perfectly secret when the ciphertext is as long as the message in terms of bits?

Because for a given ciphertext I could for example know that my message is not longer than my ciphertext and therefore I could say that a given message occurs with higher probability?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You are correct that the security provided by a one-time pad is that a chosen-plaintext attacker can't distinguish between two messages of the same length, at least not with better advantage than their advantage at distinguishing the pad itself from uniform random.

Length, of course, can be a side channel for more interesting information, especially if variable-rate compression is involved! For example, the distribution of page sizes when downloading Wikipedia is likely to be very different from the distribution of file sizes when downloading the WikiLeaks archive.

If you have a maximum message length, you could extend your messages up to that maximum length with (say) zeros. But this can be costlier. Alternatively, you could break messages up into chunks. In any case, message length is something that a protocol designer must consider when striving for confidentiality!

Improve this answer
$\endgroup$
2
  • $\begingroup$ What you describe with page size distribution is called a website fingerprinting attack. $\endgroup$
    – forest ♦
    Jun 16, 2019 at 3:19
  • $\begingroup$ Well, that's an application of it. Web sites have more signals too (e.g., traffic timing, cache behavior, other effects from JavaScript execution), and file size distribution may be applied to resources that are not web sites like S3 buckets storing your laptop backups just as well as to web sites. $\endgroup$
    – Squeamish Ossifrage
    Jun 16, 2019 at 3:26
0
$\begingroup$

You say

for a given ciphertext I could for example know that my message is not longer than my ciphertext and therefore I could say that a given message occurs with higher probability?

You are thinking of the everyday semantics of the word "perfect". Recall that you cannot have a uniform probability distribution on an infinite set, so the ideal ciphertext uniform distribution towards which the encryption system should strive does not exist.

The definition of perfect secrecy holds as $n,$ the length of the (message,OTP) pair is allowed to grow arbitrarily large, though not infinite. This is perfectly sufficient (pardon the pun).

Moreover, in practice, there are no possible infinite length transmission, and actual transmissions usually come in finite length chunks.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There's no need to consider unbounded message lengths: as long as there are messages of different lengths, a pad that is as long as the message won't conceal the message length. $\endgroup$
    – Squeamish Ossifrage
    Jun 15, 2019 at 3:22

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.