Introduction Processes Inter Process Communication Deadlocks Memory Management

File Systems Protection and Security I/O Systems

Protection and Security

1. Goals of Protection

   prevent accidental or intentional misuse of a system.

   • Accidents: relatively easy to solve (can do things to make the likelihood small).
   • Malicious abuse: very hard to completely eliminate (cannot leave any loopholes, cannot play on probabilities).

   Protection mechanisms:

   • User identification (authentication): make sure we know who is doing what.
   • Authorization determination: must figure out what the user is and is not allowed to do. Need a simple database for this.
   • Access enforcement: must make sure there are no loopholes in the system.

   Even the slightest flaw in any of these areas may ruin the whole protection mechanism.

2. Authentication

   User identification is most often done with passwords, a relatively weak form of protection.

   • A password is a secret piece of information used to establish the identity of a user.
   • Passwords should not be stored in a readable form. One-way transformations should be used.
   • Passwords should be relatively long and obscure.

   Another form of identification: badge or key.

   • Does not have to be kept secret.
   • Should not be able to be forged or copied.
   • Can be stolen, but the owner should know if it is.
   Biometrics

   Key paradox: key must be cheap to make, hard to duplicate. This means there must be some trick (i.e. secret) that has to be protected.

   Once identification is complete, the system must be sure to protect the identity since other parts of the system will rely on it.

3. Authorization

   Must indicate who is allowed to do what with what. Draw the general form as an access matrix with one row per user, one column per file. Each entry indicates the privileges of that user on that object. There are two general ways of storing this information: access lists and capabilities.

   Access Lists: with each file, indicate which users are allowed to perform which operations.

   • In the most general form, each file has a list of pairs.
   • It would be tedious to have a separate listing for every user, so they are usually grouped into classes. For example, in Unix there are three classes: self, group, anybody else (nine bits per file).
   • Access lists are simple, and are used in almost all file systems.

   Capabilities: with each user, indicate which files may be accessed, and in what ways.

   • Store a list of pairs with each user. This is called a capability list.
   • Typically, capability systems use a different naming arrangement, where the capabilities are the only names of objects. You cannot even name objects not referred to in your capability list.
   • In access-list systems, the default is usually for everyone to be able to access a file. In capability-based systems, the default is for no-one to be able to access a file unless they have been given a capability. There is no way of even naming an object without a capability.
   • Capabilities are usually used in systems that need to be very secure. However, capabilities can make it difficult to share information: nobody can get access to your stuff unless you explicitly give it to them.

   Are the following things access-based or capability-based protection schemes?

   • Protection Keys
   • Page tables

4. Access Matrix Model
   O = current objects, e.g., a file, a process
   S = current subjects, e.g., a process
   R = generic rights, e.g., read, write, execute, delete
   P = access matrix, indexed by (subject, object)

   Example

   	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

   capability = tuple (o, P(s,o))
   each subject has a set of capabilities
   posession of capability confers access rights

   Capability Based Addressing

   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.
   

5. Access Enforcement

   For the access matrix model, when subject s wants to access a of object o, system views this as request (s,a,o) to monitor of o.

   Monitor permits access iff a ∈P(s,o).

   Some part of the system must be responsible for enforcing access controls and protecting the authorization and identification information.

   • Obviously, this portion of the system must run unprotected. Thus it should be as small and simple as possible. Example: the portion of the system that sets up memory mapping tables.
   • The portion of the system that provides and enforces protection is called the security kernel. Most systems, like Unix, do not have a security kernel. As a consequence, the systems are not very secure.
   • What is needed is a hierarchy of levels of protection, with each level getting the minimum privilege necessary to do its job. However, this is likely to be slow (crossing levels takes time).

   In general, protecting a computer system is extremely difficult. There is no completely secure computer system in existence. Some common problems:

   • Abuse of valid privileges.
   • Imposter.
   • Trojan Horse.
   • Listener.
   • Spoiler.
   • Send weird escape sequences to terminals that cause commands to be echoed back from the terminal.

   Once the system has been penetrated, it may be impossible to secure it again: hooks could have been left around for the imposter to regain control.

   It is not always possible to tell when the system has been penetrated, since the villain can clean up all traces behind himself.

   If we can never be sure that there are no bugs, then we can never be sure that the system is secure, since bugs could provide loopholes in the protection mechanisms.

   How are computers different from humans when it comes to security?

   • Computer memory is volatile, humans do not forget.
   • We are much more trusting of computers than of people: privileges are given away freely in huge doses: any program you run could conceivably modify any of your files.
   • Computer programs are very poorly understood.

   Solutions: nothing works perfectly, but here are some possibilities:

   • Logging: record all important actions and uses of privilege in an indelible file. Can be used to catch imposters during their initial attempts and failures. E.g. record all attempts to specify an incorrect password, all super-user logins. Even better is to get humans involved at key steps
   • Principle of minimum privilege ("need-to-know" principle): each piece of the system has access to the minimum amount of information, for the minimum possible amount of time. E.g. file system cannot touch memory map, memory manager cannot touch disk allocation tables. This reduces the chances of accidental or intentional damage. Note that capabilities are an implementation of this idea. It is very hard to provide fool-proof information containment: e.g. a trojan horse could write characters to a tty, or take page faults, in Morse code, as a signal to another process.
   • Correctness proofs. These are very hard to do. Even so, this only proves that the system works according to spec. It does not mean that the spec. is necessarily right, and it does not deal with Trojan Horses.
   • Auditing your system. e.g use tripwire

   ---

6. Encryption

   Key technology: encryption. 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.
   • 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 →→→→→→→→	Md 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

7. 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.