Strong Pass Algorithms for Zero Knowledge Authentication Galen Mecham Purdue University Information Security Fall 2005 Goal To Design a New Authentication Protocol Desired Attributes As easy to use as the conventional username password system Based on zero knowledge Strong against dictionary and eavesdropper attacks Strong against guessing attacks in which the attacker tries to guess the secret function Username Password Authentication Simple and convenient for the user Password is re used each time Susceptible to both dictionary and eavesdropper attacks Zero Knowledge Authentication User asserts their identity by proving they know a secret but without revealing that secret Based on challenge response authentication A secret function is used to generate a response from the challenge but without revealing the secret function Password changes each time Much stronger against dictionary and eavesdropper attacks The Protocol Design Dilemma A secret function which is easier for a user to remember input is also easier for an attacker to guess A secret function which is harder for a user to remember input is also harder for an attacker to guess How can we find the perfect balance The Classic Cave Example Alice knows the secret to opening the door in the back of the cave but does not wish to reveal the secret to Bob The Classic Cave Example Alice begins by randomly choosing either side A or B while Bob patiently waits outside The Classic Cave Example Bob randomly chooses a side from which he requests Alice to emerge The Classic Cave Example Alice emerges from the requested side Protocol must be repeated many times Feige Fiat Shamir Identification Requires tedious calculations in order to provide authentication Just as in the cave example must be completed many times to ensure validity The computer could do the calculations but the secret function must then be stored on the system insecure Too complex for the user to perform the calculations Smart Cards Performs complex zero knowledge calculations on behalf of the user Eliminates the need to store the secret function on the user s system Requires special hardware the card and reader Imposes the inconvenience of having to carry the card in order to provide authentication Pass Algorithms Challenge and response both consist of character strings Requires that the user enters only a single response to the challenge Secret function is not stored on the user s system Strong Pass Algorithms We will define a ZK Authentication protocol which we will call a Strong Pass Algorithm 16 character challenge 16 character response Difficult for an attacker to guess the secret function Secret function is easy for the user to both remember and enter Character Shifting Response is generated from an 8 character subset of the challenge Each user is assigned as their secret function 1 8 character positions from the challenge 2 Number of times each character is shifted Shifting consists of selecting the next n characters which come either before OR after Example User s secret function consists of every other letter each shifted once Challenge AWSORKFDVIXVKFDR Response BTSGWYLE Random Characters The user is now allowed to add 4 random characters to the response Random characters can be any characters placed anywhere within the response The randomness confuses an attacker who is trying to guess the secret function Example User s secret function consists of every other letter each shifted once Challenge AWSORKFDVIXVKFDR Response BTXSGZWDYLUE Real Randomness Fact Humans make horrible pseudo random number generators We account for this by forcing the user to type characters which will appear to be random As the user types only new characters are registered by the system This results in a small part of the secret function being stored on the system but makes the secret function harder to guess for an eavesdropper Modification 1 Upper case characters in the challenge correspond to lower case letters in the response and vise versa Numbers and control characters are also allowed Control characters used are the ones which run across the top of the keyboard Control characters are shifted using the order in which they are arranged on the keyboard Example User s secret function consists of every other character each shifted once Challenge wSor FDVi Vk Dx Response tXSe ud LUc Modification 2 Finally we add 4 additional random characters 2 each at the beginning and end of the string Helps confuse the attacker while avoiding dictionary attacks The randomness confuses an attacker who is trying to guess the secret function Example User s secret function consists of every other character each shifted once Challenge wSor FDVi Vk Dx Response A tXSe ud LUc n Conclusion Protocol is stronger against dictionary and eavesdropper attacks than username password Secret function is difficult for an attacker to guess Secret function is relatively easy for a user to remember and use Can be combined with a conventional username password system for additional security