<<

. 2
( 2)



at the right time, and prepare an ambush that turned the tide of the Paci¬c
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
( 2)