8
$\begingroup$

I'm doing some exercises before my exam, and I am stuck with task number 4 in this file: http://www.cs.umd.edu/~jkatz/crypto/f10/hw1.pdf

Could you help me with this task?

When using the one-time pad encryption scheme, it can occur that $k=0^l$ and then the ciphertext is equal to the plaintext! It has been suggested to improve the one-time pad by only choosing non-zero keys. What do you think of this improvement? In particular, is it still perfectly secret? If yes, prove it. If no, reconcile this with the fact that encryption with the all-0 key completely reveals the plaintext.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ Hint: if an all-zero key was impossible, and the attacker intercepted a ciphertext consisting of the three characters "Yes", can he deduce any information about the plaintext (and if so, what)? $\endgroup$
    – poncho
    Commented Oct 8, 2012 at 21:36
  • 3
    $\begingroup$ Hint 2: if any key is possible (including $k=0^l$), and the attacker intercepted a ciphertext consisting of the six characters "Attack", is it more likely that the plaintext was "Attack" or "Defend"? What about "Rabbit"? $\endgroup$
    – Stephen Touset
    Commented Oct 8, 2012 at 23:55
  • $\begingroup$ How about $l=1$? $\endgroup$
    – j.p.
    Commented Oct 12, 2012 at 5:58
  • 1
    $\begingroup$ Please be so kind to accept the perfectly valid answer by Bruno, Nick. $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 27, 2012 at 22:33
  • $\begingroup$ I came here after wpa2 design flaw. Stating Android can be tricked into reinstalling a zero encryption key. Does this have anything to do with this question. $\endgroup$
    – void
    Commented Oct 29, 2017 at 14:36

1 Answer 1

Reset to default
19
$\begingroup$

In few words:

  1. OTP has perfect secrecy;

  2. For a cipher to have perfect secrecy, it is required that $|K| \ge|M|$.

Let $K=M=C=\{0,1\}^n$ be the set of keys, messages and ciphertexts. If you apply the "improvement", ie, if you remove $0^n$ from the keyspace, then you've created a cipher that cannot show perfect secrecy (because now $|K| = |M| - 1 < |M|$).

Therefore, the "improvement" completely breaks perfect secrecy, which makes this modified OTP worse than the original.

In many more words, with illustrating examples.

As you should know, the one-time pad has the perfect secrecy property, which is defined as follows: let $M,C,K$ be the sets of messages, ciphertexts and keys; $\forall k \in K, \forall c \in C, \forall m \in M: P[E(k,m)=c] = P[k \,\,xor\,\,m = c] = \alpha$, for some (tiny) positive real number $\alpha$.

In words, you have absolutely no information about the original message if you're given only the ciphertext. Suppose the cipher text reads:

The password of my bank account is my wife's birthday

What's the most probable original message?

The password of my bank account is my wife's birthday
The password of my bank account is my aunt's birthday
The password of my bank account is: b4nk-P4ssw0rd1234
Love of my life you've hurt me You've broken my heart

See? The "improvement" can't possibly improve this cipher. Actually, it makes it worse: by reading the ciphertext, the attacker can be sure that your password is anything but your wife's birthday -- he could get some information from the ciphertext!!!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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