You are previewing Modern Cryptography: Theory and Practice.
O'Reilly logo
Modern Cryptography: Theory and Practice

Book Description

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.

    Table of Contents

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