Impact of distinguishing between random text and cipher text?

Question

In theory, distinguishing cipher text from random text is considered insecure for any PRP algorithm. Say for example - due to Patarin's proof with about six rounds of Feistel Network - the attacker can distinguish cipher text from random text after about $2^{(n/3)}$ queries to the encryption oracle, where $n$ is input size. For example, if the input domain is 32 bits, after around 1552 queries the attacker can distinguish cipher and random strings.

In practice, what does this mean and what exactly is the impact? How will the cipher text look after say 1553 in above example? Will the attacker get to know the key too or will he be able to guess the next few cipher texts?

Answer 1

I think abstractly, it implies that the attacker understands something about the structure of the cipher, and the fear is that with that knowledge, something of the plaintext or key could be known.

Much of this comes first from Shannon's proof of perfect security--having all the ciphertext in the world did not help you one wit to guess anything about the plaintext. This concept evolved in the early 80's in work by Blum/Micali and Yao to say, with regard to computers, that it's really only relevant to worry about what you could guess in polynomial time. The original definition of computational indistinguishability was applied to pseudorandom generators, and is met if an attacker cannot distinguish an algorithm's output from a truly random string in time polynomial in the security parameter (i.e. seed length or some such.) So the polynomial bound is really critical to this definition.

In block ciphers, the original definition doesn't apply because the security parameter is fixed--it's the block length. So the analysis comes out in constant time. I can say exactly how many computations I would need to brute-force a cipher, and it's fixed for each blocksize. Block ciphers are modeled as PRPs, as you mention, and so the distinguishability definition there requires you to be able to tell a block cipher apart from a randomly selected permutation $P:\{0,1\}^n\rightarrow\{0,1\}^n$. You could always just run all $2^n$ possibilities and check, but that's not polynomial in $n$.

Of course, we don't really know if such a PRP really exists, because we don't know if P=NP. Effectively, security in block ciphers has come to be more about whether you can say anything about the cipher in time less than $2^n$. The ability to do so says the cipher does not truly provide $n$ bits of security, since I don't need to do $2^n$ computations to learn whatever is leaked. Put another way, I could run every single 128-bit block through AES under some key. I could keep a dictionary of all possible ciphertext blocks that result. Suppose there are some 128-bit blocks that do not occur in the ciphertext, or every 200th odd value is always followed by an even value. If I look at AES output vs. random output, I could simply look for those patterns and, when I find them, say which must be truly random data. The problem is that this exercise is not polynomial in 128, but exponential and far from practical w/ today's computers. So I still feel secure.

Also, remember that distinguishability only requires non-negligible probability of distinguishing. What's negligible is up to the engineer to decide. But if the chance of distinguishing is close to 50% and the algorithm knows when it's right and when it has no idea, it only doubles the data required to get a sample of some fixed size for an attack--just discard the data you're not sure about.

Now to the practicalities of your question: Distinguishing the source of a stream of data does not necessarily imply the ability to learn the key or find the plaintext. It's unlikely they could guess the 1553rd ciphertext or plaintext, only that they have a (good) chance of saying whether it comes from that cipher or some random source. However, it doesn't inspire extraordinary confidence, either. It suggests there's some pattern that doesn't take too long to find, and knowing that tells them something specific about how the cipher works. But even just distinguishability might (depending on the nature of the weakness) have a real benefit. For instance, suppose this distinguishing algorithm can, after $2^{n/3}$ blocks, say if the next block is from the same PRP/block cipher as the others. Then perhaps it can tell when the key is changed, since a differently-keyed cipher would not be consistent. With that knowledge, suppose there's a crib in certain messages. The attacker can now begin to build a database of the same crib encrypted with what it can now tell are different keys (though it doesn't know what they are). Maybe that upgrades the attack to a known plaintext attack over multiple keys. These are the kinds of holes that eventually leak enough information that allow a combination of things to break a cryptosystem.

Practically, most if not all ciphers leak something. AES leaks key bits, but only a couple and so no one minds that much. It's the cryptosystem designer's job to make these value/risk decisions based on judgement. But for me, $2^{n/3}$ is pretty low, so in that example, I'd look for an alternative--although still technically exponential (and ignoring totally the fact that a full 32-bit cipher is trivial these days), that's just too fast to be leaking any kind of structure.

Answer 2

Patarin's proof isn't about distinguishing ciphertext from "random text", it's about distinguishing a Feistel cipher from a random permutation. That proof is also in the information theoretic world, which means that the Adversary is computationally unbounded, and as such can deduce everything about the cipher (the 'key', all remaining ciphertexts, etc).

In the more 'practical/useful' sense (i.e. against bounded Adversaries), if the Adversary can efficiently distinguish a cipher from a random permutation then they can usually mount efficient key-recovery attacks against the cipher structure (guessing part of the key in order to 'peel off' rounds, and using the 'wrong-key randomization' hypothesis). Once you know the key then you can deduce all future ciphertexts.

I should also add that any permutation, whether truly random or pseudorandom, can be distinguished from "random texts" /"random strings" with the following Advantage (probability of success): $$\mathbf{Adv} \leq \dfrac{n(n-1)}{2^{\ell+1}}$$ Where $n$ is the number of requested chosen plaintexts and $\ell$ is the blocksize of the permutation in bits. This is because if you select $n$ distinct plaintexts you will always get $n$ distinct ciphertexts if the Oracle is a permutation. But if the Oracle is returning random strings then there might be a collision in the outputs (and the probability of collision grows with the amount of requested plaintexts, becoming essentially $1$ when around $2^{\ell/2}$ requests have been made).