Preface

These are lecture notes for cs427 at Oregon State University, an introductory course in cryptography at the advanced undergraduate level. By reading and studying these notes, you should expect to learn how to:

• State and interpret the standard formal definitions for the most common cryptographic security properties (privacy and authentication).
• Formally prove security properties of sound cryptographic constructions, and break the security of unsound ones.
• Choose the appropriate cryptographic primitive for a task (block ciphers, hash functions, MACs, public-key encryption, etc.) while avoiding common pitfalls.

Along the way, you will also learn how the most common cryptographic constructions work.

Background

You will get the most out of these notes if you have a solid foundation in standard undergraduate computer science material:

• Discrete mathematics [required]: for modular arithmetic, discrete probabilities, simple combinatorics, and especially proof techniques.
• Algorithms & data structures [highly recommended]: for reasoning about computations at an abstract level.
• Theory of computation (automata, formal languages & computability) [recommended]: for even more experience formally reasoning about abstract processes of computation.

Disclaimer

You are reading an early draft of this book. Of course I make every effort to ensure the accuracy of the content, but the content has not yet benefitted from many critical readers. So, caveat emptor!

More than that, much interesting and hugely important material is not covered. Some more minor missing material is indicated as such and labeled “to-do”, but conspicuously missing major sections are simply absent. Anyone with a pre-existing opinion about cryptography will likely be appalled at what is missing. In my defense, my university schedule is on the quarter system which necessitates that I generate 10 weeks of course material. Everything beyond that is produced via the much slower labor-of-love mechanism.

I welcome feedback from readers, educators, cryptographers — not only on errors and typos but also on the selection, organization, and presentation of the material.

Code-based games

The security definitions and proofs in these notes are presented in a style that is known to the outside world as code-based games. I’ve chosen this style because I think it offers significant pedagogical benefits:

• Every security definition can be expressed in the same style, as the indistinguishability of two games. In my terminology, the games are libraries with a common interface/API but different internal implementations. An adversary is any calling program on that interface. These libraries use a concrete pseudocode that reduces ambiguity about an adversary’s capabilities. For instance, the adversary controls arguments to subroutines that it calls and sees only the return value. The adversary cannot see any variables that are privately scoped to the library.
• A consistent framework for definitions leads to a consistent process for proving and breaking security — the two fundamental activities in cryptography

In these notes, breaking a construction always corresponds to writing a program that expects a particular interface and behaves as differently as possible in the presence of two particular implementations of the interface.

Proving security nearly always refers to showing a sequence of libraries (called hybrids), each of which is indistinguishable from the previous one. Each of these hybrids is written in concrete pseudocode. By identifying what security property we wish to prove, we identify what the endpoints of this sequence must be. The steps that connect adjacent hybrids are stated in terms of syntactic rewriting rules for pseudocode, including down-to-earth steps like factoring out and inlining subroutines, changing the value of unused variables, and so on.

• Cryptography is full of conditional statements of security: “if A is a secure thingamajig, then B is a secure doohickey.” A conventional proof of such a statement would address the contrapositive: “given an adversary that attacks the doohickey-security of B, I can construct an attack on the thingamajig-security of A.”

In my experience, students struggle to find the right way to transform an abstract, hypothetical B-attacking adversary into a successful A-attacking adversary. By defining security in terms of games/libraries, we can avoid this abstract challenge, and indeed avoid the context switch into the contrapositive altogether. In these notes, the thingamajig-security of A gives the student a new rewriting rule that can be placed in his/her toolbox and used to bridge hybrids when proving the doohickey security of B.

Code-based games were first proposed by Shoup¹ and later expanded by Bellare & Rogaway.² These notes adopt a simplified and unied style of games, since the goal is not to encompass every possible security definition but only the fundamental ones. The most significant difference in style is that the games in these notes have no explicit Initialize or Finalize step. As a result, all security definitions are expressed as indistinguishability of two games/libraries, even security definitions that are fundamentally about unforgeability. Yet, we can still reason about unforgeability properties within this framework. For instance, to say that no adversary can forge a MAC, it suffices to say that no adversary can distinguish a MAC-verification subroutine from a subroutine that always returns false. An index of security definitions has been provided at the end of the book.

¹Victor Shoup: Sequences of Games: A Tool for Taming Complexity in Security Proofs. ia.cr/2004/332

²Mihir Bellare & Philip Rogaway: Code-Based Game-Playing Proofs and the Security of Triple Encryption.
ia.cr/2004/331

One instance where the approach falls short, however, is in defining collision resistance. I have not been able to define it in this framework in a way that is both easy to use and easy to interpret (and perhaps I achieved neither in the end). See Chapter 12 for my best attempt.

Supplementary Material

Security proofs in this book follow a standard pattern: We start from one “library” and perform a sequence of small, cumulative modifications. Each modification results in a separate hybrid library that is indistinguishable from the previous one.

I have prepared PDF slide decks to supplement the security proofs contained in the book. They are available from the course website. The slides allow the reader to step forward and backward through the proof’s sequence of logical steps, seeing only the current hybrid library at any time (with changes highlighted and annotated).

Acknowledgements

Some financial support for writing this book has been kindly provided by the National Science Foundation (award #1149647) and the Oregon State University Open Textbook Initiative.

About the cover

The cover design consists of assorted shell illustrations from Bibliothèque conchyliologique, published in 1846. The images are no longer under copyright, and were obtained from the Biodiversity Heritage Library (http://biodiversitylibrary.org/bibliography/11590). Like a properly deployed cryptographic primitive, a properly deployed shell is the most robust line of defense for a mollusk. To an uniformed observer, a shell is just a shell, and crypto is just crypto. However, there are a wide variety of cryptographic primitives, each of which provides protection against a different kind of attack. Just as for a seasoned conchologist, the joy is in appreciating the unique beauty of each form and understanding the subtle differences among them.

Copyright

This work is copyright by Mike Rosulek and made available under the Creative Commons BY-NC-SA 4.0 license. Under this license, you are free to:

The licensor cannot revoke these freedoms as long as you follow the following license terms:

Table of Contents:

• Chapter 0: Review of Concepts & Notation
• Chapter 1: One-Time Pad
• Chapter 2: The Basics of Provable Security
• Chapter 3: Secret Sharing
• Chapter 4: Basing Cryptography on Limits of Computation
• Chapter 5: Pseudorandom Generators
• Chapter 6: Pseudorandom Functions
• Chapter 7: Pseudorandom Permutations
• Chapter 8: Security Against Chosen Plaintext Attacks
• Chapter 9: Block Cipher Modes of Operation
• Chapter 10: Chosen Ciphertext Attacks
• Chapter 11: Message Authentication Codes
• Chapter 12: Hash Functions
• Chapter 13: The RSA Function
• Chapter 14: Diffie-Hellmann Key Agreement
• Chapter 15: Public-Key Encryption
• Index of Security Definitions