Practical Cryptography

Table of Contents

Preface

How to Read this Book

1 Our Design Philosophy

1.1 The Evils of Performance

1.2 The Evils of Features

2 The Context of Cryptography

2.1 The Role of Cryptography

2.2 The Weakest Link Property

2.3 The Adversarial Setting

2.4 Practical Paranoia

2.4.1 Attack

2.5 Threat Model

2.6 Cryptography Is Not the Solution

2.7 Cryptography Is Very Difficult

2.8 Cryptography Is the Easy Part

2.9 Background Reading

3 Introduction to Cryptography

3.1 Encryption

3.1.1 Kerckhoffs' Principle

3.2 Authentication

3.3 Public-Key Encryption

3.4 Digital Signatures

3.5 PKI

3.6 Attacks

3.6.1 Ciphertext-Only

3.6.2 Known Plaintext

3.6.3 Chosen Plaintext

3.6.4 Chosen Ciphertext

3.6.5 Distinguishing Attacks

3.6.6 Birthday

3.6.7 Meet in the Middle

3.6.8 Other Types of Attack

3.7 Security Level

3.8 Performance

3.9 Complexity

I Message Security

4 Block Ciphers

4.1 What Is a Block Cipher?

4.2 Types of Attack

4.3 The Ideal Block Cipher

4.4 Definition of Block Cipher Security

4.4.1 Parity of a Permutation

4.5 Real Block Ciphers

4.5.1 DES

4.5.2 AES

4.5.3 Serpent

4.5.4 Twofish

4.5.5 Other AES Finalists

4.5.6 Equation-Solving Attacks

4.5.7 Which Block Cipher Should I Choose?

4.5.8 What Key Size Should I Use?

5 Block Cipher Modes

5.1 Padding

5.2 ECB

5.3 CBC

5.3.1 Fixed IV

5.3.2 Counter IV

5.3.3 Random IV

5.3.4 Nonce-Generated IV

5.4 OFB

5.5 CTR

5.6 Newer Modes

5.7 Which Mode Should I Use?

5.8 Information Leakage

5.8.1 Chances of a Collision

5.8.2 How to Deal With Leakage

5.8.3 About Our Math

6 Hash Functions

6.1 Security of Hash Functions

6.2 Real Hash Functions

6.2.1 MD5

6.2.2 SHA-1

6.2.3 SHA-256, SHA-384, and SHA-512

6.3 Weaknesses of Hash Functions

6.3.1 Length Extensions

6.3.2 Partial-Message Collision

6.4 Fixing the Weaknesses

6.4.1 A Thorough Fix

6.4.2 A More Efficient Fix

6.5 Which Hash Function Should I Choose?

6.6 Future Work

7 Message Authentication Codes

7.1 What a MAC Does

7.2 The Ideal MAC

7.3 MAC Security

7.4 CBC-MAC

7.5 HMAC

7.5.1 HMAC versus SHAd

7.6 UMAC

7.6.1 Size of MAC

7.6.2 Which UMAC?

7.6.3 Platform Flexibility

7.6.4 Amount of Analysis

7.6.5 Why Mention UMAC at All?

7.7 Which MAC to Choose?

7.8 Using a MAC

8 The Secure Channel

8.1 Problem Statement

8.1.1 Roles

8.1.2 Key

8.1.3 Messages or Stream

8.1.4 Security Properties

8.2 Order of Authentication and Encryption

8.3 Outline

8.3.1 Message Numbers

8.3.2 Authentication

8.3.3 Encryption

8.3.4 Frame Format

8.4 Details

8.4.1 Initialization

8.4.2 Sending a Message

8.4.3 Receiving a Message

8.4.4 Message Order

8.5 Alternatives

8.6 Conclusion

9 Implementation Issues (I)

9.1 Creating Correct Programs

9.1.1 Specifications

9.1.2 Test and Fix

9.1.3 Lax Attitude

9.1.4 So How Do We Proceed?

9.2 Creating Secure Software

9.3 Keeping Secrets

9.3.1 Wiping State

9.3.2 Swap File

9.3.3 Caches

9.3.4 Data Retention by Memory

9.3.5 Access by Others

9.3.6 Data Integrity

9.3.7 What to Do

9.4 Quality of Code

9.4.1 Simplicity

9.4.2 Modularization

9.4.3 Assertions

9.4.4 Buffer Overflows

9.4.5 Testing

9.5 Side-Channel Attacks

9.6 Conclusion

II Key Negotiation

10 Generating Randomness

10.1 Real Random

10.1.1 Problems With Using Real Random Data

10.1.2 Pseudorandom Data

10.1.3 Real Random Data and PRNGs

10.2 Attack Models for a PRNG

10.3 Fortuna

10.4 The Generator

10.4.1 Initialization

10.4.2 Reseed

10.4.3 Generate Blocks

10.4.4 Generate Random Data

10.4.5 Generator Speed

10.5 Accumulator

10.5.1 Entropy Sources

10.5.2 Pools

10.5.3 Implementation Considerations

Distribution of Events Over Pools

Running Time of Event Passing

10.5.4 Initialization

10.5.5 Getting Random Data

10.5.6 Add an Event

10.6 Seed File Management

10.6.1 Write Seed File

10.6.2 Update Seed File

10.6.3 When to Read and Write the Seed File

10.6.4 Backups

10.6.5 Atomicity of File System Updates

10.6.6 First Boot

10.7 So What Should I Do?

10.8 Choosing Random Elements

11 Primes

11.1 Divisibility and Primes

11.2 Generating Small Primes

11.3 Computations Modulo a Prime

11.3.1 Addition and Subtraction

11.3.2 Multiplication

11.3.3 Groups and Finite Fields

11.3.4 The GCD Algorithm

11.3.5 The Extended Euclidean Algorithm

11.3.6 Working Modulo 2

11.4 Large Primes

11.4.1 Primality Testing

11.4.2 Evaluating Powers

12 Diffie-Hellman

12.1 Groups

12.2 Basic DH

12.3 Man in the Middle

12.4 Pitfalls

12.5 Safe Primes

12.6 Using a Smaller Subgroup

12.7 The Size of p

12.8 Practical Rules

12.9 What Could Go Wrong

13 RSA

13.1 Introduction

13.2 The Chinese Remainder Theorem

13.2.1 Garner's Formula

13.2.2 Generalizations

13.2.3 Uses

13.2.4 Conclusion

13.3 Multiplication Modulo n

13.4 RSA Defined

13.4.1 Digital Signatures with RSA

13.4.2 Public Exponents

13.4.3 The Private Key

13.4.4 The Size of n

13.4.5 Generating RSA Keys

13.5 Pitfalls Using RSA

13.6 Encryption

13.7 Signatures

14 Introduction to Cryptographic Protocols

14.1 Roles

14.2 Trust

14.2.1 Risk

14.3 Incentive

14.4 Trust in Cryptographic Protocols

14.5 Messages and Steps

14.5.1 The Transport Layer

14.5.2 Protocol and Message Identity

14.5.3 Message Encoding and Parsing

14.5.4 Protocol Execution States

14.5.5 Errors

14.5.6 Replay and Retries

15 Key Negotiation Protocol

15.1 The Setting

15.2 A First Try

15.3 Protocols Live Forever

15.4 An Authentication Convention

15.5 A Second Attempt

15.6 A Third Attempt

15.7 Our Final Protocol

15.8 Different Views of the Protocol

15.8.1 Alice's View

15.8.2 Bob's View

15.8.3 Attacker's View

15.8.4 Key Compromise

15.9 Computational Complexity of the Protocol

15.9.1 Optimization Tricks

15.10 Protocol Complexity

15.11 A Gentle Warning

15.12 Key Negotiation from a Password

16 Implementation Issues (II)

16.1 Large Integer Arithmetic

16.1.1 Wooping

16.1.2 Checking DH Computations

16.1.3 Checking RSA Encryption

16.1.4 Checking RSA Signatures

16.1.5 Conclusion

16.2 Faster Multiplication

16.3 Side-Channel Attacks

16.3.1 Countermeasures

16.4 Protocols

16.4.1 Protocols Over a Secure Channel

16.4.2 Receiving a Message

16.4.3 Timeouts

III Key Management

17 The Clock

17.1 Uses for a Clock

17.1.1 Expiration

17.1.2 Unique Value

17.1.3 Monotonicity

17.1.4 Real-Time Transactions

17.2 Using the Real-Time Clock Chip

17.3 Security Dangers

17.3.1 Setting the Clock Back

17.3.2 Stopping the Clock

17.3.3 Setting the Clock Forward

17.4 Creating a Reliable Clock

17.5 The Same-State Problem

17.6 Time

17.7 Conclusion

18 Key Servers

18.1 Basics

18.2 Kerberos

18.3 Simpler Solutions

18.3.1 Secure Connection

18.3.2 Setting Up a Key

18.3.3 Rekeying

18.3.4 Other Properties

18.4 What to Choose

19 The Dream of PKI

19.1 A Very Short PKI Overview

19.2 PKI Examples

19.2.1 The Universal PKI

19.2.2 VPN Access

19.2.3 Electronic Banking

19.2.4 Refinery Sensors

19.2.5 Credit Card Organization

19.3 Additional Details

19.3.1 Multilevel Certificates

19.3.2 Expiration

19.3.3 Separate Registration Authority

19.4 Conclusion

20 PKI Reality

20.1 Names

20.2 Authority

20.3 Trust

20.4 Indirect Authorization

20.5 Direct Authorization

20.6 Credential Systems

20.7 The Modified Dream

20.8 Revocation

20.8.1 Revocation List

20.8.2 Fast Expiration

20.8.3 Revocation Is Required

20.9 So What Is a PKI Good For?

20.10 What to Choose

21 PKI Practicalities

21.1 Certificate Format

21.1.1 Permission Language

21.1.2 The Root Key

21.2 The Life of a Key

21.3 Why Keys Wear Out

21.4 So What Should You Do?

22 Storing Secrets

22.1 Disk

22.2 Human Memory

22.2.1 Salting and Stretching

22.3 Portable Storage

22.4 Secure Token

22.5 Secure UI

22.6 Biometrics

22.7 Single Sign-On

22.8 Risk of Loss

22.9 Secret Sharing

22.10 Wiping Secrets

22.10.1 Paper

22.10.2 Magnetic Storage

22.10.3 Solid-State Storage

IV Miscellaneous

23 Standards

23.1 The Standards Process

23.1.1 The Standard

23.1.2 Functionality

23.1.3 Security

23.2 SSL

23.3 AES: Standardization by Competition

24 Patents

24.1 Prior Art

24.2 Continuations

24.3 Vagueness

24.4 Reading Patents

24.5 Licensing

24.6 Defensive Patents

24.7 Fixing the Patent System

24.8 Disclaimer

25 Involving Experts

Acknowledgments

Bibliography

Index

up to Practical Cryptography

Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.