Slide 1How do you authenticate?Early Password SchemesLogin ProcessAuthentication ProblemsEncrypted PasswordsHashed PasswordsEncrypted Passwords Try 1Encrypted Passwords Try 2First UNIX Password SchemeMaking Brute Force Attacks HarderDictionary Attacks86% of users are dumbMaking Dictionary Attacks HarderProblems with User RulesTrue AnecdoteEverybody loves BuddySalt of the EarthSecurity of UNIX PasswordsWhat about Eve?Simplified SSH ProtocolActual SSH ProtocolComparing to stored KUSWhy Johnny Can’t Even Loginssh.com’s SSHssh ErrorSlide 27Why Johnny (von Neumann) Can’t Even LoginRecap – Authentication ProblemsSlide 30GAO IRS StudySolution – Don’t Reuse PasswordsOne-Time Use PasswordsS-KeyS/Key LoginS/KeySlide 37Challenge-ResponseChallenge-Response SystemsBiometrics: “Something you are”UAE Iris ScanningSlide 42Problems with BiometricsChargeDavid Evanshttp://www.cs.virginia.edu/evansCS588: CryptographyUniversity of VirginiaComputer ScienceLecture 19:AuthenticationJohn Daugman, http://www.cl.cam.ac.uk/users/jgd1000/iriscollage.jpg19 April 2005 University of Virginia CS 588 2How do you authenticate?•Something you know–Password•Something you have–SecureID, physical key•Something you are–Biometrics (voiceprint, fingerprint, etc.)•Decent authentication requires combination of at least 2 of these19 April 2005 University of Virginia CS 588 3Early Password SchemesUserID Passwordalgore internalcombustionclinton buddygeorgew gorangersLogin: algorePassword: tipperFailed login. Guess again.Login does direct password lookup and comparison.19 April 2005 University of Virginia CS 588 4Login: algorePassword: internalcombustionTerminalTrusted SubsystemEveLogin Processlogin sends <“algore”, “internalcombustion”>19 April 2005 University of Virginia CS 588 5Authentication Problems•Need to store the passwords somewhere – dangerous to rely on this being secure–Encrypt them? But then, need to hide key•Need to transmit password from user to host–Use a secure line (i.e., no remote logins)–Encrypt the transmission (what key?)19 April 2005 University of Virginia CS 588 6Encrypted PasswordsUserID Passwordalgore E (“internalcombustion”, K)clinton E (“buddy”, K)georgew E (“gorangers”, K)Hmmm.... D (E (“buddy”, K), K) = “buddy”19 April 2005 University of Virginia CS 588 7Hashed PasswordsUserID Passwordalgore H (“internalcombustion”)clinton H (“buddy”)georgew H (“gorangers”)19 April 2005 University of Virginia CS 588 8Encrypted Passwords Try 1Login: algorePassword: internalcombustionTerminalTrusted Subsystemlogin sends <“algore”, H(“internalcombustion”)>Trusted subsystem compares to stored value.19 April 2005 University of Virginia CS 588 9Encrypted Passwords Try 2Login: algorePassword: internalcombustionTerminalTrusted Subsystemlogin sends <“algore”, “internalcombustion”>Trusted subsystem computes H(“internalcombustion”) and compares to stored value.19 April 2005 University of Virginia CS 588 10First UNIX Password Scheme•[Wilkes68] (recall DES was 1976)•Encryption based on M-209 cipher machine (US Army WWII)•Easy to invert unknown plaintext and known key, used password as key:–Instead of EK (password) used hash function EPassword (0) •PDP-11 could check all 5 or less letter lower-case passwords in 4 hours!19 April 2005 University of Virginia CS 588 11Making Brute Force Attacks Harder•Use a slower encryption (hashing) algorithm–Switched to DES: H(p) = DESp(0)•Even slower: run DES lots of times–UNIX uses DESp25(0) … DESp (DESp (DESp (DESp (0)))) •Require longer passwords–DES key is only 56 bits: only uses first 7.5 characters (ASCII)–95 printable characters, 958 = 6.6 * 101519 April 2005 University of Virginia CS 588 12Dictionary Attacks•Try a list of common passwords–All 1-4 letter words–List of common (dog) names–Words from dictionary–Phone numbers, license plates–All of the above in reverse•Simple dictionary attacks retrieve most user-selected passwords•Precompute H(x) for all dictionary entries19 April 2005 University of Virginia CS 588 1386% of users are dumbSingle ASCII character 0.5%Two characters 2%Three characters 14%Four alphabetic letters 14%Five same-case letters 21%Six lowercase letters 18%Words in dictionaries or names 15%Other (possibly good passwords) 14%(Morris/Thompson 79)At Least19 April 2005 University of Virginia CS 588 14Making Dictionary Attacks Harder•Force/convince users to pick better passwords–Test selected passwords against a known dictionary–Enforce rules on non-alphabet characters, length, etc.•Don’t let attacker see the password file19 April 2005 University of Virginia CS 588 15Problems with User Rules•Users get annoyed•If you require hard to remember passwords, users write them down•Attackers know the password selection rules too – reduces search space!19 April 2005 University of Virginia CS 588 16True Anecdote•One installation: machines generated random 8-letter passwords•Used PDP-11 pseudo-random number generator with 215 possible values•Time to try all possible passwords on PDP-11: One minute! •Good news: at least people don’t have to remember the 8 random letters19 April 2005 University of Virginia CS 588 17Everybody loves BuddyUserID Passwordalgore DES25 internalcombustion (0)clinton DES25 buddy (0)georgew DES25gorangers(0)hillaryc DES25 buddy (0)19 April 2005 University of Virginia CS 588 18Salt of the EarthUserID Salt Passwordalgore 1125 DES+25 (0, “internal”, 1125)clinton 2437 DES+25 (0, “buddy”, 2437)georgew 932 DES+25 (0, “goranger”, 932)hillaryc 1536 DES+25 (0, “buddy”, 1536)How much harder is the off-line dictionary attack?DES+ (m, key, salt) is DES except with salt-dependent E-tables.Salt: 12 random bits(This is the standard UNIX password scheme.)19 April 2005 University of Virginia CS 588 19Security of UNIX Passwords•Paper by Robert Morris (Sr.) and Ken Thompson, 1979 (link on manifest)•Demonstration of guessability of Unix passwords by Robert Morris, Jr. (Internet Worm, 1988)•L0ftcrack breaks ALL alphanumeric passwords in under 24 hours on Pentium II/450 (Windows NT)19 April 2005 University of Virginia CS 588 20What about Eve?Login: algorePassword: internalcombustionTerminalTrusted Subsystemlogin sends <“algore”, “internalcombustion”>Trusted subsystem computes DES+25 (0, “internal”, 12) and compares to stored value.EveSSssssshhhh…Be very quiet so Eve can’t