DOJ EX. 1021
`
`1/73
`
`DOJ EX. 1021
`
`

`
`Cryptography
`
`and Data Security
`
`Dorothy Elizabeth Robuling Denning
`PURDUE UNIVERSITY
`
`V‘?
`ADDISON-WESLEY PUBLISHING COMPANY
`
`Reading, Massachusetts I Mcnlo Park, Caiifomia
`London II Amsterdam I Don Mills, Ontario I Sydney
`
`2/73
`
`DOJ EX. 1021
`
`

`
`Library of Congress Cataloging in Publication Data
`Dunning, Dorothy E., (Dorothy Elizabeth), 194-5-
`Cryptography and data security.
`Includes bibliographical references and index.
`]. Corrtputers—Access control.
`2. Cryptography.
`3. Data protection.
`l. Title.
`Q.-*\76.9.A25D46
`I982
`ISBN 0—20|—I0l50—5
`
`DUI .64’02B'9
`
`81—|S0|2
`AACR2
`
`Copyright © [982 by Addison-Wesley Publishing Company. inc.
`All rights reserved. No part of this publication may be reproduced. stored in a retrieval system. or
`transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or other-
`wise. without the prior written permission of the publisher. Printed in the United States of America.
`Published simultaneously in Canada.
`ISBN 0-20 I —'.0l5r0—5
`ABCDE FGH IJ—M A—S93765<132
`
`3/73
`
`DOJ EX. 1021
`
`

`
`In memory of my Father.
`
`Cornelius Lowell Hobling
`
`1910-1965
`
`4/73
`
`DOJ EX. 1021
`
`

`
`5/73
`
`DOJ EX. 1021
`
`

`
`Preface
`
`Electronic computers have evolved from exiguous experimental enterprises in the
`19405 to prolific practical data processing systems in the 19805. As we have come
`to rely on these systems to process and store data. we have also come to wonder
`about their ability to protect valuable data.
`Data security is the science and study of methods of protecting data in
`computer and communication systems from unauthorized disclosure and modifica-
`tion. The goal of this book is to introduce the mathematical principles of data
`security and to show how these principles apply to operating systems, database
`systems, and computer networks. The book is for students and professionals seek-
`ing an introduction to these principles. There are many references for those who
`would like to study specific topics further.
`Data security has evolved rapidly since 1975. We have seen exciting develop-
`ments in cryptography: public-key encryption, digital signatures, the Data Encryp-
`tion Standard (DES), key safeguarding schemes, and key distribution protocols.
`We have developed techniques for verifying that programs do not leak confidential
`data, or transmit classified data to users with lower security clearances. We have
`found new controls for protecting data in statistical databases——and new methods
`of attacking these databases. We have come to a better understanding of the
`theoretical and practical limitations to security.
`Because the field is evolving so rapidly, it has been difficult to write a book
`that is both coherent and current. Even as the manuscript was in production, there
`were new developments in the field. Although I was able to incorporate a few of
`these developments, they are not as well integrated into the book as I would like.
`In many cases,
`I was only able to include references.
`Some areas are still unsettled, and I was unable to treat them to my satisfac-
`tion. One such area is operating system verification: another is the integration of
`V
`
`6/73
`
`DOJ EX. 1021
`
`

`
`PREFACE
`
`1 hope to
`
`cryptographic controls into operating systems and database systems.
`cover these topics better in later editions of the book.
`Data security draws heavily from mathematics and computer science. I have
`assumed my audience has some background in programming, data structures,
`operating systems, database systems, computer architecture, probability theory,
`and linear algebra. Because I have found most computer science students have
`little background in information theory and number theory, I have included self-
`contained tutorials on these subjects. Because complexity theory is a relatively new
`area, I have also summarized it.
`This book is used in a one-semester graduate computer science course at
`Purdue University. The students are assigned exercises, programming projects,
`and a term project. The book is suitable for a graduate or advanced undergraduate
`course and for independent study. There are a few exercises at the end of each
`chapter, most of which are designed so the reader can recognize the right answer. I
`have purposely not included solutions. There is also a puzzle.
`Here is a brief summary of the chapters:
`
`Chapter I, Introduction. introduces the basic concepts of cryptography, data
`security, information theory. complexity theory, and number theory.
`Chapter 2, Encryption Aigorithms, describes both classical and modern
`encryption algorithms, including the Data Encryption Standard (DES) and
`public-key algorithms.
`Chapter 3, Cryptographic Techniques, studies various techniques related to
`integrating cryptographic controls into computer systems,
`including key
`management.
`Chapter 4, Access Controls‘, describes the basic principles of mechanisms
`that control access by subjects (e.g., users or programs) to objects (e.g., files
`and records). These mechanisms regulate direct access to objects, but not
`what happens to the information contained in these objects.
`Chapter 5, Information Flow Controls, describes controls that regulate the
`dissemination of information. These controls are needed to prevent programs
`from leaking confidential data, or from disseminating classified data to users
`with lower security clearances.
`Chapter 6, Inference Controls. describes controls that protect confidential
`data released as statistics about subgroups of individuals.
`
`I am deeply grateful to Jim Anderson, Bob Blakley. Peter Denning, Whit
`Diflie, Peter Neumann, and Rich Reitman, whose penetrating criticisms and sug-
`gestions guided me to important results and helped me focus my ideas. I am also
`grateful to Greg Andrews, Leland Beck, Garrett Birkhoff, Manuel Blum, David
`Chaum, Francis Chin, Larry Cox, Tore Dalenius, George Davida, Dave Gifford,
`Carl Hammer, Mike Harrison, Chris I-Ioifmann, Stephen Matyas, Glen Myers,
`Bob Morris, Steve Reiss, Ron Rivest, Jan Schlorer, Gus Simmons, and Larry
`Snyder. These people gave generously of their time to help make this a better
`book.
`
`7/73
`
`DOJ EX. 1021
`
`

`
`PREFACE
`
`I am thankful to the students who read the book, worked the problems, and
`provided numerous comments and suggestions: George Adams, Brian Beuning,
`Steve Booth, Steve Breese, Carl Burch, Steve Burton, Ray Ciesielski, Cliff
`Cockerham, Ken Dickman, James Dobrina, Dave Eckert. Jeremy Epstein, Tim
`Field, Jack Fitch, Jim Fuss, Greg Gardner, Neil Harrison, Ching-Chih Hsiao,
`Teemu Kerola, Ron Krol, Meng Lee, Peter Liesenlelt, Paul Morrisett, Tim Nodes,
`Bhasker Parthasarathy, Steve Pauley, Alan Pieramico, Steve Raiman, Dan Reed,
`David Rutkin, Paul Scherf, Carl Smith, Aian Stanson, Mark Stinson, Andy Tong,
`and Kim Tresner. I am especially thankful to Matt Bishop for providing solutions
`and for grading.
`The working version of the book was prepared on the department’s VAX
`computer. I am grateful to Doug Comer, Herb Schwetrnan, and the many others
`who kept the system operational and paid careful attention to backup procedures.
`I am grateful to the people who helped with the publication of the book. especially
`Peter Gordon, Gail Goodall, Cheryl Wurzbacher, and Judith Gimple.
`I am especially grateful to my husband, Peter, for his encouragement, sup-
`port, advice, and help throughout.
`
`8/73
`
`DOJ EX. 1021
`
`

`
`9/73
`
`DOJ EX. 1021
`
`

`
`Contents
`
`1
`
`7
`
`1 1
`
`14
`
`INTRODUCTION
`1
`1.1 Cryptography
`3
`1.2 Data Security
`1.3 Cryptographic Systems
`1.3.1
`Public-Key Systems
`1.3.2 Digital Signatures
`lnlormation Theory
`16
`1.4.1
`Entropy and Equivocation
`1.4.2 Pertect Secrecy
`22
`1.4.3 Unicity Distance
`25
`30
`Complexity Theory
`30
`1.5.1 Algorithm Complexity
`31
`1.5.2
`Problem Complexity and NP-Completeness
`1.5.3 Ciphers Based on Computationally Hard Problems
`Number Theory
`35
`1.6.1 Congruenoes and Modular Arithmetic
`1.6.2 Computing Inveraes
`39
`1.6.3 Computing in Galois Fields
`Exercises
`54
`References
`56
`
`34
`
`36
`
`48
`
`59
`
`ENCRYPTION ALGORITHMS
`59
`2.1 Transposition Ciphers
`62
`2.2
`Simple Substitution Ciphers
`2.2.1
`Single-Letter Frequency Analysis
`2.3 Hcmophonic Substitution Ciphers
`67
`2.3.1 Beale C-iphers
`70
`
`66
`
`10/73
`
`DOJ EX. 1021
`
`

`
`CONTENTS
`
`2.3.2 Higher—Order Homophonics
`Polyalphabetic Substitution Ciphers
`2.4.1 Vigenére and Beaufort Ciphers
`2.4.2
`index of Coincidence
`77
`2.4.3 Kasiski Method
`
`79
`
`72
`73
`
`74
`
`83
`Ftunning—Key Ciphers
`2.4.4
`84
`2.4.5 Rotor and Hagelin Machines
`2.4.6 Vernam Cipher and 0ne—Time Pads
`Polygram Substitution Ciphers
`87
`2.5.1
`Playtair Cipher
`87
`88
`2.5.2
`Hill Cipher
`90
`Product Ciphers
`2.6.1
`Substitution-Permutation Ciphers
`2.6.2 The Data Encryption Standard (DES)
`2.6.3
`Time—Memory Tradeofl
`98
`Exponentiation ciphers
`101
`103
`2.7.1
`Pohlig-Hellman Scheme
`2.7.2 Hivest-Shamir-Adieman (PISA) Scheme
`2.7.3 Mental Poker
`110
`2.7.4 Oblivious Transfer
`
`1 15
`
`90
`
`86
`
`92
`
`104
`
`117
`Knapseck Ciphers
`118
`2.8.1 Merkle-Hellman Knapsacks
`121
`2.8.2 Graham-Shemir Knapsacks
`2.8.3
`Shamir Signature-Only Knapsacks
`2.8.4
`A Breakable NP—Complete Knapsack
`Exercises
`126
`References
`129
`
`122
`125
`
`CRYPTOGRAPHIC TECHNIQUES
`135
`3.1 Block and Stream Ciphers
`138
`3.2
`Synchronous Stream Ciphers
`3.2.1
`Linear Feedback Shift Registers
`3.2.2 Output-Block Feedback Mode
`3.2.3 Counter Method
`143
`
`135
`
`139
`142
`
`144
`
`149
`
`Self-Synchronous Stream ciphers
`3.3.1 Autokey Ciphers
`145
`3.3.2 Cipher Feedback
`145
`Block Ciphers
`147
`3.4.1 Block Chaining and Cipher Block Chaining
`3.4.2 Block Ciphers with Subkeys
`151
`Endpoints of Encryption
`154
`3.5.1
`End-to-End versus Link Encryption
`3.5.2
`Privacy Homomorphisms
`157
`One-Way Ciphere
`161
`3.6.1
`Passwords and User Authentication
`
`154
`
`181
`
`11/73
`
`DOJ EX. 1021
`
`

`
`CONTENTS
`
`164
`3.? Key Management
`164
`3.7.1
`Secret Keys
`169
`3.7.2
`Public Keys
`3.7.3 Generating Block Encryption Keys
`3.7.4 Distribution ot Session Keys
`Threshold Schemes
`179
`3.8.1
`Lagrange interpolating Polynomial Scheme
`3.8.2
`congruence Class Scheme
`183
`Exercises
`135
`Fteferenoes
`167
`
`173
`
`1?1
`
`180
`
`191
`
`207
`
`ACCESS CONTROLS
`192
`4.1 Access-Matrix Model
`4.1.1
`The Protection State
`4.1.2 State Transitions
`4.1.3 Protection Policies
`Access Control Mechanisms
`4.2.1
`Security and Precision
`4.2.2 Reliability and Sharing
`4.2.3 Design Principles
`Access Hierarchies
`4.3.1
`Privileged Modes
`4.3.2 Nested Program Units
`Authorization Lists
`209
`4.4.1 Owned Objects
`4.4.2 Revocation
`
`192
`
`194
`199
`200
`200
`201
`
`206
`
`207
`
`208
`
`210
`
`213
`
`216
`Capabilities
`4.5.1 Domain Switching with Protected Entry Points
`4.5.2 Abstract Data Types
`219
`4.5.3 Capability—Based Addressing
`4.5.4 Revocation
`227
`
`224
`
`218
`
`228
`230
`231
`232
`
`4.5.5 Locks and Keys
`4.5.6 Query Modification
`Verifiably Secure Systems
`4.6.1
`Security Kernels
`4.6.2 Levels of Abstraction
`4.6.3 Verification
`236
`240
`Theory of Safe Systems
`4.7.1 Mono-Operational Systems
`4.7.2 General Systems
`242
`4.7.3 Theories for General Systems
`4.7.4 Take-Grant Systems
`248
`Exercises
`257
`References
`259
`
`235
`
`241
`
`245
`
`12/73
`
`DOJ EX. 1021
`
`

`
`CONTENTS
`
`267
`
`265
`265
`265
`
`276
`
`281
`
`279
`
`282
`
`INFORMATION FLOW CONTROLS
`5.1
`Lattice Model of Information Flow
`5.1.1
`Information Flow Policy
`5.1.2
`information State
`266
`5.1.3
`State Transitions and information Flow
`5.1.4
`Lattice Structure
`2T3
`5.1.5
`Flow Properties of Lattices
`Flow Control Mechanisms
`2?9
`5.2.1
`Security and Precision
`5.2.2 Channels of Flow
`Execution-Based Mechanisms
`5.3.1
`Dynamically Enforcing Security for Implicit Flow
`285
`Flowvsecure Access Controls
`5.3.2
`5.3.3 Data Mark Machine
`288
`5.3.4
`Single Accumulator Machine
`Compiler—Based Mechanism
`291
`5.4.1
`Flow Specifications
`292
`5.4.2 Security Requirements
`293
`5.4.3 Certification Semantics
`29?
`General Data and Control Structures
`5.4.4
`5.4.5 Concurrency and Synchronization
`5.4.6 Abnormal Terminations
`305
`Program Verification
`30?
`5.5.1 Assignment
`309
`5.5.2 Compound
`310
`5.5.3 Alternation
`31 1
`5.5.4
`Iteration
`312
`5.5.5 Procedure Call
`5.5.6
`Security
`316
`Flow Controls in Practice
`
`290
`
`298
`302
`
`313
`
`318
`
`System Verification
`5.6.1
`5.6.2 Extensions
`320
`
`5.6.3
`Exercises
`References
`
`A Guard Application
`324
`32?
`
`318
`
`321
`
`INFERENCE CONTROLS
`6.1
`Statistical Database Model
`6.1.1
`Information State
`6.1.2
`6.1.3
`
`334
`Types of Statistics
`Disclosure of Sensitive Statistics
`
`331
`
`332
`332
`
`6.1.4 Perfect Secrecy and Protection
`6.1.5 Complexity of Disclosure
`339
`Inference Control Mechanisms
`340
`
`6.2.1
`
`Security and Precision
`
`340
`
`13/73
`
`DOJ EX. 1021
`
`

`
`CONTENTS
`
`6.2.2 Methods of Release
`Methods of Attack
`344
`6.3.1
`Smail and Large Query Set Attacks
`6.3.2 Tracker Attacks
`346
`
`341
`
`344
`
`6.3.3 Linear System Attacks
`6.3.4 Median Attacks
`356
`6.3.5
`Insertion and Deletion Attacks
`Mechanisms that Restrict Statistics
`
`352
`
`358
`358
`
`Cell Suppression
`6.4.1
`Implied Queries
`6.4.2
`368
`Partitioning
`6.4.3
`Mechanisms that Add Noise
`
`360
`364
`
`371
`
`6.5.1 Response Perturbation (Rounding)
`6.5.2 Random-Sample Queries
`374
`6.5.3 Data Perturbation
`380
`
`383
`6.5.4 Data Swapping
`6.5.5 Randomized Response (Inquiry)
`Summary
`387
`6.6
`Exercises
`References
`INDEX 393
`
`388
`390
`
`333
`
`14/73
`
`DOJ EX. 1021
`
`

`
`15/73
`
`DOJ EX. 1021
`
`

`
`Introduction
`
`1.1 CRYPTOGFIAPHY
`
`Cryptography is the science and study of secret writing. A cipher is a secret meth-
`od of' writing, whereby plaintext (or cleartext) is transformed into ciphertext
`(sometimes called a cryptograln). The process of transforming plaintext into ci-
`phertext is called enciplterment or encryption; the reverse process of transforming
`ciphertext into plaintext is called deciplnerment or decryption. Both encipherment
`and decipherment are controlled by a cryptographic key or keys (see Figure 1.1).
`There are two basic types of ciphers: transpositions and substitutions. Trans-
`position ciphers rearrange bits or characters in the data. With a “rail-fence”
`cipher, for example, the letters of a plaintext message are written down in a
`
`FIGURE 1.1 Secret writing.
`
`plaimext
`
`ciphertext
`
`16/73
`
`DOJ EX. 1021
`
`

`
`INTRODUCTION
`
`pattern resembling a rail fence, and then removed by rows. The following illus-
`trates this pattern:
`
`DISC ONC]:.RTED COMPOSER
`
`DORCOICNETDOPSRSCEME
`
`The key to the cipher is given by the depth of the fence. which in this example is 3.
`Substitution ciphers replace hits, characters, or blocks of characters with
`substitutes. A simple type of substitution cipher shifts each letter in the English
`alphabet forward by K positions (shifts past 2 cycle back to A); K is the key to the
`cipher. The cipher is often called a Caesar cipher because Julius Caesar used it
`with K = 3. The following illustrates Caesar’s method:
`TMPATIENT WAITER
`
`J.
`LPSDWLHQW ZDLWHU .
`
`A code is a special type of substitution cipher that uses a “code book” as the
`key. Plaintext words or phrases are entered into the code book together with their
`ciphertext substitutes, as shown next:
`Word
`Code
`BAKER
`1701
`FRETTING 5603
`
`LOAFING BAKER
`
`GUITARIST 4008
`LOA FING
`3790
`
`L
`
`3790 1701
`
`The term code is sometimes used to refer to any type of cipher.
`In computer applications, transposition is usually combined with substitu-
`tion. The Data Encryption Standard (DES), for example, cnciphers 64-bit blocks
`using a combination of transposition and substitution (see Chapter 2).
`C1-yptanalysis is the science and study of methods of breaking ciphers. A
`cipher is breakable if it is possible to determine the plaintext or key from the
`ciphertext, or to determine the key from plaintext-ciphertext pairs. There are three
`basic methods of attack: ciphertext-only, known-plaintcxt, and chosen-plaintext.
`Under a ciphertext-only attack, a cryptanalyst must determine the key solely
`from intercepted ciphertext, though the method of encryption, the plaintext lan-
`guage, the subject matter of the ciphcrtext, and certain probable words may be
`
`17/73
`
`DOJ EX. 1021
`
`

`
`DATA SECURITY
`
`known. For example. a message describing the location of a buried treasure would
`probably contain words such as BURIED, TREASURE, NORTH, TURN,
`RIGHT, MILES.
`Under a known-plaintext attack, a cryptanalyst knows some plair1text-
`ciphertext pairs. As an example, suppose an enciphered message transmitted from
`a user's terminal to the computer is intercepted by a cryptanalyst who knows that
`the message begins with a standard header such as “LOGlN". As another exam-
`ple, the cryptanalyst may know that the Department field of a particular record
`contains the ciphertext for Physics; indeed, the cryptanalyst may know the De-
`partment field of every record in the database. In some cases, knowledge of prob»
`able words allows a close approximation to a known-plaintext attack. Encrypted
`programs are particularly vulnerable because of the regular appearance of
`keywords—e.g. begin, end, var, procedure, if, then. Even if the exact position of
`encrypted keywords is unknown, a cryptanalyst may be able to make reasonable
`guesses about them. Ciphers today are usually considered acceptable only if they
`can withstand a known-plaintext attack under the assumption that the cryptana-
`lyst has an arbitrary amount of plaintext-ciphertext pairs.
`Under a chosen-plaintext attack, a cryptanalyst is able to acquire the cipher-
`text corresponding to selected plaintext. This is the most favorable case for the
`cryptanalyst. A database system may be particularly vulnerable to this type of
`attack if users can insert elements into the database, and then observe the changes
`in the stored ciphertext. Bayer and Metzger [Baye76] call this the planted record
`problem.
`Public—key systems (defined in Section 1.3) have introduced a fourth kind of
`attack: a chosen-ciphertext attack. Although the plaintext is not likely to be intelli-
`gible, the cryptanalyst may be able to use it to deduce the key.
`A cipher is unconditionally secure if, no matter how much ciphertext is inter-
`cepted, there is not enough information in the ciphertext to determine the plaintext
`uniquely. We shall give a formal definition of an unconditionally secure cipher in
`Section 1.4. With one exception, all ciphers are breakable given unlimited re-
`sources, so we are more interested in ciphers that are computationally infeasible to
`break. A cipher is computationally secure, or strong, if it cannot be broken by
`systematic analysis with available resources.
`The branch of knowledge embodying both cryptography and cryptanalysis is
`called cryptology.
`
`1.2 DATA SECURITY
`
`Classical cryptography provided secrecy for information sent over channels where
`eavesdropping and message interception was possible. The sender selected 3. cipher
`and encryption key. and either gave it directly to the receiver or else sent it indi-
`rectly over a slow but secure channel (typically a trusted courier). Messages and
`replies were transmitted over the insecure channel in ciphcrtext (see Figure 1.2).
`Classical encryption schemes are described in Chapter 2.
`Modern cryptography protects data transmitted over high-speed electronic
`
`18/73
`
`DOJ EX. 1021
`
`

`
`INTRODUCTION
`
`FIGURE 1.2 Classical information channel.
`
`Sender
`
`Receiver
`
`T? ciphertext -j-P
`
`insecure channel
`
`secure key distribution channel
`
`lines or stored in computer systems. There are two principal objectives: secrecy (or
`privacy). to prevent the unauthorized disclosure of data; and authenticity or integ-
`rity), to prevent the unauthorized modification of data.
`Information transmitted over electronic lines is vulnerable to passive wire-
`tapping, which threatens secrecy, and to active wiretapping. which threatens au-
`thenticity (see Figure 1.3). Passive wiretapping (eavesdropping) refers to the
`interception of messages, usually without detection. Although it is normally used
`to disclose message contents, in computer networks it can also be used to monitor
`traffic flow through the network to determine who is communicating with whom.
`Protection against disclosure of message contents is provided by enciphering trans-
`formations, which are described in Chapter 2, and by the cryptographic techniques
`described in Chapter 3. Protection against traflic flow analysis is provided by
`controlling the endpoints of encryption; this is discussed in Chapter 3.
`Active wiretapping (tampering) refers to deliberate modifications made to
`the message stream. This can be for the purpose of making arbitrary changes to a
`message, or of replacing data in a message with replays of data from earlier
`messages (e.g., replacing the amount field of a transaction “CREDIT SMlTH’S
`ACCOUNT WITH $10“ with the amount field of an earlier transaction “CRED-
`IT JONES’S ACCOUNT WITH $5000”). It can be for the purpose of injecting
`false messages, injecting replays of previous messages (e.g., to repeat a credit
`transaction), or deleting messages (eg, to prevent a transaction “DEDUCT
`$1000 FROM SMITH’S ACCOUNT"). Encryption protects against message
`
`FIGURE 1.3 Threats to secure communication.
`
`sender
`
`insecure channel
`
`receiver
`
`passive wiretapping
`
`active wiretapping
`
`19/73
`
`DOJ EX. 1021
`
`

`
`DATA SECURITY
`
`modification and injection of false messages by making it infeasible for an oppo-
`nent to create ciphertext that deciphcrs into meaningful plaintext. Note, however,
`that whereas it can be used to detect message modification, it cannot prevent it.
`Encryption alone does not protect against replay, because an opponent could
`simply replay previous ciphertext. Cryptographic techniques for protecting against
`this problem are discussed in Chapter 3. Although encryption cannot prevent
`message deletion, the cryptographic techniques discussed in Chapter 3 can detect
`deletions of blocks or characters within a message stream. Deletion of entire mes-
`sages can be detected with communication protocols that require message
`acknowledgment.
`
`FIGURE 1.4 Threats to data stored in computer systems.
`
`Computer system
`
`modifying
`
`replaying
`
`inserting
`
`faulty
`program
`
`overwritmg
`
`browsing
`
`\
`con fidenlial
`data
`\
`\
`
`inference
`
`unclassified
`user
`
`20/73
`
`DOJ EX. 1021
`
`

`
`INTRODUCTION
`
`Data in computer systems is vulnerable to similar threats (see Figure 1.4).
`Threats to secrecy include browsing, leakage, and inference. Browsing refers to
`searching through main memory or secondary storage for information (e.g., confi-
`dential data or proprietary software programs). It is similar to eavesdropping on
`communication channels, but there are two important differences. On the one
`hand, information stored in computer systems has a longer lifetime; in this sense,
`browsing poses a more serious threat than eavesdropping. On the other hand,
`information transmitted over electronic lines is vulnerable to tapping even when
`access to the system is denied. Browsing is possible only if the user has access to
`the system and to unauthorized regions of memory. Access controls, described in
`Chapter 4, can prevent this.
`Cryptography protects against browsing by making the information unintel-
`ligible. It can supplement access controls and is especially useful for protecting
`data on tapes and discs which, if stolen, can no longer be protected by the system.
`Cryptography cannot, however, protect data from disclosure while it is being pro-
`cessed in the clear. Access controls are needed for this purpose, and these controls
`must include procedures that clear memory between use to ensure that confiden-
`tial data is not inadvertently exposed. If access is not controlled, encrypted data
`can also be vulnerable to eiphertext searching (e.g., finding employees making
`identical salaries by searching for records with identical ciphertext salaries); cryp-
`tographic solutions to this problem are described in Chapter 3.
`Leakage refers to the transmission of data to unauthorized users by processes
`with legitimate access to the data. A compiler, for example, could leak a propri-
`etary software program while it is being compiled. An income tax program could
`leak confidential information about a user. A file editor could leak classified mili~
`
`tary data to a user without a security clearance. Cryptography and access controls
`must be supplemented with information flow controls, discussed in Chapter 5, to
`control information dissemination.
`
`[nference refers to the deduction of confidential data about a particular
`individual by correlating released statistics about groups of individuals. For exam-
`ple,
`if Smith is the only non-Ph.D. faculty member in a Physics department,
`Smith’s salary can be deduced by correlating the average salary of all faculty in
`the department with the average salary of all Ph.D. faculty in the department.
`Although cryptography and access controls can protect
`the data records from
`browsing, they do not provide a mathematical framework for determining which
`statistics can be released without disclosing sensitive data. Inference controls, dis-
`cussed in Chapter 6, address this problem.
`Threats to authenticity include tampering and accidental destruction. Tam-
`pering with data in computer systems is analogous to active wiretapping on com-
`munication channels, but differs from it in the same ways browsing differs from
`passive wiretapping. Like active wiretapping, tampering can be for the purpose of
`making arbitrary changes to data (e.g., changing the Salary field of an employee
`record from $20,000 to $25,000). It can be for the purpose of replaying data stored
`previously in a record (e.g., to restore a previous balance in an accounting record),
`or replaying data stored in some other record (e.g., to make the Salary field of an
`employee record the same as that of a higher paid employee). It can also be for the
`
`21/73
`
`DOJ EX. 1021
`
`

`
`CFIYPTOGFIAPHIC SYSTEMS
`
`purpose of overwriting data with nonsense (e.g., overwriting a cryptographic key
`so that encrypted data becomes inaccessible). Finally, it can be for the purpose of
`inserting records (c.g., adding a dummy employee record to the payroll file) or
`deleting files or records (e.g., to remove a bad credit report). Cryptographic tech-
`niques can help protect against these threats by making it possible to detect false
`or replayed ciphertext. But it cannot prevent them. Access controls are essential
`for the reliable operation of the system. Backup is vital for recovery.
`Accidental destruction refers to the unintentional overwriting or deletion of
`data. Unintentional overwriting is caused by faulty software (e.g., because an
`array subscript is out-of-range). Cryptography cannot protect against this threat.
`Access controls,
`implemented in language processors and in hardware, provide
`error confinement by preventing programs from writing into the memory regions
`of other programs or into system tables. Unintentional deletion is caused by soft-
`ware or hardware failure (e.g., a disk head crash), and by user mistakes (e.g.,
`inadvertently deleting lines of a file during an editing session). Backup is needed to
`recover from accidental as well as deliberate destruction. Many text editors have
`automatic backup facilities so that an earlier version of a file is easily recovered;
`some have facilities for undoing each editing command.
`Computer systems are vulnerable to another problem: masquerading. If an
`intruder can gain access to a system under another user’s account, then the intrud-
`er can access the user’s data files and all other information permitted to the user.
`Similarly, if a program can spoof legitimate users logging into the system into
`believing that they are conversing with the system, the program might be able to
`obtain confidential information from these users (e.g., their login passwords). Pro-
`tection against masquerading requires that the system and user be able to mutual-
`ly authenticate each other. Such strategies that use encrypted passwords are
`described in Chapter 3. “Digital signatures” provide a more general means of
`authenticating users or processes; they are introduced in Section 1.3.3.
`Data security is the science and study of methods of protecting data in
`computer and communications systems. It embodies the four kinds of controls
`studied in this book: cryptographic controls. access controls, information flow con-
`trols, and inference controls. it also embodies procedures for backup and recovery.
`
`1.3 CRYPTOGRAPHIC SYSTEMS
`
`This section describes the general requirements of all cryptographic systems, the
`specific properties of public-key encryption, and digital signatures.
`A cryptographic system (or cryptosystem for short) has five components:
`
`A plaintext message space, 7?}.
`A ciphertext message space, if.
`A key space, X
`A family of enciphering transformations, Ex: ‘fit -> C’, where K c J(.
`A family of deciphering transformations. DK: C’ —* M, where K 5 J('.
`
`22/73
`
`DOJ EX. 1021
`
`

`
`FIGURE 1.5 Cryptographic system.
`
`INTFlODUCTiON
`
`plaintext
`
`oiphertext
`
`plain text
`
`Each enciphering transformation EX is defined by an enciphering algorithm
`E, which is common to every transformation in the family, and a key K, which
`distinguishes it from the other transformations. Similarly. each deciphering trans-
`formation DK is defined by a deciphering algorithm .0 and a key K. For a given K,
`D‘ is the inverse of E‘; that is, DK(EK(M)) = M for every plaintext message M. In
`a given cryptographic system, the transformations ER and DK are described by
`parameters derived from K (or directly by K). The set of parameters describing Ex
`is called the enciphering key, and the set of parameters describing DK the decipher-
`ing key. Figure 1.5 illustrates the enciphering and deciphering of data.
`Cryptosystems must satisfy three general requirements:
`
`The enciphering and deciphering transformations must be efiicient for all
`keys.
`The system must be easy to use.
`The security of the system should depend only on the secrecy of the keys and
`not on the secrecy of the algorithms E or D.
`
`Requirement (1) is essential for computer applications; data is usually enciphcred
`and deciphered at the time of transmission. and these operations must not be
`bottlenecks. Requirement (2) implies it must be easy for the cryptographer to find
`a key with an invertible transformation. Requirement (3) implies the enciphering
`and deciphering algorithms must be inherently strong; that is, it should not be
`possible to break a cipher simply by knowing the method of enciphermcnt. This
`requirement is needed because the algorithms may be in the public domain or
`known to a cryptanalyst. whence knowing K reveals EK and DK. Note, however, the
`converse need not hold; that is, knowing EX or DK need not reveal K. This is
`because the enciphering key describing EX or the deciphering key describing DK
`could be derived from K by a one-way (irreversible) transformation (see Section
`1.5.3). This technique is used in public-key systems (see Section 1.3). We shall
`assume the algorithms E and D are public knowledge.
`There are specific requirements for secrecy and authenticity. Secrecy re-
`quires that a cryptanalyst not be able to determine plaintext data from intercepted
`ciphertext. Formally, there are two requirements:
`
`Secrecy requirements
`It should be computationally infeasible for a cryptanalyst to systematically
`determine the deciphcrin g transformation DK from intercepted ciphertext C,
`even if the corresponding plaintext M is known.
`
`23/73
`
`DOJ EX. 1021
`
`

`
`CHYPTOGRAPHIC SYSTEMS
`
`2.
`
`It should be computationally infeasible for a cryptanalyst to systematically
`determine plaintext M from intercepted ciphertext C.
`
`Requirement (1) ensures that a cryptanalyst cannot systematically determine the
`deciphering transformation (guessing may be possible). Thus, the cryptanalyst will
`be unable to decipher C or other ciphertext enciphered under the transformation
`EX. Requirement (2) ensures that a cryptanalyst cannot systematically determine
`plaintext without the deciphering transformation. Both requirements should hold
`regardless of the length or number of ciphertext messages intercepted.
`Secrecy requires only that the transformation DK (i.e., the deciphering key)
`be protected. The transformation E, can be revealed if it does not give away DK.
`Figure 1.6 illustrates. The straight line shows the intended flow through the sys-
`tem, while the bent line shows the undesired flow that results from successful
`attacks.
`
`Data authenticity requires that a cryptanalyst not be able to substitute a
`false ciphertext C’ for a ciphertext C without detection. Formally, the two require-
`ments are:
`
`Authenticity requirements
`It should be computationally infeasible for a cryptanalyst to systematically
`determine the encipheriug transformation Ex given C, even if the correspond-
`ing plaintext M is known.
`It should be computationally infeasible for a cryptanalyst to systematically
`find ciphertext C’ such that DX(C’) is valid plaintext in the set ‘Vii.
`
`Requirement (1) ensures that a cryptanalyst cannot systematically determine the
`enciphering transformation. Thus the cryptanalyst will be unable to encipher a
`different plaintext message M ', and substitute the false eiphertext C’ = EK(M’)
`for C. Requirement (2) ensures that a cryptanalyst cannot find ciphertext C’