Modern Cryptography: Theory and Practice [Hardcover]

Many cryptographic schemes and protocols, especially those based on public-keycryptography, have basic or so-called "textbook crypto" versions, as these versionsare usually the subjects for many textbooks on cryptography. This book takes adifferent approach to introducing cryptography: it pays much more attention tofit-for-application aspects of cryptography. It explains why "textbook crypto" isonly good in an ideal world where data are random and bad guys behave nicely.It reveals the general unfitness of "textbook crypto" for the real world by demonstratingnumerous attacks on such schemes, protocols and systems under variousreal-world application scenarios. This book chooses to introduce a set of practicalcryptographic schemes, protocols and systems, many of them standards or de factoones, studies them closely, explains their working principles, discusses their practicalusages, and examines their strong (i.e., fit-for-application) security properties, oftenwith security evidence formally established. The book also includes self-containedtheoretical background material that is the foundation for modern cryptography.

"This book would be a good addition to any cryptographer's bookshelf. The book is self-contained; it presents all the background material to understand an algorithm and all the development to prove its security. I'm not aware of another book that's as complete as this one."

--Christian Paquin, Cryptographic/Security Developer, Silanis Technology Inc. "The book is both complete, and extraordinarily technically accurate. It would certainly be a useful addition to any cryptographer's or crypto-engineer's library."

--Marcus Leech, Advisor, Security Architecture and Planning, Nortel Networks Build more secure crypto systems--and prove their trustworthiness Modern Cryptography is the indispensable resource for every technical professional who needs to implement strong security in real-world applications.

Leading HP security expert Wenbo Mao explains why "textbook" crypto schemes, protocols, and systems are profoundly vulnerable by revealing real-world-scenario attacks. Next, he shows how to realize cryptographic systems and protocols that are truly "fit for application"--and formally demonstrates their fitness. Mao presents practical examples throughout and provides all the mathematical background you'll need.

Coverage includes:

• Crypto foundations: probability, information theory, computational complexity, number theory, algebraic techniques, and more
• Authentication: basic techniques and principles vs. misconceptions and consequential attacks
• Evaluating real-world protocol standards including IPSec, IKE, SSH, TLS (SSL), and Kerberos
• Designing stronger counterparts to vulnerable "textbook" crypto schemes

Mao introduces formal and reductionist methodologies to prove the "fit-for-application" security of practical encryption, signature, signcryption, and authentication schemes. He gives detailed explanations for zero-knowledge protocols: definition, zero-knowledge properties, equatability vs. simulatability, argument vs. proof, round-efficiency, and non-interactive versions.

WENBO MAO, PhD, is a Technical Contributor to the Trusted Systems Lab at Hewlett-Packard Laboratories, Bristol, UK. Mao leads HP's participation and research activities in Computer Aided Solutions to Secure Electronic Commerce Transactions (CASENET), a research project funded by the European Union. His research interests include cryptography, computer security, and formal methods. He is a member of the International Association for Cryptographic Research (IACR), the Institute of Electrical and Electronics Engineers (IEEE), and the British Computer Society (BCS).

Preface

Our society has entered an era where commerce activities, business transactionsand government services have been, and more and more of them will be, conductedand offered over open computer and communications networks such as the Internet,in particular, via WorldWideWeb-based tools. Doing things online has a greatadvantage of an always-on availability to people in any corner of the world. Hereare a few examples of things that have been, can or will be done online:

Banking, bill payment, home shopping, stock trading, auctions, taxation,gambling, micro-payment (e.g., pay-per-downloading), electronicidentity, online access to medical records, virtual private networking, securedata archival and retrieval, certified delivery of documents, fair exchangeof sensitive documents, fair signing of contracts, time-stamping,notarization, voting, advertising, licensing, ticket booking, interactivegames, digital libraries, digital rights management, pirate tracing, . . .

And more can be imagined.

Fascinating commerce activities, transactions and services like these are onlypossible if communications over open networks can be conducted in a secure manner.An effective solution to securing communications over open networks is to applycryptography. Encryption, digital signatures, password-based user authentication,are some of the most basic cryptographic techniques for securing communications.However, as we shall witness many times in this book, there are surprising subtletiesand serious security consequences in the applications of even the most basiccryptographic techniques. Moreover, for many "fancier" applications, such as manylisted in the preceding paragraph, the basic cryptographic techniques are no longeradequate.

With an increasingly large demand for safeguarding communications over opennetworks for more and more sophisticated forms of electronic commerce, businessand servicesa, an increasingly large number of information security professionalsaGartner Group forecasts that total electronic business revenues for business to business (B2B)and business to consumer (B2C) in the European Union will reach a projected US $2.6trillion inwill be needed for designing, developing, analyzing and maintaining informationsecurity systems and cryptographic protocols. These professionals may range fromIT systems administrators, information security engineers and software/hardwaresystems developers whose products have security requirements, to cryptographers.

In the past few years, the author, a technical consultant on information securityand cryptographic systems at Hewlett-Packard Laboratories in Bristol, haswitnessed the phenomenon of a progressively increased demand for information securityprofessionals unmatched by an evident shortage of them. As a result, manyengineers, who are oriented to application problems and may have little propertraining in cryptography and information security have become "roll-up-sleeves"designers and developers for information security systems or cryptographic protocols.This is in spite of the fact that designing cryptographic systems and protocolsis a diffcult job even for an expert cryptographer.

The author's job has granted him privileged opportunities to review many informationsecurity systems and cryptographic protocols, some of them proposedand designed by "roll-up-sleeves" engineers and are for uses in serious applications.In several occasions, the author observed so-called "textbook crypto" features insuch systems, which are the result of applications of cryptographic algorithms andschemes in ways they are usually introduced in many cryptographic textbooks. Directencryption of a password (a secret number of a small magnitude) under abasic public-key encryption algorithm (e.g., "RSA") is a typical example of textbookcrypto. The appearances of textbook crypto in serious applications with a"non-negligible probability" have caused a concern for the author to realize thatthe general danger of textbook crypto is not widely known to many people whodesign and develop information security systems for serious real-world applications.

Motivated by an increasing demand for information security professionals anda belief that their knowledge in cryptography should not be limited to textbookcrypto, the author has written this book as a textbook on non-textbook cryptography.This book endeavors to:

• Introduce a wide range of cryptographic algorithms, schemes and protocols
• with a particular emphasis on their non-textbook versions.
• Reveal general insecurity of textbook crypto by demonstrating a large number
• of attacks on and summarizing typical attacking techniques for such systems.
• Provide principles and guidelines for the design, analysis and implementation
• of cryptographic systems and protocols with a focus on standards.
• Study formalism techniques and methodologies for a rigorous establishment of strong and fit-for-application security notions for cryptographic systems and
• protocols.
• Include self-contained and elaborated material as theoretical foundations of
• modern cryptography for readers who desire a systematic understanding of
• the subject.

Scope

Modern cryptography is a vast area of study as a result of fast advances made in thepast thirty years. This book focuses on one aspect:in troducing fit-for-applicationcryptographic schemes and protocols with their strong security properties evidentlyestablished.

The book is organized into the following six parts:

Part I This part contains two chapters (1--2) and serves an elementary-level introductionfor the book and the areas of cryptography and information security.Chapter 1 begins with a demonstration on the effectiveness of cryptographyin solving a subtle communication problem. A simple cryptographic protocol(first protocol of the book) for achieving "fair coin tossing over telephone"will be presented and discussed. This chapter then carries on to conduct acultural and "trade" introduction to the areas of study. Chapter 2 uses aseries of simple authentication protocols to manifest an unfortunate fact inthe areas:pitfalls are everywhere.As an elementary-level introduction, this part is intended for newcomers tothe areas.

Part II This part contains four chapters (3--6) as a set of mathematical backgroundknowledge, facts and basis to serve as a self-contained mathematicalreference guide for the book. Readers who only intend to "knowhow," i.e.,know how to use the fit-for-application crypto schemes and protocols, mayskip this part yet still be able to follow most contents of the rest of the book.Readers who also want to "know-why," i.e., know why these schemes andprotocols have strong security properties, may find that this self-containedmathematical part is a suffcient reference material. When we present workingprinciples of cryptographic schemes and protocols, reveal insecurity forsome of them and reason about security for the rest, it will always be possiblefor us to refer to a precise point in this part of the book for supportingmathematical foundations.This part can also be used to conduct a systematic background study of thetheoretical foundations for modern cryptography.

Part III This part contains four chapters (7--10) introducing the most basic cryptographicalgorithms and techniques for providing privacy and data integrity protections. Chapter 7 is for symmetric encryption schemes, Chapter 8, asymmetrictechniques. Chapter 9 considers an important security quality possessedby the basic and popular asymmetric cryptographic functions whenthey are used in an ideal world in which data are random. Finally, Chapter10 covers data integrity techniques.Since the schemes and techniques introduced here are the most basic ones,many of them are in fact in the textbook crypto category and are consequentlyinsecure. While the schemes are introduced, abundant attacks onmany schemes will be demonstrated with warning remarks explicitly stated.For practitioners who do not plan to proceed with an in-depth study of fitfor-application crypto and their strong security notions, this textbook cryptopart will still provide these readers with explicit early warning signals on thegeneral insecurity of textbook crypto.

Part IV This part contains three chapters (11--13) introducing an important notionin applied cryptography and information security:authen tication. Thesechapters provide a wide coverage of the topic. Chapter 11 includes technicalbackground, principles, a series of basic protocols and standards, common attackingtricks and prevention measures. Chapter 12 is a case study for fourwell-known authentication protocol systems for real world applications. Chapter13 introduces techniques which are particularly suitable for open systemswhich cover up-to-date and novel techniques.Practitioners, such as information security systems administration staff in anenterprise and software/hardware developers whose products have securityconsequences may find this part helpful.

Part V This part contains four chapters (14--17) which provide formalism andrigorous treatments for strong (i.e., fit-for-application) security notions forpublic-key cryptographic techniques (encryption, signature and signcryption)and formal methodologies for the analysis of authentication protocols. Chapter14 introduces formal definitions of strong security notions. The next twochapters are fit-for-application counterparts to textbook crypto schemes introducedin Part III, with strong security properties formally established (i.e.,evidently reasoned). Finally, Chapter 17 introduces formal analysis methodologiesand techniques for the analysis of authentication protocols, which wehave not been able to deal with in Part IV.

Part VI This is the final part of the book. It contains two technical chapters (18--19) and a short final remark (Chapter 20). The main technical content of thispart, Chapter 18, introduces a class of cryptographic protocols called zeroknowledgeprotocols. These protocols provide an important security service claimant. Zero-kno...