Serious Cryptography A Practical Introduction to Modern Encryption (Jean-Philippe Aumasson) (Z-Library)

SERIOUS CRYPTOGRAPHY A Practical Introduction to Modern Encryption Jean-Philippe Aumasson San Francisco

SERIOUS CRYPTOGRAPHY. Copyright © 2018 by Jean-Philippe Aumasson. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. ISBN-10: 1-59327-826-8 ISBN-13: 978-1-59327-826-7 Publisher: William Pollock Production Editor: Laurel Chun Cover Illustration: Jonny Thomas Interior Design: Octopod Studios Developmental Editors: William Pollock, Jan Cash, and Annie Choi Technical Reviewers: Erik Tews and Samuel Neves Copyeditor: Barton D. Reed Compositor: Meg Sneeringer Proofreader: James Fraleigh For information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly: No Starch Press, Inc. 245 8th Street, San Francisco, CA 94103 phone: 1.415.863.9900; sales@nostarch.com www.nostarch.com Library of Congress Control Number: 2017940486 No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

BRIEF CONTENTS Foreword by Matthew D. Green Preface Abbreviations Chapter 1: Encryption Chapter 2: Randomness Chapter 3: Cryptographic Security Chapter 4: Block Ciphers Chapter 5: Stream Ciphers Chapter 6: Hash Functions Chapter 7: Keyed Hashing Chapter 8: Authenticated Encryption Chapter 9: Hard Problems Chapter 10: RSA Chapter 11: Diffie–Hellman Chapter 12: Elliptic Curves Chapter 13: TLS Chapter 14: Quantum and Post-Quantum Index

CONTENTS IN DETAIL FOREWORD by Matthew D. Green PREFACE This Book’s Approach Who This Book Is For How This Book Is Organized Fundamentals Symmetric Crypto Asymmetric Crypto Applications Acknowledgments ABBREVIATIONS 1 ENCRYPTION The Basics Classical Ciphers The Caesar Cipher The Vigenère Cipher How Ciphers Work The Permutation The Mode of Operation Why Classical Ciphers Are Insecure Perfect Encryption: The One-Time Pad Encrypting with the One-Time Pad Why Is the One-Time Pad Secure? Encryption Security Attack Models Security Goals Security Notions

Asymmetric Encryption When Ciphers Do More Than Encryption Authenticated Encryption Format-Preserving Encryption Fully Homomorphic Encryption Searchable Encryption Tweakable Encryption How Things Can Go Wrong Weak Cipher Wrong Model Further Reading 2 RANDOMNESS Random or Non-Random? Randomness as a Probability Distribution Entropy: A Measure of Uncertainty Random Number Generators (RNGs) and Pseudorandom Number Generators (PRNGs) How PRNGs Work Security Concerns The PRNG Fortuna Cryptographic vs. Non-Cryptographic PRNGs The Uselessness of Statistical Tests Real-World PRNGs Generating Random Bits in Unix-Based Systems The CryptGenRandom() Function in Windows A Hardware-Based PRNG: RDRAND in Intel Microprocessors How Things Can Go Wrong Poor Entropy Sources Insufficient Entropy at Boot Time Non-cryptographic PRNG Sampling Bug with Strong Randomness

Further Reading 3 CRYPTOGRAPHIC SECURITY Defining the Impossible Security in Theory: Informational Security Security in Practice: Computational Security Quantifying Security Measuring Security in Bits Full Attack Cost Choosing and Evaluating Security Levels Achieving Security Provable Security Heuristic Security Generating Keys Generating Symmetric Keys Generating Asymmetric Keys Protecting Keys How Things Can Go Wrong Incorrect Security Proof Short Keys for Legacy Support Further Reading 4 BLOCK CIPHERS What Is a Block Cipher? Security Goals Block Size The Codebook Attack How to Construct Block Ciphers A Block Cipher’s Rounds The Slide Attack and Round Keys Substitution–Permutation Networks

Feistel Schemes The Advanced Encryption Standard (AES) AES Internals AES in Action Implementing AES Table-Based Implementations Native Instructions Is AES Secure? Modes of Operation The Electronic Codebook (ECB) Mode The Cipher Block Chaining (CBC) Mode How to Encrypt Any Message in CBC Mode The Counter (CTR) Mode How Things Can Go Wrong Meet-in-the-Middle Attacks Padding Oracle Attacks Further Reading 5 STREAM CIPHERS How Stream Ciphers Work Stateful and Counter-Based Stream Ciphers Hardware-Oriented Stream Ciphers Feedback Shift Registers Grain-128a A5/1 Software-Oriented Stream Ciphers RC4 Salsa20 How Things Can Go Wrong Nonce Reuse Broken RC4 Implementation Weak Ciphers Baked Into Hardware

Further Reading 6 HASH FUNCTIONS Secure Hash Functions Unpredictability Again Preimage Resistance Collision Resistance Finding Collisions Building Hash Functions Compression-Based Hash Functions: The Merkle–Damgård Construction Permutation-Based Hash Functions: Sponge Functions The SHA Family of Hash Functions SHA-1 SHA-2 The SHA-3 Competition Keccak (SHA-3) The BLAKE2 Hash Function How Things Can Go Wrong The Length-Extension Attack Fooling Proof-of-Storage Protocols Further Reading 7 KEYED HASHING Message Authentication Codes (MACs) MACs in Secure Communication Forgery and Chosen-Message Attacks Replay Attacks Pseudorandom Functions (PRFs) PRF Security Why PRFs Are Stronger Than MACs

Creating Keyed Hashes from Unkeyed Hashes The Secret-Prefix Construction The Secret-Suffix Construction The HMAC Construction A Generic Attack Against Hash-Based MACs Creating Keyed Hashes from Block Ciphers: CMAC Breaking CBC-MAC Fixing CBC-MAC Dedicated MAC Designs Poly1305 SipHash How Things Can Go Wrong Timing Attacks on MAC Verification When Sponges Leak Further Reading 8 AUTHENTICATED ENCRYPTION Authenticated Encryption Using MACs Encrypt-and-MAC MAC-then-Encrypt Encrypt-then-MAC Authenticated Ciphers Authenticated Encryption with Associated Data Avoiding Predictability with Nonces What Makes a Good Authenticated Cipher? AES-GCM: The Authenticated Cipher Standard GCM Internals: CTR and GHASH GCM Security GCM Efficiency OCB: An Authenticated Cipher Faster than GCM OCB Internals OCB Security

OCB Efficiency SIV: The Safest Authenticated Cipher? Permutation-Based AEAD How Things Can Go Wrong AES-GCM and Weak Hash Keys AES-GCM and Small Tags Further Reading 9 HARD PROBLEMS Computational Hardness Measuring Running Time Polynomial vs. Superpolynomial Time Complexity Classes Nondeterministic Polynomial Time NP-Complete Problems The P vs. NP Problem The Factoring Problem Factoring Large Numbers in Practice Is Factoring NP-Complete? The Discrete Logarithm Problem What Is a Group? The Hard Thing How Things Can Go Wrong When Factoring Is Easy Small Hard Problems Aren’t Hard Further Reading 10 RSA The Math Behind RSA The RSA Trapdoor Permutation RSA Key Generation and Security

Encrypting with RSA Breaking Textbook RSA Encryption’s Malleability Strong RSA Encryption: OAEP Signing with RSA Breaking Textbook RSA Signatures The PSS Signature Standard Full Domain Hash Signatures RSA Implementations Fast Exponentiation Algorithm: Square-and-Multiply Small Exponents for Faster Public-Key Operations The Chinese Remainder Theorem How Things Can Go Wrong The Bellcore Attack on RSA-CRT Sharing Private Exponents or Moduli Further Reading 11 DIFFIE–HELLMAN The Diffie–Hellman Function The Diffie–Hellman Problems The Computational Diffie–Hellman Problem The Decisional Diffie–Hellman Problem More Diffie–Hellman Problems Key Agreement Protocols An Example of Non-DH Key Agreement Attack Models for Key Agreement Protocols Performance Diffie–Hellman Protocols Anonymous Diffie–Hellman Authenticated Diffie–Hellman Menezes–Qu–Vanstone (MQV) How Things Can Go Wrong Not Hashing the Shared Secret

Legacy Diffie–Hellman in TLS Unsafe Group Parameters Further Reading 12 ELLIPTIC CURVES What Is an Elliptic Curve? Elliptic Curves over Integers Adding and Multiplying Points Elliptic Curve Groups The ECDLP Problem Diffie–Hellman Key Agreement over Elliptic Curves Signing with Elliptic Curves Encrypting with Elliptic Curves Choosing a Curve NIST Curves Curve25519 Other Curves How Things Can Go Wrong ECDSA with Bad Randomness Breaking ECDH Using Another Curve Further Reading 13 TLS Target Applications and Requirements The TLS Protocol Suite The TLS and SSL Family of Protocols: A Brief History TLS in a Nutshell Certificates and Certificate Authorities The Record Protocol The TLS Handshake Protocol TLS 1.3 Cryptographic Algorithms

TLS 1.3 Improvements over TLS 1.2 Downgrade Protection Single Round-Trip Handshake Session Resumption The Strengths of TLS Security Authentication Forward Secrecy How Things Can Go Wrong Compromised Certificate Authority Compromised Server Compromised Client Bugs in Implementations Further Reading 14 QUANTUM AND POST-QUANTUM How Quantum Computers Work Quantum Bits Quantum Gates Quantum Speed-Up Exponential Speed-Up and Simon’s Problem The Threat of Shor’s Algorithm Shor’s Algorithm Solves the Factoring Problem Shor’s Algorithm and the Discrete Logarithm Problem Grover’s Algorithm Why Is It So Hard to Build a Quantum Computer? Post-Quantum Cryptographic Algorithms Code-Based Cryptography Lattice-Based Cryptography Multivariate Cryptography Hash-Based Cryptography How Things Can Go Wrong Unclear Security Level

Fast Forward: What Happens if It’s Too Late? Implementation Issues Further Reading INDEX

FOREWORD If you’ve read a book or two on computer security, you may have encountered a common perspective on the field of cryptography. “Cryptography,” they say, “is the strongest link in the chain.” Strong praise indeed, but it’s also somewhat dismissive. If cryptography is in fact the strongest part of your system, why invest time improving it when there are so many other areas of the system that will benefit more from your attention? If there’s one thing that I hope you take away from this book, it’s that this view of cryptography is idealized; it’s largely a myth. Cryptography in theory is strong, but cryptography in practice is as prone to failure as any other aspect of a security system. This is particularly true when cryptographic implementations are developed by non-experts without sufficient care or experience, as is the case with many cryptographic systems deployed today. And it gets worse: when cryptographic implementations fail, they often do so in uniquely spectacular ways. But why should you care, and why this book? When I began working in the field of applied cryptography nearly two decades ago, the information available to software developers was often piecemeal and outdated. Cryptographers developed algorithms and protocols, and cryptographic engineers implemented them to create opaque, poorly documented cryptographic libraries designed mainly for other experts. There was—and there has been—a huge divide between those who know and understand cryptographic algorithms and those who use them (or ignore them at their peril). There are a few decent textbooks on the market, but even fewer have provided useful tools for the practitioner. The results have not been pretty. I’m talking about compromises with labels like “CVE” and “Severity: High,” and in a few alarming cases, attacks on slide decks marked “TOP SECRET.” You may be familiar with some of the more famous examples if only because they’ve affected systems that you rely on. Many of these problems occur because

cryptography is subtle and mathematically elegant, and because cryptographic experts have failed to share their knowledge with the engineers who actually write the software. Thankfully, this has begun to change and this book is a symptom of that change. Serious Cryptography was written by one of the foremost experts in applied cryptography, but it’s not targeted at other experts. Nor, for that matter, is it intended as a superficial overview of the field. On the contrary, it contains a thorough and up-to-date discussion of cryptographic engineering, designed to help practitioners who plan to work in this field do better. In these pages, you’ll learn not only how cryptographic algorithms work, but how to use them in real systems. The book begins with an exploration of many of the key cryptographic primitives, including basic algorithms like block ciphers, public encryption schemes, hash functions, and random number generators. Each chapter provides working examples of how the algorithms work and what you should or should not do. Final chapters cover advanced subjects such as TLS, as well as the future of cryptography—what to do after quantum computers arrive to complicate our lives. While no single book can solve all our problems, a bit of knowledge can go a long way. This book contains plenty of knowledge. Perhaps enough to make real, deployed cryptography live up to the high expectations that so many have of it. Happy reading. Matthew D. Green Professor Information Security Institute Johns Hopkins University

PREFACE I wrote this book to be the one I wish I had when I started learning crypto. In 2005, I was studying for my masters degree near Paris, and I eagerly registered for the crypto class in the upcoming semester. Unfortunately, the class was canceled because too few students had registered. “Crypto is too hard,” the students argued, and instead, they enrolled en masse in the computer graphics and database classes. I’ve heard “crypto is hard” more than a dozen times since then. But is crypto really that hard? To play an instrument, master a programming language, or put the applications of any fascinating field into practice, you need to learn some concepts and symbols, but doing so doesn’t take a PhD. I think the same applies to becoming a competent cryptographer. I also believe that crypto is perceived as hard because cryptographers haven’t done a good job of teaching it. Another reason why I felt the need for this book is that crypto is no longer just about crypto—it has expanded into a multidisciplinary field. To do anything useful and relevant in crypto, you’ll need some understanding of the concepts around crypto: how networks and computers work, what users and systems need, and how attackers can abuse algorithms and their implementations. In other words, you need a connection to reality. This Book’s Approach The initial title of this book was Crypto for Real to stress the practice- oriented, real-world, no-nonsense approach I aimed to follow. I didn’t want to make cryptography approachable by dumbing it down, but

instead tie it to real applications. I provide source code examples and describe real bugs and horror stories. Along with a clear connection to reality, other cornerstones of this book are its simplicity and modernity. I focus on simplicity in form more than in substance: I present many non-trivial concepts, but without the dull mathematical formalism. Instead, I attempt to impart an understanding of cryptography’s core ideas, which are more important than remembering a bunch of equations. To ensure the book’s modernity, I cover the latest developments and applications of cryptography, such as TLS 1.3 and post-quantum cryptography. I don’t discuss the details of obsolete or insecure algorithms such as DES or MD5. An exception to this is RC4, but it’s only included to explain how weak it is and to show how a stream cipher of its kind works. Serious Cryptography isn’t a guide for crypto software, nor is it a compendium of technical specifications—stuff that you’ll easily find online. Instead, the foremost goal of this book is to get you excited about crypto and to teach you its fundamental concepts along the way. Who This Book Is For While writing, I often imagined the reader as a developer who’d been exposed to crypto but still felt clueless and frustrated after attempting to read abstruse textbooks and research papers. Developers often need—and want—a better grasp of crypto to avoid unfortunate design choices, and I hope this book will help. But if you aren’t a developer, don’t worry! The book doesn’t require any coding skills, and is accessible to anyone who understands the basics of computer science and college-level math (notions of probabilities, modular arithmetic, and so on). This book can nonetheless be intimidating, and despite its relative accessibility, it requires some effort to get the most out of it. I like the mountaineering analogy: the author paves the way, providing you with ropes and ice axes to facilitate your work, but you make the ascent yourself. Learning the concepts in this book will take an effort, but there

will be a reward at the end. How This Book Is Organized The book has fourteen chapters, loosely split into four parts. The chapters are mostly independent from one another, except for Chapter 9, which lays the foundations for the three subsequent chapters. I also recommend reading the first three chapters before anything else. Fundamentals Chapter 1: Encryption introduces the notion of secure encryption, from weak pen-and-paper ciphers to strong, randomized encryption. Chapter 2: Randomness describes how a pseudorandom generator works, what it takes for one to be secure, and how to use one securely. Chapter 3: Cryptographic Security discusses theoretical and practical notions of security, and compares provable security with probable security. Symmetric Crypto Chapter 4: Block Ciphers deals with ciphers that process messages block per block, focusing on the most famous one, the Advanced Encryption Standard (AES). Chapter 5: Stream Ciphers presents ciphers that produce a stream of random-looking bits that are XORed with messages to be encrypted. Chapter 6: Hash Functions is about the only algorithms that don’t work with a secret key, which turn out to be the most ubiquitous crypto building blocks. Chapter 7: Keyed Hashing explains what happens if you combine a hash function with a secret key, and how this serves to authenticate messages. Chapter 8: Authenticated Encryption shows how some algorithms