2
$\begingroup$

For example, if $m = 10011$, $k = 11001$, $n=3$ (which is the number of 1's in k), $c = m \oplus k = 01010$. If $c$ and $n$ are revealed to the attacker, is this scheme still secure?

$\endgroup$
3
  • 4
    $\begingroup$ Hint: what if you are given that $n = 1$? $n = 2$? How many keys does that rule out, and how many are left? (are they equiprobable?) $\endgroup$
    – Thomas
    Jul 7 '15 at 19:38
  • 1
    $\begingroup$ Heh, what about $n = 0$ :) If an attacker gains more knowledge about $k$ any cipher will be less secure, including OTP. $\endgroup$
    – Maarten Bodewes
    Jul 7 '15 at 22:50
  • $\begingroup$ You definitely loose the information theoretic security. How bad it is depends on your $n$: In a bitstring of length $2x$ and hamming weight $x$, there are ${{2x}\choose{x}} \approx \frac{4^x}{\sqrt{\pi n}}$possibilities, which differs from the full $2^{2x}$ only by the denominator. However, the lower or higher values can give a lot of information about the key. $\endgroup$
    – tylo
    Jul 8 '15 at 12:56
5
$\begingroup$

The security notion one usually considers for OTP is perfect secrecy, which informally means that the ciphertext does not reveal any information about the original message, regardless of the computational power of the adversary. It is already known that this requires that the key size must be equal to the plaintext size and that all keys are equiprobable. That way, for each ciphertext you could find a key that decrypts the ciphertext to any possible message.

However, your proposal violates these principles. Assuming the key size (and plaintext size) is $S$, then the number of possible keys is not $2^S$ (i.e., all the possible keys of length $S$, as in the regular OTP), but $\binom{S}{n}$, which is much less than $2^S$. This has the consequence that for a given message $m$, not all possible ciphertexts are equiprobable, or conversely, for a given ciphertext not all possible messages are equiprobable (in fact, some of them have no probability).

Let's see it with your example. With regular OTP, for a length of 5 bits there are $2^5 = 32$ possible keys (as well as messages and ciphertexts). If an adversary gets $c$, there are 32 possible messages that correspond to that ciphertext. That is, the ciphertext is completely useless to the adversary. Now, in your proposal, for $n = 3$ there are $\binom{5}{3} = 10$ possible messages for a given ciphertext, since there are only 10 possible keys. The ciphertext $c$ and knowledge of $n$ makes possible to the adversary to deduce which 10 messages (out of the 32 possible) are related to the ciphertext. Therefore, he is gaining some knowledge about the original message.

$\endgroup$
3
  • $\begingroup$ @JanLeo Sorry, that doesn't make any sense. The key should be of equal size than the ciphertext, therefore, $|k| = |c|$. And what is $r$? $\endgroup$
    – cygnusv
    Jul 10 '15 at 19:38
  • $\begingroup$ @cygnusy Sorry, that is a mistake. I mean if $|c|=256$ and $|n|=128$, then $|k|=\binom{|c|}{|n|}>2^{128}$. Is it computationally secure? Why key space should be of equal size to the ciphertext space? I don't need perfect security. If the key space is super-polynomial, then it is computationally-secure, isn't it? $\endgroup$
    – Jan Leo
    Jul 11 '15 at 7:31
  • $\begingroup$ @JanLeo, I recommend you check out Dirk Rijmenants's One-Time-Pad page. In short, re-use of any key, especially within the same message, compromises those parts of the messages where that part of the key was used. Also, knowing how many binary 1's exist in a given key is HUGE. It simply renders your key easily breakable (just a matter of computational budget). This scenario is even worse than the former as the whole message can be deciphered, not just the parts where the key use was doubled. $\endgroup$ Jul 31 '15 at 20:51

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.