Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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$
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 :-)
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).
