A SHORT DESCRIPTION OF THE BOOK
PREFACE
LIST OF FIGURES
LIST OF ALGORITHMS, PROTOCOLS AND ATTACKS
I INTRODUCTION
1 BEGINNING WITH A SIMPLE COMMUNICATION GAME
1.1 A Communication Game
1.1.1 Our First Application of Cryptography
1.1.2 An Initial Hint on Foundations of Cryptography
1.1.3 Basis of Information Security: More than Computational
Intractability
1.1.4 Modern Role of Cryptography: Ensuring Fair Play of Games
1.2 Criteria for Desirable Cryptographic Systems and Protocols
1.2.1 Stringency of Protection Tuned to Application Needs
1.2.2 Confidence in Security Based on Established Pedigree
1.2.3 Practical Efficiency
1.2.4 Use of Practical and Available Primitives and Services
1.2.5 Explicitness
1.2.6 Openness
1.3 Chapter Summary
Exercises
2 WRESTLING BETWEEN SAFEGUARD AND ATTACK
2.1 Introduction
2.1.1 Chapter Outline
2.2 Encryption
2.3 Vulnerable Environment the Dolev-Yao Threat Model
2.4 Authentication Servers
2.5 Security Properties for Authenticated Key Establishment
2.6 Protocols for Authenticated Key Establishment Using Encryption
2.6.1 Protocols Serving Message Confidentiality
2.6.2 Attack, Fix, Attack, Fix ...
2.6.3 Protocol with Message Authentication
2.6.4 Protocol With Challenge-Response
2.6.5 Protocol With Entity Authentication
2.6.6 A Protocol Using Public-key Cryptosystems
2.7 Chapter Summary
Exercises
II MATHEMATICAL FOUNDATIONS
STANDARD NOTATION
3 PROBABILITY AND INFORMATION THEORY
3.1 Introduction
3.1.1 Chapter Outline
3.2 Basic Concept of Probability
3.3 Properties
3.4 Basic Calculation
3.4.1 Addition Rules
3.4.2 Multiplication Rules
3.4.3 The Law of Total Probability
3.5 Random Variables and their Probability Distributions
3.5.1 Uniform Distribution
3.5.2 Binomial Distribution
3.5.3 The Law of Large Numbers
3.6 Birthday Paradox
3.6.1 Application of Birthday Paradox: Pollard´s Kangaroo
Algorithm for Index Computation
3.7 Information Theory
3.7.1 Properties of Entropy
3.8 Redundancy in Natural Languages
3.9 Chapter Summary
Exercises
4 COMPUTATIONAL COMPLEXITY
4.1 Introduction
4.1.1 Chapter Outline
4.2 Turing Machines
4.3 Deterministic Polynomial Time
4.3.1 Polynomial-Time Computational Problems
4.3.2 Algorithms and Computational Complexity Expressions
4.4 Probabilistic Polynomial Time
4.4.1 Error Probability Characterizations
4.4.2 Subclass Always Fast and Always Correct
4.4.3 Subclass Always Fast and Probably Correct
4.4.4 Subclass Probably Fast and Always Correct
4.4.5 Subclass Probably Fast and Probably Correct
4.4.6 Efficient Algorithms
4.5 Non-deterministic Polynomial Time
4.5.1 Non-deterministic Polynomial-time Complete
4.6 Non-Polynomial Bounds
4.7 Polynomial-time Indistinguishability
4.8 Theory of Computational Complexity and Modern Cryptography
4.8.1 A Necessary Condition
4.8.2 Not a Sufficient Condition
4.9 Chapter Summary
Exercises
5 ALGEBRAIC FOUNDATIONS
5.1 Introduction
5.1.1 Chapter Outline
5.2 Groups
512.1 Lagrange´s Theorem
5.2.2 Order of Group Element
5.2.3 Cyclic Groups
5.2.4 The Multiplicative Group Z*n
5.3 Rings and Fields
5.4 The Structure of Finite Fields
5.4.1 Finite Fields of Prime Numbers of Elements
5.4.2 Finite Fields Modulo Irreducible Polynomials
5.4.3 Finite Fields Constructed Using Polynomial Basis
5.4.4 Primitive Roots
5.5 Group Constructed Using Points on an Elliptic Curve
5.5.1 The Group Operation
5.5.2 Point Multiplication
5.5.3 Elliptic Curve´Discrete Logarithm Problem
5.6 Chapter Summary
Exercises
6 NUMBER THEORY
6.1 Introduction
6.1.1 Chapter Outline
6.2 Congruences and Residue Classes
6.2.1 Congruent Properties for Arithmetic in Zn
6.2.2 Solving Linear Congruence in Zn
6.2.3 The Chinese Remainder Theorem
6.3 Euler´s Phi Function
6.4 The Theorems of Fermat, Euler and Lagrange
6.5 Quadratic Residues
6.5.1 Quadratic Residuosity
6.5.2 Legendre-Jacobi Symbols
6.6 Square Roots Modulo Integer
6.6.1 Computing Square Roots Modulo Prime
6.6.2 Computing Square Roots Modulo Composite
6.7 Blum Integers
6.8 Chapter Summary
Exercises
III BASIC CRYPTOGRAPHIC TECHNIQUES
7 ENCRYPTION--SYMMETRIC TECHNIQUES
7.1 Introduction
7.1.1 Chapter Outline
7.2 Definition
7.3 Substitution Ciphers
7.3.1 Simple Substitution Ciphers
7.3.2 Polyalphabetic Ciphers
7.3.3 The Vernam Cipher and the One-Time Pad
7.4 Transposition Ciphers
7.5 Classical Ciphers: Usefulness and Security
7.5.1 Usefulness of Classical Ciphers
7.5.2 Security of Classical Ciphers
7.6 The Data Encryption Standard DES
7.6.1 A Description of the DES
7.6.2 The Kernel Functionality of the DES: Random and
Non-linear Distribution of Message
7.6.3 The Security of the DES
7.7 The Advanced Encryption Standard AES
7.7.1 An Overview of the Rijndael Cipher
7.7.2 The Internal Functions of the Rijndael Cipher
7.7.3 Summary of the Roles of the Rijndael Internal Functions
7.7.4 Fast and Secure Implementation
7.7.5 Positive Impact of the AES on Applied Cryptography
7.8 Confidentiality Modes of Operation
7.8.1 The Electronic Codebook Mode .ECB
7.8.2 The Cipher Block Chaining Mode CBC
7.8.3 The Cipher Feedback Mode CFB
7.8.4 The Output Feedback Mode OFB
7.8.5 The Counter Mode CTR
7.9 Key Channel Establishment for Symmetric Cryptosystems
7.10 Chapter Summary
Exercises
8 ENCRYPTION--ASYMMETRIC TECHNIQUES
8.1 Introduction
8.1.1 Chapter Outline
8.2 Insecurity of Textbook Encryption Algorithms
8.3 The Diffie-Hellman Key Exchange Protocol
8.3.1 The Man-in-the-Middle Attack
8.4 The Diffie-Hellman Problem and the Discrete Logarithm Problem
8.4.1 Importance of Arbitrary Instances for Intractability
Assumptions
8.5 Encryption in RSA Textbook Version
8.6 Cryptanalysis Against Public-key Cryptosystems
8.7 The RSA Problem
8.8 The Integer Factorization Problem
8.9 Insecurity of the Textbook RSA Encryption
8.9.1 Meet-in-the-Middle Attack and Active Attack on
the Textbook RSA
8.10 Encryption in Rabin Textbook Version
8.11 Insecurity of the Textbook Rabin Encryption
8.12 Encryption in ElGamal Textbook Version
8.13 Insecurity of the Textbook E1Gamal Encryption
8.13.1 Meet-in-the-Middle Attack and Active Attack on
the Textbook E1Gamal Encryption
8.14 Need for Stronger Security Notions for Public-key Cryptosystems
8.15 Combination of Asymmetric and Symmetric Cryptography
8.16 Key Channel Establishment for Public-key Cryptosystems
8.17 Chapter Summary
Exercises
9 IN AN IDEAL WORLD: BIT SECURITY OF THE BASIC
PUBLIC-KEY CRYPTOGRAPHIC FUNCTIONS
9.1 Introduction
9.1.1 Chapter Outline
9.2 The RSA Bit
9.3 The Rabin Bit
9.3.1 The Blum-Blum-Shub Pseudo-random Bits Generator
9.4 The ElGamal Bit
9.5 The Discrete Logarithm Bit
9.6 Chapter Summary
Exercises
10 DATA INTEGRITY TECHNIQUES
10.1 Introduction
10.1.1 Chapter Outline
10.2 Definition
10.3 Symmetric Techniques
10.3.1 Cryptographic Hash Functions
10.3.2 MAC Based on a Keyed Hash Function
10.3.3 MAC Based on a Block Cipher Encryption Algorithm
10.4 Asymmetric Techniques h Digital Signatures
10.4.1 Textbook Security Notion for Digital Signatures
10.4.2 Signing in RSA Textbook Version
10.4.3 Informal Security Argument for the RSA Signature
10.4.4 Signing in Rabin Textbook Version
10.4.5 A Paradoxical Security Basis for Signing in Rabin
10.4.6 The ElGamal Signature
10.4.7 Informal Security Argument for the ElGamal Signature
10.4.8 Signature Schemes in the ElGamal Signature Family
10.4.9 Formal Security Proof for Digital Signature Schemes
10.5 Asymmetric Techniques II: Data Integrity Without Source
Identification
10.6 Chapter Summary
Exercises
IV AUTHENTICATION
11 AUTHENTICATION PROTOCOLS- PRINCIPLES
11.1 Introduction
11.1.1 Chapter Outline
11.2 Authentication and Refined Notions
11.2.1 Data-Origin Authentication
11.2.2 Entity Authentication
11.2.3 Authenticated Key Establishment
11.2.4 Attacks on Authentication Protocols
11.3 Convention
11.4 Basic Authentication Techniques
11.4.1 Message Freshness and Principal Liveness
11.4.2 Mutual Authentication
11.4.3 Authentication Involving Trusted Third Party
11.5 Password-based Authentication
11.5.1 Needham´s Password Protocol and its Realization in
the UNIX Operating System
11.5.2 A One-time Password Scheme and a Flawed Modification
11.5.3 Add Your Own Salt: Encrypted Key Exchange EKE
11.6 Authenticated Key Exchange Based on Asymmetric Cryptography
11.6.1 The Station-to-Station Protocol
11.6.2 A Flaw in a Simplified STS Protocol
11.6.3 A Minor Flaw of the STS Protocol
11.7 Typical Attacks on Authentication Protocols
11.7.1 Message Replay Attack
11.7.2 Man-in-the-Middle Attack
11.7.3 Parallel Session Attack
11.7.4 Reflection Attack
11.7.5 Interleaving Attack
11.7.6 Attack Due to Type Flaw
11.7.7 Attack Due to Name Omission
11.7.8 Attack Due to Misuse of Cryptographic Services
11.8 A Brief Literature Note
11.9 Chapter Summary
Exercises
12 AUTHENTICATION PROTOCOLS--THE REAL WORLD
12.1 Introduction
12.1.1 Chapter Outline
12.2 Authentication Protocols for Internet Security
12.2.1 Communications at the Internet Protocol Layer
12.2.2 Internet Protocol Security IPSec
12.2.3 The Internet Key Exchange IKE Protocol
12.2.4 A Plausible Deniability Feature in IKE
12.2.5 Critiques on IPSec and IKE
12.3 The Secure Shell SSH Remote Login Protocol
12.3.1 The SSH Architecture
12.3.2 The SSH Transport Layer Protocol
12.3.3 The SSH Strategy
12.3.4 Warnings
12.4 The Kerberos Protocol and its Realization in Windows 2000
12.4.1 A Single-signon Architecture
12.4.2 The Kerberos Exchanges
12.4.3 Warnings
12.5 SSL and TLS
12.5.1 TLS Architecture Overview
12.5.2 TLS Handshake Protocol
12.5.3 A Typical Run of the TLS Handshake Protocol
12.5.4 A Side Channel Attack on a TLS Application
12.6 Chapter Summary
Exercises
13 AUTHENTICATION FRAMEWORK FOR PUBLIC-KEY
CRYPTOGRAPHY
13.1 Introduction
13.1.1 Chapter Outline
13.2 Directory-Based Authentication Framework
13.2.1 Certificate Issuance
13.2.2 Certificate Revocation
13.2.3 Examples of Public-key Authentication Framework
13.2.4 Protocols Associated with X.509 Public-key
Authentication Infrastructure
13.3 Non-Directory Based Public-key Authentication Framework
13.3.1 Shamir´s ID-Based Signature Scheme
13.3.2 What Exactly does ID-Based Cryptography Offer
13.3.3 Self-certified Public Keys
13.3.4 Identity-Based Public-key Cryptosystems from Pairings
on Weak Elliptic Curves
13.3.5 ID-based Non-interactive Key Sharing System of Sakai,
Ohgishi and Kasahara
13.3.6 Tripartite Diffie-Hellman Key Agreement of Joux
13.3.7 ID-Based Cryptosystem of Boneh and Franklin
13.3.8 Non-interaction Property: Authentication Without
Key Channel
13.3.9 Two Open Questions for Identity-based Public-key
Cryptography
13.4 Chapter Summary
Exercises
V FORMAL APPROACHES TO SECURITY
ESTABLISHMENT
14 FORMAL AND STRONG SECURITY DEFINITIONS
FOR PUBLIC-KEY CRYPTOSYSTEMS
14.1 Introduction
14.1.1 Chapter Outline
14.2 A Formal Treatment for Security
14.3 Semantic Security--the Debut of Provable Security
14.3.1 The SRA Mental Poker Protocol
14.3.2 A Security Analysis Based on Textbook Security
14.3.3 Probabilistic Encryption of Goldwasser and Micali
14.3.4 The Security of the GM Cryptosystem
14.3.5 A Semantically Secure Version of the ElGamal Cryptosystem
14.3.6 Semantically Secure Cryptosystems Based on Rabin Bits
14.4 Inadequacy of Semantic Security
14.5 Beyond Semantic Security
14.5.1 Security Against Chosen-ciphertext Attack
14.5.2 Security Against Adaptive Chosen-ciphertext Attack
14.5.3 Non-Malleable Cryptography
14.5.4 Relations between Non-Malleability and Indistinguishability
14.6 Chapter Summary
Exercises
15 PROVABLY SECURE AND EFFICIENT PUBLIC-KEY
CRYPTOSYSTEMS
15.1 Introduction
15.1.1 Chapter Outline
15.2 The Optimal Asymmetric Encryption Padding
15.2.1 Random Oracle Model for Security Proof
15.2.2 RSA-OAEP
15.2.3 A Twist in the Security Proof for RSA-OAEP
15.2.4 Rescue Work for RSA-OAEP
15.2.5 Tightness of Reduction to Contradiction for RSA-OAEP
15.2.6 A Critique on the Random Oracle Model
15.2.7 The Author´s View on the Value of the Random Oracle
Model
15.3 The Cramer-Shoup Public-key Cryptosystem
15.3.1 Provable Security Under Standard Intractability
Assumptions
15.3.2 The Cramer-Shoup Scheme
15.3.3 Proof of Security
15.4 An Overview of Provably Secure Hybrid Cryptosystems
15.5 Literature Notes on Practical and Provably Secure Public-key
Cryptosystems
15.6 Chapter Summary
Exercises
16 STRONG AND PROVABLE SECURITY FOR DIGITAL
SIGNATURES
16.1 Introduction
16.1.1 Chapter Outline
16.2 Strong Security Notion for Digital Signatures
16.3 Strong and Provable Security for ElGamal-family Signatures
16.3.1 Triplet ElGamal-family Signatures
16.3.2 Forking Reduction Technique
16.3.3 Heavy-Row Reduction Technique
16.4 Fit-for-application Ways for Signing in RSA and Rabin
16.4.1 Signatures with Randomized Padding
16.4.2 The Probabilistic Signature Scheme--PSS
16.4.3 PSS-R: Signing with Message Recovery
16.4.4 Universal PSS-R Padding for Signature and Encryption
16.5 Signcryption
16.5.1 Zheng´s Signcryption Scheme
16.5.2 Two Birds One Stone: Signcryption using RSA
16.6 Chapter Summary
Exercises
17 FORMAL METHODS FOR AUTHENTICATION
PROTOCOLS ANALYSIS
17.1 Introduction
17.1.1 Chapter Outline
17.2 Toward Formal Specification of Authentication Protocols
17.2.1 Imprecision of Encryption-decryption Approach for
Authentication
17.2.2 A Refined Specification for Authentication Protocols
17.2.3 Examples of Refined Specification for Authentication
Protocols
17.3 A Computational View of Correct Protocols--the Bellare-Rogaway
Model
17.3.1 Formal Modeling of the Behavior of Principals
17.3.2 The Goal of Mutual Authentication: Matching Conversations
17.3.3 Protocol M AP1 and its Proof of Security
17.3.4 Further Work in Computational Model for Protocols
Correctness
17.3.5 Discussion
17.4 A Symbolic Manipulation View of Correct Protocols
17.4.1 Theorem Proving
17.4.2 A Logic of Authentication
17.5 Formal Analysis Techniques: State System Exploration
17.5.1 Model Checking
17.5.2 The NRL Protocol Analyzer
17.5.3 The CSP Approach
17.6 Reconciling Two Views of Formal Techniques for Security
17.7 Chapter Summary
Exercises
VI CRYPTOGRAPHIC PROTOCOLS
18 ZERO-KNOWLEDGE PROTOCOLS
18.1 Introduction
18.1.1 Chapter Outline
18.2 Basic Definitions
18.2.1 Model of Computation
18.2.2 Formal Definition of Interactive Proof Protocols
18.2.3 A Complexity Theoretic Result
18.3 Zero-knowledge Properties
18.3.1 Perfect Zero-knowledge
18.3.2 Honest-Verifier Zero-knowledge
18.3.3 Computational Zero-knowledge
18.3.4 Statistical Zero-knowledge
18.4 Proof or Argument
18.4.1 Zero-knowledge Argument
18.4.2 Zero-knowledge Proof
18.5 Protocols with Two-sided-error
18.5.1 Zero-knowledge Proof of Two-prime Integers
18.6 Round Efficiency
18.6.1 Lower-bound Round Efficiency for Subgroup Membership
18.6.2 Constant-round Proof for Discrete Logarithm
18.7 Non-interactive Zero-knowledge
18.7.1 NIZK Achieved using Designation of Verifier
18.8 Chapter Summary
Exercises
19 RETURNING TO COIN FLIPPING OVER TELEPHONE
19.1 Blum´s Coin-Flipping-by-Telephone Protocol
19.2 Security Analysis
19.3 Efficiency
19.4 Chapter Summary
20 AFTERREMARK
BIBLIOGRAPHY
SUBJECT INDEX