[Pulsing Star Animation]

THE BLOCK AND PARRY

A Lesson on Cryptographic Attacks and Countermeasures

TRANSLATION TABLES AND ALGORITHMS. A generalized block cipher maps fixed length blocks on plaintext onto one or more unique blocks of cipher text. The mapping can be stored as a table (subject to size limitations) or, equivalently, as a function for computing table elements as required. A series of tables can be indexed to allow different mappings to be used for each transmission. Equivalently, a mapping algorithm can be parameterized with an index, called a key. The function is written: cipher=f(plain,key)

EXAMPLE SUBSTITUTION CIPHER. Map table #3 ("A" to "D", "B" to "E", etc.) is equivalent to the computable function, f(p,k)=p+k where k=3. Applying table #3 to the sample text "plain" encrypts to "sodlq".

ATTACK - BRUTE FORCE. In the example above, a prospective codebreaker need only try each of the 26 possible keys to find which one yields a readable plaintext.

COUNTERMEASURE - INCREASE KEY SPACE. Extend the number of possible tables by allowing the table to be fully scrambled (i.e. "A" to "D", "B" to "Q", "C" to "Z"). is one of 26! possible mappings of one letter to another). Further extend the key space by using different keys for each position in a block of several letters (key #1 for the 1st 6th and 11th letters and key #2 for the 2nd 7th and 12th letters for 5 separate codes with 26! possible keys each ).

ATTACK - PATTERN ANALYSIS. Patterns inherent in the plaintext may result in detectable patterns in the ciphertext. In English, the letter E occurs more frequently than any other letter. Counting the frequency of letters in the ciphertext may indicate the mapping for E. Frequent count signatures apply to all individual letters and to digraphs, TH occurs more frequently than TR even though R is more common than H. Common words have frequency signatures, AND is more likely than CAT. Words have grammatical syntax and semantic signs when taken in context, for example the 3 letter article in the phrase OVER --- HILL. Word length indicates likely patterns of vowels and consonants; for example, 5 letter words often start and end with a consonant and have a vowel as the third letter. Collectively, the pattern analysis can significantly reduce the attackers search space and allow long samples of code to be readily cracked.

COUNTERMEASURE - REMOVING PATTERNS. Letter frequency can be disguised through one-to-many mappings (i.e. "B" to "QL", "E" to "WX" or "JO" or "LT"). This method causes the ciphertext to be longer than the plaintext. A well designed mapping can completely hide normal letter frequency patterns. A simpler, more effective alternative is to use data compression prior to encryption in order to remove many types of pattern and redundancy. Unlike one-to-many mappings, data compression yields a ciphertext shorter than the original. In addition to preparing the plaintext, the mapping can also be used to mask patterns by using longer block sizes ( "AB" to "LQ", "AC" to "BZ" ...). A simple and effective combination of both techniques is a codebook ("ATTACK" to "L23", "AT" to "B11", "DAWN" to "J83").

ATTACK - KNOWN PLAINTEXT. An attacker may sometimes possess a fully decoded specimen (often secret documents are made public after a period of time). For one-to-one block ciphers, this can be disastrous (if L23 had been used in a declassified message, then it's meaning in other messages would be obvious). Known plaintext allows tampering (intercept the message and replace "J83" with code for DUSK).

COUNTERMEASURE - MAKE EACH USAGE UNIQUE. Frequent key changes reduce the risk. Also, the plaintext taken as a whole can be made unique by adding a date/time stamp or random padding to the beginning of a message. The uniqueness of the message can be diffused to individual blocks through interlinking. For example, cipher-block-chaining prepares plaintext for encoding by adding the result of encoding the previous block. Unique encodings can also result from one-to-many mappings. A systematic approach to one-many-mappings is called probabilistic encryption and results in the same message being encoded in different ways yet still having a unique decryption. The result is mathematically equivalent to adding random padding to each block prior to encoding with a one-to-one mapping.

ATTACK - CHOSEN PLAINTEXT. Sometimes an attacker may have the ability to submit messages of his choice for encryption by a single key and then have the opportunity to examine the resulting ciphertext. This information allows verifiable plaintext guesses at an unknown ciphertext. It also allows sophisticated mathematical analysis on an encryption function with the goal of determining the key. Examples of systems vulnerable to chosen plaintext attacks are automatic encrypting relays, identification-friend-or-foe systems, and password storage systems (as in UNIX access passwords). Japanese surprise was lost at Midway because of a US chosen plaintext attack on the Japanese code (at issue was the code word for Midway Island).

COUNTERMEASURE - PROBABILISTIC ENCRYPTION AND NON-INVERTIBLE FUNCTIONS. The ability to verify plaintext guesses is crippled by probabilistic encryption. The random padding must be added during the encryption process and not by plaintext author. An encryption function calculates a mapping from a key. If the mapping is known, a non-invertible function assures that the key will not be compromised. One of my favorite techniques is to use a key to repeated shuffle a mapping table (shuffles are notoriously difficult to unwind). Invertibility is gray area. Finding a key is pointless if the entire mapping is known. Some simple functions (such as the one key for each letter position) instantly surrender their key in either a known or chosen plaintext attack. The US Data Encryption Standard is a very complex function which does not have obvious inversions, yet it was decertified because designed in invertibility was suspected (another reason was the small key space, 256 keys can be searched by brute force). During WWII, the Axis code, Enigma, was cracked because of invertibility (and some other mathematical symmetries).

ATTACK - BYPASS THE CIPHER. Even sophisticated ciphers get compromised by poor security protocols. Key holders frequently write down passwords and leave them unsecured; soldiers get captured with current codebooks in hand. Passwords are guessable if the user selects their own passwords from a small keyspace (i.e. names of relatives, phone numbers, words found in a dictionary, etc). Under duress, a key holders can be forced to reveal the key (an uncrackable code falls against a grand jury subpoena). Versions of the original plaintext may exist on hard-drives or in hard-copy.

COUNTERMEASURES - GOOD SECURITY PROTOCOLS. Do not write down the key. Change keys often. Use a random selection method (i.e. dice) to create keys. Have different keys for each possible recipient to reduce the number of people available to be compelled to reveal the key. If possible, shroud messages with legal protections (i.e. attorney-client privilege, first amendment protections) and do not waive those rights. Do not print the plaintext. Shred originals. Use a disk erase tool to overwrite dormant plaintext files.

ATTACK - TRAFFIC ANALYSIS. Old crypto saying: you can throw a blanket over a camel but you can't hide the humps. Sudden increases in the volume of coded message can be as strong indicator of imminent military activity. Suddenly talking in a whisper when someone walks by will raise a flag. Sending a single coded message among many unencoded messages immediately flags will focus attention on that one message. Message length may suggest its content( "I'm fine" versus "Well, the troubles first started when ...")

COUNTERMEASURES - CAMOUFLAGE THE TRAFFIC. Routinely password files and encrypt messages so as to not highlight a change in security level. When message length provides a unique signature, the pad the file with random filler.

RECOMMENDATION - COMBINED COUNTERMEASURES. First, compress your plaintext to remove patterns. Second, add random padding and/or a date stamp. Third apply a fully scrambled, one-to-one mapping with a large blocksize and keyspace. Fourth, apply a block interlinking method such as cipher block chaining. Fifth, change keys often. Sixth, apply strict security protocols (ideally, one tool should take care of random key generation and saving only in encrypted form). Seventh, routinely encrypt files and message traffic.

SCRIPT - SESSION WITH COUNTERMEASURES

Randgen goodkey1 goodkey2				; Select two good keys
Randgen rand.fil						; Create random padding
Pkzip -ex crypt.zip rand.fil plain.txt 	; Data stamp, add pad, compress, and add integrity check
Diffuse crypt.zip			    		; Interlink blocks in plaintext
DES goodkey1 crypt.zip					; Use any strong block cipher
Diffuse crypt.zip						; Interlink blocks i n ciphertext and protect key #1
DES goodkey2 crypt.zip					; Lock-in interlinks
Mail name@address crypt.zip				; Beam it out
Wipefile crypt.zip plain.txt rand.fil	; Destroy traces of unencrypted file

Crypto links: Algorithms, Software

Click here to return to home page.