Tadayoshi KohnoCSE P 590 / CSE M 590 (Spring 2010)Computer Security and PrivacyThanks to Dan Boneh, Dieter Gollmann, John Manferdelli, John Mitchell, Vitaly Shmatikov, Bennet Yee, and many others for sample slides and materials ...Goals for TodayLab 1 (Announcement)User authenticationPhysical securityBasic Problem?How do you prove to someone that you are who you claim to be?Any system with access control must solve this problemMany Ways to Prove Who You AreWhat you know• Passwords• Secret keyWhere you are• IP address• Physical locationWhat you are• BiometricsWhat you have• Secure tokensAll have advantages and disadvantagesWhy Authenticate?To prevent an attacker from breaking into our account• Co-worker, family member, ...To prevent an attacker from breaking into any account on our system• Unix system– Break into single account, then exploit local vulnerability or mount a “stepping stones” attack• Calling cards• BuildingTo prevent an attacker from breaking into any account on any systemAlso NeedUsability!• Remember password?• Have to bring physical object with us all the time?Denial of service• Stolen wallet• Try to authenticate as you until your account becomes locked• What about a military or other mission critical scenario– Lock all accounts - system unusablePassword-Based AuthenticationUser has a secret password. System checks it to authenticate the user.• May be vulnerable to eavesdropping when password is communicated from user to systemHow is the password stored?How does the system check the password?How easy is it to remember the password?How easy is it to guess the password?• Easy-to-remember passwords tend to be easy to guess• Password file is difficult to keep secretCommon usage modesAmazon = t0p53cr37UWNetID = f0084r#1Bank = a2z@m0$;Image from http://www.interactivetools.com/staff/dave/damons_office/Common usage modesWrite down passwordsShare passwords with othersUse a single password across multiple sites• Amazon.com and Bank of America?• UW CSE machines and Facebook?• GMail and Facebook?Use easy to remember passwords• Favorite <something>?• Name + <number>?Other “authentication” questions• Mother’s maiden name?Some anecdotes [Dhamija and Perrig]Users taught how to make secure passwords, but chose not to do soReasons:• Awkward or difficult• No accountability• Did not feel that it was importantUniversity of Sydney Study [Greening ‘96]336 CS students emailed message asking them to supply their password• Pretext: in order to “validate” the password database after a suspected break-in138 students returned their password30 returned invalid password200 changed their password(Not disjoint)Still, 138 is a lot!AwkwardHow many times do you have to enter your password before it actually works?• Sometimes quite a few for me! (Unless I type extra slowly.)Interrupts normal activity• Do you lock your computer when you leave for 5 minutes?• Do you have to enter a password when your computer first boots? (Sometimes it’s an option.)And memorability is an issue!Untrusting of friends• Locking computer every time you get upMemorability [Anderson]Hard to remember many PINs and passwordsOne bank had this idea• If pin is 2256, write your favorite 4-letter word in this grid• Then put random letters everywhere elseMemorability [Anderson]Problem!Normally 10000 choices for the PIN --- hard to guess on the first tryNow, only a few dozen possible English words --- easy to guess on first try!How should we store passwords on a server?• In cleartext?• Encrypted?• Hashed?UNIX-Style Passwords t4h97t4m43 fa6326b1c2 N53uhjr438 Hgg658n53 …usersystem password file“cypherpunk”hashfunctionPassword HashingInstead of user password, store H(password)When user enters password, compute its hash and compare with entry in password file• System does not store actual passwords!• System itself can’t easily go from hash to password– Which would be possible if the passwords were encryptedHash function H must have some properties• One-way: given H(password), hard to find password– No known algorithm better than trial and error(Early) UNIX Password SystemUses DES encryption as if it were a hash function• Encrypt NULL string using password as the key– Truncates passwords to 8 characters!• Artificial slowdown: run DES 25 times– Why 25 times? Slowdowns like these are important in practice!• (“Don’t use DES like this at home.”)• Can instruct modern UNIXes to use MD5/SHA1 hash functionProblem: passwords are not truly random• With 52 upper- and lower-case letters, 10 digits and 32 punctuation symbols, there are 948 ≈ 6 quadrillion possible 8-character passwords (around 252)• Humans like to use dictionary words, human and pet names ≈ 1 million common passwordsDictionary AttackPassword file /etc/passwd is world-readable• Contains user IDs and group IDs which are used by many system programsDictionary attack is possible because many passwords come from a small dictionary• Attacker can compute H(word) for every word in the dictionary and see if the result is in the password file• With 1,000,000-word dictionary and assuming 10 guesses per second, brute-force online attack takes 50,000 seconds (14 hours) on average– This is very conservative. Offline attack is much faster!• As described (H(word)), could just create dictionary of “word to H(word)” mapping once -- for all users!!Saltalice:fURxfg,4hLBX:14510:30:Alice:/u/alice:/bin/csh/etc/passwd entrysalt(chosen randomly whenpassword is first set)hash(salt,pwd)Password• Users with the same password have different entries in the password file • Online dictionary attack is still possible! (Precomputed dictionaries possible too -- but significantly more expensive.)Basically, encrypt NULL plaintextAdvantages of SaltingWithout salt, attacker can pre-compute hashes of all dictionary words once for all password entries• Same hash function on all UNIX machines• Identical passwords hash to identical values; one table of hash values can be used for all password filesWith salt, attacker must compute hashes of all dictionary words once for each password entry• With 12-bit random salt, same password can hash to 212 different hash values• Attacker must try all dictionary
View Full Document