UNIX System Security LISA `95 September 18, 1995 Matt Bishop Department of Computer Science University of California at Davis Davis, CA 95616-8562 phone (916) 752-8060 email bishop@cs.ucdavis.edu UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 2 What Is Security? A college computing center does not allow copying from one class account to another. A student solves a homework assignment on the computer, but does not read-protect it. A second student copies it. Has a breach of security occurred? Policy vs Mechanism policy what is (and is not) allowed mechanism what enforces the policy Response to scenario: since the college asserts that each student's class account is private, a breach of security has occurred. The failure to use the mechanism to enforce this policy does not change this breach. Classes of Security Policies Military worry mainly about disclosure (revealing information) Commercial worry mainly about modifying information The Orange Book DOD 5200.28-STD; de facto standard for many agencies Specifies rating criteria for the security of systems: class A1: Verified Design class B3: Security Domains class B2: Structured Protection class B1: Labelled Security Protection class C2: Controlled Access Protection class C1: Discretionary Security Protection class D : Minimal Protection Class D All systems not falling into any higher class Class C1 * discretionary access control * creditable protection mechanism to enforce this * used for cooperating users working at same sensitivity level UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 8 Class C1 (2) Design Documentation: description of philosophy of protection, how this is incorporated into the operating system; description of any interfaces between modules of the TCB Discretionary Access Control: control access between named users (or defined groups) and named objects Identification and Authentication: requires user authentication, protection of authentication data --- most versions of UNIX fail this test Security Features User's Guide: single summary (chapter, manual, etc.) describing protection mechanisms, their use, etc. UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 9 Class C1 (3) Security Testing: ensure the security mechanisms work as described, and there are no obvious ways around them System Architecture: TCB must run in protected mode--- personal computers fail this test System Integrity: provide software, hardware (features) to allow validation of hardware, firmware elements of the TCB Test Documentation: how were the mechanisms tested, and what was the result? Trusted Facility Manual: a manual describing what the system administrator should be sure to control to run a secure facility UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 10 Class C2 Like C1, but ... * individual accountability * auditing of security-related events * resource isolation UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 11 Class C2 (2) Audit: be able to maintain logs (audit trails) actions based on user identity and protect the logs from modification or deletion Discretionary Access Control: control access from groups of individuals (whether or not defined by the system); control assignment of privileges Identification and Authentication: requires identification to granularity of a single user (no group accounts) Object Reuse: clear all information from an object before reuse (eg, scrub disk blocks) Security Testing: ensure resource isolation, no unauthorized access to audit, authentication data System Architecture: isolate system resources but keep them auditable. Trusted Facility Manual: Describe how to access, maintain, read logs UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 12 Class B1 Add to C2 ... * mandatory access control * informal statement of security policy model * data labelling * removal of flaws found by testing UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 13 Class B1 (2) Audit: log security levels of objects Design Documentation: description of model, show how model enforces the policy and the mechanisms enforce the model Design Specification and Verification: maintain model of policy, show it is consistent with its axioms I/O of Labeled Information: designate comm channel single- or multi level; be able to audit changes I/O with Multi-level Devices: must write label on output, assign (read) labels on input I/O with Single-Level Devices: must be able to designate compartment Identification and Authentication: maintain security compartment information too UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 14 Class B1 (3) Label Integrity: protect labels when output, tie them to objects Labelling Human-Readable Output: label all output designed to be readable by people with printable representations of security labels Labels: maintain sensitivity labels under the control of the TCB Mandatory Access Control: enforce it for objects, subjects directly under the TCB's control Security Testing: use friendly penetration attacks to demonstrate absence, removal, or neutralization of flaws System Architecture: process isolation through separate address spaces under TCB control Trusted Facility Manual: how to change security compartment of user UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 15 Class B2 Add to B1 ... * formal statement of security policy model * address covert storage channels * TCB structured into protection-critical, non protection-critical elements * stronger authentication mechanisms * well tested and relatively resistant to penetration UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 16 Class B2 (2) Audit: log identified events used to exploit covert channels Configuration Management: need one of these that ensures consistent mapping among code, documentation for the TCB, and allows comparisons of code for successive TCBs Covert Channels: identify, find max bandwidth of covert storage channels Design Documentation: describe TCB interfaces, document how TCB implements reference monitor, least privilege; show top level description (specification) of TCB is accurate; document covert channels Design Specification and Verification: formal model of security policy proven to satisfy security policy Device Labels: support minimum, maximum security levels for devices Labels: maintain sensitivity labels for everything directly or indirectly accessible by subjects under the control of the TCB UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 17 Class B2 (3) Mandatory Access Control: enforce it for objects, subjects directly or indirectly under the TCB's control Security Testing: correct all flaws, show TCB relatively resistant to penetration Subject Sensitivity Labels: notify user of change in his/her security compartment during an interactive session System Architecture: TCB has its own domain of execution which protects it from being tampered or interfered with Test Documentation: include results of covert channel testing, effectiveness Trusted Facility Management: separate administrator, operator functions Trusted Facility Manual: identify sections containing mechanism used to validate the TCB, how to generate a new TCB Trusted Path: required for initial login, authentication UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 18 Class B3 Add to B2 ... * TCB must be a reference monitor * support for system security administrator * signal security-related events * recovery procedures * well tested and highly resistant to penetration UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 19 Class B3 (2) Audit: monitor occurrences, events indicating imminent security violation Covert Channels: identify, find max bandwidth of all covert channels Design Documentation: show TCB to be consistent with descriptive top-level specification (informally) Design Specification and Verification: need convincing argument that descriptive top-level specification is consistent with model Discretionary Access Control: work on a per-user, per-right basis (ie, access control matrix implementation) Security Testing: show TCB is resistant to penetration; no design flaws, only a few correctable flaws in implementation UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 20 Class B3 (3) System Architecture: TCB to use a complete, conceptually simple protection mechanism; TCB to incorporate data hiding, abstraction, and layering Trusted Facility Management: security administrator functions identified, separated (as much as possible) from non-security administrative role Trusted Facility Manual: how to start the system in a secure manner, or to resume secure operation after operational problems Trusted Recovery: how to recover without compromising protection mechanisms UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 21 Class A1 Add to B3 ... * formal design specification of TCB * formal verification of TCB * stringent configuration management * secure distribution * support for system security administrator UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 22 Class A1 (2) Configuration Management: for life-cycle, this must be in place for all aspects of system development, with safeguards to protect what it manages Covert Channels: use formal methods in the analysis Design Documentation: show TCB to be consistent with formal top level specification; describe mechanisms part of TCB but not dealt with in the FTLS (mapping registers, etc.) Design Specification and Verification: need combination of formal, informal methods to show that formal top-level specification is consistent with model Security Testing: show TCB is consistent with formal top-level specification Test Documentation: show results of mapping between formal top level specification and TCB source Trusted Distribution: maintain integrity during distribution UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 23 UNIX Systems Most are class D * Class C1 requires protection of authentication data, and on most UNIX systems this data is world readable Some are class C2 * These usually are enhanced by add-on packages which protect authentication data, add extensive auditing capabilities, etc. A very few are class B2 * These are completely redone versions of the UNIX system and are only now becoming available UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 24 Who Sets The Standards In the Federal Government? In the Federal Government: Each agency sets its own standards, in consultation with the National Institute for Science and Technology UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 25 Who Sets The Standards In the Commercial World? In industry: each company decides what it wants to protect, and how far to go to protect it UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 26 What Makes Up a Policy? * Risk analysis: * what are the threats? * how likely are they to arise? * how can they best be dealt with? * Analysis of other factors: * what else affects the policy (federal or state law, needs, etc.)? * Procedures * what procedures need to be put in place, and how will they affect security? UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 27 What Are the Threats? * depends on nature of installation, what is done there, external requirements example: if working on proprietary projects, non disclosure is important; integrity may be less so as you can reload from backups example: if doing accounting or inventory control, integrity is vital as the data may change too quickly to do backups after each change; non-disclosure is less so, as it may embarrass but will not corrupt billing UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 28 How Likely are They to Arise? Depends on nature of users and work done as well as nature of the installation example: if the computer is not attacked to networks, system crackers cannot access it remotely example: if competing projects are using the system, it is likely one project may try to read another's reports to see what progress is being made UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 29 How Can They Be Dealt With? Depends on nature of the security mechanisms provided and the procedures allowed example: if you can require every line of code of all programs added to the system to be inspected by all programmers, it is unlikely a Trojan horse will slip in. (Most sites do not do this as it is too expensive.) example: use file system controls to restrict access to users' directories UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 30 Other Factors Depend on local/national laws and treaties, needs of users, etc. example: Shipping encrypted data over an international network may violate some laws and so not be possible, even if it is desireable example: Put more effort into securing what the users use than into what they don't UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 31 Procedures Depends on what you are allowed to do (see earlier) and what you are willing to trust example: Allowing operators to change passwords on the basis of telephoned requests, with no additional validation, is not a good idea example: Some sites allow the above if confirmation of the request by electronic mail follows UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 32 Password Security Goal: To examine the password mechanisms used by UNIX, and discuss potential security problems Overview * How the password changing programs work * How passwords are stored * Password file do's and don't's * What makes a good (or bad) password * Proactive vs. reactive checking * Special cases * Alternatives to the standard UNIX scheme UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 33 Case #1, Columbia University On Friday, Multimax seemed unusually sluggish Investigation showed an unauthorized person had gained access to the guest account. The guest account had an easy-to-guess password, and an unauthorized user guessed it and logged in - and used the machine in unauthorized ways UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 34 Joes A joe is an account with the account name as password. It was speculated once that every machine in which the user can select his/her own password has at least one joe. In a nationwide experiment (done informally), this was verified for all computers examined. UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 35 Common Joes root, rootsh, rootcsh, toor superuser account; as a variation, not given a password on many distribution versions sysdiag, diag system diagnostic account; some vendors use this to check hardware. This should always have a password different than the account name. UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 36 Common Joes (2) sync used during an emergency shutdown to protect disks. Okay as long as it does only this. general information who, finger, date, w these can help an attacker get information that makes attacks easier (such as legitimate login names); but they may be desirable. Again, okay as long as they only do what you expect. Note: these may reveal that the system is a UNIX system should an attacker be using a modem to make blind calls UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 37 Common Joes (3) games often has a password like "play" or "fun" rather than "games" demo this is usually a temporary account (in the sense that it is meant to be deleted but is instead forgotten ...) guest, visitor usually meant only for on-site guests, but used by off-site (uninvited) visitors as well UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 38 Common Joes (4) telnet so they can jump from your site to others (obscuring their trail) uucp, nuucp so they can gain access to stored files, or to others' traffic through you mail in some cases, simply to read mail; in other cases, to use a shell escape to get access to your system UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 39 Recommendation Look for Joes, and eliminate them. No machine should have a full account with an account name as a password. UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 40 On Some Systems * repeatedly guessing a login/password pair may be very slow and may raise alarms Examples of such systems are IBM's AIX, but this feature can be set or cleared by the sysadmin. Do not assume that this alerts you to all password guessing, as some accounts may have no passwords, or passwords common across systems, or very easily guessed passwords, and often these can be cracked without triggering alarms. Also, patience of some attackers is incredible; in Danish incident, they tried for two weeks before succeeding! UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 41 User Authentication How does the user prove his or her identity to the computer? * what you know (passwords, etc.) * what you have (smart cards, etc.) * what you are (biometrics, etc.) Accepted identity is the basis for controlling all future actions by the user, so it is the first and most basic security mechanism UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 42 What You Know Checks identity based on something you remember: * a word (password) * an algorithm (pass-algorithm) * a phrase (pass-phrase) * some transformation of any or all of the above (key crunching) Vanilla UNIX uses passwords, so we start there UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 43 Why is it Important? Probably 90-95% of all successful intrusions can be traced to a guessed password (or a missing password): * At MIT, Purdue, and other universities, programs which guess passwords (and report them to the system administrators) typically get 25-30% of the users' passwords * An experiment at the Software Engineering Institute analyzed the password files from 50 sites (of all kinds); total 15,000 passwords. 3% (450) guessed in 10 minutes; 21% (3150) within a week. UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 44 What a Password Is A password authenticates a user, binding that identity to all actions undertaken during that session. Passwords are initially given by the superuser; users can (and should) change them as soon as possible The user may be another computer (eg, connecting using a network protocol) UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 45 Changing Your Password If you are not the superuser, type passwd You are asked for your current password and then you must type the new password twice. Short passwords with an insufficient mixture of letters, cases, and digits are rejected. If you insist (try three or more times), the system gives up and resets the password as you want. UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 46 Recommendation Do not insist on an insufficient mixture of letters, cases, and/or digits, nor on a short password UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 47 Superuser Changing Password If you are the superuser, type passwd username to change username's password. You must type the new password twice. Short passwords with an insufficient mixture of letters, cases, and digits are rejected. If you insist (try three or more times), the system gives up and resets the password as you want. UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 48 Superuser Changing Password (2) The superuser can edit the password file directly: * obtain the hash of the new password * invoke vipw (if edited without this editor, there is no assurance of exclusive access to the file) * replace the second field of the user's entry with the hash UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 49 Password File Format * one line per account * 7 colon-separated fields root:abcdefghijklm:0:1:The Wizard:/:/bin/csh account name hashed password UID GID user info home dir shell UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 50 Dangers of Direct Editing * if the editor does not support the password file locking convention, simultaneous edits could create problems * could mistype hashed password, thereby locking user out of system * (older versions of vi and ex) check the first five and last five lines of the file for constructs of the form :[ve][ix]... treat the rest of the line as an editor command, and execute it UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 51 Recommendations Do not insist on an insufficient mixture of letters, cases, and/or digits, nor on a short password Unless disabling an account, use the passwd(1) program to change a user's password UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 52 System V Version There is an upper limit (when passwords must be changed) and a lower limit (before which they cannot be changed): root:abcdefghijklm,n.o.:0:1:The Wizard:/:/bin/csh change at least every 50 weeks (n) as often as root likes (.) when password last changed in weeks since the epoch To disable, set min, max to 0 (.) UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 53 Password Aging Idea is to force users to change passwords often enough so that by the time old one is guessed, it has been changed to something else Very controversial: * can force users to think up new passwords quickly (and usually badly) * easy to evade: change password, then change it back UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 54 System V Version (2) Problem: If password expired, user will be allowed to begin login procedure, but cannot complete it until his/her password is changed! UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 55 Recommendation If you use password aging, every time a user logs in, print out how much time remains until his/her current password expires. UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 56 Going to the Limit Change password each time it is used Called one-time passwords * challenge-response: S/Key, etc. * work from a list UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 57 Password File Corruption *Blank lines at end of file (added during edits or by broken versions of passwd(1)) lead to spurious lines of the form *::0:0:: *This allows users to log in using: * rlogin host -l '' *and they become superusers! *Recommendation: check for blank lines each time the password file is edited UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 58 Password File Corruption (2) Only accounts with root privileges should ever have a UID of 0. Access checking is based on the UID number, not the account name. The password file should be owned by root and writeable only by root. UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 59 Password File Corruption (3) If a line has too few fields and any field other than the last one is missing, a user may not be able to log in. Example: mbishop:abcdefghijklm:77:Matt Bishop:/home/m:/bin/sh Here mbishop's home directory is a program, and the login will fail. Should it succeed, he will be in group 0. UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 60 Recommendations Check for blank lines each time the password file is edited Periodically scan the password file to see if there are any accounts with a UID of 0, and check that those accounts are authorized UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 61 Recommendations Check that root owns the password file and no-one else can write it Periodically scan the password file to see if there are any lines with an incorrect number of fields UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 62 How to Check /etc/passwd Use COPS: reports duplicate login names non-alphanumeric login names non-numeric UIDs, GIDs account has no password UID is 0, name not root blank lines login directory invalid (ie, file, not executable, etc.) incorrect number of fields (must be 7) Get it from: anonymous ftp to cert.org:pub/tools/cops UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 63 More Potential Security Holes Other things to look out for: * password field empty: no password needed to log in * password field set to something other than a valid hash (like "*" or "no-login"): authentication cannot be completed successfully (this does not mean the user cannot log in, but only that he/she cannot be authenticated!!!) UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 64 Recommendations All accounts should have passwords installed. If a user account is to be disabled, replace the password field with "*" (or "no-login") and the shell with "/bin/true" UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 65 Passwords * stored in hashed form * hashing function is believed to be one-way (not invertible), and is based on a modified version of the Data Encryption Standard * in general, stored in a user information database "/ etc/passwd" which can be read by anyone * library functions to do the hashing are available to users (crypt(3)) UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 66 UNIX Password System 5 components: passwords strings of up to 8 ASCII characters, salt } hashes strings of 13 chars from ./A...Za...z0...9 hashing function crypt(3) generates a hash from a given password password selection function passwd(1), passwd+, pwrand selects and sets a password authentication functions login(1), rlogin(1), su(1), pwtest validate a user UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 67 Protecting the Passwords Do not allow access to unencrypted passwords * Passwords must not be kept on-line in the clear * Don't decrypt passwords in shared memory * Need to encrypt passwords when sent over a network (ie, as part of remote login procedure using telnet/rlogin/ftp, etc.) UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 68 Protecting the Passwords on Disk Three approaches: * encrypt passwords using a "master password" -- if an attacker gets that "master password" many systems are endangered * put passwords in a protected file -- if an attacker gets enough privilege to read the file, it's all over * transform passwords into a cryptographic hash -- if an attacker gets the file, he/she must still try to guess passwords UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 69 One-Way Hash Functions The function crypt, which is like a normal hash function, but satisfies some other properties: * crypt can be applied to input x from 1 to 8 chars long * crypt always produces a fixed size output y * given x it is easy to compute y = crypt(x) * it is computationally infeasible to find two inputs x and z such that crypt(x) = crypt(z) called a strong one-way hash function UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 70 Password Hashing How the password is hashed: * obtain random 12 bits (called the salt), permute internal DES table as indicated by the salt * use password as key to encrypt the message of zero bits; iterate 25 times * prepend salt to result of encryption * convert to printable format UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 71 The Data Encryption Standard First proposed in 1976 as a standard for encrypting non-classified traffic * Described in FIPS PUB 46 * Reviewed every 5 years, last time in 1992 * Based (heavily) on work done at IBM; some modifications made before being adopted * Only one exploitable weakness found in 17 years of trying,and it requires using a chosen plaintext attack and 2 encryptions 47 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 72 Overview of the DES A block cipher: * encrypts blocks of 64 bits using a 64 bit key * outputs 64 bits of ciphertext A product cipher * basic unit is the bit * performs both substitution and transposition (permutation) on the bits Cipher consists of 16 rounds (iterations) each with a round key generated from the user-supplied key UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 73 Generation of Round Keys key PC-1 C0 D0 LSH LSH C1 D1 PC-2 K1 PC-2 K16 Each round key Ki, 1 <<= i <= 16, is 48 bits long LSH LSH UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 74 The Main Body * f input IP L0 R0 L1=R0 R1=L0 * f(R0,K1) K1 The body of the DES; IP is the Initial Permutation, Ki the ith round key, and f a function to be defined later. Note the crossing (swap of L and R) is not done after the last round L16=R15 R16=L15 * f(R15,K16) output IP-1 UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 75 The f Function R (32 bits) E 48 bits Ki (48 bits) S1 S2 S3 S4 S5 S6 S7 S8 P 32 bits * 6 bits into each 4 bits out from each UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 76 Dictionary Attack A one-way hash function cannot be inverted, but ... given a hash y, to find the x for which crypt(x) = y, use trial and error: (1) Guess a possible password (2) Try it out (3) If the computed hash is wrong, go to (1) UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 77 Quick Dictionary Attack Instead of recomputing guesses, whenever you try something, save both the tried word and the hash; then when you get a set of hashes, just compare against the precomputed list Note: DES chips are cheap and fast too UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 78 Why Salt? Solution: perturb the standard algorithm Nice Side Effects: * you can have the same password on two different systems, and someone looking at both password files will not know this * if an attacker tries to guess a password, he or she must hash it once for each salt being used (which can take a lot more time or space!) UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 79 In More Detail ... Due to salt, simply precomputing a list of guesses and matching is infeasible (you would need 4096 different precomputed lists!) This does not help if an attacker is trying to guess one user's password, as he/she knows the salt for that user. root:abcdefghijklm:0:1:The Wizard:/:/bin/csh hashed password salt UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 80 Salting The perturbations are numbered 0 to 4095; the number of the one used is stored with the password using a base 64 representation: ./0123456789ABCD 0 ... 15 EFGHIJKLMNOPQRST 16 ... 31 UVWXYZabcdefghij 32 ... 47 klmnopqrstuvwxyz 48 ... 63 UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 81 The f Function in the Password Hash R (32 bits) E 48 bits Ki (48 bits) S1 S2 S3 S4 S5 S6 S7 S8 P 32 bits * 6 bits into each 4 bits out from each salt varies this table in one of 4096 ways UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 82 Perturbation of the E Table 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 32 17 18 3 4 5 4 21 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 1 2 19 20 21 20 5 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 The salt "04" is 2 * 64 + 6 = 134 = 2 +2 +2 , so the E table used is 7 2 1 UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 83 Hashing the Password (1) Perturb the E Table (2) Use the password as the key (3) Encrypt the message composed of 0 bits (4) Encrypt the result of step (3) using the password as key. (5) Iterate step (4) 23 more times (for a total of 25 encryptions in steps (3)-(5)) (6) Prepend the 12 bits of salt to the 64 bit output This is the hashed password (authenticator) UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 84 Password Storage 1 1 1 1 e 7 0 0 0 0000 Map each set of 6 bits into the alphabet: ./0123456789ABCD 0 ... 15 EFGHIJKLMNOPQRST 16 ... 31 UVWXYZabcdefghij 32 ... 47 klmnopqrstuvwxyz 48 ... 63 (42) (9) 1 UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 85 Dictionary Attack (1) Guess a possible password (2) Try it out: * use it to try to log in (or something like that) * if hash function is available, use that directly: int isright(hash, guess) char *hash, *guess; { return(strcmp(hash, crypt(guess, hash)) == 0); } UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 86 Case #1, Columbia University Remember that CPU hog? When the system admins looked, sure enough ... Found copy of local password file and a password guessing program (executable; determined purpose by running strings(1) and nm(1)) UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 87 What You Need * access to the site's password hashes * access to the crypt function * ability to run the guesser for a long time UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 88 Problems Implementation of hash function may be very slow the standard UNIX hashing algorithm, as implemented on most systems, takes a fair amount of time (0.4 sec on a Sun 3/50, 0.1 on a Cray 2), and this must be done once per guess What to do? Write a faster one! The algorithm is common knowledge UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 89 How Fast? computer type fast/call sys/call speedup Amdahl 5880 0.0024 0.053 21.6 Convex C-1 (32) 0.011 0.19 17.6 Convex C-1 (32) 0.0089 0.19 22.0 Cray 2 0.0019 0.13 72.0 Cray 2 (vectorized) 0.000080 0.13 1625.0 IBM PC/RT 0.0075 0.21 28.0 IRIS 2500T 0.013 0.44 33.8 Sequent 2100 0.040 1.3 32.6 Sun 3/50 0.012 0.37 27.7 Figures are from 1987 and can be made considerably faster in many cases ... UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 90 Software Fastest freely available version of crypt(3) is ufc crypt by Michael Glad via anonymous ftp to ftp.uu.net:usenet/comp.sources.misc/ volume28/ufc-crypt Faster ones have been done for specialized hardware (e.g. Connection Machines) which are not commonly available UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 91 Thwarting a Dictionary Attack Unlike most: cannot be blocked Goal: ensure expected time of success is as high as possible It Can Be Shown: that of a uniform random distribution of passwords is best UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 92 Set of Possible Passwords * Must be "large enough" so it takes sufficient time to guess passwords This means you have to make the password selection function either give the user, or force the user to give, any of a large number of passwords; for UNIX systems, any sequence of characters of length 1 to 8 (takes roughly 11,500 years to try everything, assuming 10,000/ sec) Should not restrict it to random sequences of characters of length 5 (takes roughly 4 days to try everything, assuming 10,000/sec) UNIX System Security LISA `95 September 18, 1995 UNIX System Security (Bishop, (C)1991-1995) LISA `95, M2, # 93 Why This is Important In 1970s: * one site required 8 character passwords of letters and digits, randomly generated For uniform random distribution, E(X) *