2
$\begingroup$

I am generating a ciphertext by XORing the message bits with key stream bits of a stream cipher. But, if I know a priori that message bits contain a predefined number of 0's (say 60%) at unknown positions, then how to analyze the security of such system both mathematically and empirically.

Can we analyze using hypothesis testing (given two messages m1 and m2 with the same distribution and analyze whether ciphertext leaks any information about messages) or using entropy bounds?

$\endgroup$
4
$\begingroup$

Can we analyze using hypothesis testing (given two messages m1 and m2 with the same distribution and analyze whether ciphertext leaks any information about messages) or using entropy bounds?

If the output of the key stream generator is indistinguishable from a random stream and uncorrelated to the plaintext, then no, you cannot.

Consider the case where we know almost all of the paintext, that is, we have an encrypted message $e = m \oplus s$ (where $m$ is the plaintext, and $s$ is the keystream output), and we know apriori that either $m = m_1$ or $m = m_2$ (but we don't know which).

We can compute $e \oplus m_1$ and $e \oplus m_2$, one of which will be $s$ and the other will be $s \oplus m_1 \oplus m_2$

However, if we assume that $s$ is random and uncorrelated, then both $s$ and $s \oplus m_1 \oplus m_2$ will be random; we have no way of deciding which is which. Any hypothesis testing on $s = e \oplus m_1$ will give the same expected result as on $s = e \oplus m_2$

$\endgroup$
3
$\begingroup$

Let the ciphertext be $e = s \oplus m$, with $m$ a message bit, and $s$ the stream cipher output.

One key property of the XOR operator is that when the distribution of $s$ is equiprobable (50% 1's, 50% 0's, which hold for a strong stream cipher), the resulting ciphertext $e$ will also have this probability, independently of the distribution of $m$.

This is easily seen the following way: any bit $m$ has 50% chance of "switching", as $s=1$ will switch $m$, and $s=0$ will not. Hence, the output of the stream cipher therefore will be equiprobable.

Can we analyze using hypothesis testing (given two messages m1 and m2 with the same distribution and analyze whether ciphertext leaks any information about messages) or using entropy bounds?

So, as both ciphertexts, and the key stream are indistinguishable from random, we cannot distinguish $s'=e\oplus m_1$ nor $s''=e\oplus m_2$ from random, as poncho said right before me :-)

$\endgroup$
  • 2
    $\begingroup$ Note, you cannot use @poncho in answers. You can however click the share option below the answer and use that as link. This also works for questions and copying the link for edits or even copying the link represented by the time in comments. $\endgroup$ – Maarten Bodewes Jun 11 '17 at 12:30
  • $\begingroup$ @MaartenBodewes, thanks, will remember that! (it works here, right?) $\endgroup$ – Ruben De Smet Jun 11 '17 at 14:54
  • $\begingroup$ Yup, it works within comments, I think only as response to one of the earlier persons posting a comment (and you don't have to inform the author of the question / answer you are responding to, they get it automatically) $\endgroup$ – Maarten Bodewes Jun 11 '17 at 15:04
  • $\begingroup$ Roger that; Thank you! Shouldn't we now remove these comments? It's pretty off topic :-) $\endgroup$ – Ruben De Smet Jun 11 '17 at 15:07
0
$\begingroup$

Let $c_n$ be a cryptotext for message $m_n$. For sake of simplicity, I'll assume all messages have the same length. This does not mean you cannot apply this for messages of different length, it would just make it unnecessarily complex for now.

If you reuse the keystream, then $c_1 \oplus c_2 = m_1 \oplus m_2$. If 60 % of $m_1$ are zeroes and 40% of $m_1$ are random garbage, you'll get 60% of $m_2$. Consider this to be just an example, there is more attacker can learn in general.

For this reason, initialization vectors (IVs) are used. In stream ciphers, independent IVs will produce independeent keystreams, so the xor relations between $c_1$ and $c_2$ no longer holds. Various stream ciphers might have various requirements for IVs. All of them require to be unique, some have further requirements, like not using some subsequent numbers for IVs (depending on the message length).

$\endgroup$

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.