How Software Works The Magic Behind Encryption, CGI, Search Engines, and Other Everyday Technologies (V. Anton Spraul) (Z-Library)

WOW! eBook www.wowebook.org

HOW SOFTWARE WORKS The Magic Behind Encryption, CGI, Search Engines, and Other Everyday Technologies by V. Anton Spraul San Francisco WOW! eBook www.wowebook.org

HOW SOFTWARE WORKS. Copyright © 2015 by V. Anton Spraul. 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. Printed in USA First printing 19 18 17 16 15 1 2 3 4 5 6 7 8 9 ISBN-10: 1-59327-666-4 ISBN-13: 978-1-59327-666-9 Publisher: William Pollock Production Editor: Alison Law Cover Illustration: Josh Ellingson Interior Design: Octopod Studios Developmental Editors: Hayley Baker, Seph Kramer, and Greg Poulos Technical Reviewer: Randall Hyde Copyeditor: Rachel Monaghan Compositor: Susan Glinert Stevens 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: 415.863.9900; info@nostarch.com www.nostarch.com Library of Congress Cataloging-in-Publication Data: Spraul, V. Anton. How software works : the magic behind encryption, CGI, search engines, and other everyday technologies / by V. Anton Spraul. pages cm Includes index. Summary: “A guide for non-technical readers that explores topics like data encryption; computer graphics creation; password protection; video compression; how data is found in huge databases; how programs can work together on the same problem without conflict; and how map software finds routes.”— Provided by publisher. ISBN 978-1-59327-666-9 — ISBN 1-59327-666-4 1. Electronic data processing—Popular works. 2. Computer software—Popular works. 3. Computer networks— Popular works. I. Title. QA76.5.S6663 2015 005.3—dc23 2015022623 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. WOW! eBook www.wowebook.org

About the Author V. Anton Spraul has taught introductory programming and computer science to students from all over the world for more than 15 years. He is also the author of Think Like a Programmer (No Starch Press) and Computer Science Made Simple (Broadway). WOW! eBook www.wowebook.org

About the Technical Reviewer Randall Hyde is the author of The Art of Assembly Language and Write Great Code (both No Starch Press), and is also the co-author of The Waite Group’s Microsoft Macro Assembler 6.0 Bible (Sams Publishing). Hyde taught assembly language at the University of California, Riverside, for more than a decade and has been programming software for nuclear reactor consoles for the past 12 years. WOW! eBook www.wowebook.org

Brief Contents Acknowledgments Introduction Chapter 1: Encryption Chapter 2: Passwords Chapter 3: Web Security Chapter 4: Movie CGI Chapter 5: Game Graphics Chapter 6: Data Compression Chapter 7: Search Chapter 8: Concurrency Chapter 9: Map Routes Index WOW! eBook www.wowebook.org

Contents in Detail Acknowledgments Introduction Who This Book Is For Topics Covered Behind the Magic 1 Encryption The Goal of Encryption Transposition: Same Data, Different Order Cipher Keys Attacking the Encryption Substitution: Replacing Data Varying the Substitution Pattern Key Expansion The Advanced Encryption Standard Binary Basics AES Encryption: The Big Picture Key Expansion in AES AES Encryption Rounds Block Chaining Why AES Is Secure Possible AES Attacks The Limits of Private-Key Encryption 2 Passwords Transforming a Password into a Number Properties of Good Hash Functions The MD5 Hash Function Encoding the Password Bitwise Operations MD5 Hashing Rounds Meeting the Criteria of a Good Hash Function WOW! eBook www.wowebook.org

Digital Signatures The Problem of Identity Collision Attacks Passwords in Authentication Systems The Dangers of Password Tables Hashing Passwords Dictionary Attacks Hash Tables Hash Chaining Iterative Hashing Salting Passwords Are Password Tables Safe? Password Storage Services A Final Thought 3 Web Security How Public-Key Cryptography Solves the Shared Key Problem Math Tools for Public-Key Cryptography Invertible Functions One-Way Functions Trapdoor Functions The RSA Encryption Method Creating the Keys Encrypting Data with RSA RSA Effectiveness RSA Use in the Real World RSA for Authentication Security on the Web: HTTPS Handshaking Transmitting Data Under HTTPS The Shared Key Problem Solved? 4 Movie CGI Software for Traditional Animation WOW! eBook www.wowebook.org

How Digital Images Work How Colors Are Defined How Software Makes Cel Animations From Cel Animation Software to Rendered 2D Graphics Software for 3D CGI How 3D Scenes Are Described The Virtual Camera Direct Lighting Global Illumination How Light Is Traced Full-Scene Anti-Aliasing Combining the Real and the Fake The Ideal of Movie-Quality Rendering 5 Game Graphics Hardware for Real-Time Graphics Why Games Don’t Ray Trace All Lines and No Curves Projection Without Ray Tracing Rendering Triangles The Painter’s Algorithm Depth Buffering Real-Time Lighting Shadows Ambient Light and Ambient Occlusion Texture Mapping Nearest-Neighbor Sampling Bilinear Filtering Mipmaps Trilinear Filtering Reflections Faking Curves Distant Impostors WOW! eBook www.wowebook.org

Bump Mapping Tessellation Anti-Aliasing in Real Time Supersampling Multisampling Post-Process Anti-Aliasing The Rendering Budget What’s Next for Game Graphics 6 Data Compression Run-Length Encoding Dictionary Compression The Basic Method Huffman Encoding Reorganizing Data for Better Compression Predictive Encoding Quantization JPEG Images A Different Way to Store Colors The Discrete Cosine Transform The DCT for Two Dimensions Compressing the Results JPEG Picture Quality Compressing High-Definition Video Temporal Redundancy MPEG-2 Video Compression Video Quality with Temporal Compression The Present and Future of Video Compression 7 Search Defining the Search Problem Putting Data in Order Selection Sort Quicksort WOW! eBook www.wowebook.org

Binary Search Indexing Hashing Web Search Ranking Results Using the Index Effectively What’s Next for Web Search 8 Concurrency Why Concurrency Is Needed Performance Multiuser Environments Multitasking How Concurrency Can Fail Making Concurrency Safe Read-Only Data Transaction-Based Processing Semaphores The Problem of Indefinite Waits Orderly Queues Starvation from Circular Waits Performance Issues of Semaphores What’s Next for Concurrency 9 Map Routes What a Map Looks Like to Software Best-First Search Reusing Prior Search Results Finding All the Best Routes at Once Floyd’s Algorithm Storing Route Directions The Future of Routing Index WOW! eBook www.wowebook.org

Acknowledgments This book was shaped and guided by a platoon of talented editors: Alison Law, Greg Poulos, Seph Kramer, Hayley Baker, Randall Hyde, Rachel Monaghan, and the “Big Fish” of No Starch, Bill Pollock. Beyond the editorial staff, I appreciate the support and kindness of everyone I’ve worked with at No Starch. The two people who helped me the most, though, are Mary Beth and Madeline, the best wife and daughter I can imagine. Without their love and support, this book would not have been written. WOW! eBook www.wowebook.org

Introduction Science fiction author Arthur C. Clarke wrote that “any sufficiently advanced technology is indistinguishable from magic.” If we don’t know how something works, then it might as well be explained by supernatural forces. By that standard, we live in an age of magic. Software is woven into our lives, into everyday things like online transactions, special effects in movies, and streaming video. We’re forgetting we used to live in a world in which the answer to a question wasn’t just a Google search away, or where finding a route for a car trip began with unfolding a cumbersome map. But few of us have any idea how all this software works. Unlike many innovations of the past, you can’t take software apart to see what it’s doing. Everything happens on a computer chip that looks the same whether the device is performing an amazing task or isn’t even turned on. Knowing how a program works seems to require spending years of study to become a programmer. So it’s no wonder that many of us assume that software is beyond our understanding, a collection of secrets known only to a technological elite. But that’s wrong. Who This Book Is For Anyone can learn how software works. All you need is curiosity. Whether you’re a casual fan of technology, a programmer in the making, or someone in between, this book is for you. This book covers the most commonly used processes in software and does so without a single line of programming code. No prior knowledge of how computers operate is required. To make this possible, I’ve simplified a few processes and clipped some details, but that doesn’t mean these are mere high-level overviews; you’ll be getting the real goods, with enough details that you’ll truly understand how these programs do what they do. Topics Covered Computers are so ubiquitous in the modern world that the list of subjects I could cover seems endless. I’ve chosen topics that are most central to our daily lives and with the most interesting explanations. • Chapter 1: Encryption allows us to scramble our data so that only we can access it. WOW! eBook www.wowebook.org

When you lock your phone or password-protect a .zip file, you’re using encryption. We’ll see how different scrambling techniques are combined in modern encryption software. • Chapter 2: Passwords are the keys we use to lock our data and how we identify ourselves to remote systems. You’ll see how passwords are used in encryption and learn the surprising steps that must be taken to keep passwords safe from attackers. • Chapter 3: Web Security is what we need to safely purchase goods online or access our accounts. Locking data for transmission requires a different method of scrambling called public-key encryption. You’ll discover how a secure web session requires all the techniques covered in the first three chapters. • Chapter 4: Movie CGI is pure software magic, creating whole worlds out of mathematical descriptions. You’ll discover how software took over traditional cel animation and then learn the key concepts behind making a complete movie set with software. • Chapter 5: Game Graphics are impressive not just for their visuals but also for how they are created in mere fractions of a second. We’ll explore a host of clever tricks games use to produce stunning images when they don’t have time for the techniques discussed in the previous chapter. • Chapter 6: Data Compression shrinks data so that we can get more out of our storage and bandwidth limits. We’ll explore the best methods for shrinking data, and then see how they are combined to compress high-definition video for Blu-ray discs and web streams. • Chapter 7: Search is about finding data instantly, whether it’s a search for a file on our own computer or a search across the whole Web. We’ll explore how data is organized for quick searches, how search zeros in on requested data, and how web searches return the most useful results. • Chapter 8: Concurrency allows multiple programs to share data. Without concurrency, multiplayer video games wouldn’t be possible, and online bank systems could allow only one customer at a time. We’ll talk about the methods that enable different processors to access the same data without getting in each other’s way. • Chapter 9: Map Routes are those instant directions we get from mapping sites and in- car navigators. You’ll discover what a map looks like to software and the specialized search techniques that find the best routes. Behind the Magic I think it’s important to share this knowledge. We shouldn’t have to live in a world we don’t understand, and it’s becoming impossible to understand the modern world without also understanding software. Clarke’s message can be taken as a warning that those who understand technology can fool those who don’t. For example, a company may claim that the theft of its login data poses little danger to its customers. Could this be true, and how? After reading this book, you’ll know the answer to questions like these. WOW! eBook www.wowebook.org

Beyond that, though, there’s an even better reason to learn the secrets of how software works: because those secrets are really cool. I think the best magic tricks are even more magical once you learn how they are done. Read on and you’ll see what I mean. WOW! eBook www.wowebook.org

1 Encryption We rely on software to protect our data every day, but most of us know little about how this protection works. Why does a “lock” icon in the corner of your browser mean it’s safe to enter your credit card number? How does creating a password for your phone actually protect the data inside? What really prevents other people from logging into your online accounts? Computer security is the science of protecting data. In a way, computer security represents technology solving a problem that technology created. Not that long ago, most data wasn’t stored digitally. We had filing cabinets in our offices and shoeboxes of photographs under our beds. Of course, back then you couldn’t easily share your photographs with friends around the world or check your bank balance from a mobile phone, but neither could anyone steal your private data without physically taking it. Today, not only can you be robbed at a distance, but you might not even know you’ve been robbed—that is, until your bank calls to ask why you are buying thousands of dollars in gift cards. Over these first three chapters, we’ll discuss the most important concepts behind computer security. In this chapter, we talk about encryption. By itself, encryption provides us with the capability to lock our data so only we can unlock it. Additional techniques, discussed in the next two chapters, are needed to provide the full security suite that we depend on, but encryption is the core of computer security. The Goal of Encryption Think of a file on your computer: it might contain text, a photograph, a spreadsheet, audio, or video. You want to access the file but keep it secret from everyone else. This is the fundamental problem of computer security. To keep the file secret, you can use encryption to transform it into a new format that is unreadable until the file has been returned to its original form using decryption. The original file is the plaintext (even if the file isn’t text), and the encrypted file is the ciphertext. An attacker is someone who attempts to decrypt the ciphertext without authorization. The goal of encryption is to create a ciphertext that is easy for authorized users to decrypt, while practically impossible for attackers to decrypt. “Practically” is the source of many WOW! eBook www.wowebook.org

headaches for security researchers. Just as no lock is absolutely unbreakable, no encryption can be absolutely impossible to decrypt. With enough time and enough computing power, any encryption scheme can be broken in theory. The goal of computer security is to make an attacker’s job so difficult that successful attacks are impossible in practice, requiring computing resources beyond an attacker’s means. Rather than jump headfirst into the intricacies of software-based encryption, I’ll start this chapter with some simple examples from the pre-software days of codes and spies. Although the strength of encryption has vastly improved over the years, these same classic techniques form the basis of all encryption. Later, you’ll see how these ideas are combined in a modern digital encryption scheme. Transposition: Same Data, Different Order One of the simplest ways to encrypt data is called transposition, which simply means “changing position.” Transposition is the kind of encryption my friends and I used when passing notes in grade school. Because these notes were passed through untrustworthy hands, it was imperative the notes were unintelligible to anyone but us. To keep messages secret, we rearranged the order of the letters using a simple, easy-to- reverse scheme. Suppose I needed to share the vital intelligence that CATHY LIKES KEITH (the names have been changed to protect the innocent). To encrypt the message, I copied every third letter of the plaintext (ignoring any spaces). During the first pass through the message, I copied five letters, as shown in Figure 1-1. Figure 1-1: The first pass in the transposition of the sample message Having reached the end of the message, I started back at the beginning and continued selecting every third remaining letter. The second pass got me to the state shown in Figure 1-2. Figure 1-2: The second transposition pass On the last pass I copied the remaining letters, as shown in Figure 1-3. WOW! eBook www.wowebook.org

Figure 1-3: The final transposition pass The resulting ciphertext is CHISIAYKKTTLEEH. My friends could read the message by reversing the transposition process. The first step is shown in Figure 1-4. Returning all the letters to their original position reveals the plaintext. Figure 1-4: The first pass in reversing the transposition for decryption This basic transposition method was fun to use, but it’s terribly weak encryption. The biggest concern is a leak—one of my friends blabbing about the encryption method to someone outside the circle. Once that happens, sending encrypted messages won’t be secure anymore; it will just be more work. Leaks are sadly inevitable—and not just with schoolchildren. Every encryption method is vulnerable to leaks, and the more people use a particular method, the more likely it will leak. For this reason, all good encryption systems follow a rule formulated by early Dutch cryptographer Auguste Kerckhoffs, known as Kerckhoffs’s principle: the security of data should not depend on the encryption method remaining a secret. Cipher Keys This raises an obvious question. If the encryption method is not a secret, how do we securely encrypt data? The answer lies in following a general, publically disclosed encryption method, but varying the encryption of individual messages using a cipher key (or just key). To understand what a key is, let’s examine a more general transposition method. In this method, senders and receivers share a secret number prior to sending any messages. Let’s say my friends and I agree on 374. We’ll use this number to alter the transposition pattern in our ciphertexts. This pattern is shown in Figure 1-5 for the message CATHY LIKES KEITH. The digits of our secret number dictate which letter should be copied from the plaintext to the ciphertext. Because the first digit is 3, the third letter of the plaintext, T, becomes the first letter of the ciphertext. The next digit is 7, so the next letter is the seventh letter after the T, which is S. Next, we select the fourth letter from the S. The first three letters of the ciphertext are TST. Figure 1-6 shows how the next two letters are copied to the ciphertext. Starting from WOW! eBook www.wowebook.org

where we left off (indicated by the circled 1 in the figure), we count three positions, returning to the beginning of the plaintext when we reach the end, to select A as the fourth letter of the ciphertext. The next letter chosen is seven positions after the A, skipping letters that have already been copied: the K. The process continues until all of the letters of the plaintext have been transposed. Figure 1-5: The first pass in transposing using the key 374 Figure 1-6: The second pass in transposing using the key 374 The secret number 374, then, is our cipher key. Someone who intercepts this message won’t be able to decrypt it without the key, even if they understand we’re using a transposition method. The code can be regularly changed to prevent blabbermouths and turncoats from compromising the encryption. Attacking the Encryption Even without the key, attackers can still try to recover the plaintext through other means. Encrypted data can be attacked through brute force, trying all the possible ways of applying the encryption method to the ciphertext. For a message encrypted using transposition, a brute-force attack would examine all permutations of the ciphertext. Because brute force is almost always an option, the number of trials an attacker will need to find the plaintext is a good baseline for encryption strength. In our example, the message CATHY LIKES KEITH has around 40 billion permutations. That’s a huge number, so instead of brute force, a smart attacker would apply some common sense to recover the plaintext faster. If the attacker can assume the plaintext is in English, then most of the permutations can be ruled out before they are tested. For example, the attacker can assume the plaintext won’t start with the letters HT because no English word starts with those letters. That’s a billion permutations the attacker won’t have to check. An attacker with some idea of the words in the message can be even smarter about figuring out the plaintext. In our example, the attacker might guess the message includes the name of a classmate. They can see what names can be formed from the ciphertext WOW! eBook www.wowebook.org

letters and then determine what words can be formed from the leftover letters. Guesses about the plaintext content are known as cribs. The strongest kind of crib is a known-plaintext attack. To carry out this type of attack, the attacker must have access to a plaintext A, its matching ciphertext A, and a ciphertext B that uses the same cipher key as ciphertext A. Although this scenario sounds unlikely, it does happen. People often leave documents unguarded when they are no longer considered secret without realizing they may aid attacks on other documents. Known-plaintext attacks are power ful; figuring out the transposition pattern is easy when you have both the plaintext and ciphertext in front of you. The best defenses against known-plaintext attacks are good security practices, such as regularly changing passwords. Even with the best security practices, though, attackers will almost always have some idea of a plaintext’s contents (that’s why are they so interested in reading it). In many cases, they will know most of the plaintext and may have access to known plaintext-ciphertext pairs. A good encryption system should render cribs and known plaintexts useless to attackers. Substitution: Replacing Data The other fundamental encryption technique is more resistant to cribs. Instead of moving the data around, substitution methods systematically replace individual pieces of data. With text messages, the simplest form of substitution replaces every occurrence of one letter with another letter. For example, every A becomes a D, every B an H, and so on. A key for this type of encryption looks like Table 1-1. Table 1-1: A Substitution Cipher Key Original A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Replacement M N B V C X Z L K F H G J D S A P O I U Y T R E W Q Although simple substitution, as this method is called, is an improvement over transposition, it too has problems: there are only so many possible substitutions, so an attacker can sometimes decrypt ciphertext through brute force. Simple substitution is also vulnerable to frequency analysis, in which an attacker applies knowledge of how often letters or letter combinations occur in a given language. Stated broadly, knowing how often data items are likely to appear in a plaintext gives the attacker an advantage. For example, the letter E is the most common letter in English writing, and TH is the most common letter pair. Therefore, the most frequently occurring letter in a long ciphertext is likely to represent plaintext E, and the most frequently occurring letter pair is likely to represent plaintext TH. The power of frequency analysis means that substitution encryption becomes more vulnerable as the text grows longer. Attacks are also easier when a collection of ciphertexts is known to have been encrypted with the same key; avoiding such key reuse is an important security practice. WOW! eBook www.wowebook.org