1 AuthenticationCS461/ECE422Fall 20072Reading•Chapter 4.5 from Security in Computing•Chapter 10 from Handbook of Applied Cryptography http://www.cacr.math.uwaterloo.ca/hac/about/chap10.pdf3Overview•Basics of an authentication system•Passwords–Storage–Selection–Breaking them–One time•Challenge Response•Biometrics4Ivanhoe, Sir Walter Scott•Paraphrased:(Wamba gains entry to the castle dressed as a friar)Wamba: Take my disguise and escape, I will stay and die in your place.Cedric: I can’t possibly impersonate a friar, I only speak English.Wamba: If anyone says anything to you, just say “Pax vobiscum.”Cedric: What does that mean?Wamba: I don’t know, but it works like a charm!5Basics•Authentication: binding of identity to subject–Identity is that of external entity (my identity, the Illini Union Bookstore, etc.)–Subject is computer entity (process, network connection, etc.)6Establishing Identity•One or more of the following–What entity knows (e.g. password, private key)–What entity has (e.g. badge, smart card)–What entity is (e.g. fingerprints, retinal characteristics)–Where entity is (e.g. In front of a particular terminal)•Example: scene from Ivanhoe•Example: Credit card transaction7Authentication System•(A, C, F, L, S)–A: information that proves identity–C: information stored on computer and used to validate authentication information–F: set of complementation functions that generates C; f : A → C–L: set of authentication functions that verify identity; l : A × C → { true, false }–S: functions enabling entity to create, alter information in A or C8Authentication SystemA: identity proving infoComputerF: ComplementationC: identityvalidating infoL: AuthenticationF: ComplementationTrue or FalseS: Update9Example•Password system, with passwords stored online in clear text–A set of strings making up passwords–C = A–F singleton set of identity function { I(a) = a }–L single equality test function { eq }–S function to set/change password10Storage•Store as cleartext–If password file compromised, all passwords revealed•Encipher file–Need to have decipherment, encipherment keys in memory–Reduces to previous problem•Store one-way hash of password–If file read, attacker must still guess passwords or invert the hash11Example•Original UNIX system standard hash function–Hashes password into 11 char string using one of 4096 hash functions•As authentication system:–A = { strings of 8 chars or less }–C = { 2 char hash id || 11 char hash }–F = { 4096 versions of modified DES }–L = { login, su, … }–S = { passwd, nispasswd, passwd+, … }12Dictionary Attacks•Trial-and-error from a list of potential passwords–Off-line: know f and c’s, and repeatedly try different guesses g ∈ A until the list is done or passwords guessed•Examples: crack, john-the-ripper–On-line: have access to functions in L and try guesses g until some l(g,c) succeeds•Examples: trying to log in by guessing a password13Preventing Attacks•How to prevent this:–Hide information so that either a, f, or c cannot be found•Prevents obvious attack from above•Example: UNIX/Linux shadow password files–Hides c’s–Block access to all l ∈ L or result of l(a,c)•Prevents attacker from knowing if guess succeeded•Example: preventing any logins to an account from a network–Prevents knowing results of l (or accessing l)14Using TimeAnderson’s formula:•P probability of guessing a password in specified period of time•G number of guesses tested in 1 time unit•T number of time units•N number of possible passwords (|A|)•Then NTGP≥15Example•Goal–Passwords drawn from a 96-char alphabet–Can test 104 guesses per second–Probability of a success to be 0.5 over a 365 day period–What is minimum password length?•Solution–N ≥ TG/P = (365×24×60×60)×104/0.5 = 6.31×1011–Choose s such that–So s ≥ 6, meaning passwords must be at least 6 chars long–What exactly does that equation mean?Nsjj≥∑=09616Approaches: Password Selection•Random selection–Any password from A equally likely to be selected–See previous example–Make sure it’s random! (e.g. period of 232 is not enough for (26+10)8 passwords)•Key crunching (e.g. hashing) a long key to a sequence of shorter keys•Pronounceable passwords•User selection of passwords17Pronounceable Passwords•Generate phonemes randomly–Phoneme is unit of sound, e.g. cv, vc, cvc, vcv–Examples: helgoret, juttelon are; przbqxdfl, zxrptglfn are not•~ 440 possible phonemes•4406 possible keys with 6 phonemes (12-18 characters long), about the same as 968•Used by GNU Mailman mailing list software (?)18User Selection•Problem: people pick easy-to-guess passwords–Based on account names, user names, computer names, place names–Dictionary words (also reversed, odd capitalizations, control characters, “l33t-speak”, conjugations or declensions, Torah/Bible/Koran/… words)–Too short, digits only, letters only–License plates, acronyms, social security numbers–Personal characteristics or foibles (pet names, nicknames, etc.)19Picking Good Passwords•Examples from textbook–“LlMm*2^Ap”•Names of members of 2 families–“OoHeO/FSK”•Second letter of each word of length 4 or more in third line of third verse of Star-Spangled Banner, followed by “/”, followed by author’s initials •What’s good here may be bad there–“DMC/MHmh” bad at Dartmouth (“Dartmouth Medical Center/Mary Hitchcock memorial hospital”), ok here•Why are these now bad passwords? 20Proactive Password Checking•Analyze proposed password for “goodness”–Always invoked–Can detect, reject bad passwords for an appropriate definition of “bad”–Discriminate on per-user, per-site basis–Needs to do pattern matching on words–Needs to execute subprograms and use results•Spell checker, for example–Easy to set up and integrate into password selection system21Salting•Goal: slow dictionary attacks•Method: perturb hash function so that:–Parameter controls which hash function is used–Parameter differs for each password–So given n password hashes, and therefore n salts, need to hash guess n•Doesn't help against attacking a single user–Does help in bulk attack22Examples•Vanilla UNIX method–Use DES to encipher 0 message with password as key; iterate 25 times–Perturb E table in DES in one of 4096