Lecture notes for CSC 2/456, 12 April 2000 ff Reading: chapters 19 and 20 ======================================= Protection and security ----------------------- Definitions Protection involves specifying which active subjects (e.g. threads, processes) can access which objects (e.g. files) in which ways. Security involves ensuring that protection is enforced. Protection can be divided into policy and mechanism. Mechanism provides the operations necessary to specify who can do what. Policy involves choosing what to specify. It is sometimes useful to distinguish between protection and safety. Protection means keeping users from hurting each other, even if they're malicious. Safety means making it difficult (if not impossible) to shoot yourself in the foot; it assumes that malice isn't a factor. An example of a safety measure is array bounds checking in Pascal: you can defeat it if you try hard enough (e.g. via clever use of untagged variant records), but you are unlikely to defeat it by accident. Protection is supposed to be solid (that's what security is for); safety doesn't have to be. ----------------------- Protection Policy versus Mechanism Policies: specification of allowable actions on resources users cannot access device registers superusers may read any file need-to-know principle (needs change dynamically) Mechanisms: how protection policies are enforced bounds registers privileged instructions encryption Policy/Mechanism separation policies tend to change fairly often mechanisms are usually provided by the kernel if the policies were too closely related to the mechanisms, then the kernel would have to be changed fairly often kernel should provide small, complete set of mechanisms user-level software should implement policies using kernel mechanisms Access Control Model Terms subjects - entities that wish to access a resource procedures, processes, users objects - the resource units that may be accessed variables, data segments, procedures, files, physical devices privilege - the right to access an object in a particular fashion read, write, execute, create, delete domain - set of ordered pairs kernel/user modes are machine-dependent domains system calls => domain switch (uid,gid) pairs are Unix domains process scheduling => domain switch setuid programs => domain switch Objects are viewed as ADTs. Each operation on an object requires the associated privilege (access right). Processes execute within some domain, which defines what objects a process may access and what operations may be performed. A change in domain implies a change to the set of privileges. Access control matrix The set of all privileges can be described by an access control matrix M = Domain X Object, where M[i,j] contains the privileges for domain i on object j. The matrix is usually very sparse, and therefore is not actually stored as a matrix. Access lists (columns) Associated with each object is the set of all domains that have access to the object and the type of access allowed. Only the object may modify the access list => protection is implemented by each object. Default rights are usually given for domains not listed. If too many domains exist, they can be grouped in classes. Group id in Unix is an example of a domain class. Access is allowed if at least one entry in the access list allows it. Sometimes a systems permits negative rights, too. E.g. anybody can access this except John Doe. Capability lists (rows) Associated with each domain is the set of all objects that the domain may access, and the particular privileges this domain has. This can result in very long lists of capabilities, particularly for superusers. If a subject has access to its capability list, it can grant itself any rights it chooses => capability lists must be protected from access tagged architecture: capabilities have a tag bit and can only be modified in kernel mode kernel space capabilities: capabilities are stored in kernel space (which can't be modified by the user) and are addressed by the user indirectly (eg, file descriptors in Unix) encrypted capabilities: capabilities are stored in user space in encrypted form; successful forgery is highly unlikely Capabilities include both object specific rights (read, write, execute) and generic capability rights limits distribution of capabilities limits copying of capabilities allows a capability to be deleted Amplification In some capability systems (eg, Hydra), the internal representation of an object is only accessible within the object If a process is executing outside the object, it has no access to the internal structure of the object However, when the process IS within the object, it must have access Using amplification, the act of executing within the object automatically provides the process with additional rights, namely the ability to access the internal representation The rights to be added are specified in an object template Lock/Keys Compromise between capabilities and access lists Each object has a random bit pattern "lock" Subjects also have random bit patterns "keys" If a subject has a key that fits an object's lock, access is allowed Can be used to represent an arbitrary rectangle in the access control matrix (with same protections for all subjects) separation of protection information from object names means you don't have to keep rights with every pointer. like probabilistic capabilities, probabilistic keys can be moved without kernel intervention and without notifying the object(s) to which the key grants access. a single key can convey an arbitrarily complex set of rights over an arbitrary set of objects to an arbitrary set of subjects. the rights associated with a key can be changed without the knowledge of the subjects that hold the key. drawback: N x M checking required on access. some of the same effect (small handle for a large set of rights over many objects) can be achieved (a bit less transparently) by allowing capabilities to point to lists of capabilities. Revocation Rights are not always intended to be given forever. Access lists: since the rights are associated with the object (which presumably is where revocation takes place), implementing revocation is easy. Capability lists: rights are scattered among all domains and may be very difficult to find => revocation is hard. To simplify revocation, each capability can refer "indirectly" to the object. If the object knows the location of the "indirection", revocation is easy again. does not allow selective revocation Alternatively, each capability can contain a "version" field. The object is allowed to change versions, and a capability with the wrong version is rejected. If capabilities are managed by the kernel, version fields can contain simple serial numbers. If capabilities are in user space, version fields need to contain large pseudo-random bit patterns. also does not allow selective revocation Lock/Keys: as with version fields, removing a lock from an access list revokes all corresponding keys. -------------------------- Unix Each subject (process) and object (file, socket, etc.) has a user id (uid). Each object also has a group id, and each subject has one or more group ids. Objects have access lists that specify read, write, and execute permissions for user group and world. A subject can r/w/x an object if (1) it has the same uid and the appropriate user permission is set, (2) one of its gid's is the same as that of the object, and the appropriate group permission is set, or (3) the appropriate world permission is set. Superusers (uid 'root') can do anything. Special things happen via 'setuid' and 'setgid' programs (the latter is less common). A setuid/gid program, when executed, causes its subject to uid/gid of the a.out file. (Presumably the permissions on that file do not include write by world!) A process with uid root can change its own uid/gid. The login program is setuid root. It looks up the typed-in username in the /etc/passwd file to get a uid, changes its uid to match, and starts up a shell. It also looks up the username in /etc/group to get a list of gids, and adopts those as well. The Andrew distributed file system (AFS) (a Unix add-on) retains the user/group/world r/w/x system for regular files, for backward compatibility, but has a more general access-list scheme for directories. The access lists permit hierarchical (nested) groups and negative rights. ----------------------- Security Truly secure systems are at least as difficult to build as truly reliable systems. Anecdotes ln /etc/passwd ./core Trojan horses login program anything that a super-user executes Tenex passwords, aligned at page boundaries Internet worm, 11-2-88 Robert Morris, Jr. rsh for trusting machines string overflow in fingerd that could be used to force return to an address in the stack that would start a shell sendmail bug that permitted execution of a mail message viruses typically appends code to end, replaces first instruction with jump to virus IP spoofing, 12-94. Robert Mitnik. Send out IP packets that appear to come from a trusted host. Solution: put a gateway (firewall) between you and all untrusted hosts. The gateway refuses to forward packets from outside that claim to come from inside. Also logs all transactions. Also runs "proxy" programs that perform similar checks for other protocols (telnet, rlogin, finger, sendmail, http, ftp, X?, talk?) user authentication login procedures usual mechanism: store encrypted version of password, preferably with a per-user "salt". DON'T store plain-text password. Salt makes dictionary attack more difficult, though still feasible. There exist widely-circulated programs that will break passwords on most Unix systems within hours or days. Major vulnerability: typing of plain-text passwords over computer networks. Solutions generally depend on cryptographic techniques. ---- cryptography C = E(M,K_e) M = D(C,K_d) In a conventional cryptosystem, K_e = K_d; in a public-key system, they are different. Types of attack: ciphertext only -- eavesdropper has encrypted message, together with some general knowledge (e.g. frequency of letters in the plaintext) known plaintext -- eavesdropper has some translated stuff chosen plaintext -- eavesdropper can find the encrypted form of plaintext of his/her own choosing (e.g. can trick users into sending a given message) chosen ciphertext -- eavesdropper can find the plaintext version of chosen ciphertext (e.g. by sending junk down the wire and getting a mole to swipe the "translation") practical systems are considered secure if they guard against chosen plaintext attack. A code can be either unconditionally secure computationally secure Only known unconditionally secure cryptographic technique is a one-time pad with truly random data. E.g.: hook a source of random noise (e.g. radioactive decay) to a high-capacity tape, DVD, etc. Make one copy and send it to your friend via a trusted physical channel (Secret Service agent with a briefcase). XOR your message with bits from the tape. Problems: (1) the physical channel may not warrant trust, and is certainly expensive and cumbersome; (2) the tape doesn't last. More practical techniques depend on the difficulty (NOT impossibility) of decoding. The best known techniques can be proven to take a long time unless P=NP. Problem: you still have to get a copy of the key safely to your friend. It turns out that it is possible to exchange keys securely over an insecure channel, but you have to be willing to ship a lot of bits, and devote a lot of computer power to the exchange. Here's the idea: I send you a very large number (e.g. 10^5) of encrypted pairs (K, n), where K is suitable for use as a cryptographic key, and n is a serial number. You choose one of the pairs at random, and break it by brute force. They you send me back the serial number. Now we both know the key, but an eavesdropper would have to break about half the pairs to find it. A trusted central authority can facilitate communication between strangers, if it has already established secure communication with both of them. I send a request to the authority for a session key. The authority sends me one, encrypted with my key and, separately, with your key. I decrypt mine to get the session key, and send you yours, which you decrypt to get the session key. Then I can send you things encoded with the session key and you'll be able to read them. A trusted authority can also facilitate authentication (signatures). I send my message, encrypted with my key, to the authority. The authority decrypts it, then encrypts it with its own secret key and sends the result back to me. I forward it to you. You send it to the authority, who decrypts it and then encrypts it with your key and forwards it back to you. You can then decrypt it. << draw pictures >> --- DES (Data Encryption Standard) is widely used. It's very old now (adopted as National Bureau of Standards official scheme in January of 1977), and the amount of time it takes to invert has become feasible for many organizations. (DES is not NP-hard.) There has been a lot of controversy about what to replace it with. The National Security Agency has been pushing a proposal called Clipper that would use a secret algorithm with keys held in escrow by the government for use in wiretapping. The Clinton Administration has backed the scheme, but has run into a lot of public opposition. DES was originally proposed to use significantly longer keys. Some authorities contend that the NSA was responsible for scaling it back, to a level they were capable of breaking in 1977. Clipper raises an important public policy issue. How do we as a society balance the desire for personal privacy against the desire for safety in the form of law enforement wiretaps? Rolled into the debate is the issue of evolving changes in the ways people communicate. Many old-fashioned communication channels that are either fairly secure, or at least invulnerable to blanket monitoring are being replaced with digital communications. How much do we want to insist on privacy for these communications? --- The main alternative to DES and/or Clipper is public key cryptography, and the RSA (Rivest/Shamir/Adelman algorithm in particular (see CACM Feb '78). This uses a PAIR of keys, one to encrypt and the other to decrypt. Guessing either given the other is very hard. The nice thing about public keys is that you don't have to have a secure physical channel to exchange keys. We all publish our public (encryption) keys in the phone book or on the web. We keep our private keys. Anybody who wants to send us a message encrypts it with the public key and sends it. Only we can decrypt it. All known public key systems depend on a *trapdoor* or *one-way* function. That's a function that is NP-hard to invert, unless you know some secret "trapdoor" information. RSA uses prime factorization: choose two large prime numbers, p and q (use an efficient primality test, probably a probabilistic one) compute n = pq compute L(n) = (p-1)(q-1) choose a random number d such that max (p,q) < d < L(n) and d is relatively prime to L(n) find a number e such that 0 < e < L(n) and ed = 1 mod L(n) (not hard) Then for any X such that 0 <= X <= n-1, X^e^d mod n = X^d^e mod n = X publish (n, e) as the encryption key; keep (n, d) as the decryption key To encrypt a message, represent it as a string of integers in the range 0 .. n-1. Raise each integer to the e-th power, mod n, and send the resulting string. To decrypt, raise each integer to the d-th power, mod n. The obvious (only known) cryptanalytic attack is to factor n. That's hard. Rivest, Shamir, and Adelman suggest choosing p and q such that n is about 200 digits. They claim that will take more than 10^23 mathematical operations to crack. At 1GHz, that's over 10^6 years. Example: let p = 47, q = 59, n = 2773, d = 157. Then L(n) = 2668 and e = 17 let blank = 0, A = 1, B = 2, Z = 26. IT IS ALL GREEK TO ME = 0920 0009 1900 0112 1200 0718 0505 1100 2015 0013 0500 First block is encrypted as 920^17 mod 2773 = 0948. It's decrypted as 948^157 mod 2773 = 0920. These functions can be computed reasonably fast, but not nearly as fast as private key schemes like DES. A common strategy is to use RSA to transmit a private session key. Merkle and Hellman have devised a public-key scheme based on the knapsack problem. Two earlier versions were broken; confidence in their current scheme is consequently relatively low. There are other schemes based on discrete logarithms and on elliptic curves. Public key cryptography can be used for authentication (signatures) as well, with no need for a central authority. The two keys are true inverses: if I encrypt something with my private key, you can decrypt it with my public key. If I encrypt my message with my private key, attach my name, and encrypt again with your public key, you can decrypt with your private key, see my name, and decrypt again with y public key, and be sure it was me who sent it. This assumes that my private key is really private. You wouldn't want me to get out of a deal by saying my private key was stolen. We can use a "notary" to seal things. I encrypt with my private key and send the result to the notary, who encryptes it with its own private key and returns the result to me. Then I encrypt with your public key and send to you. You can decrypt with your private key, the notary's public key, and my public key. If you hang onto the un-decrypted version, and if both the notary and I included dates in what we signed, I won't be able to deny having sent the message unless I claim my key was stolen far in the past, without my knowledge. --- RSA is used in the freeware PGP (pretty good privacy) system, written by Phil Zimmerman. The US Justice Department hounded Zimmerman for several years under arms control legislation. The claim is that by making PGP available on the Internet he facilitated its export by others (encryption software is classified as a "munition" under US export laws). The Justice Department acknowledges that Zimmerman did not export the software himself. It is not clear how the government responds to the observation that RSA is a widely-known (and not terribly complicated) algorithm that any foreign power could easily implement on its own. It is tempting to conclude that the real objection to Zimmerman's work is that he made secure encryption available in convenient form for ordinary citizens. --- One-way functions are useful even without a trapdoor. Here's an example: the S/KEY mechanism, devised by researchers at Bell Core, can be used to permit remote logins over insecure networks, without transmitting plain-text passwords. We now use S/KEY here in the department for log-ins over the network. Here's the basic idea. You visit the computer center and, in person, enter a password on the console. The computer runs the password through a one way function a large number of times (say 100). It keeps the result, and throws away the password (no secret stored on-line). You program the one-way function into your PC at home. When you want to log in remotely, the computer sends you the number x=100-n-1, where n is the number of times you have logged in previously. You type your password into your PC, which runs it through the one-way function x times and send the result back to the main computer. The main computer runs it through the one-way function one more time and compares it to the number stored on-line. If it matches, it lets you log in, and replaces the on-line number with the one you just sent. After 100 logins, you have to visit the center again and enter another password. ================================ Other privacy issues. Cookies. Shopper's cards. Selling of database info. Cf. video rentals and Judge Bork. Call id. Blanket collection of data that was once vulnerable only to targeted collection. Pentland's comments on ubiquitous v. wearable computing.