Cryptology Known Plaintext Attack

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Frequently asked question: What is an »attack with known plaintext«? If the attacker knows the plaintext, there is nothing left to crack!

Answer: Often the cryptanalyst knows a chunk of plaintext, maybe only a single probable word, and then tries to determine some further chunks of plaintext—or the key and thereby the complete plaintext.

Grading of the Attack

1. Plaintext completely unknown.
2. Supposed (probable) word:
   • a frequent word (for example articles or, what the German cryptanalysts in World War II utilized in breaking the American M-209, numbers spelled as letters—»five seven three«),
   • a special word in the context of the message.
3. Known chunk of plaintext (for example set phrases).
4. One or more complete compromised messages.

Often the position of the probable word is determined by trial and error.

Probable words and and chunks of known plaintext occur as:

• Frequent words
• Stereotypical phrases (»Yours sincerily«)
• Context information (»Oberkommando der Wehrmacht«)
• Provoked messages (»Erloschen ist Leuchttonne«)
• Carelessness of operators (for example sending the same message in an old, already broken cipher and in a new one that is not yet implemented at all receivers
  • This frequently happened in history, and even in World War II resulted in some spectacular cryptanalytic successes.
• ... or by activities of the secret service

Or the same message was sent in two different ciphers, one of them already broken, providing a complete known plaintext message for the other cipher. In history this happened when an old cipher was replaced by a new one and not all receivers had yet implemented the new cipher.

Some procedures of modern cryptography use challenge-response techniques for authenticating users. They send a random plaintext and get back the corresponding ciphertext. The attacker sees both of them.

The amount of known plaintext that is needed for a certain attack method serves as measure of the efficiency of this attack. Therefore it contributes to assessing the security of the cipher. This measure is somewhat coarser than the time complexity of the attack because every part of the known plaintext has to be touched (otherwise the attack could dispense with it).

Examples

Shift Cipher

Even a single known letter of plaintext reveals the key.

General Monoalphabetic Substitution

Each known letter of plaintext revels one letter of the key.

Breaking a monoalphabetic substitution is trivial with known plaintext of about 5 or 6 letters. These suffice for guessing many words in the plaintext and reconstructing the complete key.

Stepping Up: Chosen Plaintext Attack

The cryptanalyst has even better promises if she can encrypt a plaintext of her own choice.

At first view this sounds completely absurd, but in certain situations it is a real danger:

• A weak form is the provoked message.
• With one-way ciphers or asymmetric ciphers [see later] each one can encrypt any plaintext.
• A similar situation is a black box, for example a stolen smartcard or the built-in encryption of a hardware or software system, where the goal is finding the key and then using it »illegaly«,
• ... or a challenge-response procedure.

An example is given in

• Jeff Zamora: ActiveSync 2.x allows unauthorized access to your NT password.

Some General Remarks on Cryptanalysis

• Cryptanalysis uses context knowledge almost always. How much and what kind of context knowledge is needed differs from case to case.
• Cryptanalysis consumes time. Often a cipher is considered sufficiently secure, if this time is long enough for making the message useless for the cryptanalyst. Pursuing this idea further leads into complexity theory.
• An essential requirement for the cryptanalyst is to have as many methods as possible at her disposition. If one method fails, she tries another one.
• Encrypting the same plaintext with different keys, or different plaintexts with the same key, offers ways for attack.
• The history of cryptology teaches that not only direct attacks on the algorithm but also attacks on the »protocol« lead to cryptanalytic success, that is, attacks on the circumstances of the use. Bruce Schneier's notion for this is »Side Channel Cryptanalysis«.

And an important lesson from the cryptanalytic methods learned up to now is:

In the next section we'll study an approach that tries to accomplish this goal: polyalphabetic encryption.

Exercises

1. EJGGZ TGWOF IPOHI HONAW OCIAO TQUPO HZTHI EFOTQ QCHIO TNAIO
   IOHHZ TGUJP QRAOT QCGWO FIIJP ROTQR OTQNA VJHOT RJQJQ EOP
   (The plaintext is supposed to be in German. It could mention the village Waidhaus near the German-Czech border.)
   
   
2. FTCZQ POFHM ATPOZ WDZUC HUOQJ TUQZE BDUTQ
   OADHP OTCBN WEDUP KATPO ZWDFH MHWQJ TUAZW
   WCZMD PZKOL THUEZ UQHMZ UDUTQ OAOAD QDTCK
   HVVTM ZUBOT QTHEY NUFOZ TUCZM DCZMD UHNBA
   OKKGH PFTVG
   (William Friedman; probably the language is English.)