Cryptology Exhaustion

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

The most primitive of all cryptanalytic attacks is exhaustion, also known as brute force attack. It consists of a complete key search—run through the complete key space, and try key after key until you get a valid decryption. This is especially successful against shift ciphers.

The exhaustion attack applies to each cipher! [See below.]

Procedure: Write the ciphertext (or a part of it) in one row. Below it write the tentative plaintexts for all possible keys, line by line. For a shift cipher simply write the alphabet in columns below the ciphertext, begin with the siphertext letter and repeat cyclically. The correct plaintext catches the eyes.

Beispiel

FDHVDU
GEIWEV
HFJXFW
IGKYGX
JHLZHY
KIMAIZ
LJNBJA
MKOCKB
NLPDLC
OMQEMD
PNRFNE
QOSGOF
RPTHPG
SQUIQH
TRVJRI
USWKSJ
VTXLTK
WUYMUL
XVZNVM
YWAOWN
ZXBPXO
AYCQYP
BZDRZQ
CAESAR
DBFTBS
ECGUCT

The only meaningful plaintext is CAESAR. The key is 3. Note the structure of the columns.

Because of this scheme the exhaustion method is sometimes called »generatrix method«. This notation comes from an analogy with cipher cylinders.

Practical Execution

Prepare some vertical strips [paper strips or wooden bars] that carry the alphabet twice in vertical order. Put these side by side, and slide them against each other in such a way that one row contains the ciphertext (or a part thereof). Then one of the other rows shows the plaintext [image].

Turning the strips by 90° the arrangement looks like this:

                     |
                ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
                  ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
              ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
                  ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ
                     |

Here is a prototype. Print some exemplars and cut them out [PDF].

Question: Why did we omit the letter »Z« at the end of the strips?

Lessons from the Sample Cryptanalysis

1. Shift ciphers are solvable, as soon as the ciphertext is a few letters long, the alphabet is not too large, and, as we saw in the example, the meaningful texts are only a small part of all character stings, that is, if the language is »sparse«. Later on we'll make this more precise using the notions »high redundancy« or »low entropy« of the language.
   
   
2. A first approach at strengthening the encryption is:
   
   

   Use a cipher with a large effective key length.

   
   For XOR this would mean a large block size l. If for example the blocks are sectors of a disc à 512 bytes = 4096 bits, then l = 4096. This makes exhaustion practically impossible—there are 2⁴⁰⁹⁶ different keys. In spite of its gigantic key length this cipher is not secure.

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

General Procedure for Exhausion

The exhaustion (or complete key search) is a cryptanalytic procedure that works against every cipher: Simply try all keys in any order until you find the correct key. You recognize it by the appearance of meaningful plaintext.

A precondition for the success is that the plaintext language is highly redundant. That means that »meaningful« texts by far outweigh random character strings. In general there is a unique solution as soon as the text length exceeds the »unity distance« of the cipher, see later.

Here is an informal algorithmic description of exhaustion:

1. Take the next key, tentatively decrypt a chunk of the ciphertext.
2. If you get a meaningful text (for example by some statistical criterion), tentatively decrypt some more ciphertext until you reach the end of the text. If the text is still meaningful, mark the key as possible solution.
3. Go to the next key.