APPLl ED CRYPTANALYSIS
Breaking Ciphers in the Real World
Mark
Stamp
Richard
M.
Low
San
Jose State University
San Jose,
CA
BICENTENNIAL
BICENTENNIAL
WILEY-INTERSCIENCE
A
JOHN
WILEY
&
SONS,
INC., PUBLICATION
This Page Intentionally Left Blank
APPLIED CRYPTANALYSIS
THE
WILEY
BICENTENNIAL-KNOWLEDGE
FOR GENERATIONS
ach generation has its unique needs and aspirations. When Charles Wiley first
opened his small printing shop in lower Manhattan in
1807,
it was a generation

EXECUTIVE OFFICER
CHAIRMAN
OF
THE
BOARD
APPLl ED CRYPTANALYSIS
Breaking Ciphers in the Real World
Mark
Stamp
Richard
M.
Low
San
Jose State University
San Jose,
CA
BICENTENNIAL
BICENTENNIAL
WILEY-INTERSCIENCE
A
JOHN
WILEY
&
SONS,
INC., PUBLICATION
Copyright
0
2007 by John Wiley
&
Sons, Inc.

completeness of the contents
of
this book and specifically disclaim any implied warranties of
merchantability
or
fitness for a particular purpose. No warranty may be created
or
extended by sales
representatives
or written sales materials. The advice and strategies contained herein may not be
suitable for your situation.
You
should consult with a professional where appropriate. Neither the
publisher nor author shall be liable for any
loss
of profit or any other commercial damages, including
but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services
or
for technical support, please contact our
Customer Care Department within the United States at (800) 762-2974, outside the United States at
(317) 572-3993
or
fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may
not be available in electronic format.
For
information about Wiley products, visit our web site at
www.wiley.com.
Wiley Hicentennial

Printed in the United States
of
America
10987654321
To
Melody, Austin, and Males
~
MSS
TO
Amy
-
RML
This Page Intentionally Left Blank
Contents
Preface xiii
About the Authors xvii
Acknowledgments xix
1
Classic Ciphers
1
1.1 Introduction

1
1.2
Good Guys and Bad Guys

1
1.3
Terminology



2.2.2
Enigma Keyspace

2.2.3 Rotors

2.2.4 Enigma Attack

2.2.5 More Secure Enigma?

2.3 Purple

2.3.1 Purple Cipher Machine

2.3.2 Purple Keyspace

2.3.3 Purple Diagnosis

2.3.4 Decrypting Purple

2.3.5 Purple versus Enigma

2.4 Sigaba

2.2.1 Enigma Cipher Machine

25
25
26
26

2.6 Problerns

69
3
Stream
Ciphers
79
3.1
Introduction

79
3.2 Shift Registers

81
3.2.1 Berlekamp-Massey Algorithm

83
3.2.2 Cryptographically Strong Sequences

85
3.2.3 Shift Register-Based Stream Ciphers

89
3.2.4 Correlation Attack

90
3.3
ORYX

93


111
3.5.2
PKZIP
Attack

113
3.5.3 Improved PKZIP?

120
3.6 Summary

120
3.7 Problems

121
4
Block
Ciphers
127
4.1 Introduction

127
4.2 Block Cipher Modes

128
4.3 Feistel Cipher

131
4.4 Hellman’s Time-Memory Trade-off

ix
4.5.4 CMEA Chosen Plaintext Attack

148
4.5.5 SCMEA Known Plaintext Attack

151
4.5.6 CMEA Known Plaintext Attack

158
4.5.7 More Secure CMEA?

159
4.6 Akelarre

160
4.6.1 Akelarre Cipher

160
4.6.2 Akelarre Attack

166
4.6.3 Improved Akelarre?

169
4.7 FEAL

170
4.7.1
FEAL-4

200
5.2.2 Birthday Attacks on Hash Functions

201
5.2.3 Digital Signature Birthday Attack

202
5.2.4 Nostradamus Attack

203
5.3 MD4

208
5.3.1
MD4
Algorithm

208
5.3.2 MD4 Attack

210
5.3.3 A Meaningful Collision

224
5.4 MD5

225
5.4.1 MD5 Algorithm

225

Public
Key
Systems
265
6.1 Introduction

265
6.2 MerkleeHellman Knapsack

267
6.2.1 Lattice-Reduction Attack

270
6.2.2 Knapsack Conclusion

275
X
CONTENTS
6.3
Difie-Hellman Key Exchange

6.3.1
Man-in-the-Middle Attack

6.3.2
Diffie-Hellman Conclusion

6.4
Arithmetica Key Exchange



6.7.2
Multiple Transmission Attack

6.7.3
Chosen Ciphertext Attack

6.7.4
NTRU
Conclusion

6.8
ElGarnal Signature Scheme

6.8.1
Mathematical Issues

6.8.2
ElGamal Signature Conclusioil

6.9
Summary

6.10
Problems

7
Public
Key
Attacks

7.3.4
Discrete Log Conchlsions

7.4
RSA Iniplenieritation Attacks

7.4.1
Tinling Attacks

7.4.2
Glitchirlg Attack

7.4.3
Implementatiorl Attacks Conclusiorls

7.5
Summary

7.6
Problems

275
277
278
279
283
284
284
285
288

355
CONTENTS
xi
Appendix
361
A-1
MD5Tables

361
A-2
Math

371
A-2.1
Number
Theory

371
A-2.2
Group Theory

372
A-2.3
Ring
Theory

372
A-2.4
Linea.
r

ematical background. Some of the public key topics are inherently more
mathematical, but in every case we have strived to minimize the advanced
mathematics. We also believe that we have provided enough background in-
formation
so
that the book is essentially self-contained. Some of the more
advanced mathematical topics are treated briefly in the Appendix. Any moti-
vated upper-division undergraduate student-in any technical field of study-
should be able to tackle this book. Some of the material is not easy, but those
who persist
will
be rewarded with
a
solid understanding of cryptanalysis, as
well
as
the knowledge, tools, and experience to confidently explore cutting-
edge cryptanalytic topics.
We have provided an extensive set of problems for each chapter.
A
few
of
these problems are relatively easy, but most range from moderate to some-
what challenging. Generally, we have tried to avoid obvious problems
of
the
“implement such-and-such attack” variety.
Of
course, it is useful and instruc-
tive

the homework problems require some computer
programming.
For the terminally cryptanalytically insane, we have created
it
collection
of
challenge problems. These problems, which are posted on the textbook
website at

consist primarily
of
cryptanalytic challenges based on the ciphers and attacks
presented in the text.
A
few research-oriented problems are
also
included.
Each problem carries
a
difficulty rating
so
that you will have some idea
of
what
you
might be getting into. For each challenge problem,
a
small prize2 is
offered to the first solver. We promise to update the website as the challenge
problems are solved.

5.
Hash Functions
6.
Public Key Systems
7.
Public Key Attacks
Enigma, Purple, Sigaba
Shift registers,
correlation at tacks,
ORYX.
RC4,
PKZIP
Block cipher modes,
MAC, Hellman's TMTO,
CMEA, Akelarre,
FEAL
HMAC, birthday attacks,
Nostrasamus at tack,
MD4, MD5
Knapsack, Diffie-Hellman,
Arithmetica, RSA
Rabin, NTRU, EIGamal
Factoring, discrete log,
RSA timing attacks,
RSA ditching attack
Y
-
'The
emphasis
here

a
relatively generic
method of attack (correlation attacks, Hellman’s TMTO and birthday at-
tacks, respectively). These attacks are interesting in their own right, but
each also serves as an introduction to the type of cipher under consideration.
Each of these chapters then segues into the cryptanalysis of specific ciphers.
For public key crypto, the introductory material has been expanded to
an entire chapter. In Chapter
6,
several public key systems are introduced
and discussed from the perspective of relatively straightforward attacks or
implementation issues that can lead to weaknesses. Then selected public key
attacks are covered in depth in Chapter
7.
The chapters are highly independent of each other, as are many of the sec-
tions within chapters. The most dependent chapters are
6
and
7,
which cover
public key crypto. In addition, some familiarity with hashing (Chapter 5)
would be useful before diving into the public key material. The terminology
and background covered in Chapter
1
is used throughout the text. Regardless
of your background in cryptography, we recommend that you read Chapter
1
first, since terminology is not consistent throughout the crypto world. Not
only is crypto terminology inconsistent, but notation is even worse. Notation-
wise, we have tried to be as internally consistent as possible. Consequently,

Authors
Mark Stamp has an extensive background in information security in general
and cryptography in particular, having spent more than seven years
as
a
Cryptologic Mathematician
at
the National Security Agency. His other rele-
vant experience includes two years as Chief Cryptologic Scientist at
a
small
Silicon Valley startup company. Since the demise of his startup company
in
2002,
he has been
a
faculty member in the department
of
computer science
at San Jose State University, where he primarily teaches courses in informa-
tion security. In
2005,
Dr. Stamp published his first textbook,
Information
Security: Principles
a.nd
Practice
(Wiley Interscience).
Richard
M.

Richard Low deserves credit for enthusiastically signing on to this project
and for convincing
me
to persevere at
a
couple of points where
I
was ready
to throw in the towel. He also tolerated my occasional rants very well.
A very special thanks to Wan-Teh Chang for his careful reading of most
sections of this book. Wan-Teh has an excellent eye for detail and he provided
numerous corrections and useful suggestions.
Thanks are due to all of the people at Wiley who were involved with this
book. In particular,
I
want to thank Paul Petralia, Whitney A. Lesch, and
Kellsee Chu who were extremely helpful throughout.
Last but certainly not least, thanks to my lovely wife, Melody, and my
two boys, Austin and Miles, for their patience during the seemingly endless
hours
I
spent working on this project.
~-
MSS
My
love of mathematics was cultivated by many
of
my former math teach-
ers (from junior high school to graduate school). Those that come particularly
to mind include: Joseph Buckley, Gary Chartrand, Daniel Goldston, Doug

Barr
[7]
presents a readable introduction to cryptography,
Spillman [139] nicely covers the cryptanalysis of several classic cipher systems
and Bauer
[8]
provides rigorous coverage of a large number of classical crypto
topics. The ciphers we discuss in this chapter have been selected to illustrate
a
few important points that arise in upcoming chapters.
Even if you are familiar with classical cryptosystems, you should read
the next two sections where terminology is discussed, since the terminology
in cryptography is not always consistent. In addition, the material in Sec-
tions 1.4.3 and 1.4.4 is directly referenced in upcoming chapters.
1.2
Good
Guys
and Bad
Guys
In cryptography, it is traditional that Alice and Bob are the good guys who
are trying to communicate securely over an insecure channel. We employ
Trudy (the “intruder”)
as
our generic bad guy. Some books have a whole
cast of bad guys with the name indicating the particular evil activity (Eve,
the eavesdropper, for example), but we use Trudy
as
our all-purpose bad
“guy”
.

(the breaking
of
secret codes). The secret
codes themselves are known
as
ciphers
or
cryptosystems.
In this book, we are
focused on cryptanalysis, but many topics in cryptography naturally arise.
It is common practice to use the term cryptography as a synonym for
cryptology, and we generally follow this practice. In fact, we often use
crypto
as shorthand for cryptology, cryptography, cryptanalysis, or any variety of
other crypto-related topics. The precise meaning should be clear from the
context.
The original readable message is the
plaintext,
while the
ciphertext
is the
unreadable text that results from
encrypting
the plaintext.
Decryption
is the
inverse process, where the ciphertext is converted into plaintext.
A
key
is used to configure

some
sort has been used to read the messages, while
decryption implies that the plaintext has been retrieved using the key by the
expectcd process. Of course,
if
Trudy recovers the key via cryptanalysis, then
she can simply decrypt
a
particular ciphertext.
The typical encryption and decryption process is illustrated in Figure
1.1,
where
Pi
is
the ith unit
of
plaintext (which may be
a
bit, a letter,
a
word, or
a
la.rger block, depending
on
the particular cipher),
Ci
is the corresponding
unit
of
ciphertext, and the squiggly line represenh the transmission