Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
Google for "traffic analysis" for some ideas about how the traffic can be used without decryption, but only if you can distinguish real traffic from random trash. – Jerry Coffin Sep 26 '13 at 20:51
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). – D.W. Sep 27 '13 at 1:17
up vote 6 down vote accepted

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.

share|improve this answer
That "The bias in the underlying cipher…" part answered what I was wondering about. [+1] and accepted. Thanks! – e-sushi Sep 27 '13 at 17:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.