Johnny Can Obfuscate; Beyond Mother’s Maiden NameWilliam CheswickLumeta Corp.AbstractChallenge/response authentication is stronger thanpassword authentication, but has traditionally re-quired a device for computing the challenge. Thoughhuman computation is limited, people can computesimple responses to challenges. If the challenge andthe corresponding response is obfuscated with de-coy information, an authentication scheme might bestrong enough for a number of applications. Thesigns used in major league baseball provide some in-teresting techniques for obfuscation.1 IntroductionPasswords have a long history of use, and of fail-ure. They are subject to eavesdropping, guessing,and in many cases dictionary attacks. The humanis the weak link in the chain: we would like him tochoose cryptographically-strong keys, and he wantsto remember something simple and get on with hiswork. Passwords can work acceptably if we can ruleout eavesdropping and dictionary attacks. Unfortu-nately, eavesdropping is a common part of malwareattacks.Any one-time password solution is at least asgood as, and usually better than fixed pass-words. The strongest of these is challenge/responseauthentication[3], but that usually requires a hard-ware token, (expensive to deploy in quantity) orsome sort of printout.[13] These something-you-havesolutions are useless if you lose the token. Asomething-you-know solution would be more conve-nient, and could be worth deployment.I propose to have the unaided human computethe proper response to a challenge. If successful,this technique would offer much of the strength ofone-time passwords over fixed passwords, at muchless cost and similar or greater usability. The usercomputes a simple response to a varying challenge,and is then encouraged to obfuscate this responsein his answer. This can be fun, and a nice changefrom the strict spelling requirements of a passwordor passphrase.A response of a single character might be suffi-cient for a rarely-used system. The hiding mecha-nism must be good enough that simple random au-thentication guesses will not succeed. We can rejectthe response if there is insufficient obfuscation. Thenumber of unsuccessful attempts must be strictlylimited, just as an automated teller will swallow ordeactivate a card if too many incorrect PINs are en-tered. It would be nice if an eavesdropper watchinga year’s worth of daily logins would be unlikely torecover the algorithm used.We can use a secret algorithm, or a public algo-rithm with some sort of key. Secret algorithms havea bad history in cryptography: we’ve learned thatit is better to have a public algorithm, open for in-spection, and a secret key. This paper presents anumber of secret algorithms, but the goal is to re-duce the problem to a key of some sort.The motivation for this work is the demand forbetter authentication, especially in the banking andinteractive community. We need better authentica-tion than passwords, and better back-up authentica-tion than personal questions like “mother’s maidenname (MMN)”.The next section briefly touches the related work.Section 3 covers some of the basics of major leaguebaseball signals, which offers some time-tested tech-niques for obfuscation. Section 4 describes two ex-periments with human computation. Section 5 ex-amines the problem further, finishing with someopen questions in Section 6.12 Related WorkThere is a rich literature on authentication, pass-words, and one-time passwords, which will not bereviewed here. There are also a growing number ofgraphical challenge/response solutions: text-basedsolutions are more general, and can be implementedin Pluggable Authentication Modules (PAM)[15] onUnix systems.Related work falls under several categories:pass-algorithms and reconstructed passwords,[4]zero knowledge authentication, human-computercryptography,[10] HumanAut,[6] Secure Human-Computer Identification (secHCI),[8] cognitive trap-door games,[14] and human interactive proofs(HIP).[1] I will use pass-algorithms, the earliestterm.Text-based pass-algorithms fall into two cate-gories, ad hoc and information-theoretic. The for-mer are the oldest, and also the kind proposed inthis paper. They start with proposals in Hoffman[5],Haskett[4], and Lipton[10], who gave a taxonomy ofpass-algorithms.In 1991, Matsumoto and Imai[12] created and an-alyzed mathematically a pass-algorithm, the first inthe information-theoretic approach. The goal is amathematical analysis that lays out the exact secu-rity against particular attacks for a given key lengthin their algorithm. This work has advanced withwork by Wang et. al.[18], Matsumoto again[11], Liand Teng[9], Hopper[6], and Li and Shaum[8]. (Thelast has a good review of the literature, and in par-ticular the theoretic approach.)All of the information-theoretic approaches wres-tle with the tradeoff between a sufficiently rich keyfor strong authentication, and usability. Keys mustbe short enough to be memorable and usable. I don’tthink they are there yet, but they may have reason-ably simple solutions if they accept the weakenedrequirements suggested here. Roth et. al.[14] in par-ticular seeks to obfuscate simple PINs in ways thatseem more usable.The field of military communications may offerother examples, or lessons, for our pursuit.It is also possible that espionage fieldcraft mayhave some techniques of interest. I have not pursuedeither of these.One technique of accessing a networked computeris port knocking.[7] A series of TCP connection at-tempts to certain ports, or special packets, can un-lock a network server.3 Baseball SignsIn a typical major league baseball game, nearly athousand signs may be issued. Most of these signsare missed by the fans,[2] but they are an importantpart of the game, as are stealing signs from the otherteam.The various coaches and players have to commu-nicate some simple secrets in full public view. Inparticular, the pitcher and catcher negotiate whatthe next pitch is going to be, to help the catcher toprepare to catch it. The base coaches relay a steadystream of instructions to the batter and base run-ners from the head coach. Coordination of offensiveplays can make the difference in a close game. In allcases, this information must be transmitted quicklyand accurately, in public, to and by players who areunder stress, and may not have graduated in the topof their class.They provide some technologies that may help usconfound eavesdroppers of our
View Full Document
Unlocking...