`
`Page 1 0f 86
`
`GOOGLE EXHIBIT 1024
`
`Page 1 of 86
`
`GOOGLE EXHIBIT 1024
`
`

`

`Cryptography and 13ata Security Dorothy Elizabeth Rob, ling Denning
`
`PURDUE UNIVERSITY
`
`A VV
`ADDISON-WESLEY PUBLISHING COMPANY
`Reading, Massachusetts [] Menlo Park, California
`London II
`Amsterdam • Don Mills, Ontario I Sydney
`
`Page 2 of 86
`
`

`

`Library of Congress Cataloging in Publication Data
`
`Denning, Dorothy E., (Dorothy Elizabeth), 1945-
`Cryptography and data security.
`Includes bibliographical references and index.
`1. Computers--Access control. 2. Cryptography.
`3. Data protection. 1. Title.
`QA76.9.A25D46
`1 9 8 2
`001.64'028'9
`ISBN 0-201-10150-5
`
`81-15012
`AACR2
`
`Copyright © 1982 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-201-10150-5
`A BCDE FG H I J-M A-898765432
`
`Page 3 of 86
`
`

`

`In memory of my Father,
`
`Cornelius Lowell Robling
`
`1910-1965
`
`Page 4 of 86
`
`

`

`
`
`Page 5 of 86
`
`

`

`Electronic computers have evolved from exiguous experimental enterprises in the
`1940s to prolific practical data processing systems in the 1980s. 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 difticult 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
`
`Page 6 of 86
`
`Preface
`

`

`vi
`
`PREFACE
`
`cryptographic controls into operating systems and database systems. I hope to
`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:
`
`introduces the basic concepts of cryptography, data
`security, information theory, complexity theory, and number theory.
`describes both classical and modern
`encryption algorithms, including the Data Encryption Standard (DES) and
`public-key algorithms.
`
`studies various techniques related to
`integrating cryptographic controls into computer systems, including key
`management.
`
`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.
`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.
`
`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
`Dime, 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, Ttire Dalenius, George Davida, Dave Gifford,
`Carl Hammer, Mike Harrison, Chris Hoffmann, Stephen Matyas, Glen Myers,
`Bob Morris, Steve Reiss, Ron Rivest, Jan Schlt~rer, Gus Simmons, and Larry
`Snyder. These people gave generously of their time to help make this a better
`book.
`
`Page 7 of 86
`
`Chapter 1, Introduction,
`Chapter 2, Encryption Algorithms,
`Chapter 3, Cryptographic Techniques,
`Chapter 4, Access Controls,
`Chapter 5, Information Flow Controls,
`Chapter 6, Inference Controls,
`

`

`PREFACE
`
`vii
`
`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 Liesenfelt, Paul Morrisett, Tim Nodes,
`Bhasker Parthasarathy, Steve Pauley, Alan Pieramico, Steve Raiman, Dan Reed,
`David Rutkin, Paul Scherf, Carl Smith, Alan 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 Schwetman, 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 Goodell, Cheryl Wurzbacher, and Judith Gimple.
`I am especially grateful to my husband, Peter, for his encouragement, sup-
`port, advice, and help throughout.
`
`Page 8 of 86
`
`

`

`
`
`Page 9 of 86
`
`

`

`7
`
`11
`14
`
`17
`
`INTRODUCTION
`1
`Cryptography
`1.1
`3
`Data Security
`1.2
`Cryptographic Systems
`1.3
`1.3.1 Public-Key Systems
`1.3.2 Digital Signatures
`Information Theory
`16
`1.4.1 Entropy and Equivocation
`1.4.2 Perfect 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 Congruences and Modular Arithmetic
`1.6.2 Computing Inverses
`39
`1.6.3 Computing in Galois Fields
`Exercises
`54
`References
`56
`
`1.4
`
`1.5
`
`1.6
`
`36
`
`48
`
`34
`
`ix
`
`59
`
`ENCRYPTION ALGORITHMS
`59
`2.1 Transposition Ciphers
`62
`2.2 Simple Substitution Ciphers
`2.2.1 Single-Letter Frequency Analysis
`2.3 Homophonic Substitution Ciphers
`67
`2.3.1 Beale Ciphers
`70
`
`66
`
`Page 10 of 86
`
`Contents
`

`

`2.4
`
`2.5
`
`2.6
`
`2.7
`
`2.8
`
`2.3.2 Higher-Order Homophonics
`Polyalphabetic Substitution Ciphers
`2.4.1 Vigen6re and Beaufort Ciphers
`2.4.2
`Index of Coincidence
`77
`Kasiski Method
`79
`2.4.3
`83
`Running-Key Ciphers
`2.4.4
`84
`Rotor and Hagelin Machines
`2.4.5
`Vernam Cipher and One-Time Pads
`2.4.6
`Polygram Substitution Ciphers
`87
`2.5.1 Playfair 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 Tradeoff
`98
`Exponentiation Ciphers
`101
`103
`2.7.1 Pohlig-Hellman Scheme
`2.7.2 Rivest-Shamir-Adleman (RSA) Scheme
`2.7.3 Mental Poker
`110
`2.7.4 Oblivious Transfer
`Knapsack Ciphers
`117
`118
`2.8.1 Merkle-Hellman Knapsacks
`121
`Graham-Shamir Knapsacks
`2.8.2
`Shamir Signature-Only Knapsacks
`2.8.3
`A Breakable NP-Complete Knapsack
`2.8.4
`126
`Exercises
`129
`References
`
`72
`73
`74
`
`CONTENTS
`
`86
`
`90
`
`92
`
`104
`
`122
`125
`
`115
`
`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
`Self-Synchronous Stream Ciphers
`3.3.1 Autokey Ciphers
`145
`3.3.2 Cipher Feedback
`145
`147
`Block Ciphers
`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 Ciphers
`161
`3.6.1 Passwords and User Authentication
`
`135
`
`139
`142
`
`144
`
`149
`
`154
`
`161
`
`3.3
`
`3.4
`
`3.5
`
`3.6
`
`Page 11 of 86
`
`

`

`CONTENTS
`
`xi
`
`3.7
`
`3.8
`
`164
`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 of Session Keys
`173
`Threshold Schemes
`179
`Lagrange Interpolating Polynomial Scheme
`3.8.1
`Congruence Class Scheme
`183
`3.8.2
`185
`Exercises
`187
`References
`
`171
`
`180
`
`218
`
`192
`194
`199
`200
`200
`201
`
`206
`
`207
`
`208
`
`210
`
`213
`
`191
`ACCESS CONTROLS
`192
`4.1 Access-Matrix Model
`4.1.1 The Protection State
`4.1.2 State Transitions
`4.1.3 Protection Policies
`4.2 Access Control Mechanisms
`4.2.1 Security and Precision
`4.2.2 Reliability and Sharing
`4.2.3 Design Principles
`4.3 Access Hierarchies
`207
`4.3.1 Privileged Modes
`4.3.2 Nested Program Units
`4.4 Authorization Lists
`209
`4.4.1 Owned Objects
`4.4.2 Revocation
`4.5 Capabilities
`216
`Domain Switching with Protected Entry Points
`4.5.1
`Abstract Data Types
`219
`4.5.2
`Capability-Based Addressing
`4.5.3
`Revocation
`227
`4.5.4
`Locks and Keys
`4.5.5
`4.5.6 Query Modification
`4.6 Verifiably Secure Systems
`4.6.1 Security Kernels
`4.6.2
`Levels of Abstraction
`4.6.3 Verification
`236
`240
`4.7 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
`
`228
`230
`231
`232
`
`235
`
`224
`
`241
`
`245
`
`Page 12 of 86
`
`

`

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

`

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

`

`
`
`Page 15 of 86
`
`

`

`1 Introduction
`
`1.1 CRYPTOGRAPHY
`
`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 cryptogram). The process of transforming plaintext into ci-
`phertext is called encipherment or encryption; the reverse process of transforming
`ciphertext into plaintext is called decipherment or deeryption. 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.
`
`plaintext
`
`key
`
`ciphertext
`
`Page 16 of 86
`
`1
`1
`

`

`2
`
`INTRODUCTION
`
`pattern resembling a rail fence, and then removed by rows. The following illus-
`trates this pattern:
`
`DISCONCERTED COMPOSER
`
`D
`
`0
`
`C
`
`N
`
`R
`
`E
`
`T
`
`C
`
`D
`
`O
`
`O
`
`P
`
`M
`
`E
`
`C
`
`I
`
`S
`
`E
`
`DO RCOICNETDOPS RSCEM E
`
`The key to the cipher is given by the depth of the fence, which in this example is 3.
`Substitution ciphers replace bits, 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 Z 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:
`IMPATIENT WAITER
`
`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
`FRETTING
`GUITARIST
`LOAFING
`
`5603
`4008
`3790
`
`LOAFING BAKER
`
`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, enciphers 64-bit blocks
`using a combination of transposition and substitution (see Chapter 2).
`Cryptanalysis 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-plaintext, and chosen-plaintext.
`Under a eiphertext-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 ciphertext, and certain probable words may be
`
`Page 17 of 86
`
`S R
`1701
`

`

`DATA SECURITY
`
`3
`
`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 plaintext-
`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 "LOGIN". As another exam-
`ple, the cryptanalyst may know that the Department
`field of a particular record
`indeed, the cryptanalyst may know the De- partment
`contains the ciphertext for Physics;
`field of every record in thedatabase. 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
`keywordsue.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 ehosen-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
`
`Public-key systems (defined in Section 1.3) have introduced a fourth kind of
`attack: a chosen-eiphertext 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 eryptology.
`
`1.2 DATA SECURITY
`
`Classical cryptography provided secrecy for information sent over channels where
`eavesdropping and message interception was possible. The sender selected a 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 ciphertext (see Figure 1.2).
`Classical encryption schemes are described in Chapter 2.
`Modern cryptography protects data transmitted over high-speed electronic
`
`Page 18 of 86
`
`problem.
`

`

`4
`
`FIGURE 1.2 Classical information channel.
`
`Sender
`
`Receiver
`
`plaintext
`
`ciphertext
`insecure channel
`
`INTRODUCTION
`
`plaintext
`
`key'
`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 traffic 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 SMITH'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 (e.g., 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
`
`Page 19 of 86
`
`7
`

`

`DATA SECURITY
`
`5
`
`modification and injection of false messages by making it infeasible for an oppo-
`nent to create ciphertext that deciphers 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
`
`overwriting
`
`P
`classified
`data
`
`browsing
`
`"'"k__
`
`confidential
`data
`
`statistic
`
`inference
`
`leaking
`
`r
`unclassified
`user
`
`modifying
`
`replaying
`
`inserting
`
`deleting
`
`Page 20 of 86
`
`FT]
`

`

`6
`
`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 ciphertext 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.
`Inference 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
`
`Page 21 of 86
`
`

`

`CRYPTOGRAPHIC 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 (e.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.
`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.
`If an
`Computer systems are vulnerable to another problem: masquerading.
`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.
`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-
`trois, 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:
`
`1. A plaintext message space, if/. 2. A ciphertext message space, C. 3. A key space, .K. 4. A family of enciphering transformations, EK: ~ ~ C, where K ~ .K. 5. A family of deciphering transformations, DK: C ~ ~, where K ~ .K.
`
`Page 22 of 86
`
`Accidental destruction
`Data security
`

`

`8
`
`INTRODUCTION
`
`FIGURE 1.5 Cryptographic system.
`
`plaintext
`
`ciphertext
`
`plaintext
`
`E K is defined by an enciphering algorithm
`Each enciphering transformation
`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 D K
`is defined by a deciphering algorithm
`D and a key K. For a given K,
`D K is the inverse of EK; that is, DK(EK(M )) = M
`for every plaintext message M. In
`a given cryptographic system, the transformations E K and D K are described by
`parameters derived from K (or directly by K). The set of parameters describing E K
`
`and the set of parameters describing D K the decipher- ing key. is called the enciphering key,
`Figure 1.5 illustrates the enciphering and deciphering of data.
`Cryptosystems must satisfy three general requirements:
`
`1.
`
`2.
`3.
`
`The enciphering and deciphering transformations must be efficient 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 enciphered
`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 encipherment. This
`requirement is needed because the algorithms may be in the public domain or
`known to a cryptanalyst, whence knowing K reveals E g and D g. Note, however, the
`converse need not hold; that is, knowing E g or DE need not reveal K. This is
`because the enciphering key describing E g or the deciphering key describing D x
`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:
`
`It should be computationally infeasible for a cryptanalyst to systematically
`determine the deciphering transformation D K from intercepted ciphertext C,
`even if the corresponding plaintext M is known.
`
`Page 23 of 86
`
`Secrecy requirements
`

`

`CRYPTOGRAPHIC SYSTEMS
`
`,
`
`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
`E g. 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 on