I started reading about the most recent cryptanalysis of RC4 and it's variants. One of the papers I just finished reading ("Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers" by Alexander Maximov) handles Linear Distinguishing Attacks.

Now, I understand that a Linear Distinguishing Attack can be used to (simply said) differ cryptotext from real random data. I also understand this proves the related stream cipher to be cryptographically broken, because the successful attack can be used as a base for further attacks. Yet, I am not sure I fully understand the whole range of consequences of a successful Linear Distinguishing Attack.

Does a successful Linear Distinguishing Attack mean the attacked stream cipher is completely broken from a practical point of view?

The question popped up in my mind, because there might be scenarios where Alice and Bob can guarantee that Eve will never get her hands on any plaintext at all. If I'm not mistaking, when Eve does not have (enough) plaintext, Eve can't do a successful linear cryptanalysis. That again could imply that a successfully attacked cipher could be still be used "under certain conditions". Is that correct?

Yeah, I know. No sane person would actually implement a cryptographically broken cipher (like RC4) as long as there are safer alternatives (like AES256) available… so please think of the scenario as a theoretical one. I'm only using it at part of the question since it might help me to completely understand the full impact of a successful Linear Distinguishing Attack, what it practically means for attacked ciphers, and how much a successful Linear Distinguishing Attack actually breaks an attacked stream cipher.

In fact, I guess my question boils down to a more general question covering more than just linear distinguishing attacks… do all distinguishing attacks generally count as a complete break, from a practical perspective?

  • 1
    $\begingroup$ It sounds like your real question is: "Does a distinguishing attack count as a complete break, from a practical perspective?" If so, you might want to re-write your question from this much more general perspective (whether it's a linear distinguishing attack or some other distinguishing attack is probably of limited relevance). $\endgroup$
    – D.W.
    Commented Sep 27, 2013 at 1:17

1 Answer 1


I would say a distinguishing attack should count as a break. Especially so if it is practical.

The reason for this is that if you can distinguish the key-stream from random, you invariably leak details about the plain-text.

For example, suppose somebody turned up a few terabyte disks encrypted with VMPC under the same key. It says in the paper that after approximately $2^{40}$ bytes the cipher can be distinguished from random. The bias in the underlying cipher might allow an attacker to work out whether the plain-text was written in Arabic or English.

That in itself is useful information to know about the plain-text and, to me at least, constitutes an unacceptable weakening of the cipher.

  • $\begingroup$ "might allow an attacker to work out whether the plain-text was written in Arabic or English." For me, the danger of a distinguishing attack feels so completely vague and theoretical, especially with how how little you actually hope you might get from it. $\endgroup$
    – Chris_F
    Commented Mar 24 at 6:18

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.