ńņš. 2 |

War.

Ā© 2003 by CRC Press LLC

1.3. Classiļ¬cation of Attacks 27

x Adaptive Chosen-Plaintext

This is a variant of the chosen-plaintext attack where a cryptanalyst can

not only choose the plaintext that is enciphered, but also can modify the choice

based upon the results of previous encryption. Thus, a cryptanalyst can choose

a block of plaintext, then choose another based on the results of the ļ¬rst and

continue this iterative procedure. This is, in general terms, the means by which

DC attacks product ciphers (a notion due to Shannon [205]) which are block

ciphers that iterate several operations such as substitution, transposition, mod-

ular addition or multiplication, and linear transformation.

x Adaptive Chosen-Ciphertext

This is a variant of the chosen-ciphertext attack where a cryptanalyst chooses

ciphertext depending upon previously received ciphertexts. This has been used

successfully against public-key cryptosystems as well (see Chapter 6).

Remark 1.30 It should be pointed out that some sources break up the above

categories and consider, for instance, chosen-plaintext as an active attack, since

the cryptanalysts can choose to have their desired plaintext enciphered and see

the ciphertext which results. However, this is still eavesdropping, so we maintain

the above as the subcategorization of passive attacks since there is no proactive

involvement of the cryptanalyst under our deļ¬nition.

There are also passive attacks that do not involve any cryptanalysis. Loss of

a key through noncryptanalytic techniques is called a compromise. For instance,

a passive attack on pretty good privacy (PGP), which we will study in Chapter

8, called keypress snooping involves an attacker installing a keylogger, which can

capture the password of the target, and involves no cryptanalysis; the system is

completely compromised, and may go completely undetected.

The following provides some important active attacks, but is by no means

exhaustive. Moreover, our primary focus will be on passive attacks on cryp-

tosystems. Active attacks, due to their very nature, are more diļ¬cult to carry

out than passive attacks.

ā· Active Attacks

x Man-in-the-Middle Attack

This is an attack that is particularly relevant for key exchange protocols,

which we will study in Section 2.1.

The central idea is perhaps best described if we take this opportunity to

introduce our ļ¬rst in a list of a cast of characters, who are well-known in the

cryptographic community. There is Alice and her friend Bob who are partici-

pants in all communications, and Mallory, the malicious active attacker. The

central idea of the man-in-the-middle attack is that Mallory assumes a position

between Alice and Bob. Mallory can stop all or parts of the data being sent

by Alice and Bob and substitute them with his own messages. In this fashion,

Ā© 2003 by CRC Press LLC

28 1. History and Basic Cryptographic Concepts

he impersonates Alice and Bob who believe they are communicating with each

other directly, while they are really talking to Mallory.

Diagram 1.31 (Man-in-the-middle Attack)

ā„ Ā ā’ā’ā’ ā’ā’ā’ ā„ Ā

ā’ā’ ā’ā’

ALICE ā ā ā’ ā’

ā’ā’ āā’ā’ ā‚

ā’ā’

M ALLORY BOB ā

ā‚

In Chapter 7, we will see how to prevent this type of attack against public-

key exchange and the providing of digital signatures.

x Rubber-hose Attack

The cryptanalyst threatens, blackmails, or tortures someone until they give

up the key. Sometimes bribery comes into play, in which case, the attack is a

subcategory called a purchase-key attack.

x Timing Attack

This is the most recent of the active attacks described here. This involves

the repeated measuring of the exact execution times of modular exponentiation

operations, the applications of which we will study in Section 2.3. This allows

the cryptanalyst to get information on the decryption exponent in RSA; for

instance (see Chapter 6). Another interpretation of a timing attack would be the

interception of a message, which is re-sent at a later time (called a replay attack

ā” see page 133 for this and other types of attacks). As a precaution against

this type of attack, this active interference could be detected by a timestamp in

messages.

We conclude this section with an illustration of a ciphertext-only attack on

polyalphabetic cryptosystems, developed in 1863.

s Kasiskiā™s1.12 Attack on Polyalphabetic Ciphers

The central idea behind this attack is the observation that repeated por-

tions of plaintext encrypted with the same segment of the key result in identical

ciphertext portions. Therefore, if repeated occurrences in ciphertext are not

accidental, one would expect the same plaintext portion was enciphered, start-

ing from the same position in the key. Consequently, the number of symbols

between the beginnings of repeated ciphertext portions should be a multiple of

the keylength. For instance, if the repeated ciphertext is the adjacent triple of

letters XY Z, called a trigram, and the number of characters between the Z and

1.12 Friedrich W. Kasiski (1805ā“1881) was born on November 29, 1805 in a western Prussian

town. He enlisted in East Prussiaā™s thirty-third Infantry Regiment at the age of seventeen

and retired in 1852 as a major. Although he became interested in cryptography during his

military career, it was not until the 1860ā™s that he published his ideas. In 1863, he published

Die GeheimschRiften und die Dechiļ¬rir-kunst which dealt largely with a general solution,

sought for centuries, for polyalphabetic ciphers with repeating keywords. His revolutionary

work went unrecognized in his time, and he himself turned from cryptography. He took an

active interest in anthropology, publishing his ļ¬ndings in archeological journals. He died on

May 22, 1881, without knowing the impact his work in cryptanalysis would ultimately have.

Ā© 2003 by CRC Press LLC

1.3. Classiļ¬cation of Attacks 29

the occurrence X in the next XY Z is seventeen, and this is not an accident,

then 20 is a multiple of the keylength.

Since some of these repeated segments are coincidental, a means of analyz-

ing these segments, called a Kasiski examination is to compute the greatest

common divisor (gcd) of the collection of all the distances between repeated

segments. Then choosing the largest factor occurring most often among these

gcds is probably the keylength. Once a probable keylength , say, is determined,

a frequency analysis can be done on a breakdown of the ciphertext into classes

(with an individual class containing every -th character (beginning at the n-th

character) for a ļ¬xed n ā N) to determine the suspected key. Then one can ap-

ply knowledge of frequency analysis such as that given in Appendix A on page

203 to actually determine the key, assuming the plaintext is English, which we

will do throughout the text. If the plaintext is another language, comparing

the frequency of ciphertext letters to that of a suspected language actually may

determine that language.

Letā™s apply this to one of our classical polyalphabetic block ciphers discussed

in Section 1.2. We need to introduce another in our cryptographic cast of

characters, Eve, the eavesdropper.

Example 1.32 (Kasiskiā™s Attack on the Vigen`re Cipher)

e

Suppose that the following ciphertext was encrypted with the Vigen`re Cipher

e

and Eve knows this. She wants to use Kasiskiā™s method to decipher it.

EMFQYXRDJEOGYHZW

OHXEYIRLADTUAEKW

OHXFLPZNARXFALVE

DEWGZXIGUEWVVBEK

PHXAYISMELMCJMKQ

XOMJZXIMCGEGZIEV

BODTDEIDKRWUYYCW

First, Eve looks for multiple occurrences in the ciphertext. She discovers

that the trigram OHX has a spacing of 16 between the ļ¬rst O and the next

occurrence of an O in the trigram. Similarly, she ļ¬nds the following spacings:

16 for WOHX, 8 for EW, and 8 for XF. She quickly guesses that since 8

divides all of these, then it is a good assumption that the keylength is 8. She is

now ready to do a frequency analysis, so she breaks the ciphertext down into 8

classes as follows.

Ā© 2003 by CRC Press LLC

30 1. History and Basic Cryptographic Concepts

Initial Position Position in Ciphertext Ciphertext Class

n n + 8k (k = 0, 1, . . . , 13) Letters in positions n + 8k

1 1, 9, . . . , 105 EJOAOADUPEXCBK

2 2, 10, . . . , 106 MEHDHREEHLOGOR

3 3, 11, . . . , 107 FOXTXXWWXMMEDW

4 4, 12, . . . , 108 QGEUFFGVACJGTU

5 5, 13, . . . , 109 YYYALAZVYJZZDY

6 6, 14, . . . , 110 XHIEPLXBIMXIEY

7 7, 15, . . . , 111 RZRKZVIESKIEIC

8 8, 16, . . . , 112 DWLWNEGKMQMVDW

Eve now must analyze every class to determine each individual letter in the

sought-after key. She does this by a series of frequency analysis techniques,

depending on information in Appendix A, as follows.

(1) In the ļ¬rst class, Eve calculates the following frequency of letters and the

percentages of the highest total occurrences in the class: A, 2, 14%; B,

C, D, 1 occurrence each; E, 2, 14%; J,K, 1 occurrence each; O, 2, 14%;

P,U,X, 1 occurrence each.

Since Appendix A tells us that the most frequently occurring letter in the

English language is E, then she has three choices for it. If O is the cipher-

text for it in this class, then this means a shift of 10 places from plaintext

into ciphertext (the distance from E to O). However, by data in Appendix

A, we know that the most commonly occurring letters in the English lan-

guage are the letters in the family E,T,A,I,N,O,S,H,R, and within this

ļ¬rst class of ciphertext, the only consecutively occurring letters are RST,

so if O were E, then the letters RST would encipher to BCD having the

low frequency 1, 1, 1 in this class, so Eve discards this as unlikely. She

notes that it is also unlikely to have E as itself in the ļ¬rst letter of a key,

so she discards this as well and chooses A as the enciphering of E. This

means a shift of 22 places (the distance from E to A modulo 26). Hence,

the ļ¬rst letter of our key is W, the distance from A to W being 22.

Now Eve calculates frequencies for each of the other classes to determine

the remaining seven letters of the key.

(2) D, 1; E, 3, 21.4%; G, 1; H, 3, 21.4%; L,M, 1 occurrence each; O,R. 2

occurrences each, 14% each.

Since no letter other than E is likely to have the high occurrence of 21.4%,

Eve concentrates upon E and H as the two possibilities. If H were the

candidate, then this would mean a shift of 3, so D (3 places to the right

of A in this class) would be the second key letter. However, WD is a

very unlikely beginning of a meaningful English word, so she discards it

and takes E itself as the enciphering of E for a shift of zero places. This

means that A itself is the second key letter. (Result: WA .)

Ā© 2003 by CRC Press LLC

1.3. Classiļ¬cation of Attacks 31

(3) D, E, F, 1 occurrence each; M, 2, 14%; O,T, 1 occurrence each; W, 3,

21.4%; X, 4, 29%.

Here Eve sees that there is no contest for E since X has such a command-

ing frequency, so the shift is 19. Hence, T is the third letter in the key,

19 places from A. (Result: WAT .)

(4) A,C,E, 1 occurrence each; F, 2, 14%; G, 3, 21.4%; J, 1; Q,T, 1 occurrence

each; U, 2, 14%; V, 1.

Again, Eve sees that G is the most likely candidate for E, so she chooses

this which means a shift of 2. Thus, the third letter in the key is C, 2

places from A. (Result: WATC .)

(5) A, 2, 14%; D,J,L,V, 1 occurrence each; Y, 5, 35.7%; Z, 3, 21.4%.

Here Eve employs a diļ¬erent strategy since there are some quite high fre-

quencies in this class. She notes that since RST is the only consecutively

occurring trigram in the most often used English letters, as we observed

for the ļ¬rst class above, and since YZA is the only possible trigram of

consecutive letters in this class, then YZA must be the enciphering of

RST. This is a shift of 7, so H must be the fourth key letter, since H is

7 places to the right of A. (Result: WATCH .)

(6) B, 1; E, 2, 14%; H, 1; I, 3, 21.4%; L,M,P, 1 occurrence each; X, 3,

21.4%, Y, 1.

Here Eve has no consecutive trigrams, so she looks at the most likely can-

didates, I and X, for E. Since X would mean a shift of 19, then the sixth

key letter would be T, but adding a T at this stage would render it mean-

ingless, so Eve chooses I, for a shift of 4, and E is the sixth key letter.

(Result: WATCHE .)

(7) C, 1; E, 2, 14%; I, 3, 21.4%; K,R, 2, 21.4% each; S,V, 1 occurrence each;

Z, 2, 14%.

Here the method breaks down since there are no trigrams and the most

likely candidates for E yield a key letter that does not ļ¬t with what we

already have in step six. Thus, Eve decides to go to the ļ¬nal family and

make an educated guess at the seventh letter.

(8) D, 2, 14%; E, G, K, L, 1 occurrence each; M, 2, 14%; N,Q,V, 1 occur-

rence each; W, 3, 21.4%.

Eve sees that W is the most likely for E so the shift is 18 giving us S a

the eighth key letter. Hence, Eve, sees that we have WATCHE S and

clearly sees the seventh letter should be R, so we have the key

WATCHERS.

The reader may now go to the example on page 16 and Exercises 1.29ā“1.34

for a complete deciphering of the cryptogram.

Ā© 2003 by CRC Press LLC

32 1. History and Basic Cryptographic Concepts

Exercises

In Exercises 1.61ā“1.66, use Kasiskiā™s method to ļ¬nd the key assuming the

ciphertext was obtained via the Vigen`re Cipher. Then use the key to decrypt

e

the message.

1.61.

ZEOLDSTFZEOLDMGTPZUGKQRTU

KCBYOUFZFAGJQSPOMTLVQVXY

1.62.

VFKILRXKFBJYGUYENYR

JAAVADPMNIYGJUXIQ

1.63.

HZVUBLLZXUPBWAJFSBA

MODPFLPPFQXWQBXHW

1.64.

VISHMTEUCRLKMKMXR

FKXVIYLLYFLEHGVSRS

1.65.

OOPETAAYBAARUIWE

JEZEKGIDJTPVTRGQ

1.66.

EALPBNSSVTQVSTZYHGZAVMHYFEK

HYIEPGOFHCEJZBNKJBNULCTGM

UIKYRLSAVOFABTZLPNKTBSRG

1.67.

GZWWNOEJRWEWKFDLYBZWMCWG

HIESROELTIXLYOWZGMDSXSNLUIVC

ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”

You see itā™s like a portmanteau ā” there are two meanings packed up into

one word. from Through the Looking-Glass (1872)

Lewis Carrol (Charles Lutwidge Dodgson) (1832ā“1898)

English writer and logician

Ā© 2003 by CRC Press LLC

ńņš. 2 |