6
$\begingroup$

Commonly there are four ways to "break" a secrecy-focused cryptosystem:

  1. Recover the secret key
  2. Recover the message
  3. Distinguish an encryption from random noise
  4. Distinguish the encryption of two different messages

The practical implications of the first two breaks are obious: They allow arbitrary message recovery (more or less) fast.

However I'm unclear about the practical implications of the the last two breaks.

So let's assume an encryption algorithm or a public key cryptosystem which fails to provide indistinguishability but also doesn't allow key or message recovery. As an example assume the scheme from the "Present an attack for the combination of OTP and textbook RSA" question under a chosen plaintext attack.

So:
What are the practical implications if a distinguishable cryptosystem would be used in practice?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
12
$\begingroup$

This isn't really a "hard" answer, but an attempt to give some intuition or motivation.

One can interpret indistinguishability as an overapproximation of the most common notions of security: Any system that is broken in a more practical way will also fail to meet indistinguishability, that is, all practically important security requirements are in fact subsumed by indistinguishability. It is therefore a sensible and defensive approach to require indistinguishability. This proceeding also agrees with the expectations one usually poses to a "good" system: It should be as close as realistically possible to Shannon's definition of perfect secrecy.

On the other hand, a system may well be distinguishable but do not admit any relevant attacks — however, in practice, distinguishing attacks are often the first sign that a system may be about to break in more severe ways. A potential reason for this could be the fact that the structure of a system needs to be well-understood by researchers to find such attacks, and then other weaknesses can become visible as well. I suppose the most prominent example is the RC4 cipher, which continued to accumulate more and more known biases (breaking indistinguishability) over time until it had to be considered insecure for practical purposes.

Improve this answer
$\endgroup$
10
$\begingroup$

Katz & Lindell mention in their book "Introduction to Modern Cryptography: Principles and Protocols" an example of an IND-CPA attack from World War II.

Navy cryptanalysts suspected that Japanese ciphertexts containing the fragment "AF" where referring to the Midway island. Then, they told officials at Midway to send unencrypted messages reporting they were low on water. Consequently, the Japanese intercepted the messages and reported that "AF" was low on water. After confirming their suspicions with this "encryption oracle", they were able to know when intercepted ciphertexts were about this island, thus adapting their military strategies.

They didn't have to recover the original message or the key. They simply used an encryption oracle to distinguish between different ciphertexts, thus breaking the indistinguishability of the Japanese encryption scheme.

I don't know if this story is completely true or not, but at least it is completely believable, and illustrates that indistinguishability is a basic notion for encryption schemes.

Improve this answer
$\endgroup$
2
$\begingroup$

It can be proved, mathematically, that your (2), (3), and (4) are all equivalent under chosen plaintext attack. That is, if you can do any of those things then you can also do the other two!

It should be obvious that (2) implies both (3) and (4): if you can decrypt a message then you know which message it is, and also you know it's not random noise.

The proofs of (3) implying (4) and vice versa are covered in this older question: Is the reduction from left-or-right IND-CPA to real-or-random IND-CPA tight? (which goes a bit beyond them, in fact).

All of the proofs are covered in this paper by Bellare et al: https://cseweb.ucsd.edu/~mihir/papers/sym-enc.pdf

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ The question was about practical implications, and this answer remains entirely within the theoretical scenario of a CPA attack. $\endgroup$
    – tylo
    Aug 3, 2015 at 12:20
  • $\begingroup$ @tylo The proofs are constructive - if you have an algorithm to do any of (2), (3), or (4), they give you an algorithm to do the other two. Thus, the practical implications are exactly the same as the theoretical implications. A cipher whose output is distinguishable from randomness is a cipher whose plaintext can be recovered. (And this is in fact exactly what people have been doing to RC4 lately: 1 2) $\endgroup$
    – zwol
    Aug 3, 2015 at 12:56
  • 1
    $\begingroup$ I don't see how e.g. leaking the parity of messages would allow you direct access to the plaintext. Maybe an attack would be possible but that would require more messages. This seems contrary to your answer; you'd have at least substantially add to your answer to make this believable. Just pointing to a paper for this is not enough. Please prove my initial assumption wrong! $\endgroup$
    – Maarten Bodewes ♦
    Feb 5, 2016 at 9:53
  • $\begingroup$ While I surely recognize the aim of your answer, I tend to agree with the argumentation of tylo and @MaartenBodewes in their comments. After all, there’s a rather large gap between those academical findings and “practical implications”. Fact is, the question asked for the later… $\endgroup$
    – e-sushi
    Feb 5, 2016 at 19:39
  • $\begingroup$ @e-sushi I'm just going to point at those RC4 papers again. RC4 keystream being distinguishable from randomness has led directly to RC4 being decryptable w/o knowledge of the key. $\endgroup$
    – zwol
    Feb 5, 2016 at 20:05

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.