Network Security: Private Communication in a Public World

by Charlie Kaufman, Radia Perlman, Mike Speciner, Ray Perlner

Overview

The classic guide to cryptography and network security – now fully updated!

“Alice and Bob are back!”

Widely regarded as the most comprehensive yet comprehensible guide to network security and cryptography, the previous editions of Network Security received critical acclaim for lucid and witty explanations of the inner workings of cryptography and network security protocols. In this edition, the authors have significantly updated and revised the previous content, and added new topics that have become important.

This book explains sophisticated concepts in a friendly and intuitive manner. For protocol standards, it explains the various constraints and committee decisions that led to the current designs. For cryptographic algorithms, it explains the intuition behind the designs, as well as the types of attacks the algorithms are designed to avoid. It explains implementation techniques that can cause vulnerabilities even if the cryptography itself is sound. Homework problems deepen your understanding of concepts and technologies, and an updated glossary demystifies the field's jargon. Network Security, Third Edition will appeal to a wide range of professionals, from those who design and evaluate security systems to system administrators and programmers who want a better understanding of this important field. It can also be used as a textbook at the graduate or advanced undergraduate level.

Coverage includes

• Network security protocol and cryptography basics
• Design considerations and techniques for secret key and hash algorithms (AES, DES, SHA-1, SHA-2, SHA-3)
• First-generation public key algorithms (RSA, Diffie-Hellman, ECC)
• How quantum computers work, and why they threaten the first-generation public key algorithms
• Quantum-safe public key algorithms: how they are constructed, and optimizations to make them practical
  
• Multi-factor authentication of people
• Real-time communication (SSL/TLS, SSH, IPsec) 
• New applications (electronic money, blockchains)
• New cryptographic techniques (homomorphic encryption, secure multiparty computation)

 

Product Details

ISBN-13:	9780136643524
Publisher:	Pearson Education
Publication date:	08/31/2022
Sold by:	Barnes & Noble
Format:	eBook
Pages:	544
File size:	9 MB

About the Author

Charlie Kaufman is currently Security Architect for Dell Storage Systems. Previously, he was the Security Architect for Microsoft Azure and before that for Lotus Notes. He has contributed to a number of IETF standards efforts including IPsec, S/MIME, and DNSSEC and served as a member of the Internet Architecture Board. He served on the National Academy of Sciences expert panel that wrote the book Trust In Cyberspace.

Radia Perlman is currently a Fellow at Dell Technologies. She is known for her contributions to bridging (spanning tree algorithm), routing (link state routing), and security (distributed systems robust despite malicious participants). She's the author of Interconnections: Bridges, Routers, Switches, and Internetworking Protocol. She's been elected to the National Academy of Engineering, the National Inventors Hall of Fame, the Internet Hall of Fame, and awarded lifetime achievement awards from Usenix and ACM's SIGCOMM. She has a PhD in computer science from MIT.

Mike Speciner is an MIT-trained technologist with expertise in mathematics, physics, and computer science. He currently serves as CTO and cofounder of The Singing Torah. His hobby is writing software for educational purposes in various common and obscure programming languages. 

Ray Perlner is a Mathematician in the Cryptographic Technology Group of the National Institute of Standards and Technology. He has over a dozen research papers focusing primarily on post-quantum cryptography. He has degrees in both physics and mathematics from MIT.

Read an Excerpt

Preface

It was a dark and stormy night. Somewhere in the distance a dog howled. A shiny object caught Alice's eye. A diamond cufflink! Only one person in the household could afford diamond cufflinks! So it was the butler, after all! Alice had to warn Bob. But how could she get a message to him without alerting the butler? If she phoned Bob, the butler might listen on an extension. If she sent a carrier pigeon out the window with the message taped to its feet, how would Bob know it was Alice that was sending the message and not Trudy attempting to frame the butler because he spurned her advances? That's what this book is about. Not much character development for Alice and Bob, we're afraid, nor do we really get to know the butler. But we do discuss how to communicate securely over an insecure medium.

What do we mean by communicating securely? Alice should be able to send a message to Bob that only Bob can understand, even though Alice can't avoid having others see what she sends. When Bob receives a message, he should be able to know for certain that it was Alice who sent the message, and that nobody tampered with the contents of the message in the time between when Alice launched the message and Bob received it.

What do we mean by an insecure medium? Well, in some dictionary or another, under the definition of "insecure medium" should be a picture of the Internet. The world is evolving towards interconnecting every computer, and people talk about connecting household appliances as well, all into some wonderful global internetwork. How wonderful! You'd be able to send electronic mail to anyone in the world.

You'd also be able to control your nuclear powerplant with simple commands sent across the network while you were vacationing in Fiji. Or sunny Libya. Or historic Iraq. Inside the network the world is scary. There are links that eavesdroppers can listen in on. Information needs to be forwarded through packet switches, and these switches can be reprogrammed to listen to or modify data in transit. The situation might seem hopeless, but we may yet be saved by the magic of mathematics, and in particular cryptography, which can take a message and transform it into a bunch of numbers known as ciphertext. The ciphertext is unintelligible gibberish except to someone who knows the secret to reversing the transformation. Cryptography allows us to disguise our data so that eavesdroppers gain no information from listening to the information as transmitted.

Cryptography also allows us to create an unforgeable message and protect it from being modified in transit. One method of accomplishing this is with a digital signature, a number associated with a message and its sender that can be verified as authentic by others, but can only be generated by the sender. This should seem astonishing. How can there be a number which you can verify but not generate? A person's handwritten signature can (more or less) only be generated by that person, though it can be verified by others. But it would seem as if a number shouldn't be hard to generate, especially if it can be verified. Theoretically you could generate someone's signature by trying lots of numbers and testing each one until one passed the verification test. But with the size of the numbers used, it would take too much compute time (for instance, several universe lifetimes) to generate the signature that way. So a digital signature has the same property as a handwritten signature, in that it can only be generated by one person. But a digital signature does more than a handwritten signature.

Since the digital signature depends on the contents of the message, if someone alters the message the signature will no longer be correct and the tampering will be detected. This will all become clear if you read Chapter 2 Introduction to Cryptography.

Cryptography is a major theme in this book, not because cryptography is intrinsically interesting (which it is), but because the security features people want in a computer network can best be provided through cryptography.

1.1. Roadmap to the Book The book is divided into three main sections.

Cryptography.

Chapter 2 Introduction to Cryptography is the only part of the cryptography section of the book essential for understanding the rest of the book, since it explains the generic properties of secret key, message digest, and public key algorithms, and how each is used. We've tried our best to make the descriptions of the actual cryptographic algorithms nonthreatening yet thorough, and to give intuition into why they work. It's intended to be readable by anyone, not just graduate students in mathematics. Never once do we use the term lemma. We do hope you read.

Chapter 3 Secret Key Cryptography, Chapter 4 Hashes and Message Digests, and Chapter 5 Public Key Algorithms which give the details of the popular standards, but it's also OK to skip them and save them for later, or just for reference. For you math types who would have noticed that we skipped a number if we didn't mention it, Chapter 6 Number Theory gives a deeper treatment of the mathematics behind the cryptography.

Authentication.

Chapter 7 Authentication Systems introduces the general issues involved in proving your identity across a network.

Chapter 8 Authentication of People deals with the special circumstances when the device proving its identity is a human being.

Chapter 9 Security Handshake Pitfalls deals with the details of authentication handshakes. There are many security flaws that keep getting designed into protocols. This chapter attempts to describe variations of authentication handshakes and their relative security and performance strengths. We end the chapter with a checklist of security attacks, so that someone designing a protocol can specifically check their protocol for these flaws.

Chapter 10 Kerberos V4 and Chapter 11 Kerberos V5 describe the details of those authentication systems. Secure electronic mail. Chapter 12 Electronic Mail Security describes the various types of security features one might want, and how they might be provided. Chapter 13 Privacy Enhanced Mail (PEM), Chapter 14 PGP (Pretty Good Privacy), and Chapter 15 X.400 describe three mail standards which are compared in Chapter 16 A Comparison of PEM, PGP, and X.400. There are two chapters that aren't in any of the three main sections. The first chapter (the one you're reading now) gives a whirlwind tour of computer networking and computer security to set the stage for the main focus of the book-computer network security. The final chapter, Chapter 17 More Security Systems, describes a variety of security systems, including Novell NetWare (Versions 3 and 4), Lotus Notes, DCE, KryptoKnight/NetSP, Clipper, SNMP, DASS/SPX, and sabotage-proof routing protocols.

1.2. What type of book is this?

We believe the reason most computer science is hard to understand is because of jargon and irrelevant details. When people work with something long enough they invent their own language, come up with some meta-architectural framework or other, and forget that the rest of the world doesn't talk or think that way. We intend this book to be reader-friendly. We try to extract the concepts and ignore the meta-architectural framework, since whatever a meta-architectural framework is, it's irrelevant to what something does and how it works.

We believe someone who is a relative novice to the field ought to be able to read this book. But readability doesn't mean "lack of technical depth". We try to go beyond the information one might find in specifications. The goal is not just to describe exactly how the various standards and de facto standards work, but to explain why they are the way they are, why some protocols designed for similar purposes are different, and the implications of the design decisions. Sometimes engineering tradeoffs were made.

Sometimes the designers could have made better choices (they are human after all), in which case we explain how the protocol could have been better. This analysis should make it easier to understand the current protocols, and aid in design of future protocols.

The primary audience for this book is engineers, especially those who might need to evaluate the security of or add security features to a distributed system, but the book is also intended to be useable as a textbook, either on the advanced undergraduate or graduate level. Most of the chapters have homework problems at the end.

1.3. Terminology

Any field with science in its name isn't.

Tony Lauck

Computer science is filled with ill-defined terminology used by different authors in conflicting ways, often by the same author in conflicting ways. We apologize in advance for probably being guilty sometimes ourselves. Some people take terminology very seriously, and once they start to use a certain word in a certain way, are extremely offended if the rest of the world does not follow.

When I use a word, it means just what I choose it to mean-neither more nor less.

Humpty Dumpty (in Through the Looking Glass)

Some terminology we feel fairly strongly about. We do not use the term hacker to describe the vandals that break into computer systems. These criminals call themselves hackers, and that is how they got the name. But they do not deserve the name. True hackers are master programmers, uncorruptably honest, unmotivated by money, and careful not to harm anyone. The criminals termed "hackers" are not brilliant and accomplished. It is really too bad that they not only steal money, people's time, and worse, but they've also stolen a beautiful word that had been used to describe some remarkable and wonderful people. We instead use words like intruder, bad guy, and impostor. When we need a name for a bad guy, we usually choose Trudy (since it sounds like intruder).

We grappled with the terms secret key and public key cryptography. Often in the security literature the terms symmetric and asymmetric are used instead of secret and public. We found the terms symmetric and asymmetric intimidating and sometimes confusing, so opted instead for secret key and public key. We occasionally regretted our decision to avoid the words symmetric and asymmetric when we found ourselves writing things like secret key based interchange keys rather than symmetric interchange keys.

We use the term privacy when referring to the desire to keep communication from being seen by anyone other than the intended recipients. Some people in the security community avoid the term privacy because they feel its meaning has been corrupted to mean "the right to know", because in some countries there are laws known as privacy laws, which states that citizens have the right to see records kept about themselves.

The security community also avoids the use of the word secrecy, because secret has special meaning within the military context, and they feel it would be confusing to talk about the secrecy of a message that was not actually labeled top secret or secret. The term which is most commonly used in the security community is confidentiality. We find that strange because confidential, like secret, is a security label and the security community should have scorned use of confidential, too. We chose not to use confidentiality because we felt it was too many syllables, and saw no reason not to use privacy.

Speaker: Isn't it terrifying that on the Internet we have no privacy?

Heckler1: You mean confidentiality. Get your terms straight.

Heckler2: Why do security types insist on inventing their own language?

Heckler3: It's a denial of service attack.

Overheard at recent gathering of security types

We often refer to things involved in a conversation by name, for instance, Alice and Bob, whether the things are people or computers. This is a convenient way of making things unambiguous with relatively few words, since the pronoun she can be used for Alice and he can be used for Bob. It also avoids lengthy inter- (and even intra-) author arguments about whether to use the politically incorrect he, a confusing she, an awkward he/she or (s)he, an ungrammatical they, an impersonal it, or an incredibly awkward rewriting to avoid the problem. We remain slightly worried that people will assume when we've named things with human names that we are referring to people. Assume Alice, Bob, and the rest of the gang may be computers unless we specifically say something like the user Alice, in which case we're talking about a human.

With a name like yours, you might be any shape, almost.

Humpty Dumpty (in Through the Looking Glass)

Occasionally, one of the three of us authors will want to make a personal comment. In that case we use I or me with a subscript. When it's a comment that we all agree with, or that we managed to slip past me3 (the rest of us are wimpier) we use the term we. We use the symbol (pronounced ex-or) for the bitwise exclusive or operation. We denote secret key encryption with curly brackets preceded by the key with which something was encrypted, as in K{message}, which means message is secret-key encrypted with K. Public key encryption we denote with curly braces, and the name of the owner of the public key subscripting the close brace, as in {message} Bob.

Signing (which means using the private key), we denote with square brackets, with the name of the owner of the key subscripting the close bracket, as in message Bob.

1.4. Primer on Networking

You have to know something about computer networks to understand computer network security, so we're including this primer. For a more detailed understanding, we recommend .

Networks today need to be very easy to use and configure. Networks are no longer an expensive and educational toy for researchers, but instead are being used by real people. Most sites with networks will not be able to hire a full time person with networking expertise to start and keep the network running.

1.4.1. OSI Reference Model
Somehow, a book about computer networks would seem incomplete without a picture of the OSI (Open Systems Interconnection) Reference Model, The OSI Reference model is useful because it gives some commonly used terminology, though it might mislead you into thinking that there is only one way to construct a network. The reference model was designed by an organization known as the International Standards Organization (ISO). ISO decided it would be a good idea to standardize computer networking. Since that was too big a task for a single committee, they decided to subdivide the problem among several committees. They somewhat arbitrarily chose seven, shown in the diagram above. The basic idea is that each layer uses the services of the layer below, adds functionality, and provides a service to the layer above. When you start looking at real networks, they seldom neatly fit into the seven-layer model, but for basic understanding of networking, the OSI Reference model is a good place to start.

1. physical layer. This layer delivers an unstructured stream of bits across a link or some sort.

2. data link layer. This layer delivers a piece of information across a single link. It organizes the physical layer's bits into packets and control who on a shared link gets each packet.

3. network layer. This layer computes paths across an interconnected mesh of links and packet switches, and forwards packets over multiple links from source to destination.

4. transport layer. This layer establishes a reliable communication stream between a pair of systems across a network by putting sequence numbers in packets, holding packets at the destination until they can be delivered in order, and retransmitting lost packets.

5. session layer. The OSI session layer adds extra functions to the reliable pair-wise communication provided by the transport layer. Most network architectures do not have or need the functionality in this layer, and it is not of concern to security, so for the purposes of this book we can ignore it.

6. presentation layer. This layer encodes application data into a nonical format.

7. application layer. This is where the applications, such as file transfer and electronic mail, reside. These are the applications that use the network. OSI tried to make all the world a layer by calling network users the top layer.

A layer communicates with the equivalent layer in a different node. In order to get data to a peer layer, though, the layer at the transmitting node gives the data to the layer below it (on the same node), which adds a header containing additional information if necessary, and that layer in turn gives it to the layer below. As the packet is received by the destination node, each layer reads and strips off its own header, so that the packet received by layer n looks to that layer just like it did when it was sent down to layer n-1 for transmission.

1.4.2. Directory Service

Having a telephone line into your house means you can access any phone in the world, if you know the telephone number. The same thing is true, more or less, in computer networks. If you know the network layer address of a node on the network, you should be able to communicate with that node. (This isn't always true because of security gateways, which we'll discuss in 1.6 Firewalls/Security Gateways). But how do you find out another nodeÕs network layer address? Network layer addresses are not the kind of things that people will be able to remember, or type. People instead will want to access something using a name such as File-Server-3.

This is a similar problem to finding someone's telephone number. Typically you start out by knowing the name of the person or service you want to talk to, and then look the name up in a telephone book. In a computer network there is a service known as the directory service, which stores information about a name, including its network layer address. Anything that needs to be found is listed in the directory service. Anything that needs to find something searches the directory service.

Rather than keeping all names in one directory, the directory service is typically structured as a tree of directories. Usually a name is hierarchical, so that the directory in which the name can be found is obvious from the name. For example, an internet name looks like [e-mail]. The top level consists of pointers to the directories com for commercial enterprises, edu for educational institutions, gov for U.S. government, and various country names. Under com, there are various company names. Having multiple directories rather than keeping all names in one directory serves two purposes. One is to prevent the directory from getting unreasonably large. The other reason is to reduce name collisions (more than one object with the same name). For instance, when you're looking up a telephone number for your friend John Smith, it's bad enough trying to figure out which John Smith is the one you want if you know which town he lives in and the telephone company has separate directories for each town, but imagine if the telephone company didn't have separate books for each town and simply had a list of names and telephone numbers!

Ideally, with a hierarchy of directories, name collisions could be prevented. Once a company hired one Radia Perlman, they just wouldn't hire another. I2 think that's reasonable, but someone with a name like John Smith might start having problems finding a company that could hire him.

Now why did you name your baby John? Every Tom, Dick, and Harry is named John.

Sam Goldwyn

For electronic mail addresses, conflicts must be prevented. Typically, companies let the first John Smith use the name John@companyname for his email address, and then perhaps the next one will be Smith@companyname, and the next one JSmith@companyname, and the next one has to start using middle initials. But for directories of names, there is usually no way to avoid name collisions within a directory. In other words, both John Smiths will use the same name within the company. Then, just like with a telephone book and multiple John Smiths, you have to do the best you can to figure out which one you want based on various attributes (such as in the telephone directory, using the street address). And just like in real life, there will be lots of confusion where one John Smith gets messages intended for a different John Smith.

The directory service is very important to security. It is assumed to be widely available and convenient to access otherwise large scale networking really is too inconvenient to be practical. The directory service is a convenient place to put information, such as a user's public cryptographic key. But the directory service, although convenient, is not likely to be very secure. An intruder might tamper with the information. The magic of cryptography will help us detect such tampering so that it will not be necessary to physically secure all locations that store directory service information. If the information is tampered with, it might prevent good guys from accessing the network, but it will not allow bad guys to access things they are not authorized to access.

1.4.3. Replicated Services

Sometimes it is convenient to have two or more computers performing the same function. One reason is performance. A single server might become overloaded, or might not be sufficiently close to all users on a large network. Another reason is availability. If the service is replicated, it does not matter if some of the replicas are down or unavailable. When someone wants to access the service provided, it doesn't matter which of the computers they reach. Often the fact that the service is replicated is transparent to the user, meaning that the user does not know whether thereÕs a single copy of the service or whether there are replicas.

What are the security issues with a replicated service? YouÕd want the user to have the same authentication information regardless of which replica was authenticating the user. If authentication information is stored at each replica, then coordinating the databases, for example after a change password command, can be tricky. And if the identical exchange will work with any of the replicas, then having an eavesdropper repeat the authentication handshake with a different replica might be a security problem.

1.4.4. Packet Switching

A really naive assumption would be that if people wanted computer A to talk to computer B, they'd string a wire between A and B. This doesn't work if networks get large, either in number of nodes (n2 wires) or physical distance (it takes a lot of wire to connect each of 10 000 nodes in North America with each of 10 000 nodes in Asia). So in a network, messages do not go directly from sender to recipient, but rather have to be forwarded by various computers along the way. These message forwarders are referred to as packet switches, routers, gateways, bridges, and probably lots of other names as well. A message is generally broken into smaller chunks as it is sent through the network. There are various reasons for this, all irrelevant for the purposes of this book, but we'll mention some of them anyway.

Messages from various sources can be interleaved on the same link. You wouldn't want your message to have to wait until someone else finished sending a huge message, so messages are sent a small chunk at a time. If the link is in the process of sending the huge message when your little single-chunk message arrives, your message only has to wait until the link finishes sending a single chunk of the large message.

Error recovery is done on the transmission unit. If you find out that one little chunk got mangled in transmission, only that chunk needs to be retransmitted.

Buffer management in the routers is simpler if the size of packets has a reasonable upper limit. Encryption and integrity protection is sometimes done end-to-end on the original message or hop-by-hop, on each chunk of the message.

1.4.5. Network Components

The network is a collection of packet switches (usually called routers) and links. A link can either be a wire between two computers or a multiaccess link such as a LAN (local area network). A multiaccess link has interesting security implications. Whatever is transmitted on the link can be seen by all the other nodes on that link. Multiaccess links with this property are Ethernet (also known as CSMA/CD), token rings, and packet radio networks.

Connected to the backbone of the network are various types of nodes. A common categorization of the nodes is into clients, which are workstations that allow humans to access the resources on the network, and servers, which are typically dedicated machines that provide services such as file storage and printing.

It should be possible to deploy a new service and have users be able to conveniently find the service. Users should be able to access the network from various locations, such as a public workstation a company makes available for visitors. If a person has a dedicated workstation located in one location, such as an office, it should be possible with a minimum of configuration for the user to plug the workstation into the network. Another method for users to access a network is through a dumb terminal. A dumb terminal is not a general purpose computer and does not have the compute power to do cryptographic operations.

Usually a dumb terminal hooks directly into a host machine, or hooks into a terminal server, which relays the terminal's keystrokes via a network protocol across the network to the host machine (the machine the user logs into).

1.4.6. Destinations: Ultimate and Intermediate

A network is something to which multiple systems can attach. We draw it as a cloud since from the point of view of the systems connected to it, exactly what goes on inside is not relevant. If you want to send a message to a system, and you are both connected to the same cloud, you hand your message to the cloud, together with a header that contains your address (the source address) and the address of the desired recipient (the destination address).

But how do you connect to the network? It might be with a point-to- point link to a packet switch inside the network, in which case things are reasonably simple. If A wants to send a message to B, A will put A as source address and B as destination address and send the message on the point to point link. But what if A is connected on a LAN? In that case, in order to transmit the packet across the LAN A has to specify which destination on that link should receive the message. For example:

If A wants to send a message to D it has to know (somehow-if you care you can read my2 book ???ref) that the appropriate neighbor on the LAN that will forward the packet is R2. So when A transmits the message there are two destinations: R2 as the next recipient and D as the ultimate recipient. A reasonably simple way of thinking about this is that the data link layer worries about transmission across a single link. The data link header has a source and destination address that indicate the transmitter on that link and the receiver on that link. The network layer worries about transmission across a multi-hop network. It has a header that carries the ultimate source and ultimate destination. The data link header is removed each time a message is received, and a new data link header is tacked onto the message when it is forwarded to the next hop. When A transmits the packet, the network header has source A, destination D. The data link header has source A, destination R2. R2 forwards the packet to R5. Since R2 is connected to R5 with a point-to-point link, the data link header will not have addresses. But when R5 forwards the packet to R6 across the LAN, the network layer header will (still) be source A, destination D.

The data link header will be source R5, destination R6. When R6 forwards it (across the token ring LAN) the network header is still the same, and the data link header has source R6, destination D. Most likely A's data link address will look different from its network layer address, so it's a bit sloppy to say source A in both the data link header and network header. But this is all irrelevant to security. Fascinating in its own right, but irrelevant to this book.

The network layer header can be thought of as an envelope for the message. The data link header is an outer envelope. We've described the case of two envelopes; a network header inside a data link header. The world can be even more complicated than this. In fact the data link layer might be a multi-hop network with multi-hop networks inside it as well. So a message might wind up with several envelopes. Again this is fascinating stuff but is irrelevant to this book.

1.4.7. Address Structure

What do addresses look like? In terms of security, the main issue is how difficult it is to forge a source address, and how easy it is to arrange for the network to deliver packets to you when they are addressed to someone other than you. For instance, think of a letter as having a source address (the return address, it's called in paper mail) and a destination address. It's easy to send a letter to anyone and put President, White House, USA as the source address. It's harder to arrange to receive mail sent to President, White House, USA if you are not the U.S. President, especially if you don't live in the White House, and most likely more difficult the further you live from the address you'd like to impersonate. Addresses are usually hierarchical, just like a postal address. If we think of the address as specifying country/state/city/person, then in general it will be easier to arrange to receive someone else's messages if you reside in the same city (for instance by bribing a postal employee), and most difficult if they're in a different country.

Forging source addresses is easy in most network layers today. Routers could be built more defensively and do a sanity check on the source address, based on where they receive the packet from, but routers in general do not do this. Sometimes security gateways (also known as firewalls) have such features.

1.5. Tempest

One security concern in this layer is having intruders tap into a wire, giving them the ability to eavesdrop and possibly modify or inject messages. Another security concern is electronic emanation, whereby through the magic of physics, the movement of electrons can be measured from a surprising distance away. This means that intruders can sometimes eavesdrop without even needing to physically access the link. The U.S. military TEMPEST program measures how far away an intruder must be before eavesdropping is impossible. That distance is known as the device's control zone. The control zone is the region that must be physically guarded to keep out intruders that might be attempting to eavesdrop. A well-shielded device will have a smaller control zone.

1 -- remember being told in 1979 of a tape drive that had a control zone over 2 miles. Unfortunately, most control zone information is classified, and

2 -- couldn't get me to be very specific about them, other than that they're usually expressed in metric.

Since it is necessary to keep intruders away from the control zone, it's certainly better to have something with a control zone on the order of a few inches rather than a few miles (oh yeah, kilometers).

CIA eavesdroppers could not intercept the radio transmissions used by Somali warlord Mohammed Farah Aidid; his radios, intelligence officials explained, were too low tech.

Larry Downing, Newsweek, Oct 10, 1994, page 32

1.6. Firewalls/Security Gateways

Firewalls are the wrong approach. They don't solve the general problem, and they make it very difficult or impossible to do many things. On the other hand, if I were in charge of a corporate network, I'd never consider hooking into the Internet without one. And if I were looking for a likely financially successful security product to invest in, I'd pick firewalls.

Charlie Kaufman

A firewall is a computer that sits between your internal network and the rest of the network and filters packets as they go by, according to various criteria you can configure. It is sometimes called other things, like a security gateway, or various more colorful names thought up by frustrated network users.

Why is a firewall needed? It wouldn't be, if security was done right, meaning that every system in your network had sophisticated authentication, the ability to do integrity protected and encrypted communication, (see the rest of this book to see how to do security right), and was well-managed (when users rely on passwords, they choose good passwords, system accounts are not left with no password or a default password, etc.). The dilemma is that most corporate networks are not designed for security, and yet it is desirable to have some connectivity to a global network. You want to be able to send mail to anyone. You want to occasionally share files. You want to communicate with publicly available services. But a large global network is a scary place. There will be spies from unfriendly countries, users from competing companies, playful undergraduates, press people eager for a juicy scoop, criminals anxious to steal information for profit, and disgruntled ex-employees.

1.6.1. Packet Filters

The simplest form of firewall selectively discards packets based on things it can be configured to look for, for instance the network address. For example, it might be configured to only allow some systems on your network to communicate outside, or some addresses outside your network to communicate into your network. For each direction, the firewall might be configured with a set of legal source and destination addresses, and it drops any packets that don't conform. This is known as address filtering. Address filtering has the problem that it is often easy to forge a network address.

1.6.2. Application Level Gateway

Another strategy for protecting your vulnerable network is an application level gateway. This can be accomplished with three boxes. The two firewalls are routers that refuse to forward anything unless it's to or from the gateway. Firewall F2 refuses to forward anything from the global net unless the destination address is the gateway, and refuses to forward anything to the global net unless the source is the gateway. Firewall F1 refuses to forward anything from your network unless the destination address is the gateway, and refuses to forward anything to your network unless the source address is the gateway. To transfer a file from your network to the global network you need to have someone from inside transfer the file to the gateway machine, and then the file is accessible to be read by the outside world. Similarly to read a file into your network a user has to arrange for it to first get copied to the gateway machine. To log into a machine in the global network you first log into the gateway machine, and from there you can access machines in the remote network.

The gateway machine need not support every possible application. A common strategy is only to allow electronic mail to pass between your corporate network and the outside world. The intention is to specifically disallow file transfer and remote login. But electronic mail can certainly be used to transfer files. Sometimes a firewall might specifically disallow very large electronic mail messages, on the theory that will limit the ability to transfer files. But often large electronic mail messages are perfectly legitimate, and any file can be broken down into small pieces. Because of such firewalls, many applications that post data for public retrieval on the Internet have automatic mail responders to which you can send an email message requesting the file, and the file will be sent back as an email message--several email messages, in fact, since such applications also realize the email messages have to be kept small in order to make it through the firewall. It is slow and painful for legitimate users to get files that way. Typically the file arrives in several pieces. Each piece has to be extracted from the received email (to get rid of email headers), rearranged into order (since email tends to get out of order), and edited into a file.

1.6.3. Encrypted Tunnels

A tunnel is a point-to-point connection in which the actual communication occurs across a network. This becomes a useful concept when you are thinking about your communication path as a sequence of links, some of which are secure and some of which aren't. The right way to ensure secure communication is end-to-end, i.e. where the two communicating parties do all the security work and assume that the medium over which they are communicating is insecure. But the parties may not capable of providing security, which is okay if the links themselves are secure. When some of the links are subject to eavesdropping, you can encrypt over those links. Only the routers on those links need to do encryption and decryption.

Suppose the only reasons you've hooked into a public internet is to connect disconnected pieces of your own network to each other and to allow your off-site users to connect to your network. You donÕt care about making internet resources available to the users inside your corporate network.

The typical solution for this is to have G1, G2, and G3 treat the internet just as if it's some sort of insecure wire. G1, G2, and G3 are configured with security information about each other. All information between them is encrypted and integrity protected. This can be done with a single shared secret key for all of them, or with any sort of pairwise authentication scheme based on secrets or public keys.

You might want your users to be able to access the corporate network from across the internet as well.

Suppose X is some sort of workstation that can attach to the internet in any location. To do this, X would create a tunnel with one of the G's.

1.7. Key Escrow for Law Enforcement

The U.S. government has proposed technology to preserve its ability to wiretap otherwise secure communication. To do this it must either prevent use of encryption, break the codes used for encryption (as it did in a military context during World War II), or somehow learn everyoneÕs cryptographic keys. The proposed technology takes the last option. It allows the Government to reconstruct your key (only upon court order and with legitimate cause of course). This is made possible through the use of a device known as the Clipper chip. A lot about Clipper is classified by the government as secret (and classified by a lot of other people as evil). We describe the basic technical design of Clipper in 17.9 Clipper. The simple concept is that encryption is done with a special chip (the Clipper chip). Each chip manufactured has a unique key, and the government keeps a record of the serial number/encryption key correspondence of every chip manufactured. Because not all people have complete trust in the government, rather than keeping the key in one place, each key is broken into two quantities which must be in order to obtain the actual key. Each piece is completely useless without the other. Since each piece is kept with a separate government agency, it would require two U.S. government agencies to cooperate in order to cheat and obtain the key for your Clipper chip without a valid court order. The government assures us, and evidence of past experience supports its claim, that cooperation between U.S. government agencies is unlikely.

The Clipper proposal is controversial, starting with its name. The name will certainly change, since it violates someone's trademark on something unrelated. But since everyone calls the proposal Clipper, we will too, especially since the new name has not been chosen. Why would anyone use Clipper when alternative methods should be cheaper and more secure? The reason alternatives would be cheaper is that enforcing the ability of the U.S. government to wiretap will add a lot of complexity. Proponents of Clipper have given several answers to this question.

The government will buy a lot of Clipper chips, bringing the cost down because of volume production, so Clipper will wind up being the most cost-effective solution.

Encryption technology is only useful if both parties have compatible equipment. If you want to talk securely to the U.S. government, you will have to use Clipper. So any other mechanism would have to be implemented in addition to Clipper.

Again, since encryption technology is only useful if both parties have compatible equipment, if Clipper takes over enough market share, it will essentially own the market (just like VHS, a technically inferior standard supposedly, beat out Beta in the VCR marketplace). Since Clipper will be one of the earliest standards, it might take over the marketplace before any other standards have an opportunity to become entrenched. Most people won't care that Clipper enables wiretapping, because they'll assume they have nothing to fear from the U.S. government wiretapping them.

The government claims that the cryptographic algorithm in Clipper is stronger than you'll be able to get from a commercial source. Civil libertarians fear Clipper is a first step towards outlawing untappable cryptography. Clipper proponents say it is not. It's true that outlawing alternatives is not part of the Clipper proposal. However, there have been independent efforts to outlaw cryptography. Those efforts have been thwarted in part with the argument that industry needs security. But if Clipper is deployed, that argument goes away. Clipper is designed for telephones, fax, and other low-speed applications, and in some sense is not relevant to computer networking. Many people regard it, however, as a first step and a model for taking the same approach for computer networks.

1.8. Key Escrow for Careless Users

It is prudent to keep your key in a safe place so that when you misplace your own key you can retrieve a copy of the key rather than conceding that all your encrypted files as irretrievably lost. It would be a security risk to have all users' keys stored unencrypted somewhere. The database of keys could be stored encrypted with a key known to the server that was storing the database, but that would mean that someone that had access to that machine could access all the user keys. Another possibility is to encrypt the key in a way that can only be reconstructed with the cooperation of several independent machines. This is feasible and we'll discuss it more in 17.9.1 Key Escrow.

Some applications don't require recoverable keys. An example of such an application is login. If a user loses the key required for login, the user can be issued a new key. A user may therefore want different keys for different uses, where only some of the keys are escrowed. For applications that do require recoverable keys, protection from compromise can be traded off against protection from loss.

1.9. Viruses, Worms, Trojan Horses

Lions and tigers and bears, oh my!

Dorothy (in The Wizard of Oz movie)

People like to categorize different types of malicious software and assign them cute biological terms (if one is inclined to think of worms as cute). We donÕt think it's terribly important to distinguish between these things, but will define some of the terms that seem to be infecting the literature.

Trojan horse-instructions hidden inside an otherwise useful program that do bad things. Usually the term Trojan horse is used when the malicious instructions are installed at the time the program is written (and the term "virus" is used if the instructions get added to the program later).

virus-a set of instructions that, when executed, inserts copies of itself into other programs

bacterium-a free-standing program that replicates itself, causing harm by consuming resources

worm-a program that replicates itself by installing copies of itself on other machines across a network. Similar to a bacterium, but it replicates over a network whereas a bacterium tends to stay confined to one machine.

trapdoor-an undocumented entry point intentionally written into a program, often for debugging purposes, which can be exploited as a security flaw

logic bomb-malicious instructions that trigger on some event in the future, such as a particular time occurring.

We do not think it's useful to take these categories seriously. Like most things people have tried to categorize (plants vs animals, intelligence vs instinct) there are things that don't fit neatly within these categories. We'll refer to them generically as digital pests.

1.9.1. Where do they come from?

Where do these nasties come from? Except for trapdoors, which may be intentionally installed to facilitate troubleshooting, they are written by bad guys with nothing better to do with their lives than annoy people.

How could an implementer get away with writing a digital pest into a program? Wouldn't someone notice by looking at the program? One of the most famous results id computer science is that it is probably impossible to be able to tell what an arbitrary program will do by looking at it, so certainly it would be impossible to tell, in general, whether the program had any unpleasant side effects besides its intended purpose. But that's not the real problem. The real problem is that nobody looks. Often when you buy a program you do not have access to the source code, and even if you did, you probably wouldn't bother reading it all, or reading it very carefully. Many programs that run have never been reviewed by anybody.

If it were possible to examine source code to see if it did anything other than its intended purpose, nobody would have an excuse for shipping software with bugs.

What does a virus look like? A virus can be installed in just about any program by doing the following:

replace any instruction, say the instruction at location x, by a jump to some free place in memory, say location y.

Write the virus program starting at location y, place the instruction that was originally at location x at the end of the virus program, followed by a jump to x+1.

Besides doing whatever damage the virus program does, it might replicate itself by looking for any executable files in any directory and infecting them. Once an infected program is run, the virus is executed again, to do more damage and to replicate itself to more programs. Most viruses spread silently until some triggering event causes them to wake up and do their dastardly deeds. If they did their dastardly deeds all the time, they wouldn't spread as far. How does a digital pest originally appear on your computer? All it takes is running a single infected program. A program posted on a bulletin board might certainly be infected. But even a program bought legitimately might conceivably have a digital pest. It might have been planted by a disgruntled employee or a saboteur that might have broken into the computers of the company and installed the pest into the software before it was shipped. There have been cases where commercial programs were infected because some employee ran a program gotten from a friend or a bulletin board.

Often at holiday times people send email messages that are programs, with the instruction that you extract the mail message and run it. Often the result is some sort of cute holiday-specific thing, like displaying a picture of a turkey or playing a Christmas carol. It could certainly also contain a virus. Few people will scan the program before running it, especially if the message arrives from a friend. And if you were to run such a program and it did something cute, you might very well forward it to a friend, not realizing that in addition to doing the cute thing it might very well have installed a virus that will start destroying your directory a week after the virus is first run. A good example of a Christmas card email message is a program written by Ian Phillipps, which was a winner of the 1988 International Obfuscated C Code Contest. It is delightful as a Christmas card. It does nothing other than its intended purpose (I1 have analyzed the thing carefully and I2 have complete faith in me1), but we doubt many people would take the time to understand this program before running it.



Sometimes you don't realize you're running a program. PostScript is a complete programming language. It is possible to imbed a Trojan horse into a PostScript file that infects files with viruses and does other damage. Someone could send you a file and tell you to display it. You wouldn't realize you were running a program by merely displaying the file. And if there was any hope of scanning a C program to find suspicious instructions, there are very few people who could scan a PostScript file and look for suspicious PostScript commands. PostScript is, for all practical purposes, a write-only language. As mail systems get more clever in their attempt to make things more convenient for users, the risk becomes greater. If you receive a PostScript file and you are running a non-clever mail program, you will see delightful crud like:

If you wanted to display the file, you'd have to extract the mail message and send it to the printer, or input it into a special program that displays PostScript on your screen. However, a clever mail program might look at the message, recognize that it was PostScript, and automatically run the PostScript code to display the message. Although this is convenient, it is dangerous, since no matter how clever your vendor claims their mail product is, we can assure you it won't scan the PostScript for Trojan horses before displaying the message.

There are various other clever features being added to mail programs. Some mail programs allow the sender to send a program along with the mail message. Usually the mail message will arrive and display some sort of icon. If the receiver clicks on the icon, the transmitted program is executed. Someone, to illustrate this point, sent such a mail message. It displayed only as a button that said push me. When the person that received the message clicked on the box, it came up with a message that said, I could have just reformatted your hard drive.

Before the technology for clever mail goes much further, we ought to consider how we can reap the benefits of such cleverness while minimizing the security risks.

There are dangers associated with booting from floppy disks. Even if system software becomes sophisticated about security, it won't be able to protect against Trojan horses on the boot device, and people still commonly boot from floppies. When you turn the machine on with a floppy disk inserted into the drive, the machine executes the code on the floppy. If there is a virus in that code, it can stay resident in memory, and infect any new floppies inserted into the drive (unless the machine is powered off between floppies). Even machines with hard drives allow booting off floppies. If the hard drive were completely wiped clean, there has to be some way to come up again, so machines provide the feature that if there is a floppy in the drive when the machine is powered on, the machine boots off the floppy. Often it is convenient to boot off a floppy. It is common to run games by booting off the floppy containing the game.

Once you run code on a floppy, the code can do anything, so if it contains a virus it can destroy or infect all the files on the hard disk.

1.9.2. Spreading Pests from Machine to Machine

How might a virus or worm spread from machine to machine? An infected program might be copied to a floppy and moved to another machine. Or, as we said, a mail message might carry the infection. But it is also possible for the pest to explore the network and send itself to other machines, once it is running in one machine on a network. Such a pest is called a worm.

One method a worm can employ to transmit itself to another machine is to actually log onto the other machine. It can do this by guessing passwords. Sometimes things are set up to make it really easy, for instance, account name/password pairs might be stored in script files so that a naive user can access remote resources automatically. If the worm manages to find that information, it can easily log into other machines and install itself. Sometimes machines have trapdoor debugging features, such as the ability to run a command remotely. Sometimes it isn't even necessary to log in order to run such a command.

And if intruders can execute commands, they can do anything.

The only reason all the computers in the world haven't crashed at the same time is that they're not all connected together yet.

Tony Lauck

One Christmas card type email message displayed a pretty animated tree on the screen, but also scanned the user's directory for all possible correspondents, including distribution lists, and mailed itself to them. Each time a recipient read a copy of the message, it sprang into life and mailed itself off to all the mailboxes it could locate from that node. Although this program did not destroy data, like a classic worm it completely disabled the corporation's electronic mail.

1.9.3. Virus Checkers

How can a program check for viruses? There's rather a race between the brave and gallant people who analyze the viruses and write clever programs to detect and eliminate the known viruses, and the foul- smelling scum who devise new types of viruses that will escape detection by all the current virus checkers.

The most common form of virus checker knows the instruction sequence for lots of types of viruses, checks all the files on disk and instructions in memory for those patterns of commands, and raises a warning if it finds a match hidden somewhere inside some file. Once you own such a virus checker, you need to periodically get updates of the patterns file that includes the newest viruses. To evade detection of their virus, virus creators have devised what is known as a polymorphic virus which changes the order of its instructions, or changes to functionally similar instructions, each time it copies itself. Such a virus may still be detectable, but it takes more work and typically requires a coding change and not just a new pattern file.

Another type of virus checker takes a snapshot of disk by recording the information in the directory, such as file lengths. It might even take message digests of the files. It is designed to run, store the information, and then run again at a future time. It will warn you if there are suspicious changes. One type of virus, wary of changing the length of a file by adding itself to the program, compressed the program so that the infected program would wind up being the same length as the original. When the program was executed, the uncompressed portion containing the virus decompressed the rest of the program so (other than the virus portion), the program could run normally.

1.9.4. What can we do today?

The world was a scary place before computer viruses came along, and will most likely continue to be scary. How can you know whether you can trust a program not to do bad things when you run it? Wouldn't it be nice to have the equivalent of a lie-detector test for programs?

Ames slipped by a lie-detector test because no one had told the polygrapher he was under suspicion.

Larry Downing, Newsweek article on CIA and traitor Aldrich Ames,
October 10, 1994
Given that there is no infallible method to test a program for hidden bad side effects, we can't be completely safe, but there are some precautions that are worth taking:

Don't run software from suspicious sources, like bulletin boards, or software gotten from people who aren't as careful as you are.

Frequently run virus checkers. Have the industry employ people whose job it is to keep up with virus technology and come up with vaccines.

Try to run programs in the most limited possible environments. For instance, if you have a PC in order to get real work done, and you also want to play games, sometimes using shareware or games copied from bulletin boards, have two machines. If you run a game with a virus, you'll only wipe out your games.

Do frequent backups, and save old backups for a long time.

Don't boot off floppies, except in an extreme circumstance, such as the first time you unpack your machine and turn it on.

In those circumstances, be extremely careful about what floppy you boot from.
But mostly, the situation is pretty bleak, given the design of the operating systems for PCs. Maybe in the future, some of our suggestions in the next section might be implemented.

1.9.5. Wish list for the Future

I2 always assumed computers were designed in such a way that no program that ran on the machine could possibly injure the machine. Likewise, it should not be possible to send a piece of information to a machine that might damage the machine. People are designed properly that way, aren't they?

Sticks and stones may break my bones but words will never hurt me. chant designed to encourage bullies to get physical

But one of my2 first programs consisted of something that just sat around and waited for interrupts, and processed the interrupts. The program itself, not counting the instructions for processing the interrupts, was HERE: JUMP HERE (that's not the exact instruction because I'm attempting not to divulge the computer brandname).

I2 discovered (the hard way) that you weren't supposed to do that, because it burned out core at the instruction that kept getting executed over and over. Gerry Sussman, while a high school student, wrote a program that broke magnetic tapes. The guru who guarded and ran the mainframe didn't believe Gerry when he boasted that he could write a program to break tapes, so Gerry wrote his program to go down the entire row of tape drives, breaking the tape in each one. Another example was a machine designed with a small amount of nonvolatile memory, but the type that wore out after a finite number of writes, say 10,000.

That kind of memory is fine for something like saving terminal settings, since a human has to type the key sequence to cause a write, and a human won't do it very often. But if the same kind of message is used for storing parameter settings received by a network management message, then it is possible to break the machine within seconds by sending it parameter settings over and over.

In an ideal world, it should be possible to load a floppy and examine the contents without fear. You should be able to receive any email message without fear. If it is a multimedia message, it should be possible to play the audio, display the video, print the text, or waft the odors without damage to either the machine or files stored on the machine. A file is just a bunch of bits. If the file claims to be audio, it should be possible, without risk of any type of harm, to play the file. Likewise, if the file claims to be something worthy of printing, it should not cause any harm to print the file.

Programs are a bit trickier. It should be possible to run a program and not have it affect the files stored on your machine, or the basic integrity of the operating system.

We know none of these "shoulds" are true today. The files on your machine can be virus-infected through email, printing a PostScript file, or simply inserting a floppy disk (on some machines). How could systems be designed more defensively?

One simple feature would be a write-protect switch on your hard disk. Sometimes you run programs that you know should not be writing to your hard disk. A game program shouldn't be writing to your hard disk. Perhaps it wants to record highest score, but consumers might be willing to do without that frill, if it means that they can run any game they want, without fear of wiping out their life's work.

Legitimate game manufacturers could design their games to work with write-protected hard disks. Even the social misfits who design games that spread viruses could design their games to work with write- protected hard disks, but just have their program check to see if some user has forgotten to write-protect the disk, and then launch the virus.

Time sharing systems used to be much more defensive. You could not run a program that would write into some other user's memory, or modify any portion of the disk that you were not authorized to write into. But PCs make the assumption that there is only one human on the machine at a time, and that human ought to be able to do anything it wants. To make matters worse, to enable snazzy maximally flexible features, there are all sorts of surprising places in which someone can insert a program which will be executed.

The operating system ought to be built more defensively. PCs should have accounts just like timesharing systems so that you can set up a game account that can't affect the rest of the system. Likewise your normal account shouldn't be able to alter system software. The world is moving in this direction, but progress is slow.

Booting off a flop py is unavoidably dangerous, since it involves loading the operating system itself. Since a program that is supposed to be the operating system will certainly be allowed to do anything it wants, there's no way to prevent polluted software on a floppy from destroying the world, if you boot off that floppy.

At least, one should only boot off the floppy that came with the machine, rather than using the boot feature to more conveniently run games. One game I1 ran recently ran out of memory, and with the error message giving the bad news, offered to make a special floppy that could run the game, finding extra memory by avoiding loading anything that wasn't essential to the running of the game. That was a very helpful suggestion, but it means that people still, for various reasons, will be tempted to boot off floppies of suspicious heritage.

1.10. The Military Model of Security

The main concern in the military model of security is with keeping data secret. It involves worrying about arcane threats such as covert channels, and creating cumbersome mechanisms such as mandatory access controls for keeping secret data from leaking out.

1.10.1. Mandatory Access Controls

O negligence! what cross devil made me put this main secret in the packet I sent the king? Is there no way to cure this? No new device to beat this from his brains?

Shakespeare's King Henry VIII, Act 3, scene 2

Discretionary means that someone who owns a resource can make a decision as to who is allowed to use (access) it. Nondiscretionary access controls are where strict rules are automatically enforced about who is allowed access to certain resources, and even the owners of the resources cannot change the attributes of a resource.

The basic philosophy behind discretionary controls is that the users and the programs they run are the good guys, and it is up to the operating system to trust them and protect each user from outsiders and other users. The basic philosophy behind nondiscretionary controls is that everything would be fine except for the pesky human beings that unfortunately have to be allowed to use the system. The system must be ever vigilant to prevent the users from accidentally or intentionally giving information to someone who shouldn't have it.

This philosophy does not necessarily imply that the users are expected to be evil, but it does expect them to be careless, and possibly run programs with digital pests. Careless users might accidentally type the wrong file name when including a file in a mail message, or might leave a message world readable.

Non-discretionary access controls grew out of the military mindset. The primary concern is secret data getting leaked to the enemy. The concept is to confine information within a security perimeter, and not allow any information to move from a more secure environment to a less secure environment.

Now of course, if you allow the users out of the building there is an avenue for information to leak out of a secure environment, since a user can remember the information and tell someone once the user gets out of the security perimeter. But the designers of these controls weren't primarily worried about the authorized users selling secrets. There really is no way for a computer system to prevent that. But they wanted to ensure that no Trojan horse in software could transmit any information out of the perimeter, and they wanted to make sure that nothing inadvertent a user did could leak information.

1.10.2. Levels of Security

What does it mean for something to be "more sensitive" than something else. We will use a somewhat simplified description of the U.S. Department of Defense (DoD) definitions of levels of security as an example. It is a reasonably general model and similar to what is done in other contexts. It is sufficient to understand the security mechanisms we'll describe.

The security label of something consists of two components:

A security level which might be an integer in some range, but in the U.S. DoD consists of one of the four ratings unclassified, confidential, secret and top secret, where unclassified

< confidential
< secret
< top secret.

A set of zero or more categories (also known as compartments) which describe the kind of information which is applicable. For instance the name CRYPTO might mean information about cryptographic algorithms, INTEL might mean information about military intelligence, COMSEC might mean information about communications security, or NUCLEAR might mean information about types of families.

Documents (or computer files) are marked with a security label saying how sensitive the information is, and people are issued security clearances according to how trustworthy they are perceived to be and for which they have demonstrated a "need to know".

A clearance might therefore be (SECRET;{COMSEC,CRYPTO}), which would mean someone was allowed to know information classified unclassified, confidential or secret (but not top secret) dealing with cryptographic algorithms or communications security. Given two security labels, (X, S1) and (Y, S2 ), (X, S1) is defined as being "at least as sensitive as" (Y, S2 ) iff X ³ Y and S2 Í S1.
For example
(TOP SECRET, {CRYPTO, COMSEC}) > (SECRET, {CRYPTO})
where > means more sensitive than.

It is possible for two labels to be incomparable, in the sense that neither is more sensitive than the other.
For example, neither of the following are comparable to each other:
(TOP SECRET, {CRYPTO, COMSEC})
(SECRET, {NUCLEAR, CRYPTO})

1.10.3. Mandatory Access Control Rules

Every person, process, and piece of information has a security label. A person cannot run a process with a label higher than the person's label, but may run one with a lower label. Information is only allowed to be read by a process that has at least as high a rating as the information. The terminology used for having a process read something with a higher rating than the process is read-up. Read-up is illegal and must be prevented. A process cannot write a piece of information with a rating lower than the process's rating.

The terminology used for a process writing something with a lower rating than the process is write-down. Write-down is illegal and must be prevented.

The rules are a human can only run a process which has a security label below or equal to that of the human's label

A process can only read information marked with a security label below or equal to that of the process

A process can only write information marked with a security label above or equal to that of the process. Note that if a process writes information marked with a security label above that of the process, the process can't subsequently read that information.

The prevention of read-up and write-down is the central idea behind mandatory access controls. The concepts of confinement within a security perimeter, and a generalized hierarchy of security classes was given a mathematical basis by Bell and La Padula in 1973 . There is significant complexity associated with the details of actually making them work.

1.10.4. Covert Channels

A covert channel is a method for a Trojan horse to circumvent the automatic prevention of information outside a security domain. Let's assume an operating system has enforced the rules in the previous section. Let's assume also that a bad guy has successfully tricked someone inside a security perimeter into running a program with a Trojan horse. The program has access to some sensitive data, and wants to pass the data to a process outside the security perimeter. We're assuming the operating system prevents the process from doing this straightforwardly, but there are diabolical methods that theoretically could be employed to get information out. These are known as covert channels.

The Trojan horse program cannot directly pass data, but all it needs is for there to be anything it can do that can be detected by something outside the security perimeter. As long as information can be passed one bit at a time, anything can be transmitted, given enough time.

One possible covert channel is a timing channel. The Trojan horse program alternately loops and waits, in cycles of, say 1 minute per bit. When the next bit is a 1, the program loops for one minute. When the next bit is a 0, the program waits for a minute. The program outside the perimeter constantly tests the loading of the system. If the system is sluggish, its conspirator inside the perimeter is looping, and therefore transmitting a 1. Otherwise the conspirator is waiting, and therefore transmitting a 0.

This assumes those two processes are the only ones running on the machine. What happens if there are other processes running and stopping at seemingly random times (from the point of view of the program trying to read the covert channel). That introduces noise into the channel. But communications people can deal with a noisy channel. It just lowers the potential bandwidth, depending on the signal to noise ratio.

Another example of a covert channel involves the use of shared resources other than CPU. For instance, suppose there were a queue of finite size, say the print queue. The Trojan horse program could fill the queue to transmit a 1, and delete some jobs to transmit a 0. The covert channel reader would attempt to print something and note whether the request was accepted. Other possible shared resources that might be exploited for passing information include physical memory, disk space, and I/O buffers. Yet another example depends on how clever the operating system is about not divulging information in error messages. For instance, suppose the operating system says file does not exist when a file really does not exist, but says insufficient privilege for requested operation when the file does exist, but inside a security perimeter off limits to the process requesting to read the file. Then the Trojan horse can alternately create and delete a file of some name known to the other process. The conspirator process periodically attempts to read the file and uses the information about which error message it gets to determine the setting of the next bit of information.

There is no general way to prevent all covert channels. Instead, people imagine all the different ways they can think of, and specifically attempt to plug those holes. For instance, the timing channel can be eliminated by giving each security perimeter a fixed percentage of the CPU. This is wasteful, and impractical in general because there can be an immense number of distinct classifications (in our model of (one of four levels, {categories}), the number of possible security perimeters is 4 2n, where n is the number of categories.

Most covert channels are very low bandwidth. In many cases, instead of attempting to eliminate a covert channel, it is more practical to introduce enough noise into the system so that the bandwidth becomes too low to be useful to an enemy. It's also possible to look for jobs that appear to be attempting to exploit covert channels (a job that alternately submitted enough print jobs to fill the queue and then deleted them would be suspicious indeed if someone knew to watch). If the bandwidth is low and the secret data is large, and knowing only a small subset of the secret data is not of much use to an enemy, the threat is minimized.

How much secret data must be leaked before serious damage is done can vary considerably. For example, assume there is a file with 100 megabytes of secret data. The file has been transmitted, encrypted, on an insecure network. The enemy therefore has the ciphertext, but the cryptographic algorithm used makes it impossible for the enemy to decrypt the data without knowing the key. A Trojan horse with access to the file and a covert channel with a bandwidth of 1 bit every 10 seconds would require 250 years to leak the data (by which time it's hard to believe the divulging of the information could be damaging to anyone).

However, if the Trojan horse had access to the 56 bit key, it could leak that information across the covert channel in less than 10 minutes. That information would allow the enemy to decrypt the 100 megabyte file. For this reason, many secure systems go to great pains to keep cryptographic keys out of the hands of the programs that use them.

1.10.5. The Orange Book

The National Computer Security Center (NCSC) (an agency of the U.S. Government) has published an official standard called "Trusted Computer System Evaluation Criteria", universally known as the Orange Book" (guess what color the cover was). The Orange Book defines a series of ratings that a computer system can have based on its security features and the care that went into its design. This rating system is intended to give government agencies and commercial enterprises an objective assessment of a system's security and to goad computer manufacturers into placing more emphasis on security. The official categories are D, C1, C2, B1, B2, B3, and A1, which range from least secure to most secure.

In reality, of course, there is no way to place all the possible features in a linear scale. Different threats are more or less important in different environments. The authors of the Orange Book made an attempt to linearize these concerns given their priorities. But the results can be misleading. An otherwise A1 system that is missing some single feature might have a D rating. Systems not designed with the Orange book in mind are likely to get low rating even if they are in fact very secure.

The other problem with the Orange book rating scheme is that the designers focused on the security priorities of military security people. They focused on keeping data secret. In the commercial world, data integrity is at least as important as data confidentiality. Mandatory access controls, even if available, are not suitable for most commercial environments because they make the simplest operations incredibly cumbersome, for example having a highly privileged user send mail to an unprivileged user.

With the orange book ratings, high ratings will not protect the system from infection by viruses. The fancy mandatory access controls required for high ratings allow write-up, so if some unprivileged account became infected by having someone carelessly run, say, a game program loaded from a bulletin board, the virus could infect more secure areas. Ironically, if it was a very secure area that first got infected, the mandatory access control features would prevent the infection from spreading to the less secure environments.

The following is a summary of what properties a system must have to quality for each rating.

D Minimal Protection. Actually, this simply means the system did not qualify for any of the higher ratings; it might actually be very secure. No system is ever going to brag about the fact that it was awarded a D rating.

C1 Discretionary Security Protection. The requirements at this level correspond roughly to what one might expect from a classic time sharing system. It requires:

The operating system must prevent unprivileged user programs from overwriting critical portions of its memory. (note that most PC operating systems do not satisfy this condition).

Resources must be protected with access controls. Those access controls need not be sophisticated; classic owner/group/world controls would be sufficient.

The system must authenticate users by a password or some similar mechanism and the password database must be protected so that it cannot be accessed by unauthorized users.

There are additional requirements around testing and documentation, which become more detailed at each successive rating.

C2 Controlled Access Protection. This level corresponds roughly to a time sharing system where security is an important concern, but where users are responsible for their own fates; an example might be a commercial time sharing system. The additional requirements (over those required for C1) for a C2 rating are:

Access Control at a per user granularity: it must be possible to permit access to any selected subset of the user community, probably via ACLs. An ACL is a datastructure attached to a resource that specifies the resource's authorized users.

Clearing of allocated memory: the operating system must assure that freshly allocated disk space and memory does not contain "left over" data deleted by some previous user. It can do that by writing the space or by requiring processes to write to the space before they can read it.

Auditing: the operating system must be capable of recording security relevant events including authentication and object access. The audit log must be protected from tampering and must record date, time, user, object, and event. Auditing must be selective based on user and object.

It is reasonable to expect that C2 rateable systems will become ubiquitous, since they contain features that are commonly desired and do not represent an unacceptable overhead. It is somewhat surprising that such systems are not the norm.

B1 Labeled Security Protection. Additional requirements at this level are essentially those required to implement Mandatory Access Controls for secrecy (not integrity) except that little attention is given to covert channels. Requirements for B1 above those for C2 include:

Security Labels: Sensitivity labels must be maintained for all users, processes, and files, and read- up and write-down must be prevented by the operating system.

Attached devices must either themselves be labelled as accepting only a single level of information or they must accept and know how to process security labels.

Attached printers must have a mechanism for assuring that there is a human readable sensitivity label printed on the top and bottom of each page corresponding to the sensitivity label of the information being printed. The operating system must enforce this correspondence. B2 Structured Protection. Beyond B1, there are few new features introduced; rather, the operating system must be structured to greater levels of assurance that it behaves correctly (i.e. has no bugs).

Additional requirements for B2 include:

Trusted Path to User-there must be some mechanism to allow a user at a terminal to reliably distinguish between talking to the legitimate operating system and talking to a trojan horse password- capturing program.

Security Level changes-a terminal user must be notified when any process started by that user changes its security level.

Security Kernel-the operating system must be structured so that only a minimal portion of it is security sensitive. i.e. that bugs in the bulk of the O/S cannot cause sensitive data to leak. This is typically done by running the bulk of the O/S in the processor's user mode and having a secure kernel mini-operating system which enforces the mandatory access controls.

Covert channels must be identified and their bandwidth estimated, but there is no requirement that they be eliminated.

Strict procedures must be used in the maintenance of the security sensitive portion of the operating system. For instance, anyone modifying any portion must document what they changed, when they changed it, and why, and some set of other people should compare the updated section with the previous version.

B3 Security Domains. Additional requirements for B3 mostly involve greater assurance that the operating system will not have bugs that might allow something to circumvent mandatory access controls.

Additional requirements include:
ACLs must be able to explicitly deny access to named individuals even if they are members of groups that are otherwise allowed access. It is only at this level that ACLs must be able to separately enforce modes of access (i.e. read vs. write) to a file.

Active Audit-there must be mechanisms to detect selected audited events or thresholds of audited events and immediately trigger notification of a security administrator.

Secure Crashing-the system must assure that the crashing and restarting of the system introduces no security policy violations. A1 Verified Design. There are no additional features in an A1 system over a B3 system. Rather, there are formal procedures for the analysis of the design of the system and more rigorous controls on its implementation.

1.11. Legal Issues

The legal aspects of computer network security are fascinating, but the picture changes quickly and we are certainly not experts in law. One legal issue that affects the choice of security mechanisms is patents. The RSA public key algorithm (see 5.3 RSA) is patented, and the rights are licensed by RSADSI, a company that is not careless about collecting license fees where applicable. RSA was developed at MIT, and under the terms of MIT's funding at the time there are no license fees for U.S. government use. It is only patented in the U.S., so there are no license fees when used outside the U.S. and marketed by a non-U.S. company. At any rate, the patent on RSA runs out on September 20, 2000. A good time for a party.

The U.S. government is advocating a digital signature standard (see 5.5 Digital Signature Standard (DSS)). Although in most respects DSS is technically inferior to RSA, when first announced it was advertised that DSS would be freely licensable, i.e., it would not be necessary to reach agreement with RSADSI. But then the RSADSI people bought up the rights to a patent by Schnorr which was apparently close enough to DSS to cover it. (Technically it is a separate corporation, Public Key Partners (PKP), that bought the Schnorr patent and some others, but there are many of the same people involved in both organizations.)

So at this point PKP claimed that it owned rights to DSS as well, and DSS would no longer be freely licensable. The government had patented DSS, and after PKP pointed out that DSS infringed on PKP-held patents, lawsuits loomed, and the situation is still murky.

I don't know what you mean by your way, said the Queen: all the ways about here belong to me

Through the Looking Glass

The relevant patents are: Diffie-Hellman: Patent #4,200,770, issued 1980, expires on April 29, 1997. This covers the Diffie-Hellman key exchange described in 5.4 Diffie-Hellman. Hellman-Merkle: Patent #4,218,582, issued 1980, expires on August 19, 1997. This is claimed to cover all public key systems. There is some controversy over whether this patent should be valid.

The specific public key mechanisms described in the patent (" knapsack systems) were subsequently broken. Rivest-Shamir- Adleman: Patent #4,405,829, issued 1983, expires on September 20, 2000. This covers the RSA algorithm described in 5.3 RSA. Hellman-Pohlig: Patent #4,424,414, issued 1984, expires on January 3, 2001. This is related to the Diffie-Hellman key exchange. Schnorr: Patent #4,995,082, issued 1991, expires on February 19, 2008. This is what the DSS algorithm is directly based upon. Kravitz: Patent #5,231,668, issued 1993, expires on July 27, 2008. This is the actual DSS algorithm.

Another issue is export controls. The U.S. government considers encryption to be a dangerous technology, like germ warfare and nuclear weapons. If a U.S. corporation would like to sell to other countries (and the proceeds are not going to be funding the Contras), they need export approval. The export control laws around encryption are not clear, and their interpretation changes over time. The general principal is that the U.S. government does not want you to give out technology that would make it more difficult for them to spy. Sometimes companies get so discouraged that they leave encryption out of their products altogether. Sometimes they generate products that, when sold overseas, have the encryption mechanisms removed, with the ability for the customers to buy encryption overseas and add it back in. It is usually possible to get export approval for encryption if the key lengths are short enough for the government to brute-force check all possible keys to decrypt a message. So sometimes companies just use short keys, or sometimes they have the capability of varying the key length, and they fix the key length to be shorter when a system is sold outside the U.S. Another potential legal issue is whether the U.S. government might declare encryption illegal, even within the U.S. The Clipper proposal is an attempt to promulgate good enough encryption that the government can easily break (with a court order). Although the government claims there are no plans for making encryption of data inside the U.S. illegal, some people suspect that the only way Clipper can really be successful (i.e., that's the encryption system drug cartels and child pornography rings will be using) is if other uses of encryption are outlawed.

Table of Contents

Chapter 1 Introduction

1.1 Opinions, Products

1.2 Roadmap to the Book

1.3 Terminology

1.4 Notation

1.5 Cryptographically Protected Sessions

1.6 Active and Passive Attacks

1.7 Legal Issues

    1.7.1 Patents

    1.7.2 Government Regulations

1.8 Some Network Basics

    1.8.1 Network Layers

    1.8.2 TCP and UDP Ports

    1.8.3 DNS (Domain Name System)

    1.8.4 HTTP and URLs

    1.8.5 Web Cookies

1.9 Names for Humans

1.10 Authentication and Authorization

    1.10.1 ACL (Access Control List)

    1.10.2 Central Administration/Capabilities

    1.10.3 Groups

    1.10.4 Cross-Organizational and Nested Groups

    1.10.5 Roles

1.11 Malware: Viruses, Worms, Trojan Horses

    1.11.1 Where Does Malware Come From?

    1.11.2 Virus Checkers

1.12 Security Gateway

    1.12.1 Firewall

    1.12.2 Application-Level Gateway/Proxy

    1.12.3 Secure Tunnels

    1.12.4 Why Firewalls Don't Work

1.13 Denial-of-Service (DoS) Attacks

1.14 NAT (Network Address Translation)

    1.14.1 Summary

Chapter 2 Introduction to Cryptography

2.1 Introduction

    2.1.1 The Fundamental Tenet of Cryptography

    2.1.2 Keys

    2.1.3 Computational Difficulty

    2.1.4 To Publish or Not to Publish

    2.1.5 Earliest Encryption

    2.1.6 One-Time Pad (OTP)

2.2 Secret Key Cryptography

    2.2.1 Transmitting Over an Insecure Channel

    2.2.2 Secure Storage on Insecure Media

    2.2.3 Authentication

    2.2.4 Integrity Check

2.3 Public Key Cryptography

    2.3.1 Transmitting Over an Insecure Channel

    2.3.2 Secure Storage on Insecure Media

    2.3.3 Authentication

    2.3.4 Digital Signatures

2.4 Hash Algorithms

    2.4.1 Password Hashing

    2.4.2 Message Integrity

    2.4.3 Message Fingerprint

    2.4.4 Efficient Digital Signatures

2.5 Breaking an Encryption Scheme

    2.5.1 Ciphertext Only

    2.5.2 Known Plaintext

    2.5.3 Chosen Plaintext

    2.5.4 Chosen Ciphertext

    2.5.5 Side-Channel Attacks

2.6 Random Numbers

    2.6.1 Gathering Entropy

    2.6.2 Generating Random Seeds

    2.6.3 Calculating a Pseudorandom Stream from the Seed

    2.6.4 Periodic Reseeding

    2.6.5 Types of Random Numbers

    2.6.6 Noteworthy Mistakes

2.7 Numbers

    2.7.1 Finite Fields

    2.7.2 Exponentiation

    2.7.3 Avoiding a Side-Channel Attack

    2.7.4 Types of Elements used in Cryptography

    2.7.5 Euclidean Algorithm

    2.7.6 Chinese Remainder Theorem

2.8 Homework

Chapter 3 Secret Key Cryptography

3.1 Introduction

3.2 Generic Block Cipher Issues

    3.2.1 Blocksize, Keysize

    3.2.2 Completely General Mapping

    3.2.3 Looking Random

3.3 Constructing a Practical Block Cipher

    3.3.1 Per-Round Keys

    3.3.2 S-boxes and Bit Shuffles

    3.3.3 Feistel Ciphers

3.4 Choosing Constants

3.5 Data Encryption Standard (DES)

    3.5.1 DES Overview

    3.5.2 The Mangler Function

    3.5.3 Undesirable Symmetries

    3.5.4 What's So Special About DES?

3.6 3DES (Multiple Encryption DES)

    3.6.1 How Many Encryptions?

    3.6.1.1 Encrypting Twice with the Same Key

    3.6.1.2 Encrypting Twice with Two Keys

    3.6.1.3 Triple Encryption with Only Two Keys

3.6.2 Why EDE Rather Than EEE?

3.7 Advanced Encryption Standard (AES)

    3.7.1 Origins of AES

    3.7.2 Broad Overview

    3.7.3 AES Overview

    3.7.4 Key Expansion

    3.7.5 Inverse Rounds

    3.7.6 Software Implementations of AES

3.8 RC4

3.9 Homework

Chapter 4 Modes of Operation

4.1 Introduction

4.2 Encrypting a Large Message

    4.2.1 ECB (Electronic Code Book)

    4.2.2 CBC (Cipher Block Chaining)

        4.2.2.1 Randomized ECB

        4.2.2.2 CBC

        4.2.2.3 CBC Threat—Modifying Ciphertext Blocks

    4.2.3 CTR (Counter Mode)

        4.2.3.1 Choosing IVs for CTR Mode

    4.2.4 XEX (XOR Encrypt XOR)

    4.2.5 XTS (XEX with Ciphertext Stealing)

4.3 Generating MACs

    4.3.1 CBC-MAC

        4.3.1.1 CBC Forgery Attack

    4.3.2 CMAC

    4.3.3 GMAC

        4.3.3.1 GHASH

        4.3.3.2 Transforming GHASH into GMAC

4.4 Ensuring Privacy and Integrity Together

    4.4.1 CCM (Counter with CBC-MAC)

    4.4.2 GCM (Galois/Counter Mode)

4.5 Performance Issues

4.6 Homework

Chapter 5 Cryptographic Hashes

5.1 Introduction

5.2 The Birthday Problem

5.3 A Brief History of Hash Functions

5.4 Nifty Things to Do with a Hash

    5.4.1 Digital Signatures

    5.4.2 Password Database

    5.4.3 Secure Shorthand of Larger Piece of Data

    5.4.4 Hash Chains

    5.4.5 Blockchain

    5.4.6 Puzzles

    5.4.7 Bit Commitment

    5.4.8 Hash Trees

    5.4.9 Authentication

    5.4.10 Computing a MAC with a Hash

    5.4.11 HMAC

    5.4.12 Encryption with a Secret and a Hash Algorithm

5.5 Creating a Hash Using a Block Cipher

5.6 Construction of Hash Functions

    5.6.1 Construction of MD4, MD5, SHA-1 and SHA-2

    5.6.2 Construction of SHA-3

5.7 Padding

    5.7.1 MD4, MD5, SHA-1, and SHA2-256 Message Padding

    5.7.2 SHA-3 Padding Rule

5.8 The Internal Encryption Algorithms

    5.8.1 SHA-1 Internal Encryption Algorithm

    5.8.2 SHA-2 Internal Encryption Algorithm

5.9 SHA-3 f Function (Also Known as KECCAK-f)

5.10 Homework

Chapter 6 First-Generation Public Key Algorithms

6.1 Introduction

6.2 Modular Arithmetic

    6.2.1 Modular Addition

    6.2.2 Modular Multiplication

    6.2.3 Modular Exponentiation

    6.2.4 Fermat's Theorem and Euler's Theorem

6.3 RSA

    6.3.1 RSA Algorithm

    6.3.2 Why Does RSA Work?

    6.3.3 Why Is RSA Secure?

    6.3.4 How Efficient Are the RSA Operations?

        6.3.4.1 Exponentiating with Big Numbers

        6.3.4.2 Generating RSA Keys

        6.3.4.3 Why a Non-Prime Has Multiple Square Roots of One

        6.3.4.4 Having a Small Constant e

        6.3.4.5 Optimizing RSA Private Key Operations

    6.3.5 Arcane RSA Threats

        6.3.5.1 Smooth Numbers

        6.3.5.2 The Cube Root Problem

    6.3.6 Public-Key Cryptography Standard (PKCS)

        6.3.6.1 Encryption

        6.3.6.2 The Million-Message Attack

        6.3.6.3 Signing

6.4 Diffie-Hellman

    6.4.1 MITM (Meddler-in-the-Middle) Attack

    6.4.2 Defenses Against MITM Attack

    6.4.3 Safe Primes and the Small-Subgroup Attack

    6.4.4 ElGamal Signatures

6.5 Digital Signature Algorithm (DSA)

    6.5.1 The DSA Algorithm

    6.5.2 Why Is This Secure?

    6.5.3 Per-Message Secret Number

6.6 How Secure Are RSA and Diffie-Hellman?

6.7 Elliptic Curve Cryptography (ECC)

    6.7.1 Elliptic Curve Diffie-Hellman (ECDH)

    6.7.2 Elliptic Curve Digital Signature Algorithm (ECDSA)

6.8 Homework

Chapter 7 Quantum Computing

7.1 What Is a Quantum Computer?

    7.1.1 A Preview of the Conclusions

    7.1.2 First, What Is a Classical Computer?

    7.1.3 Qubits and Superposition

        7.1.3.1 Example of a Qubit

        7.1.3.2 Multi-Qubit States and Entanglement

    7.1.4 States and Gates as Vectors and Matrices

    7.1.5 Becoming Superposed and Entangled

    7.1.6 Linearity

        7.1.6.1 No Cloning Theorem

    7.1.7 Operating on Entangled Qubits

    7.1.8 Unitarity

    7.1.9 Doing Irreversible Operations by Measurement

    7.1.10 Making Irreversible Classical Operations Reversible

    7.1.11 Universal Gate Sets

7.2 Grover's Algorithm

    7.2.1 Geometric Description

    7.2.2 How to Negate the Amplitude of |k⟩

    7.2.3 How to Reflect All the Amplitudes Across the Mean

    7.2.4 Parallelizing Grover's Algorithm

7.3 Shor's Algorithm

    7.3.1 Why Exponentiation mod n Is a Periodic Function

    7.3.2 How Finding the Period of ax mod n Lets You Factor n

    7.3.3 Overview of Shor's Algorithm

    7.3.4 Converting to the Frequency Graph—Introduction

    7.3.5 The Mechanics of Converting to the Frequency Graph

    7.3.6 Calculating the Period

    7.3.7 Quantum Fourier Transform

7.4 Quantum Key Distribution (QKD)

    7.4.1 Why It's Sometimes Called Quantum Encryption

    7.4.2 Is Quantum Key Distribution Important?

7.5 How Hard Are Quantum Computers to Build?

7.6 Quantum Error Correction

7.7 Homework

Chapter 8 Post-Quantum Cryptography

8.1 Signature and/or Encryption Schemes

    8.1.1 NIST Criteria for Security Levels

    8.1.2 Authentication

    8.1.3 Defense Against Dishonest Ciphertext

8.2 Hash-based Signatures

    8.2.1 Simplest Scheme – Signing a Single Bit

    8.2.2 Signing an Arbitrary-sized Message

    8.2.3 Signing Lots of Messages

    8.2.4 Deterministic Tree Generation

    8.2.5 Short Hashes

    8.2.6 Hash Chains

    8.2.7 Standardized Schemes

        8.2.7.1 Stateless Schemes

8.3 Lattice-Based Cryptography

    8.3.1 A Lattice Problem

    8.3.2 Optimization: Matrices with Structure

    8.3.3 NTRU-Encryption Family of Lattice Encryption Schemes

        8.3.3.1 Bob Computes a (Public, Private) Key Pair

        8.3.3.2 How Bob Decrypts to Find m

        8.3.3.3 How Does this Relate to Lattices?

    8.3.4 Lattice-Based Signatures

        8.3.4.1 Basic Idea

        8.3.4.2 Insecure Scheme

        8.3.4.3 Fixing the Scheme

    8.3.5 Learning with Errors (LWE)

        8.3.5.1 LWE Optimizations

        8.3.5.2 LWE-based NIST Submissions

8.4 Code-based Schemes

    8.4.1 Non-cryptographic Error-correcting Codes

        8.4.1.1 Invention Step

        8.4.1.2 Codeword Creation Step

        8.4.1.3 Misfortune Step

        8.4.1.4 Diagnosis Step

    8.4.2 The Parity-Check Matrix

    8.4.3 Cryptographic Public Key Code-based Scheme

        8.4.3.1 Neiderreiter Optimization

        8.4.3.2 Generating a Public Key Pair

        8.4.3.3 Using Circulant Matrices

8.5 Multivariate Cryptography

    8.5.1 Solving Linear Equations

    8.5.2 Quadratic Polynomials

    8.5.3 Polynomial Systems

    8.5.4 Multivariate Signature Systems

        8.5.4.1 Multivariate Public Key Signatures

8.6 Homework

Chapter 9 Authentication of People

9.1 Password-based Authentication

    9.1.1 Challenge-Response Based on Password

    9.1.2 Verifying Passwords

9.2 Address-based Authentication

    9.2.1 Network Address Impersonation

9.3 Biometrics

9.4 Cryptographic Authentication Protocols

9.5 Who Is Being Authenticated?

9.6 Passwords as Cryptographic Keys

9.7 On-Line Password Guessing

9.8 Off-Line Password Guessing

9.9 Using the Same Password in Multiple Places

9.10 Requiring Frequent Password Changes

9.11 Tricking Users into Divulging Passwords

9.12 Lamport's Hash

9.13 Password Managers

9.14 Web Cookies

9.15 Identity Providers (IDPs)

9.16 Authentication Tokens

    9.16.1 Disconnected Tokens

    9.16.2 Public Key Tokens

9.17 Strong Password Protocols

    9.17.1 Subtle Details

    9.17.2 Augmented Strong Password Protocols

    9.17.3 SRP (Secure Remote Password)

9.18 Credentials Download Protocols

9.19 Homework

Chapter 10 Trusted Intermediaries

10.1 Introduction

10.2 Functional Comparison

10.3 Kerberos

    10.3.1 KDC Introduces Alice to Bob

    10.3.2 Alice Contacts Bob

    10.3.3 Ticket Granting Ticket (TGT)

    10.3.4 Interrealm Authentication

    10.3.5 Making Password-Guessing Attacks Difficult

    10.3.6 Double TGT Protocol

    10.3.7 Authorization Information

    10.3.8 Delegation

10.4 PKI

    10.4.1 Some Terminology

    10.4.2 Names in Certificates

10.5 Website Gets a DNS Name and Certificate

10.6 PKI Trust Models

    10.6.1 Monopoly Model

    10.6.2 Monopoly plus Registration Authorities (RAs)

    10.6.3 Delegated CAs

    10.6.4 Oligarchy

    10.6.5 Anarchy Model

    10.6.6 Name Constraints

    10.6.7 Top-Down with Name Constraints

    10.6.8 Multiple CAs for Any Namespace Node

    10.6.9 Bottom-Up with Name Constraints

        10.6.9.1 Functionality of Up-Links

        10.6.9.2 Functionality of Cross-Links

    10.6.10 Name Constraints in PKIX Certificates

10.7 Building Certificate Chains

10.8 Revocation

    10.8.1 CRL (Certificate Revocation list

    10.8.2 Online Certificate Status Protocol (OCSP)

    10.8.3 Good-Lists vs. Bad-Lists

10.9 Other Information in a PKIX Certificate

10.10 Issues with Expired Certificates

10.11 DNSSEC (DNS Security Extensions)

10.12 Homework

Chapter 11 Communication Session Establishment

11.1 One-way Authentication of Alice

    11.1.1 Timestamps vs. Challenges

    11.1.2 One-Way Authentication of Alice using a Public Key

11.2 Mutual Authentication

    11.2.1 Reflection Attack

    11.2.2 Timestamps for Mutual Authentication

11.3 Integrity/Encryption for Data

    11.3.1 Session Key Based on Shared Secret Credentials

    11.3.2 Session Key Based on Public Key Credentials

    11.3.3 Session Key Based on One-Party Public Keys

11.4 Nonce Types

11.5 Intentional MITM

11.6 Detecting MITM

11.7 What Layer?

11.8 Perfect Forward Secrecy

11.9 Preventing Forged Source Addresses

    11.9.1 Allowing Bob to Be Stateless in TCP

    11.9.2 Allowing Bob to Be Stateless in IPsec

11.10 Endpoint Identifier Hiding

11.11 Live Partner Reassurance

11.12 Arranging for Parallel Computation

11.13 Session Resumption/Multiple Sessions

11.14 Plausible Deniability

11.15 Negotiating Crypto Parameters

    11.15.1 Suites vs. à la Carte

    11.15.2 Downgrade Attack

11.16 Homework

Chapter 12 IPsec

12.1 IPsec Security Associations

    12.1.1 Security Association Database

    12.1.2 Security Policy Database

    12.1.3 IKE-SAs and Child-SAs

12.2 IKE (Internet Key Exchange Protocol)

12.3 Creating a Child-SA

12.4 AH and ESP

    12.4.1 ESP Integrity Protection

    12.4.2 Why Protect the IP Header?

    12.4.3 Tunnel, Transport Mode

    12.4.4 IPv4 Header

    12.4.5 IPv6 Header

12.5 AH (Authentication Header)

12.6 ESP (Encapsulating Security Payload)

12.7 Comparison of Encodings

12.8 Homework

Chapter 13 SSL/TLS and SSH

13.1 Using TCP

13.2 StartTLS

13.3 Functions in the TLS Handshake

13.4 TLS 1.2 (and Earlier) Basic Protocol

13.5 TLS 1.3

13.6 Session Resumption

13.7 PKI as Deployed by TLS

13.8 SSH (Secure Shell)

    13.8.1 SSH Authentication

    13.8.2 SSH Port Forwarding

13.9 Homework

Chapter 14 Electronic Mail Security

14.1 Distribution Lists

14.2 Store and Forward

14.3 Disguising Binary as Text

14.4 HTML-Formatted Email

14.5 Attachments

14.6 Non-cryptographic Security Features

    14.6.1 Spam Defenses

14.7 Malicious Links in Email

14.8 Data Loss Prevention (DLP)

14.9 Knowing Bob's Email Address

14.10 Self-Destruct, Do-Not-Forward,

14.11 Preventing Spoofing of From Field

14.12 In-Flight Encryption

14.13 End-to-End Signed and Encrypted Email

14.14 Encryption by a Server

14.15 Message Integrity

14.16 Non-Repudiation

14.17 Plausible Deniability

14.18 Message Flow Confidentiality

14.19 Anonymity

14.20 Homework

Chapter 15 Electronic Money

15.1 ECASH

15.2 Offline eCash

    15.2.1 Practical Attacks

15.3 Bitcoin

    15.3.1 Transactions

    15.3.2 Bitcoin Addresses

    15.3.3 Blockchain

    15.3.4 The Ledger

    15.3.5 Mining

    15.3.6 Blockchain Forks

    15.3.7 Why Is Bitcoin So Energy-Intensive?

    15.3.8 Integrity Checks: Proof of Work vs. Digital Signatures

    15.3.9 Concerns

15.4 Wallets for Electronic Currency

15.5 Homework

Chapter 16 Cryptographic Tricks

16.1 Secret Sharing

16.2 Blind Signature

16.3 Blind Decryption

16.4 Zero-Knowledge Proofs

    16.4.1 Graph Isomorphism ZKP

    16.4.2 Proving Knowledge of a Square Root

    16.4.3 Noninteractive ZKP

16.5 Group Signatures

    16.5.1 Trivial Group Signature Schemes

        16.5.1.1 Single Shared Key

        16.5.1.2 Group Membership Certificate

        16.5.1.3 Multiple Group Membership Certificates

        16.5.1.4 Blindly Signed Multiple Group Membership Certificates

    16.5.2 Ring Signatures

    16.5.3 DAA (Direct Anonymous Attestation)

    16.5.4 EPID (Enhanced Privacy ID)

16.6 Circuit Model

16.7 Secure Multiparty Computation (MPC)

16.8 Fully Homomorphic Encryption (FHE)

    16.8.1 Bootstrapping

    16.8.2 Easy-to-Understand Scheme

16.9 Homework

Chapter 17 Folklore

17.1 Misconceptions

17.2 Perfect Forward Secrecy

17.3 Change Encryption Keys Periodically

17.4 Don't Encrypt without Integrity Protection

17.5 Multiplexing Flows over One Secure Session

    17.5.1 The Splicing Attack

    17.5.2 Service Classes

    17.5.3 Different Cryptographic Algorithms

17.6 Using Different Secret Keys

    17.6.1 For Initiator and Responder in Handshake

    17.6.2 For Encryption and Integrity

    17.6.3 In Each Direction of a Secure Session

17.7 Using Different Public Keys

    17.7.1 Use Different Keys for Different Purposes

    17.7.2 Different Keys for Signing and Encryption

17.8 Establishing Session Keys

    17.8.1 Have Both Sides Contribute to the Master Key

    17.8.2 Don't Let One Side Determine the Key

17.9 Hash in a Constant When Hashing a Password

17.10 HMAC Rather than Simple Keyed Hash

17.11 Key Derivation

17.12 Use of Nonces in Protocols

17.13 Creating an Unpredictable Nonce

17.14 Compression

17.15 Minimal vs. Redundant Designs

17.16 Overestimate the Size of Key

17.17 Hardware Random Number Generators

17.18 Put Checksums at the End of Data

17.19 Forward Compatibility

    17.19.1 Options

    17.19.2 Version Numbers

        17.19.2.1 Version Number Field Must Not Move

        17.19.2.2 Negotiating Highest Version Supported

        17.19.2.3 Minor Version Number Field

Glossary

Math

M.1 Introduction

M.2 Some definitions and notation

M.3 Arithmetic

M.4 Abstract Algebra

M.5 Modular Arithmetic

    M.5.1 How Do Computers Do Arithmetic?

    M.5.2 Computing Inverses in Modular Arithmetic

        M.5.2.1 The Euclidean Algorithm

        M.5.2.2 The Chinese Remainder Theorem

    M.5.3 How Fast Can We Do Arithmetic?

M.6 Groups

M.7 Fields

    M.7.1 Polynomials

    M.7.2 Finite Fields

        M.7.2.1 What Sizes Can Finite Fields Be?

        M.7.2.2 Representing a Field

M.8 Mathematics of Rijndael

    M.8.1 A Rijndael Round

M.9 Elliptic Curve Cryptography

M.10 Rings

M.11 Linear Transformations

M.12 Matrix Arithmetic

    M.12.1 Permutations

    M.12.2 Matrix Inverses

        M.12.2.1 Gaussian Elimination

M.13 Determinants

    M.13.1 Properties of Determinants

        M.13.1.1 Adjugate of a Matrix

    M.13.2 Proof: Determinant of Product is Product of Determinants

M.14 Homework

Bibliography

 

 

9780136643609   TOC    8/2/2022

 

Preface

PREFACE:It was a dark and stormy night. Somewhere in the distance a dog howled. A shiny object caught Alice's eye. A diamond cufflink! Only one person in the household could afford diamond cufflinks! So it was the butler, after all! Alice had to warn Bob. But how could she get a message to him without alerting the butler? If she phoned Bob, the butler might listen on an extension. If she sent a carrier pigeon out the window with the message taped to its feet, how would Bob know it was Alice that was sending the message and not Trudy attempting to frame the butler because he spurned her advances? That's what this book is about. Not much character development for Alice and Bob, we're afraid, nor do we really get to know the butler. But we do discuss how to communicate securely over an insecure medium.

What do we mean by communicating securely? Alice should be able to send a message to Bob that only Bob can understand, even though Alice can't avoid having others see what she sends. When Bob receives a message, he should be able to know for certain that it was Alice who sent the message, and that nobody tampered with the contents of the message in the time between when Alice launched the message and Bob received it.

What do we mean by an insecure medium? Well, in some dictionary or another, under the definition of "insecure medium" should be a picture of the Internet. The world is evolving towards interconnecting every computer, and people talk about connecting household appliances as well, all into some wonderful global internetwork. How wonderful! You'd be able to send electronic mail to anyone in the world.

You'd also be able to control yournuclearpower plant with simple commands sent across the network while you were vacationing in Fiji. Or sunny Libya. Or historic Iraq. Inside the network the world is scary. There are links that eavesdroppers can listen in on. Information needs to be forwarded through packet switches, and these switches can be reprogrammed to listen to or modify data in transit. The situation might seem hopeless, but we may yet be saved by the magic of mathematics, and in particular cryptography, which can take a message and transform it into a bunch of numbers known as ciphertext. The ciphertext is unintelligible gibberish except to someone who knows the secret to reversing the transformation. Cryptography allows us to disguise our data so that eavesdroppers gain no information from listening to the information as transmitted.

Cryptography also allows us to create an unforgeable message and protect it from being modified in transit. One method of accomplishing this is with a digital signature, a number associated with a message and its sender that can be verified as authentic by others, but can only be generated by the sender. This should seem astonishing. How can there be a number which you can verify but not generate? A person's handwritten signature can (more or less) only be generated by that person, though it can be verified by others. But it would seem as if a number shouldn't be hard to generate, especially if it can be verified. Theoretically you could generate someone's signature by trying lots of numbers and testing each one until one passed the verification test. But with the size of the numbers used, it would take too much compute time (for instance, several universe lifetimes) to generate the signature that way. So a digital signature has the same property as a handwritten signature, in that it can only be generated by one person. But a digital signature does more than a handwritten signature.

Since the digital signature depends on the contents of the message, if someone alters the message the signature will no longer be correct and the tampering will be detected. This will all become clear if you read Chapter 2 Introduction to Cryptography.

Cryptography is a major theme in this book, not because cryptography is intrinsically interesting (which it is), but because the security features people want in a computer network can best be provided through cryptography.

1.1. Roadmap to the Book The book is divided into three main sections.

Cryptography.

Chapter 2 Introduction to Cryptography is the only part of the cryptography section of the book essential for understanding the rest of the book, since it explains the generic properties of secret key, message digest, and public key algorithms, and how each is used. We've tried our best to make the descriptions of the actual cryptographic algorithms nonthreatening yet thorough, and to give intuition into why they work. It's intended to be readable by anyone, not just graduate students in mathematics. Never once do we use the term lemma. We do hope you read.

Chapter 3 Secret Key Cryptography, Chapter 4 Hashes and Message Digests, and Chapter 5 Public Key Algorithms which give the details of the popular standards, but it's also OK to skip them and save them for later, or just for reference. For you math types who would have noticed that we skipped a number if we didn't mention it, Chapter 6 Number Theory gives a deeper treatment of the mathematics behind the cryptography.

Authentication.

Chapter 7 Authentication Systems introduces the general issues involved in proving your identity across a network.

Chapter 8 Authentication of People deals with the special circumstances when the device proving its identity is a human being.

Chapter 9 Security Handshake Pitfalls deals with the details of authentication handshakes. There are many security flaws that keep getting designed into protocols. This chapter attempts to describe variations of authentication handshakes and their relative security and performance strengths. We end the chapter with a checklist of security attacks, so that someone designing a protocol can specifically check their protocol for these flaws.

Chapter 10 Kerberos V4 and Chapter 11 Kerberos V5 describe the details of those authentication systems. Secure electronic mail. Chapter 12 Electronic Mail Security describes the various types of security features one might want, and how they might be provided. Chapter 13 Privacy Enhanced Mail (PEM), Chapter 14 PGP (Pretty Good Privacy), and Chapter 15 X.400 describe three mail standards which are compared in Chapter 16 A Comparison of PEM, PGP, and X.400. There are two chapters that aren't in any of the three main sections. The first chapter (the one you're reading now) gives a whirlwind tour of computer networking and computer security to set the stage for the main focus of the book-computer network security. The final chapter, Chapter 17 More Security Systems, describes a variety of security systems, including Novell NetWare (Versions 3 and 4), Lotus Notes, DCE, KryptoKnight/NetSP, Clipper, SNMP, DASS/SPX, and sabotage-proof routing protocols.

1.2. What type of book is this?

We believe the reason most computer science is hard to understand is because of jargon and irrelevant details. When people work with something long enough they invent their own language, come up with some meta-architectural framework or other, and forget that the rest of the world doesn't talk or think that way. We intend this book to be reader-friendly. We try to extract the concepts and ignore the meta-architectural framework, since whatever a meta-architectural framework is, it's irrelevant to what something does and how it works.

We believe someone who is a relative novice to the field ought to be able to read this book. But readability doesn't mean "lack of technical depth". We try to go beyond the information one might find in specifications. The goal is not just to describe exactly how the various standards and de facto standards work, but to explain why they are the way they are, why some protocols designed for similar purposes are different, and the implications of the design decisions. Sometimes engineering tradeoffs were made.

Sometimes the designers could have made better choices (they are human after all), in which case we explain how the protocol could have been better. This analysis should make it easier to understand the current protocols, and aid in design of future protocols.

The primary audience for this book is engineers, especially those who might need to evaluate the security of or add security features to a distributed system, but the book is also intended to be useable as a textbook, either on the advanced undergraduate or graduate level. Most of the chapters have homework problems at the end.

1.3. Terminology

Any field with science in its name isn't.

Tony Lauck

Computer science is filled with ill-defined terminology used by different authors in conflicting ways, often by the same author in conflicting ways. We apologize in advance for probably being guilty sometimes ourselves. Some people take terminology very seriously, and once they start to use a certain word in a certain way, are extremely offended if the rest of the world does not follow.

When I use a word, it means just what I choose it to mean-neither more nor less.

Humpty Dumpty (in Through the Looking Glass)

Some terminology we feel fairly strongly about. We do not use the term hacker to describe the vandals that break into computer systems. These criminals call themselves hackers, and that is how they got the name. But they do not deserve the name. True hackers are master programmers, uncorruptably honest, unmotivated by money, and careful not to harm anyone. The criminals termed "hackers" are not brilliant and accomplished. It is really too bad that they not only steal money, people's time, and worse, but they've also stolen a beautiful word that had been used to describe some remarkable and wonderful people. We instead use words like intruder, bad guy, and impostor. When we need a name for a bad guy, we usually choose Trudy (since it sounds like intruder).

We grappled with the terms secret key and public key cryptography. Often in the security literature the terms symmetric and asymmetric are used instead of secret and public. We found the terms symmetric and asymmetric intimidating and sometimes confusing, so opted instead for secret key and public key. We occasionally regretted our decision to avoid the words symmetric and asymmetric when we found ourselves writing things like secret key based interchange keys rather than symmetric interchange keys.

We use the term privacy when referring to the desire to keep communication from being seen by anyone other than the intended recipients. Some people in the security community avoid the term privacy because they feel its meaning has been corrupted to mean "the right to know", because in some countries there are laws known as privacy laws, which states that citizens have the right to see records kept about themselves.

The security community also avoids the use of the word secrecy, because secret has special meaning within the military context, and they feel it would be confusing to talk about the secrecy of a message that was not actually labeled top secret or secret. The term which is most commonly used in the security community is confidentiality. We find that strange because confidential, like secret, is a security label and the security community should have scorned use of confidential, too. We chose not to use confidentiality because we felt it was too many syllables, and saw no reason not to use privacy.

Speaker: Isn't it terrifying that on the Internet we have no privacy?

Heckler1: You mean confidentiality. Get your terms straight.

Heckler2: Why do security types insist on inventing their own language?

Heckler3: It's a denial of service attack.

Overheard at recent gathering of security types

We often refer to things involved in a conversation by name, for instance, Alice and Bob, whether the things are people or computers. This is a convenient way of making things unambiguous with relatively few words, since the pronoun she can be used for Alice and he can be used for Bob. It also avoids lengthy inter- (and even intra-) author arguments about whether to use the politically incorrect he, a confusing she, an awkward he/she or (s)he, an ungrammatical they, an impersonal it, or an incredibly awkward rewriting to avoid the problem. We remain slightly worried that people will assume when we've named things with human names that we are referring to people. Assume Alice, Bob, and the rest of the gang may be computers unless we specifically say something like the user Alice, in which case we're talking about a human.

With a name like yours, you might be any shape, almost.

Humpty Dumpty (in Through the Looking Glass)

Occasionally, one of the three of us authors will want to make a personal comment. In that case we use I or me with a subscript. When it's a comment that we all agree with, or that we managed to slip past me3 (the rest of us are wimpier) we use the term we. We use the symbol (pronounced ex-or) for the bitwise exclusive or operation. We denote secret key encryption with curly brackets preceded by the key with which something was encrypted, as in K{message}, which means message is secret-key encrypted with K. Public key encryption we denote with curly braces, and the name of the owner of the public key subscripting the close brace, as in {message} Bob.

Signing (which means using the private key), we denote with square brackets, with the name of the owner of the key subscripting the close bracket, as in message Bob.

1.4. Primer on Networking

You have to know something about computer networks to understand computer network security, so we're including this primer. For a more detailed understanding, we recommend .

Networks today need to be very easy to use and configure. Networks are no longer an expensive and educational toy for researchers, but instead are being used by real people. Most sites with networks will not be able to hire a full time person with networking expertise to start and keep the network running.

1.4.1. OSI Reference Model
Somehow, a book about computer networks would seem incomplete without a picture of the OSI (Open Systems Interconnection) Reference Model, The OSI Reference model is useful because it gives some commonly used terminology, though it might mislead you into thinking that there is only one way to construct a network. The reference model was designed by an organization known as the International Standards Organization (ISO). ISO decided it would be a good idea to standardize computer networking. Since that was too big a task for a single committee, they decided to subdivide the problem among several committees. They somewhat arbitrarily chose seven, shown in the diagram above. The basic idea is that each layer uses the services of the layer below, adds functionality, and provides a service to the layer above. When you start looking at real networks, they seldom neatly fit into the seven-layer model, but for basic understanding of networking, the OSI Reference model is a good place to start.

1. physical layer. This layer delivers an unstructured stream of bits across a link or some sort.

2. data link layer. This layer delivers a piece of information across a single link. It organizes the physical layer's bits into packets and control who on a shared link gets each packet.

3. network layer. This layer computes paths across an interconnected mesh of links and packet switches, and forwards packets over multiple links from source to destination.

4. transport layer. This layer establishes a reliable communication stream between a pair of systems across a network by putting sequence numbers in packets, holding packets at the destination until they can be delivered in order, and retransmitting lost packets.

5. session layer. The OSI session layer adds extra functions to the reliable pair-wise communication provided by the transport layer. Most network architectures do not have or need the functionality in this layer, and it is not of concern to security, so for the purposes of this book we can ignore it.

6. presentation layer. This layer encodes application data into a nonical format.

7. application layer. This is where the applications, such as file transfer and electronic mail, reside. These are the applications that use the network. OSI tried to make all the world a layer by calling network users the top layer.

A layer communicates with the equivalent layer in a different node. In order to get data to a peer layer, though, the layer at the transmitting node gives the data to the layer below it (on the same node), which adds a header containing additional information if necessary, and that layer in turn gives it to the layer below. As the packet is received by the destination node, each layer reads and strips off its own header, so that the packet received by layer n looks to that layer just like it did when it was sent down to layer n-1 for transmission.

1.4.2. Directory Service

Having a telephone line into your house means you can access any phone in the world, if you know the telephone number. The same thing is true, more or less, in computer networks. If you know the network layer address of a node on the network, you should be able to communicate with that node. (This isn't always true because of security gateways, which we'll discuss in 1.6 Firewalls/Security Gateways). But how do you find out another nodeÕs network layer address? Network layer addresses are not the kind of things that people will be able to remember, or type. People instead will want to access something using a name such as File-Server-3.

This is a similar problem to finding someone's telephone number. Typically you start out by knowing the name of the person or service you want to talk to, and then look the name up in a telephone book. In a computer network there is a service known as the directory service, which stores information about a name, including its network layer address. Anything that needs to be found is listed in the directory service. Anything that needs to find something searches the directory service.

Rather than keeping all names in one directory, the directory service is typically structured as a tree of directories. Usually a name is hierarchical, so that the directory in which the name can be found is obvious from the name. For example, an internet name looks like [e-mail]. The top level consists of pointers to the directories com for commercial enterprises, edu for educational institutions, gov for U.S. government, and various country names. Under com, there are various company names. Having multiple directories rather than keeping all names in one directory serves two purposes. One is to prevent the directory from getting unreasonably large. The other reason is to reduce name collisions (more than one object with the same name). For instance, when you're looking up a telephone number for your friend John Smith, it's bad enough trying to figure out which John Smith is the one you want if you know which town he lives in and the telephone company has separate directories for each town, but imagine if the telephone company didn't have separate books for each town and simply had a list of names and telephone numbers!

Ideally, with a hierarchy of directories, name collisions could be prevented. Once a company hired one Radia Perlman, they just wouldn't hire another. I2 think that's reasonable, but someone with a name like John Smith might start having problems finding a company that could hire him.

Now why did you name your baby John? Every Tom, Dick, and Harry is named John.

Sam Goldwyn

For electronic mail addresses, conflicts must be prevented. Typically, companies let the first John Smith use the name John@companyname for his email address, and then perhaps the next one will be Smith@companyname, and the next one JSmith@companyname, and the next one has to start using middle initials. But for directories of names, there is usually no way to avoid name collisions within a directory. In other words, both John Smiths will use the same name within the company. Then, just like with a telephone book and multiple John Smiths, you have to do the best you can to figure out which one you want based on various attributes (such as in the telephone directory, using the street address). And just like in real life, there will be lots of confusion where one John Smith gets messages intended for a different John Smith.

The directory service is very important to security. It is assumed to be widely available and convenient to access otherwise large scale networking really is too inconvenient to be practical. The directory service is a convenient place to put information, such as a user's public cryptographic key. But the directory service, although convenient, is not likely to be very secure. An intruder might tamper with the information. The magic of cryptography will help us detect such tampering so that it will not be necessary to physically secure all locations that store directory service information. If the information is tampered with, it might prevent good guys from accessing the network, but it will not allow bad guys to access things they are not authorized to access.

1.4.3. Replicated Services

Sometimes it is convenient to have two or more computers performing the same function. One reason is performance. A single server might become overloaded, or might not be sufficiently close to all users on a large network. Another reason is availability. If the service is replicated, it does not matter if some of the replicas are down or unavailable. When someone wants to access the service provided, it doesn't matter which of the computers they reach. Often the fact that the service is replicated is transparent to the user, meaning that the user does not know whether thereÕs a single copy of the service or whether there are replicas.

What are the security issues with a replicated service? YouÕd want the user to have the same authentication information regardless of which replica was authenticating the user. If authentication information is stored at each replica, then coordinating the databases, for example after a change password command, can be tricky. And if the identical exchange will work with any of the replicas, then having an eavesdropper repeat the authentication handshake with a different replica might be a security problem.

1.4.4. Packet Switching

A really naive assumption would be that if people wanted computer A to talk to computer B, they'd string a wire between A and B. This doesn't work if networks get large, either in number of nodes (n2 wires) or physical distance (it takes a lot of wire to connect each of 10 000 nodes in North America with each of 10 000 nodes in Asia). So in a network, messages do not go directly from sender to recipient, but rather have to be forwarded by various computers along the way. These message forwarders are referred to as packet switches, routers, gateways, bridges, and probably lots of other names as well. A message is generally broken into smaller chunks as it is sent through the network. There are various reasons for this, all irrelevant for the purposes of this book, but we'll mention some of them anyway.

Messages from various sources can be interleaved on the same link. You wouldn't want your message to have to wait until someone else finished sending a huge message, so messages are sent a small chunk at a time. If the link is in the process of sending the huge message when your little single-chunk message arrives, your message only has to wait until the link finishes sending a single chunk of the large message.

Error recovery is done on the transmission unit. If you find out that one little chunk got mangled in transmission, only that chunk needs to be retransmitted.

Buffer management in the routers is simpler if the size of packets has a reasonable upper limit. Encryption and integrity protection is sometimes done end-to-end on the original message or hop-by-hop, on each chunk of the message.

1.4.5. Network Components

The network is a collection of packet switches (usually called routers) and links. A link can either be a wire between two computers or a multiaccess link such as a LAN (local area network). A multiaccess link has interesting security implications. Whatever is transmitted on the link can be seen by all the other nodes on that link. Multiaccess links with this property are Ethernet (also known as CSMA/CD), token rings, and packet radio networks.

Connected to the backbone of the network are various types of nodes. A common categorization of the nodes is into clients, which are workstations that allow humans to access the resources on the network, and servers, which are typically dedicated machines that provide services such as file storage and printing.

It should be possible to deploy a new service and have users be able to conveniently find the service. Users should be able to access the network from various locations, such as a public workstation a company makes available for visitors. If a person has a dedicated workstation located in one location, such as an office, it should be possible with a minimum of configuration for the user to plug the workstation into the network. Another method for users to access a network is through a dumb terminal. A dumb terminal is not a general purpose computer and does not have the compute power to do cryptographic operations.

Usually a dumb terminal hooks directly into a host machine, or hooks into a terminal server, which relays the terminal's keystrokes via a network protocol across the network to the host machine (the machine the user logs into).

1.4.6. Destinations: Ultimate and Intermediate

A network is something to which multiple systems can attach. We draw it as a cloud since from the point of view of the systems connected to it, exactly what goes on inside is not relevant. If you want to send a message to a system, and you are both connected to the same cloud, you hand your message to the cloud, together with a header that contains your address (the source address) and the address of the desired recipient (the destination address).

But how do you connect to the network? It might be with a point-to- point link to a packet switch inside the network, in which case things are reasonably simple. If A wants to send a message to B, A will put A as source address and B as destination address and send the message on the point to point link. But what if A is connected on a LAN? In that case, in order to transmit the packet across the LAN A has to specify which destination on that link should receive the message. For example:

If A wants to send a message to D it has to know (somehow-if you care you can read my2 book ???ref) that the appropriate neighbor on the LAN that will forward the packet is R2. So when A transmits the message there are two destinations: R2 as the next recipient and D as the ultimate recipient. A reasonably simple way of thinking about this is that the data link layer worries about transmission across a single link. The data link header has a source and destination address that indicate the transmitter on that link and the receiver on that link. The network layer worries about transmission across a multi-hop network. It has a header that carries the ultimate source and ultimate destination. The data link header is removed each time a message is received, and a new data link header is tacked onto the message when it is forwarded to the next hop. When A transmits the packet, the network header has source A, destination D. The data link header has source A, destination R2. R2 forwards the packet to R5. Since R2 is connected to R5 with a point-to-point link, the data link header will not have addresses. But when R5 forwards the packet to R6 across the LAN, the network layer header will (still) be source A, destination D.

The data link header will be source R5, destination R6. When R6 forwards it (across the token ring LAN) the network header is still the same, and the data link header has source R6, destination D. Most likely A's data link address will look different from its network layer address, so it's a bit sloppy to say source A in both the data link header and network header. But this is all irrelevant to security. Fascinating in its own right, but irrelevant to this book.

The network layer header can be thought of as an envelope for the message. The data link header is an outer envelope. We've described the case of two envelopes; a network header inside a data link header. The world can be even more complicated than this. In fact the data link layer might be a multi-hop network with multi-hop networks inside it as well. So a message might wind up with several envelopes. Again this is fascinating stuff but is irrelevant to this book.

1.4.7. Address Structure

What do addresses look like? In terms of security, the main issue is how difficult it is to forge a source address, and how easy it is to arrange for the network to deliver packets to you when they are addressed to someone other than you. For instance, think of a letter as having a source address (the return address, it's called in paper mail) and a destination address. It's easy to send a letter to anyone and put President, White House, USA as the source address. It's harder to arrange to receive mail sent to President, White House, USA if you are not the U.S. President, especially if you don't live in the White House, and most likely more difficult the further you live from the address you'd like to impersonate. Addresses are usually hierarchical, just like a postal address. If we think of the address as specifying country/state/city/person, then in general it will be easier to arrange to receive someone else's messages if you reside in the same city (for instance by bribing a postal employee), and most difficult if they're in a different country.

Forging source addresses is easy in most network layers today. Routers could be built more defensively and do a sanity check on the source address, based on where they receive the packet from, but routers in general do not do this. Sometimes security gateways (also known as firewalls) have such features.

1.5. Tempest

One security concern in this layer is having intruders tap into a wire, giving them the ability to eavesdrop and possibly modify or inject messages. Another security concern is electronic emanation, whereby through the magic of physics, the movement of electrons can be measured from a surprising distance away. This means that intruders can sometimes eavesdrop without even needing to physically access the link. The U.S. military TEMPEST program measures how far away an intruder must be before eavesdropping is impossible. That distance is known as the device's control zone. The control zone is the region that must be physically guarded to keep out intruders that might be attempting to eavesdrop. A well-shielded device will have a smaller control zone.

1 -- remember being told in 1979 of a tape drive that had a control zone over 2 miles. Unfortunately, most control zone information is classified, and

2 -- couldn't get me to be very specific about them, other than that they're usually expressed in metric.

Since it is necessary to keep intruders away from the control zone, it's certainly better to have something with a control zone on the order of a few inches rather than a few miles (oh yeah, kilometers).

CIA eavesdroppers could not intercept the radio transmissions used by Somali warlord Mohammed Farah Aidid; his radios, intelligence officials explained, were too low tech.

Larry Downing, Newsweek, Oct 10, 1994, page 32

1.6. Firewalls/Security Gateways

Firewalls are the wrong approach. They don't solve the general problem, and they make it very difficult or impossible to do many things. On the other hand, if I were in charge of a corporate network, I'd never consider hooking into the Internet without one. And if I were looking for a likely financially successful security product to invest in, I'd pick firewalls.

Charlie Kaufman

A firewall is a computer that sits between your internal network and the rest of the network and filters packets as they go by, according to various criteria you can configure. It is sometimes called other things, like a security gateway, or various more colorful names thought up by frustrated network users.

Why is a firewall needed? It wouldn't be, if security was done right, meaning that every system in your network had sophisticated authentication, the ability to do integrity protected and encrypted communication, (see the rest of this book to see how to do security right), and was well-managed (when users rely on passwords, they choose good passwords, system accounts are not left with no password or a default password, etc.). The dilemma is that most corporate networks are not designed for security, and yet it is desirable to have some connectivity to a global network. You want to be able to send mail to anyone. You want to occasionally share files. You want to communicate with publicly available services. But a large global network is a scary place. There will be spies from unfriendly countries, users from competing companies, playful undergraduates, press people eager for a juicy scoop, criminals anxious to steal information for profit, and disgruntled ex-employees.

1.6.1. Packet Filters

The simplest form of firewall selectively discards packets based on things it can be configured to look for, for instance the network address. For example, it might be configured to only allow some systems on your network to communicate outside, or some addresses outside your network to communicate into your network. For each direction, the firewall might be configured with a set of legal source and destination addresses, and it drops any packets that don't conform. This is known as address filtering. Address filtering has the problem that it is often easy to forge a network address.

1.6.2. Application Level Gateway

Another strategy for protecting your vulnerable network is an application level gateway. This can be accomplished with three boxes. The two firewalls are routers that refuse to forward anything unless it's to or from the gateway. Firewall F2 refuses to forward anything from the global net unless the destination address is the gateway, and refuses to forward anything to the global net unless the source is the gateway. Firewall F1 refuses to forward anything from your network unless the destination address is the gateway, and refuses to forward anything to your network unless the source address is the gateway. To transfer a file from your network to the global network you need to have someone from inside transfer the file to the gateway machine, and then the file is accessible to be read by the outside world. Similarly to read a file into your network a user has to arrange for it to first get copied to the gateway machine. To log into a machine in the global network you first log into the gateway machine, and from there you can access machines in the remote network.

The gateway machine need not support every possible application. A common strategy is only to allow electronic mail to pass between your corporate network and the outside world. The intention is to specifically disallow file transfer and remote login. But electronic mail can certainly be used to transfer files. Sometimes a firewall might specifically disallow very large electronic mail messages, on the theory that will limit the ability to transfer files. But often large electronic mail messages are perfectly legitimate, and any file can be broken down into small pieces. Because of such firewalls, many applications that post data for public retrieval on the Internet have automatic mail responders to which you can send an email message requesting the file, and the file will be sent back as an email message--several email messages, in fact, since such applications also realize the email messages have to be kept small in order to make it through the firewall. It is slow and painful for legitimate users to get files that way. Typically the file arrives in several pieces. Each piece has to be extracted from the received email (to get rid of email headers), rearranged into order (since email tends to get out of order), and edited into a file.

1.6.3. Encrypted Tunnels

A tunnel is a point-to-point connection in which the actual communication occurs across a network. This becomes a useful concept when you are thinking about your communication path as a sequence of links, some of which are secure and some of which aren't. The right way to ensure secure communication is end-to-end, i.e. where the two communicating parties do all the security work and assume that the medium over which they are communicating is insecure. But the parties may not capable of providing security, which is okay if the links themselves are secure. When some of the links are subject to eavesdropping, you can encrypt over those links. Only the routers on those links need to do encryption and decryption.

Suppose the only reasons you've hooked into a public internet is to connect disconnected pieces of your own network to each other and to allow your off-site users to connect to your network. You donÕt care about making internet resources available to the users inside your corporate network.

The typical solution for this is to have G1, G2, and G3 treat the internet just as if it's some sort of insecure wire. G1, G2, and G3 are configured with security information about each other. All information between them is encrypted and integrity protected. This can be done with a single shared secret key for all of them, or with any sort of pairwise authentication scheme based on secrets or public keys.

You might want your users to be able to access the corporate network from across the internet as well.

Suppose X is some sort of workstation that can attach to the internet in any location. To do this, X would create a tunnel with one of the G's.

1.7. Key Escrow for Law Enforcement

The U.S. government has proposed technology to preserve its ability to wiretap otherwise secure communication. To do this it must either prevent use of encryption, break the codes used for encryption (as it did in a military context during World War II), or somehow learn everyoneÕs cryptographic keys. The proposed technology takes the last option. It allows the Government to reconstruct your key (only upon court order and with legitimate cause of course). This is made possible through the use of a device known as the Clipper chip. A lot about Clipper is classified by the government as secret (and classified by a lot of other people as evil). We describe the basic technical design of Clipper in 17.9 Clipper. The simple concept is that encryption is done with a special chip (the Clipper chip). Each chip manufactured has a unique key, and the government keeps a record of the serial number/encryption key correspondence of every chip manufactured. Because not all people have complete trust in the government, rather than keeping the key in one place, each key is broken into two quantities which must be in order to obtain the actual key. Each piece is completely useless without the other. Since each piece is kept with a separate government agency, it would require two U.S. government agencies to cooperate in order to cheat and obtain the key for your Clipper chip without a valid court order. The government assures us, and evidence of past experience supports its claim, that cooperation between U.S. government agencies is unlikely.

The Clipper proposal is controversial, starting with its name. The name will certainly change, since it violates someone's trademark on something unrelated. But since everyone calls the proposal Clipper, we will too, especially since the new name has not been chosen. Why would anyone use Clipper when alternative methods should be cheaper and more secure? The reason alternatives would be cheaper is that enforcing the ability of the U.S. government to wiretap will add a lot of complexity. Proponents of Clipper have given several answers to this question.

The government will buy a lot of Clipper chips, bringing the cost down because of volume production, so Clipper will wind up being the most cost-effective solution.

Encryption technology is only useful if both parties have compatible equipment. If you want to talk securely to the U.S. government, you will have to use Clipper. So any other mechanism would have to be implemented in addition to Clipper.

Again, since encryption technology is only useful if both parties have compatible equipment, if Clipper takes over enough market share, it will essentially own the market (just like VHS, a technically inferior standard supposedly, beat out Beta in the VCR marketplace). Since Clipper will be one of the earliest standards, it might take over the marketplace before any other standards have an opportunity to become entrenched. Most people won't care that Clipper enables wiretapping, because they'll assume they have nothing to fear from the U.S. government wiretapping them.

The government claims that the cryptographic algorithm in Clipper is stronger than you'll be able to get from a commercial source. Civil libertarians fear Clipper is a first step towards outlawing untappable cryptography. Clipper proponents say it is not. It's true that outlawing alternatives is not part of the Clipper proposal. However, there have been independent efforts to outlaw cryptography. Those efforts have been thwarted in part with the argument that industry needs security. But if Clipper is deployed, that argument goes away. Clipper is designed for telephones, fax, and other low-speed applications, and in some sense is not relevant to computer networking. Many people regard it, however, as a first step and a model for taking the same approach for computer networks.

1.8. Key Escrow for Careless Users

It is prudent to keep your key in a safe place so that when you misplace your own key you can retrieve a copy of the key rather than conceding that all your encrypted files as irretrievably lost. It would be a security risk to have all users' keys stored unencrypted somewhere. The database of keys could be stored encrypted with a key known to the server that was storing the database, but that would mean that someone that had access to that machine could access all the user keys. Another possibility is to encrypt the key in a way that can only be reconstructed with the cooperation of several independent machines. This is feasible and we'll discuss it more in 17.9.1 Key Escrow.

Some applications don't require recoverable keys. An example of such an application is login. If a user loses the key required for login, the user can be issued a new key. A user may therefore want different keys for different uses, where only some of the keys are escrowed. For applications that do require recoverable keys, protection from compromise can be traded off against protection from loss.

1.9. Viruses, Worms, Trojan Horses

Lions and tigers and bears, oh my!

Dorothy (in The Wizard of Oz movie)

People like to categorize different types of malicious software and assign them cute biological terms (if one is inclined to think of worms as cute). We donÕt think it's terribly important to distinguish between these things, but will define some of the terms that seem to be infecting the literature.

Trojan horse-instructions hidden inside an otherwise useful program that do bad things. Usually the term Trojan horse is used when the malicious instructions are installed at the time the program is written (and the term "virus" is used if the instructions get added to the program later).

virus-a set of instructions that, when executed, inserts copies of itself into other programs

bacterium-a free-standing program that replicates itself, causing harm by consuming resources

worm-a program that replicates itself by installing copies of itself on other machines across a network. Similar to a bacterium, but it replicates over a network whereas a bacterium tends to stay confined to one machine.

trapdoor-an undocumented entry point intentionally written into a program, often for debugging purposes, which can be exploited as a security flaw

logic bomb-malicious instructions that trigger on some event in the future, such as a particular time occurring.

We do not think it's useful to take these categories seriously. Like most things people have tried to categorize (plants vs animals, intelligence vs instinct) there are things that don't fit neatly within these categories. We'll refer to them generically as digital pests.

1.9.1. Where do they come from?

Where do these nasties come from? Except for trapdoors, which may be intentionally installed to facilitate troubleshooting, they are written by bad guys with nothing better to do with their lives than annoy people.

How could an implementer get away with writing a digital pest into a program? Wouldn't someone notice by looking at the program? One of the most famous results id computer science is that it is probably impossible to be able to tell what an arbitrary program will do by looking at it, so certainly it would be impossible to tell, in general, whether the program had any unpleasant side effects besides its intended purpose. But that's not the real problem. The real problem is that nobody looks. Often when you buy a program you do not have access to the source code, and even if you did, you probably wouldn't bother reading it all, or reading it very carefully. Many programs that run have never been reviewed by anybody.

If it were possible to examine source code to see if it did anything other than its intended purpose, nobody would have an excuse for shipping software with bugs.

What does a virus look like? A virus can be installed in just about any program by doing the following:

replace any instruction, say the instruction at location x, by a jump to some free place in memory, say location y.

Write the virus program starting at location y, place the instruction that was originally at location x at the end of the virus program, followed by a jump to x+1.

Besides doing whatever damage the virus program does, it might replicate itself by looking for any executable files in any directory and infecting them. Once an infected program is run, the virus is executed again, to do more damage and to replicate itself to more programs. Most viruses spread silently until some triggering event causes them to wake up and do their dastardly deeds. If they did their dastardly deeds all the time, they wouldn't spread as far. How does a digital pest originally appear on your computer? All it takes is running a single infected program. A program posted on a bulletin board might certainly be infected. But even a program bought legitimately might conceivably have a digital pest. It might have been planted by a disgruntled employee or a saboteur that might have broken into the computers of the company and installed the pest into the software before it was shipped. There have been cases where commercial programs were infected because some employee ran a program gotten from a friend or a bulletin board.

Often at holiday times people send email messages that are programs, with the instruction that you extract the mail message and run it. Often the result is some sort of cute holiday-specific thing, like displaying a picture of a turkey or playing a Christmas carol. It could certainly also contain a virus. Few people will scan the program before running it, especially if the message arrives from a friend. And if you were to run such a program and it did something cute, you might very well forward it to a friend, not realizing that in addition to doing the cute thing it might very well have installed a virus that will start destroying your directory a week after the virus is first run. A good example of a Christmas card email message is a program written by Ian Phillipps, which was a winner of the 1988 International Obfuscated C Code Contest. It is delightful as a Christmas card. It does nothing other than its intended purpose (I1 have analyzed the thing carefully and I2 have complete faith in me1), but we doubt many people would take the time to understand this program before running it.



Sometimes you don't realize you're running a program. PostScript is a complete programming language. It is possible to imbed a Trojan horse into a PostScript file that infects files with viruses and does other damage. Someone could send you a file and tell you to display it. You wouldn't realize you were running a program by merely displaying the file. And if there was any hope of scanning a C program to find suspicious instructions, there are very few people who could scan a PostScript file and look for suspicious PostScript commands. PostScript is, for all practical purposes, a write-only language. As mail systems get more clever in their attempt to make things more convenient for users, the risk becomes greater. If you receive a PostScript file and you are running a non-clever mail program, you will see delightful crud like:

If you wanted to display the file, you'd have to extract the mail message and send it to the printer, or input it into a special program that displays PostScript on your screen. However, a clever mail program might look at the message, recognize that it was PostScript, and automatically run the PostScript code to display the message. Although this is convenient, it is dangerous, since no matter how clever your vendor claims their mail product is, we can assure you it won't scan the PostScript for Trojan horses before displaying the message.

There are various other clever features being added to mail programs. Some mail programs allow the sender to send a program along with the mail message. Usually the mail message will arrive and display some sort of icon. If the receiver clicks on the icon, the transmitted program is executed. Someone, to illustrate this point, sent such a mail message. It displayed only as a button that said push me. When the person that received the message clicked on the box, it came up with a message that said, I could have just reformatted your hard drive.

Before the technology for clever mail goes much further, we ought to consider how we can reap the benefits of such cleverness while minimizing the security risks.

There are dangers associated with booting from floppy disks. Even if system software becomes sophisticated about security, it won't be able to protect against Trojan horses on the boot device, and people still commonly boot from floppies. When you turn the machine on with a floppy disk inserted into the drive, the machine executes the code on the floppy. If there is a virus in that code, it can stay resident in memory, and infect any new floppies inserted into the drive (unless the machine is powered off between floppies). Even machines with hard drives allow booting off floppies. If the hard drive were completely wiped clean, there has to be some way to come up again, so machines provide the feature that if there is a floppy in the drive when the machine is powered on, the machine boots off the floppy. Often it is convenient to boot off a floppy. It is common to run games by booting off the floppy containing the game.

Once you run code on a floppy, the code can do anything, so if it contains a virus it can destroy or infect all the files on the hard disk.

1.9.2. Spreading Pests from Machine to Machine

How might a virus or worm spread from machine to machine? An infected program might be copied to a floppy and moved to another machine. Or, as we said, a mail message might carry the infection. But it is also possible for the pest to explore the network and send itself to other machines, once it is running in one machine on a network. Such a pest is called a worm.

One method a worm can employ to transmit itself to another machine is to actually log onto the other machine. It can do this by guessing passwords. Sometimes things are set up to make it really easy, for instance, account name/password pairs might be stored in script files so that a naive user can access remote resources automatically. If the worm manages to find that information, it can easily log into other machines and install itself. Sometimes machines have trapdoor debugging features, such as the ability to run a command remotely. Sometimes it isn't even necessary to log in order to run such a command.

And if intruders can execute commands, they can do anything.

The only reason all the computers in the world haven't crashed at the same time is that they're not all connected together yet.

Tony Lauck

One Christmas card type email message displayed a pretty animated tree on the screen, but also scanned the user's directory for all possible correspondents, including distribution lists, and mailed itself to them. Each time a recipient read a copy of the message, it sprang into life and mailed itself off to all the mailboxes it could locate from that node. Although this program did not destroy data, like a classic worm it completely disabled the corporation's electronic mail.

1.9.3. Virus Checkers

How can a program check for viruses? There's rather a race between the brave and gallant people who analyze the viruses and write clever programs to detect and eliminate the known viruses, and the foul- smelling scum who devise new types of viruses that will escape detection by all the current virus checkers.

The most common form of virus checker knows the instruction sequence for lots of types of viruses, checks all the files on disk and instructions in memory for those patterns of commands, and raises a warning if it finds a match hidden somewhere inside some file. Once you own such a virus checker, you need to periodically get updates of the patterns file that includes the newest viruses. To evade detection of their virus, virus creators have devised what is known as a polymorphic virus which changes the order of its instructions, or changes to functionally similar instructions, each time it copies itself. Such a virus may still be detectable, but it takes more work and typically requires a coding change and not just a new pattern file.

Another type of virus checker takes a snapshot of disk by recording the information in the directory, such as file lengths. It might even take message digests of the files. It is designed to run, store the information, and then run again at a future time. It will warn you if there are suspicious changes. One type of virus, wary of changing the length of a file by adding itself to the program, compressed the program so that the infected program would wind up being the same length as the original. When the program was executed, the uncompressed portion containing the virus decompressed the rest of the program so (other than the virus portion), the program could run normally.

1.9.4. What can we do today?

The world was a scary place before computer viruses came along, and will most likely continue to be scary. How can you know whether you can trust a program not to do bad things when you run it? Wouldn't it be nice to have the equivalent of a lie-detector test for programs?

Ames slipped by a lie-detector test because no one had told the polygrapher he was under suspicion.

Larry Downing, Newsweek article on CIA and traitor Aldrich Ames,
October 10, 1994
Given that there is no infallible method to test a program for hidden bad side effects, we can't be completely safe, but there are some precautions that are worth taking:

Don't run software from suspicious sources, like bulletin boards, or software gotten from people who aren't as careful as you are.

Frequently run virus checkers. Have the industry employ people whose job it is to keep up with virus technology and come up with vaccines.

Try to run programs in the most limited possible environments. For instance, if you have a PC in order to get real work done, and you also want to play games, sometimes using shareware or games copied from bulletin boards, have two machines. If you run a game with a virus, you'll only wipe out your games.

Do frequent backups, and save old backups for a long time.

Don't boot off floppies, except in an extreme circumstance, such as the first time you unpack your machine and turn it on.

In those circumstances, be extremely careful about what floppy you boot from.
But mostly, the situation is pretty bleak, given the design of the operating systems for PCs. Maybe in the future, some of our suggestions in the next section might be implemented.

1.9.5. Wish list for the Future

I2 always assumed computers were designed in such a way that no program that ran on the machine could possibly injure the machine. Likewise, it should not be possible to send a piece of information to a machine that might damage the machine. People are designed properly that way, aren't they?

Sticks and stones may break my bones but words will never hurt me. chant designed to encourage bullies to get physical

But one of my2 first programs consisted of something that just sat around and waited for interrupts, and processed the interrupts. The program itself, not counting the instructions for processing the interrupts, was HERE: JUMP HERE (that's not the exact instruction because I'm attempting not to divulge the computer brandname).

I2 discovered (the hard way) that you weren't supposed to do that, because it burned out core at the instruction that kept getting executed over and over. Gerry Sussman, while a high school student, wrote a program that broke magnetic tapes. The guru who guarded and ran the mainframe didn't believe Gerry when he boasted that he could write a program to break tapes, so Gerry wrote his program to go down the entire row of tape drives, breaking the tape in each one. Another example was a machine designed with a small amount of nonvolatile memory, but the type that wore out after a finite number of writes, say 10,000.

That kind of memory is fine for something like saving terminal settings, since a human has to type the key sequence to cause a write, and a human won't do it very often. But if the same kind of message is used for storing parameter settings received by a network management message, then it is possible to break the machine within seconds by sending it parameter settings over and over.

In an ideal world, it should be possible to load a floppy and examine the contents without fear. You should be able to receive any email message without fear. If it is a multimedia message, it should be possible to play the audio, display the video, print the text, or waft the odors without damage to either the machine or files stored on the machine. A file is just a bunch of bits. If the file claims to be audio, it should be possible, without risk of any type of harm, to play the file. Likewise, if the file claims to be something worthy of printing, it should not cause any harm to print the file.

Programs are a bit trickier. It should be possible to run a program and not have it affect the files stored on your machine, or the basic integrity of the operating system.

We know none of these "shoulds" are true today. The files on your machine can be virus-infected through email, printing a PostScript file, or simply inserting a floppy disk (on some machines). How could systems be designed more defensively?

One simple feature would be a write-protect switch on your hard disk. Sometimes you run programs that you know should not be writing to your hard disk. A game program shouldn't be writing to your hard disk. Perhaps it wants to record highest score, but consumers might be willing to do without that frill, if it means that they can run any game they want, without fear of wiping out their life's work.

Legitimate game manufacturers could design their games to work with write-protected hard disks. Even the social misfits who design games that spread viruses could design their games to work with write- protected hard disks, but just have their program check to see if some user has forgotten to write-protect the disk, and then launch the virus.

Time sharing systems used to be much more defensive. You could not run a program that would write into some other user's memory, or modify any portion of the disk that you were not authorized to write into. But PCs make the assumption that there is only one human on the machine at a time, and that human ought to be able to do anything it wants. To make matters worse, to enable snazzy maximally flexible features, there are all sorts of surprising places in which someone can insert a program which will be executed.

The operating system ought to be built more defensively. PCs should have accounts just like timesharing systems so that you can set up a game account that can't affect the rest of the system. Likewise your normal account shouldn't be able to alter system software. The world is moving in this direction, but progress is slow.

Booting off a floppy is unavoidably dangerous, since i t involves loading the operating system itself. Since a program that is supposed to be the operating system will certainly be allowed to do anything it wants, there's no way to prevent polluted software on a floppy from destroying the world, if you boot off that floppy.

At least, one should only boot off the floppy that came with the machine, rather than using the boot feature to more conveniently run games. One game I1 ran recently ran out of memory, and with the error message giving the bad news, offered to make a special floppy that could run the game, finding extra memory by avoiding loading anything that wasn't essential to the running of the game. That was a very helpful suggestion, but it means that people still, for various reasons, will be tempted to boot off floppies of suspicious heritage.

1.10. The Military Model of Security

The main concern in the military model of security is with keeping data secret. It involves worrying about arcane threats such as covert channels, and creating cumbersome mechanisms such as mandatory access controls for keeping secret data from leaking out.

1.10.1. Mandatory Access Controls

O negligence! what cross devil made me put this main secret in the packet I sent the king? Is there no way to cure this? No new device to beat this from his brains?

Shakespeare's King Henry VIII, Act 3, scene 2

Discretionary means that someone who owns a resource can make a decision as to who is allowed to use (access) it. Nondiscretionary access controls are where strict rules are automatically enforced about who is allowed access to certain resources, and even the owners of the resources cannot change the attributes of a resource.

The basic philosophy behind discretionary controls is that the users and the programs they run are the good guys, and it is up to the operating system to trust them and protect each user from outsiders and other users. The basic philosophy behind nondiscretionary controls is that everything would be fine except for the pesky human beings that unfortunately have to be allowed to use the system. The system must be ever vigilant to prevent the users from accidentally or intentionally giving information to someone who shouldn't have it.

This philosophy does not necessarily imply that the users are expected to be evil, but it does expect them to be careless, and possibly run programs with digital pests. Careless users might accidentally type the wrong file name when including a file in a mail message, or might leave a message world readable.

Non-discretionary access controls grew out of the military mindset. The primary concern is secret data getting leaked to the enemy. The concept is to confine information within a security perimeter, and not allow any information to move from a more secure environment to a less secure environment.

Now of course, if you allow the users out of the building there is an avenue for information to leak out of a secure environment, since a user can remember the information and tell someone once the user gets out of the security perimeter. But the designers of these controls weren't primarily worried about the authorized users selling secrets. There really is no way for a computer system to prevent that. But they wanted to ensure that no Trojan horse in software could transmit any information out of the perimeter, and they wanted to make sure that nothing inadvertent a user did could leak information.

1.10.2. Levels of Security

What does it mean for something to be "more sensitive" than something else. We will use a somewhat simplified description of the U.S. Department of Defense (DoD) definitions of levels of security as an example. It is a reasonably general model and similar to what is done in other contexts. It is sufficient to understand the security mechanisms we'll describe.

The security label of something consists of two components:

A security level which might be an integer in some range, but in the U.S. DoD consists of one of the four ratings unclassified, confidential, secret and top secret, where unclassified

< confidential
< secret
< top secret.

A set of zero or more categories (also known as compartments) which describe the kind of information which is applicable. For instance the name CRYPTO might mean information about cryptographic algorithms, INTEL might mean information about military intelligence, COMSEC might mean information about communications security, or NUCLEAR might mean information about types of families.

Documents (or computer files) are marked with a security label saying how sensitive the information is, and people are issued security clearances according to how trustworthy they are perceived to be and for which they have demonstrated a "need to know".

A clearance might therefore be (SECRET;{COMSEC,CRYPTO}), which would mean someone was allowed to know information classified unclassified, confidential or secret (but not top secret) dealing with cryptographic algorithms or communications security. Given two security labels, (X, S1) and (Y, S2 ), (X, S1) is defined as being "at least as sensitive as" (Y, S2 ) iff X ³ Y and S2 Í S1.
For example
(TOP SECRET, {CRYPTO, COMSEC}) > (SECRET, {CRYPTO})
where > means more sensitive than.

It is possible for two labels to be incomparable, in the sense that neither is more sensitive than the other.
For example, neither of the following are comparable to each other:
(TOP SECRET, {CRYPTO, COMSEC})
(SECRET, {NUCLEAR, CRYPTO})

1.10.3. Mandatory Access Control Rules

Every person, process, and piece of information has a security label. A person cannot run a process with a label higher than the person's label, but may run one with a lower label. Information is only allowed to be read by a process that has at least as high a rating as the information. The terminology used for having a process read something with a higher rating than the process is read-up. Read-up is illegal and must be prevented. A process cannot write a piece of information with a rating lower than the process's rating.

The terminology used for a process writing something with a lower rating than the process is write-down. Write-down is illegal and must be prevented.

The rules are a human can only run a process which has a security label below or equal to that of the human's label

A process can only read information marked with a security label below or equal to that of the process

A process can only write information marked with a security label above or equal to that of the process. Note that if a process writes information marked with a security label above that of the process, the process can't subsequently read that information.

The prevention of read-up and write-down is the central idea behind mandatory access controls. The concepts of confinement within a security perimeter, and a generalized hierarchy of security classes was given a mathematical basis by Bell and La Padula in 1973 . There is significant complexity associated with the details of actually making them work.

1.10.4. Covert Channels

A covert channel is a method for a Trojan horse to circumvent the automatic prevention of information outside a security domain. Let's assume an operating system has enforced the rules in the previous section. Let's assume also that a bad guy has successfully tricked someone inside a security perimeter into running a program with a Trojan horse. The program has access to some sensitive data, and wants to pass the data to a process outside the security perimeter. We're assuming the operating system prevents the process from doing this straightforwardly, but there are diabolical methods that theoretically could be employed to get information out. These are known as covert channels.

The Trojan horse program cannot directly pass data, but all it needs is for there to be anything it can do that can be detected by something outside the security perimeter. As long as information can be passed one bit at a time, anything can be transmitted, given enough time.

One possible covert channel is a timing channel. The Trojan horse program alternately loops and waits, in cycles of, say 1 minute per bit. When the next bit is a 1, the program loops for one minute. When the next bit is a 0, the program waits for a minute. The program outside the perimeter constantly tests the loading of the system. If the system is sluggish, its conspirator inside the perimeter is looping, and therefore transmitting a 1. Otherwise the conspirator is waiting, and therefore transmitting a 0.

This assumes those two processes are the only ones running on the machine. What happens if there are other processes running and stopping at seemingly random times (from the point of view of the program trying to read the covert channel). That introduces noise into the channel. But communications people can deal with a noisy channel. It just lowers the potential bandwidth, depending on the signal to noise ratio.

Another example of a covert channel involves the use of shared resources other than CPU. For instance, suppose there were a queue of finite size, say the print queue. The Trojan horse program could fill the queue to transmit a 1, and delete some jobs to transmit a 0. The covert channel reader would attempt to print something and note whether the request was accepted. Other possible shared resources that might be exploited for passing information include physical memory, disk space, and I/O buffers. Yet another example depends on how clever the operating system is about not divulging information in error messages. For instance, suppose the operating system says file does not exist when a file really does not exist, but says insufficient privilege for requested operation when the file does exist, but inside a security perimeter off limits to the process requesting to read the file. Then the Trojan horse can alternately create and delete a file of some name known to the other process. The conspirator process periodically attempts to read the file and uses the information about which error message it gets to determine the setting of the next bit of information.

There is no general way to prevent all covert channels. Instead, people imagine all the different ways they can think of, and specifically attempt to plug those holes. For instance, the timing channel can be eliminated by giving each security perimeter a fixed percentage of the CPU. This is wasteful, and impractical in general because there can be an immense number of distinct classifications (in our model of (one of four levels, {categories}), the number of possible security perimeters is 4 2n, where n is the number of categories.

Most covert channels are very low bandwidth. In many cases, instead of attempting to eliminate a covert channel, it is more practical to introduce enough noise into the system so that the bandwidth becomes too low to be useful to an enemy. It's also possible to look for jobs that appear to be attempting to exploit covert channels (a job that alternately submitted enough print jobs to fill the queue and then deleted them would be suspicious indeed if someone knew to watch). If the bandwidth is low and the secret data is large, and knowing only a small subset of the secret data is not of much use to an enemy, the threat is minimized.

How much secret data must be leaked before serious damage is done can vary considerably. For example, assume there is a file with 100 megabytes of secret data. The file has been transmitted, encrypted, on an insecure network. The enemy therefore has the ciphertext, but the cryptographic algorithm used makes it impossible for the enemy to decrypt the data without knowing the key. A Trojan horse with access to the file and a covert channel with a bandwidth of 1 bit every 10 seconds would require 250 years to leak the data (by which time it's hard to believe the divulging of the information could be damaging to anyone).

However, if the Trojan horse had access to the 56 bit key, it could leak that information across the covert channel in less than 10 minutes. That information would allow the enemy to decrypt the 100 megabyte file. For this reason, many secure systems go to great pains to keep cryptographic keys out of the hands of the programs that use them.

1.10.5. The Orange Book

The National Computer Security Center (NCSC) (an agency of the U.S. Government) has published an official standard called "Trusted Computer System Evaluation Criteria", universally known as the Orange Book" (guess what color the cover was). The Orange Book defines a series of ratings that a computer system can have based on its security features and the care that went into its design. This rating system is intended to give government agencies and commercial enterprises an objective assessment of a system's security and to goad computer manufacturers into placing more emphasis on security. The official categories are D, C1, C2, B1, B2, B3, and A1, which range from least secure to most secure.

In reality, of course, there is no way to place all the possible features in a linear scale. Different threats are more or less important in different environments. The authors of the Orange Book made an attempt to linearize these concerns given their priorities. But the results can be misleading. An otherwise A1 system that is missing some single feature might have a D rating. Systems not designed with the Orange book in mind are likely to get low rating even if they are in fact very secure.

The other problem with the Orange book rating scheme is that the designers focused on the security priorities of military security people. They focused on keeping data secret. In the commercial world, data integrity is at least as important as data confidentiality. Mandatory access controls, even if available, are not suitable for most commercial environments because they make the simplest operations incredibly cumbersome, for example having a highly privileged user send mail to an unprivileged user.

With the orange book ratings, high ratings will not protect the system from infection by viruses. The fancy mandatory access controls required for high ratings allow write-up, so if some unprivileged account became infected by having someone carelessly run, say, a game program loaded from a bulletin board, the virus could infect more secure areas. Ironically, if it was a very secure area that first got infected, the mandatory access control features would prevent the infection from spreading to the less secure environments.

The following is a summary of what properties a system must have to quality for each rating.

D Minimal Protection. Actually, this simply means the system did not qualify for any of the higher ratings; it might actually be very secure. No system is ever going to brag about the fact that it was awarded a D rating.

C1 Discretionary Security Protection. The requirements at this level correspond roughly to what one might expect from a classic time sharing system. It requires:

The operating system must prevent unprivileged user programs from overwriting critical portions of its memory. (note that most PC operating systems do not satisfy this condition).

Resources must be protected with access controls. Those access controls need not be sophisticated; classic owner/group/world controls would be sufficient.

The system must authenticate users by a password or some similar mechanism and the password database must be protected so that it cannot be accessed by unauthorized users.

There are additional requirements around testing and documentation, which become more detailed at each successive rating.

C2 Controlled Access Protection. This level corresponds roughly to a time sharing system where security is an important concern, but where users are responsible for their own fates; an example might be a commercial time sharing system. The additional requirements (over those required for C1) for a C2 rating are:

Access Control at a per user granularity: it must be possible to permit access to any selected subset of the user community, probably via ACLs. An ACL is a datastructure attached to a resource that specifies the resource's authorized users.

Clearing of allocated memory: the operating system must assure that freshly allocated disk space and memory does not contain "left over" data deleted by some previous user. It can do that by writing the space or by requiring processes to write to the space before they can read it.

Auditing: the operating system must be capable of recording security relevant events including authentication and object access. The audit log must be protected from tampering and must record date, time, user, object, and event. Auditing must be selective based on user and object.

It is reasonable to expect that C2 rateable systems will become ubiquitous, since they contain features that are commonly desired and do not represent an unacceptable overhead. It is somewhat surprising that such systems are not the norm.

B1 Labeled Security Protection. Additional requirements at this level are essentially those required to implement Mandatory Access Controls for secrecy (not integrity) except that little attention is given to covert channels. Requirements for B1 above those for C2 include:

Security Labels: Sensitivity labels must be maintained for all users, processes, and files, and read- up and write-down must be prevented by the operating system.

Attached devices must either themselves be labelled as accepting only a single level of information or they must accept and know how to process security labels.

Attached printers must have a mechanism for assuring that there is a human readable sensitivity label printed on the top and bottom of each page corresponding to the sensitivity label of the information being printed. The operating system must enforce this correspondence. B2 Structured Protection. Beyond B1, there are few new features introduced; rather, the operating system must be structured to greater levels of assurance that it behaves correctly (i.e. has no bugs).

Additional requirements for B2 include:

Trusted Path to User-there must be some mechanism to allow a user at a terminal to reliably distinguish between talking to the legitimate operating system and talking to a trojan horse password- capturing program.

Security Level changes-a terminal user must be notified when any process started by that user changes its security level.

Security Kernel-the operating system must be structured so that only a minimal portion of it is security sensitive. i.e. that bugs in the bulk of the O/S cannot cause sensitive data to leak. This is typically done by running the bulk of the O/S in the processor's user mode and having a secure kernel mini-operating system which enforces the mandatory access controls.

Covert channels must be identified and their bandwidth estimated, but there is no requirement that they be eliminated.

Strict procedures must be used in the maintenance of the security sensitive portion of the operating system. For instance, anyone modifying any portion must document what they changed, when they changed it, and why, and some set of other people should compare the updated section with the previous version.

B3 Security Domains. Additional requirements for B3 mostly involve greater assurance that the operating system will not have bugs that might allow something to circumvent mandatory access controls.

Additional requirements include:
ACLs must be able to explicitly deny access to named individuals even if they are members of groups that are otherwise allowed access. It is only at this level that ACLs must be able to separately enforce modes of access (i.e. read vs. write) to a file.

Active Audit-there must be mechanisms to detect selected audited events or thresholds of audited events and immediately trigger notification of a security administrator.

Secure Crashing-the system must assure that the crashing and restarting of the system introduces no security policy violations. A1 Verified Design. There are no additional features in an A1 system over a B3 system. Rather, there are formal procedures for the analysis of the design of the system and more rigorous controls on its implementation.

1.11. Legal Issues

The legal aspects of computer network security are fascinating, but the picture changes quickly and we are certainly not experts in law. One legal issue that affects the choice of security mechanisms is patents. The RSA public key algorithm (see 5.3 RSA) is patented, and the rights are licensed by RSADSI, a company that is not careless about collecting license fees where applicable. RSA was developed at MIT, and under the terms of MIT's funding at the time there are no license fees for U.S. government use. It is only patented in the U.S., so there are no license fees when used outside the U.S. and marketed by a non-U.S. company. At any rate, the patent on RSA runs out on September 20, 2000. A good time for a party.

The U.S. government is advocating a digital signature standard (see 5.5 Digital Signature Standard (DSS)). Although in most respects DSS is technically inferior to RSA, when first announced it was advertised that DSS would be freely licensable, i.e., it would not be necessary to reach agreement with RSADSI. But then the RSADSI people bought up the rights to a patent by Schnorr which was apparently close enough to DSS to cover it. (Technically it is a separate corporation, Public Key Partners (PKP), that bought the Schnorr patent and some others, but there are many of the same people involved in both organizations.)

So at this point PKP claimed that it owned rights to DSS as well, and DSS would no longer be freely licensable. The government had patented DSS, and after PKP pointed out that DSS infringed on PKP-held patents, lawsuits loomed, and the situation is still murky.

I don't know what you mean by your way, said the Queen: all the ways about here belong to me

Through the Looking Glass

The relevant patents are: Diffie-Hellman: Patent #4,200,770, issued 1980, expires on April 29, 1997. This covers the Diffie-Hellman key exchange described in 5.4 Diffie-Hellman. Hellman-Merkle: Patent #4,218,582, issued 1980, expires on August 19, 1997. This is claimed to cover all public key systems. There is some controversy over whether this patent should be valid.

The specific public key mechanisms described in the patent (" knapsack systems) were subsequently broken. Rivest-Shamir- Adleman: Patent #4,405,829, issued 1983, expires on September 20, 2000. This covers the RSA algorithm described in 5.3 RSA. Hellman-Pohlig: Patent #4,424,414, issued 1984, expires on January 3, 2001. This is related to the Diffie-Hellman key exchange. Schnorr: Patent #4,995,082, issued 1991, expires on February 19, 2008. This is what the DSS algorithm is directly based upon. Kravitz: Patent #5,231,668, issued 1993, expires on July 27, 2008. This is the actual DSS algorithm.

Another issue is export controls. The U.S. government considers encryption to be a dangerous technology, like germ warfare and nuclear weapons. If a U.S. corporation would like to sell to other countries (and the proceeds are not going to be funding the Contras), they need export approval. The export control laws around encryption are not clear, and their interpretation changes over time. The general principal is that the U.S. government does not want you to give out technology that would make it more difficult for them to spy. Sometimes companies get so discouraged that they leave encryption out of their products altogether. Sometimes they generate products that, when sold overseas, have the encryption mechanisms removed, with the ability for the customers to buy encryption overseas and add it back in. It is usually possible to get export approval for encryption if the key lengths are short enough for the government to brute-force check all possible keys to decrypt a message. So sometimes companies just use short keys, or sometimes they have the capability of varying the key length, and they fix the key length to be shorter when a system is sold outside the U.S. Another potential legal issue is whether the U.S. government might declare encryption illegal, even within the U.S. The Clipper proposal is an attempt to promulgate good enough encryption that the government can easily break (with a court order). Although the government claims there are no plans for making encryption of data inside the U.S. illegal, some people suspect that the only way Clipper can really be successful (i.e., that's the encryption system drug cartels and child pornography rings will be using) is if other uses of encryption are outlawed.