Modern Cryptography : Theory and Practice

by Mao, Wenbo

• ISBN13: 9780130669438
• ISBN10: 0130669431
• Edition: 1st
• Format: Hardcover
• Copyright: 2004-01-01
• Publisher: Prentice Hall

Summary

bull; Specifies which protocols are to be followed and which are to be avoided, providing security engineers with essential knowledge. bull; Dissects schemes and protocols in standards and real-world cases, pointing out their strong security strengths and weaknesses. bull; Opens the "bag of tricks " attackers use and gives cryptographers countermeasures.

Author Biography

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

Table of Contents

A Short Description of the Book	p. ix
Preface	p. xi
List of Figures	p. xxxiii
List of Algorithms, Protocols and Attacks	p. xxxv
Introduction	p. 1
Beginning with a Simple Communication Game	p. 3
A Communication Game	p. 4
Criteria for Desirable Cryptographic Systems and Protocols	p. 9
Chapter Summary	p. 20
Exercises	p. 20
Wrestling Between Safeguard and Attack	p. 23
Introduction	p. 23
Encryption	p. 24
Vulnerable Environment (the Dolev-Yao Threat Model)	p. 27
Authentication Servers	p. 28
Security Properties for Authenticated Key Establishment	p. 30
Protocols for Authenticated Key Establishment Using Encryption	p. 31
Chapter Summary	p. 51
Exercises	p. 52
Mathematical Foundations	p. 55
Standard Notation	p. 57
Probability and Information Theory	p. 61
Introduction	p. 61
Basic Concept of Probability	p. 62
Properties	p. 63
Basic Calculation	p. 63
Random Variables and their Probability Distributions	p. 66
Birthday Paradox	p. 73
Information Theory	p. 78
Redundancy in Natural Languages	p. 80
Chapter Summary	p. 82
Exercises	p. 82
Computational Complexity	p. 85
Introduction	p. 85
Turing Machines	p. 86
Deterministic Polynomial Time	p. 88
Probabilistic Polynomial Time	p. 103
Non-deterministic Polynomial Time	p. 122
Non-Polynomial Bounds	p. 128
Polynomial-time Indistinguishability	p. 130
Theory of Computational Complexity and Modern Cryptography	p. 133
Chapter Summary	p. 136
Exercises	p. 136
Algebraic Foundations	p. 139
Introduction	p. 139
Groups	p. 139
Rings and Fields	p. 151
The Structure of Finite Fields	p. 153
Group Constructed Using Points on an Elliptic Curve	p. 166
Chapter Summary	p. 173
Exercises	p. 173
Number Theory	p. 175
Introduction	p. 175
Congruences and Residue Classes	p. 175
Euler's Phi Function	p. 184
The Theorems of Fermat, Euler and Lagrange	p. 186
Quadratic Residues	p. 186
Square Roots Modulo Integer	p. 192
Blum Integers	p. 198
Chapter Summary	p. 200
Exercises	p. 201
Basic Cryptographic Techniques	p. 203
Encryption--Symmetric Techniques	p. 205
Introduction	p. 205
Definition	p. 206
Substitution Ciphers	p. 209
Transposition Ciphers	p. 213
Classical Ciphers: Usefulness and Security	p. 214
The Data Encryption Standard (DES)	p. 218
The Advanced Encryption Standard (AES)	p. 222
Confidentiality Modes of Operation	p. 231
Key Channel Establishment for Symmetric Cryptosystems	p. 240
Chapter Summary	p. 242
Exercises	p. 243
Encryption--Asymmetric Techniques	p. 245
Introduction	p. 245
Insecurity of "Textbook Encryption Algorithms"	p. 247
The Diffie-Hellman Key Exchange Protocol	p. 249
The Diffie-Hellman Problem and the Discrete Logarithm Problem	p. 252
The RSA Cryptosystem (Textbook Version)	p. 257
Cryptanalysis Against Public-key Cryptosystems	p. 260
The RSA Problem	p. 261
The Integer Factorization Problem	p. 263
Insecurity of the Textbook RSA Encryption	p. 265
The Rabin Cryptosystem (Textbook Version)	p. 268
Insecurity of the Textbook Rabin Encryption	p. 271
The ElGamal Cryptosystem (Textbook Version)	p. 273
Insecurity of the Textbook ElGamal Encryption	p. 275
Need for Stronger Security Notions for Public-key Cryptosystems	p. 277
Combination of Asymmetric and Symmetric Cryptography	p. 278
Key Channel Establishment for Public-key Cryptosystems	p. 280
Chapter Summary	p. 281
Exercises	p. 281
In an Ideal World: Bit Security of the Basic Public-Key Cryptographic Functions	p. 285
Introduction	p. 285
The RSA Bit	p. 286
The Rabin Bit	p. 290
The ElGamal Bit	p. 292
The Discrete Logarithm Bit	p. 292
Chapter Summary	p. 295
Exercises	p. 296
Data Integrity Techniques	p. 297
Introduction	p. 297
Definition	p. 298
Symmetric Techniques	p. 300
Asymmetric Techniques I: Digital Signatures	p. 305
Asymmetric Techniques II: Data Integrity Without Source Identification	p. 322
Chapter Summary	p. 325
Exercises	p. 326
Authentication	p. 327
Authentication Protocols--Principles	p. 329
Introduction	p. 329
Authentication and Refined Notions	p. 331
Convention	p. 335
Basic Authentication Techniques	p. 337
Password-based Authentication	p. 350
Authenticated Key Exchange Based on Asymmetric Cryptography	p. 358
Typical Attacks on Authentication Protocols	p. 367
A Brief Literature Note	p. 382
Chapter Summary	p. 383
Exercises	p. 383
Authentication Protocols--the Real World	p. 387
Introduction	p. 387
Authentication Protocols for Internet Security	p. 389
The Secure Shell (SSH) Remote Login Protocol	p. 404
The Kerberos Protocol and its Realization in Windows 2000	p. 410
SSL and TLS	p. 416
Chapter Summary	p. 423
Exercises	p. 424
Authentication Framework for Public-Key Cryptography	p. 427
Introduction	p. 427
Directory-Based Authentication Framework	p. 428
Non-Directory Based Public-key Authentication Framework	p. 434
Chapter Summary	p. 456
Exercises	p. 456
Formal Approaches to Security Establishment	p. 459
Formal and Strong Security Definitions for Public-key Cryptosystems	p. 461
Introduction	p. 461
A Formal Treatment for Security	p. 463
Semantic Security--the Debut of Provable Security	p. 467
Inadequacy of Semantic Security	p. 480
Beyond Semantic Security	p. 482
Chapter Summary	p. 496
Exercises	p. 498
Provably Secure and Efficient Public-key Cryptosystems	p. 501
Introduction	p. 501
The Optimal Asymmetric Encryption Padding	p. 503
The Cramer-Shoup Public-key Cryptosystem	p. 523
An Overview of Provably Secure Hybrid Cryptosystems	p. 537
Literature Notes on Practical and Provably Secure Public-key Cryptosystems	p. 539
Chapter Summary	p. 541
Exercises	p. 542
Strong and Provable Security for Digital Signatures	p. 545
Introduction	p. 545
Strong Security Notion for Digital Signatures	p. 547
Strong and Provable Security for ElGamal-family Signatures	p. 548
Fit-for-application Ways for Signing in RSA and Rabin	p. 559
Signcryption	p. 566
Chapter Summary	p. 574
Exercises	p. 575
Formal Methods for Authentication Protocols Analysis	p. 577
Introduction	p. 577
Toward Formal Specification of Authentication Protocols	p. 579
A Computational View of Correct Protocols--the Bellare-Rogaway Model	p. 590
A Symbolic Manipulation View of Correct Protocols	p. 598
Formal Analysis Techniques: State System Exploration	p. 602
Reconciling Two Views of Formal Techniques for Security	p. 614
Chapter Summary	p. 615
Exercises	p. 616
Cryptographic Protocols	p. 617
Zero-Knowledge Protocols	p. 619
Introduction	p. 619
Basic Definitions	p. 620
Zero-knowledge Properties	p. 627
Proof or Argument?	p. 639
Protocols with Two-sided-error	p. 643
Round Efficiency	p. 648
Non-interactive Zero-knowledge	p. 657
Chapter Summary	p. 662
Exercises	p. 663
Returning to "Coin Flipping over Telephone"	p. 665
Blum's "Coin-Flipping-by-Telephone" Protocol	p. 666
Security Analysis	p. 668
Efficiency	p. 669
Chapter Summary	p. 670
Afterremark	p. 671
Bibliography	p. 673
Subject Index	p. 699
Table of Contents provided by Ingram. All Rights Reserved.

Excerpts

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 re