1. Review and Overview 2. Deadlocks 3. Distributed Systems Architecture 4. Theoretical Foundations 5. Distributed Mutual Exclusions

6. Agreement Protocols 7. Distributed Resource Management 8. Distributed Scheduling 9. Secutiry and Protection 10. Recovery and Fault Tolerance

No steam or gas ever drives anything until it is confined.
No life ever grows great until it is focused, dedicated, disciplined.

						Henry Emerson Fosdick

1. Potential Information Security Violations
   • Unauthorized information release
   • Unauthorized information modification
   • Unauthorized denial of service

2. Aspects of Security
   • external ( physical ) = access to computer system
   • internal = allowed actions within the computer system
     • policies - what should be done
     • mechanisms - how it should be done
       including protection mechanisms
   • authentication = verification of user's identity
   • implemenations:
     Writing a new OS from scratch costs too much
     Getting people to use a new OS is difficult
     New OS technology is adopted if it can be added onto an existing OS
     Otherwise, it is not adopted
     How to implement security?
     Security kernel
   • Access lists vs. capability lists
     access list ~ reservation ( e.g. party in Chuckecheese )
     capability list ~ ticket ( e.g. theater ticket )

3. Protection versus Security
   • protection -- mechanisms
     e.g., putting locks on doors
   • security -- policies,
     which specify how protection mechanisms are to be used
     e.g., who gets keys? when are doors locked?
   • protection domain of a process
     • resources process can access
     • operations it can perform on those resources
     • good policy is to restrict domain to what is needed

4. Design Principles
   • economy - overhead should be tolerable
   • complete mediation - all requests are checked
   • open design - does not depend on attacker's ignorance
   • separation of privileges -- requiring two keys is more robust
   • least privilege -- process given bare minimum right to finish
   • least common mechanism -- mechanisms common to two users should be minimized
   • acceptability -- simple to use
   • fail-safe defaults -- default should mean lack of access

5. Access Matrix Model

   A model of protection abstracts the essential features of a protection system so that various properties of it can be proven.

   • O = current objects -- finite set of entities to which access is to be controlled, e.g., a file, a process
   • S = current subjects -- finite set of entities that access current objects, e.g., a process
   note: S O
   • R = generic rights, R = { r₁, r₂, ..., r_m } e.g., read, write, execute, delete
   • P = access matrix, indexed by (subject, object)
   • Protection state of a system = ( S, O, P )
   • P(s, o) R

   • Enforcement of Model
     Every object has a monitor that validate all accesses to that object in the following manner:
     1. A subject s requests an access α to object o.
     2. The protection system presents triplet ( s, α, o ) to the monitor of o.
     3. The monitor looks into the access rights of s to o. If α ∈ P(s, o), then the access is permitted, otherwise it is denied

   • Example of Access Matrix

     	o1	o2	s1	s2	s3
     s1	read, write	own, delete	own	sendmail	recmail
     s2	execute	copy	recmail	own	block, wakeup
     s3	own	read, write	sendmail	block, wakeup	own

   • Implementation Methods
     • capability list = collapsed row of access matrix
     • access control list = collapsed column of access matrix
     • lock-key = combination

6. Capabilities
   • capability = tuple (o, P(s,o))
   • each subject has a set of capabilities
   • posession of capability confers access rights
   • Capability Based Addressing:

     A schematic view of a capability

     Object descriptor Access rights

     read, write, execute, etc.

     The object descriptor can be the address of the corresponding objects and therefore, aside from providing protection, capabilities can also be used as an addreessing mechanism by the system.

     A user program issues a request to access a word within an object. The address of the request contains the capability ID of the object and an offset within the object.

     

     How does this relate to segmented/paged virtual memory?

   • Implementing Capabilities
     • tagged memory -- one or more bits are attached to memory location or register to indicate if it contains a capability
     • partitioned memory -- capabilities and ordinary data are saved separately

   • Capability Pros & Cons
     • efficiency - no need to explicit check permissions for each access
     • simplicity - a single mechanism, based on adressability
     • flexibility - can control access by granting capabilities
     • propagation control - can pass on rights
     • review - who currently has rights?
     • revocation - cannot revoke rights
     • garbage collection - when can object be reclaimed?

7. Access Control List
   • list contains pairs (s, P(s,o))
   • when subject s requests access a of object o
     • search ACL of o for entry corresponding to s
     • check whether this entry contains a
   • ACL Example:

     Subjects	Access Rights
     Arnold	read, write, execute
     George	read
     Michael	write
     Tong	execute
     Smith	read, write

   • ACL Pros & Cons
     • slow access time
     • difficult review of accessibility, by subject
     • easy revocation
     • easy review of acessibility, by object
     • amenable to protection groups, which saves storage
     • right to change protections easily controlled

   • Changing Protections
     • self control -- by owner, the control is centralized to one process
       
     • hierarchical control -- with a tree of processes; the owner specifies a set of other processes which have the right to modify the access control list of the new object

8. The Lock-Key Method
   • each subject has capability list of tuples (o,k),
     where k is a key
   • each object has ACL of tuples (k,A),
     where A is a set of access modes
   • when s wants access a of object o
     • find a tuple (o,k) in s's capability list ( if not found, access is declined )
     • find a matching tuple (k,A) in o's ACL,
       such that a ∈ A.
   • revocation is easy

9. Encryption

   To provide data security. Store and transmit information in an encoded form that does not make any sense.

   The basic mechanism:

   • Start with text to be protected. Initial readable text is called clear text ( or plain text ).
   • Encrypt the clear text so that it does not make any sense at all. The nonsense text is called cipher text. The encryption is controlled by a secret password or number; this is called the encryption key.
   
   
   
   • The encrypted text can be stored in a readable file, or transmitted over unprotected channels.
   • To make sense of the cipher text, it must be decrypted back into clear text. This is done with some other algorithm that uses another secret password or number, called the decryption key.
   
   
   

   All of this only works under three conditions:

   • The encryption function cannot easily be inverted (cannot get back to clear text unless you know the decryption key).
   • The encryption and decryption must be done in some safe place so the clear text cannot be stolen.
   • The keys must be protected. In most systems, can compute one key from the other (sometimes the encryption and decryption keys are identical), so cannot afford to let either key leak out.

   Public key encryption: new mechanism for encryption where knowing the encryption key does not help you to find decryption key, or vice versa.

   • Consider an example:
     Question 1: What is the product of 31415926538979 x 31415926538979 ?
     Question 2: What is square root of 3912571506419387090594828508241 ?
   • User provides a single password, system uses it to generate two keys (use a one-way function, so cannot derive password from either key).
   • In these systems, keys are inverses of each other: could just as easily encrypt with decryption key and then use encryption key to recover clear text.
   • Each user keeps one key secret, publicizes the other. Cannot derive private key from public. Public keys are made available to everyone, in a phone book for example.

   Encryption procedure E and decryption procedure D must satisfy the following properties:

   1. for every message M, D(E(M)) = M
   2. E and D can be efficiently applied to any message M
   3. it is extremely hard to derive D from E

   e.g. Safe mail:

   • Use public key of destination user to encrypt mail.
   • Anybody can encrypt mail for this user and be certain that only the user will be able to decipher it.
   • It is a nice scheme because the user only has to remember one key, and all senders can use the same key. However, how does receiver know for sure who it is getting mail from?

   Does such a scheme exist?

   The RSA ( Rivest-Shamir-Adleman ) scheme:

   • encryption key is a pair ( e, n ) where e is a positive integer
   • a message block M is expressed as a value between 0 and n-1 inclusive
   • M is encrypted to give cipher text C by : C = M^e mod n ( note that C also lies between 0 and n - 1 )
   • the decryption key is a pair ( d, n ) where d is a positive integer
   • C is decrypted to M by: M = C^d mod n

     M →	Me mod n	C = Me mod n →→→→→→→→	Cd mod n	→ M
     	↑ ( e, n ) encryption key		↑ ( d, n ) decryption key

   • how to find the encryption and corresponding decryption keys?
     1. choose two large prime numbers p, q and calculate n by n = p x q
     2. choose any large integer as d so that the chosen d is relatively prime to ( p - 1) x ( q - 1 ). i.e. GCD( d, m ) = 1, where m = ( p - 1 ) x ( q - 1 )
     3. Compute e as the multiplicative inverse of d: e x d = 1 mod m

   • Example:
     Assume p = 5 and q = 11. Thus, n = 55,
     m = ( p - 1 ) x ( q - 1 ) = 4 x 10 = 40
     We choose d = 23 because 23 is relatively prime to 40
     We need to choose e satisfying

     23 x e mod 40 = 1
     e = 7 satisfies the above equation
     Some sample computations:

     M	M7	encrypt: C = M7 mod 55	C23	decrypt: M = C23 mod 55
     8	209152	2	8388608	8
     9	4782969	4	70368744177664	9
     51	897410677851	6	789730223053602816	51

10. Digital Signatures

    Positive identification: can also use public keys to certify identity:

    • To certify your identity, use your private key to encrypt a text message, e.g. "I agree to pay Mary Wallace $100 per year for the duration of life."
    • You can give the encrypted message to anybody, and they can certify that it came from you by seeing if it decrypts with your public key. Anything that decrypts into readable text with your public key must have come from you! This can be made legally binding as a form of electronic signature.

    These two forms of encryption can be combined together. To identify sender in secure mail, encrypt first with your private key, then with receiver's public key. The encryption/decryption functions to send from B to A are:

    encrypted text = E ( D( P, d-keyB ), e-keyA )

    decrypted text = E ( D( P, d-keyA ), e-keyB )

    
    
    
    
    

    Encryption appears to be a great way to thwart listeners. It does not help with Trojan Horses, though.

    Old Data Encryption Standard (DES) is not public-key based, but as implemented efficiently and appeared to be relatively safe.

    New Advanced Encryption Standard (AES), called Ryndal (pronounced "rine doll").

    General problem: how do we know that an encryption mechanism is safe? It is extremely hard to prove. This is a hot topic for research: theorists are trying to find provably hard problems, and use them for proving safety of encryption.

    Summary of Protection: very hard, but is increasingly important as things like electronic funds transfer become more and more prevalent.