CSC 474/574 Dr. Peng Ning 1Computer ScienceCSC 474/574Information Systems SecurityTopic 3.2: User AuthenticationCSC 474/574 Dr. Peng Ning 2Computer ScienceUser Authentication• What the user knows– passwords, personal information• What the user possesses– a physical key, a ticket, a passport, a token, asmart card• What the user is (biometrics)– fingerprints, voiceprint, signature dynamicsCSC 474/574 Dr. Peng Ning 3Computer SciencePasswords• Most commonly used method.AliceComputerSystemI’m Alice, the password is fiddlesticksCSC 474/574 Dr. Peng Ning 4Computer ScienceStoring User Passwords• Directly Store the Passwords?– Not a good idea!– High risk• Anyone who captures the password database couldimpersonate all the users.• The password database would be very attractive tohackers.CSC 474/574 Dr. Peng Ning 5Computer ScienceOne-Way Hash Function• One-way hash function F– F(x) is easy to compute– From F(x), x is difficult to compute– Example: F(x) = gx mod p, where p is a largeprime number and g is a primitive root of p.Fx F(x)easydifficultCSC 474/574 Dr. Peng Ning 6Computer ScienceStoring Passwords• For each user, system stores(user name, F(password))in a password file, where F is a one-way hashfunction• When a user enters the password, systemcomputes F(password); a match providesproof of identityCSC 474/574 Dr. Peng Ning 7Computer ScienceWhat is F?• crypt Algorithm (Unix)– Designed by Bob Morris and Ken Thompson– Use Data Encryption Standard (DES) encryption algorithm– User password and salt is used as the encryption key toencrypt a 64-bit block of zeros– This process is repeated 25 timesDES•00…0•x = Password+Salt25 times•F(x)64 bitsCSC 474/574 Dr. Peng Ning 8Computer ScienceChoice of Passwords• Suppose passwords can be from 1 to 9 characters inlength• Possible choices for passwords = 261 + 262 + ... + 269= 5 *1012• At the rate of 1 password per millisecond, it will takeon the order of 150 years to test all passwordsCSC 474/574 Dr. Peng Ning 9Computer ScienceChoice of Passwords (Cont’d)• However, we don’t need to try all possiblepasswords, only the probable passwords• In a Bell Labs study (Morris & Thompson 1979),3,289 passwords were examined– 15 single ASCII characters, 72 two ASCII characters, 464three ASCII characters, 477 four alphanumeric character,706 five letters(all lower or all upper case), 605 six lettersall lower case, 492 weak passwords (dictionary wordsspelled backwards, first names, surnames, etc.)– Summary: 2,831 passwords (86% of the sample) wereweak, i.e., they were either too easily predictable or tooshortCSC 474/574 Dr. Peng Ning 10Computer ScienceDictionary Attacks• Attack 1:– Create a dictionary of common words and names and theirsimple transformations– Use these to guess the passwordEagleWineRose…DictionaryEagleYes!CSC 474/574 Dr. Peng Ning 11Computer ScienceDictionary Attacks (Cont’d)• Attack 2:– Usually F is public and so is the password file• In Unix, F is crypt, and the password file is /etc/passwd.– Compute F(word) for each word in the dictionary– A match gives the passwordEagleWineRose…DictionaryTdWx%XkPTKYEN…Password fileF(Eagle)=XkPTCSC 474/574 Dr. Peng Ning 12Computer ScienceDictionary Attacks (Cont’d)• Attack 3:– To speed up search, pre-compute F(dictionary)– A simple look up gives the passwordEagleWineRose…DictionaryTdWx%XkPTKYEN …Password fileXkPT%$DVC#AED!…Pre-computedDictionaryF Look upCSC 474/574 Dr. Peng Ning 13Computer SciencePassword Salt• To make the dictionary attack a bit more difficult• Salt is a 12-bit number between 0 and 4095• Derived from the system clock and the processidentifierCSC 474/574 Dr. Peng Ning 14Computer SciencePassword Salt (Cont’d)• Storing the passwordsFPassword + SaltF(Password + Salt)Username, Salt, F(Password + Salt)Password fileCSC 474/574 Dr. Peng Ning 15Computer SciencePassword Salt (Cont’d)• Verifying the passwordsFPassword + SaltF(Password + Salt)Username, Salt, F(Password + Salt)Password fileFetch Saltaccording to usernameCompareCSC 474/574 Dr. Peng Ning 16Computer ScienceDoes Password Salt Help?• Attack 1?– Without Salt– With SaltEagleWineRose…DictionaryA wordYes/NoCSC 474/574 Dr. Peng Ning 17Computer ScienceDoes Password Salt Help?• Attack 2?– Without Salt– With SaltEagleWineRose…DictionaryTdWx%XkPTKYEN…Password fileFCSC 474/574 Dr. Peng Ning 18Computer ScienceDoes Password Salt Help?• Attack 3?– Without Salt– With SaltEagleWineRose…DictionaryTdWx%XkPTKYEN …Password file%$DVCXkPT#AED!…Pre-computedDictionaryF Look upYCSC 474/574 Dr. Peng Ning 19Computer SciencePassword Management Policy and Procedure• Educate users to make better choices– Does not work if the user population is large or novice• Define rules for good password selection and ask users tofollow them– Rules serve as guideline for attackers• Ask or force users to change their passwords periodically• Force users to use machine generated passwords– Random passwords are difficult to memorize; also password generatormay become known to the attacker through analysis• Actively attempt to break users’ passwords; force users tochange those that are broken– Attacker may have better dictionary• Screen password choices; if a choice is weak, force users tomake a different choiceCSC 474/574 Dr. Peng Ning 20Computer ScienceOne-time Passwords• Use the password exactly once!CSC 474/574 Dr. Peng Ning 21Computer ScienceLamport’s Scheme (S/Key)• Take advantage of One-Way function• One-way hash function F– F(x) is easy to compute– From F(x), x is difficult to computeFx F(x)easydifficultCSC 474/574 Dr. Peng Ning 22Computer ScienceS/Key (Cont’d)• Pre-computationThe System•1. Randomly generate x•2. Compute the followingFx F1(x)FF2(x)F…Fn(x)•3. Save (username, Fn(x)), and give x to the user.CSC 474/574 Dr. Peng Ning 23Computer ScienceS/Key (Cont’d)• Authentication– The first time, the user supplies F(n-1)(x).– The system checks if F(F(n-1)(x))=Fn(x). If yes, theuser is authenticated and the system replaces Fn(x)with F(n-1)(x).– The second time, the user supplies F(n-2)(x).– The third time, …FF(i-1)(x) Fi(x)CSC 474/574 Dr. Peng Ning 24Computer ScienceTime Synchronized• There is a hand-held authenticator– It contains an internal clock, a secret key, and a display– Display outputs a function of the current time and the key– It changes about once per