Defenses against Online Password Guessing Attacks with PGRP

Defenses against Online Password Guessing Attacks with PGRP

Nikitha H S Sowmya D M Syeda Saher Anjum Varsha V

City Engineering College, Bangalore, India.

nsubramanya72@gmail.com sowmyamanohar45@gmail.com justsweety7@yahoo.com varshav2312@gmail.com

AbstractBrute force and dictionary attacks on password-only remote login services are now widespread and ever increasing. Enabling convenient login for legitimate users while preventing such attacks is a difficult problem. Automated T u r i n g Tests (ATTs) continue to be an effective, easy-to-deploy approach to identify automated malicious login attempts with reasonable cost of inconvenience to users. In this paper, we discuss the inadequacy of existing and proposed login protocols designed to address large- scale online dictionary attacks (e.g., from a Botnet of hundreds of thousands of nodes). We proposes a new Password Guessing Resistant Protocol (PGRP), derived upon revisiting prior proposals designed to restrict such attacks. While PGRP limits the total number of login attempts from unknown remote hosts to as low as a single attempt per username, legitimate users in most cases (e.g., when attempts are made from known, frequently-used machines) can make several failed login attempts before being challenged with an ATT. We analyze the performance of PGRP w i t h two real- world data sets and find it more promising than existing proposals.

Index TermsOnline password guessing attacks, brute force attacks, password dictionary, ATTs.

1. INTRODUCTION

   ONLINE guessing attacks on password- based systems are inevitable and commonly observed against web applications and SSH logins. In a r e c e n t report, S A N S identified password guessing attacks on websites as a top c yb e r s e c ur i t y risk. As an example of

   SSH password- guessing attacks, one experimental Linux honeypot setup has been reported to suffer on average 2,805 SSH malicious login attempts per computer per day . Interestingly, SSH servers that disallow standard password authentication may also suffer guessing attacks, e.g., through the exploitation of a lesser known/used SSH server configuration called keyboard interactive authentication .However, online attacks have some inherent disadvantages compared to offline attacks: attacking machines must engage in an interactive protocol, thus allowing easier detection; and in most cases, attackers can try only limited number of guesses from a single machine before being locked out, delayed, or challenged to answer Automated Turing Tests . Consequently, attackers often must employ a large number of machines to avoid

   d e t e c t i o n or lock-out. On the other hand, as users generally choose common and relatively weak passwords (thus allowing effective password dictionaries and attackers currently control large botnets online attacks are much easier than before.

2. RELATED WORKS

   As discussed in Section 1, ATT challenges are used in some login protocols to prevent automated programs from brute force and dictionary attacks. Pinkas a n d Sander [ 17] presented a login protocol (PS protocol) based on ATTs to Protect against online password guessing attacks. It reduces the number of ATTs that legitimate users must correctly answer so that a user with a valid browser cookie (indicating that the user

   has previously logged in successfully) will rarely be prompted to answer an ATT. A deterministic function (AskAT T ðÞ) of the entered user credentials is used to decide whether to ask the user an ATT. To i m p r o v e the security of t h e PS protocol, van Oorschot and Stubblebine [23] suggested a modified protocol in which ATTs are always required once the number of failed login attempts for a particular username exceeds a threshold; other modifications were introduced to Reduce the effects of cookie theft.

   For b o t h PS and VS protocols, the d e c i s i o n function AskATT( ) requires careful design. He and Han [9] pointed out that a poor design of this function may make the login protocol vulnerable to attacks such as the known function attack (e.g., if a simple cryptographic hash function of the username and the password is used as AskATT( ) and changed password attack(i.e., an adversary mounts a dictionary attack before and after a password change event initiated by a valid user). The authors proposed a secure nondeterministic keyed hash function as AskATT( ) so that each username is associated with one key that should be changed whenever the corresponding password is changed. The p r o p o s e d function requires extra s e r v e r – side storage per username and at least one cryptographic hash operation per login attempt.

3. PASSWORD GUESSING RESISTANT PROTOCOL

   In this section, we present the PGRP protocol, including the goals and design choices.

   1. Goals and Operation Assumptions

      1. Protocol Goals

         Our objective for PGRP include the following:

         1. The login protocol should make brute force and dictionary attacks ineffective even for adversaries with access to large botnets (i.e., capable of launching the attack from many remote hosts).

            Fig 1.PGRP Password Guessing Resistant Protocol

         2. The protocol should not have any significant impact on usability (user convenience). For example: for legitimate users, a n y additional steps besides e n t e r i n g login credentials should be minimal. Increasing the security of the protocol must have minimal effect in decreasing the login usability.

         3. The protocol should be easy to deploy and scalable, requiring minimum c o m p u t a t i o n a l resources in terms of memory, processing time, and disk space.

      2. Assumptions

         We assume that adversaries can solve a small percentage of ATTs, e.g., through a u t o m a t e d p r o g r a m s , b r u t e force mechanisms, and low paid workers (e.g., Amazon Mechanical Turk [ 1]). Incidents of attackers using IP addresses of known machines and c o o k i e t h e f t f o r targeted password

         Guessing is also assumed to be minimal. Traditional password-based

         a u t h e n t i c a t i o n is n o t suitable for any entrusted environment (e.g., a key logger may r e c o r d all keystrokes, including passwords in a system, and fo r wa r d those to a remote attacker). We do not prevent existing such attacks in untr usted environments, and thus essentially assume any machines that legitimate users use for login are trustworthy. The data integrity of cookies must be protected (e.g., by a MAC using a key known only to the login server.

   2. Data Structure and Function Description

      1. Data Structures

         PGRP maintains three Data Structures

         1. W. A list of {source IP address, username} pairs such that for each pair, a successful login from the source IP a d d r e s s h a s been initiated f o r the u s e r n a m e previously.

         2. F T. Each entry in this table represents the number of failed l o g i n a t t e m p t s for a valid u s e r n a m e , UN. A maximum of K2 failed l o g i n a t t e mp t s are recorded. Accessing a nonexistent index returns 0.

         3. F S. Each entry in this table represents the number of failed login attempts for each pair of (srcI P , un). Here, srcIP is the IP address for a host in W or a host with a valid cookie, and un is a valid username attempted from srcI P . A maximum of k1 failed login attempts are recorded; crossing this threshold may mandate p a s s i n g an ATT (e.g., depending on F T ½un). An entry is set to 0 after a successful login attempt. Accessing a nonexisent index returns0.

         Each entry in W , F T , and F S has a write-expiry interval such that the entry is deleted when the given period of time (t1 , t2 , or t3 ) has lapsed since the last time the entry was inserted or modified. There are different ways to implement

         write-expiry intervals (e.g., h a s h b e l t [14]). A simple approach is to store a timestamp of the insertion time with each entry such that the timestamp is updated whenever the entry is modified. At anytime the entry is accessed, if the delta between the access time and the entry timestamp is greater than the data structure write-expiry interval (i.e., t1 , t2 , or t3 ), the entry is deleted.

      2. Functions

         PGRP uses t he following functions (IN denotes input and OUT denotes output):

         1. ReadCredential(OUT:un,pw,cookie). Shows a login prompt to the user and returns the entered username and password, and the cookie received from the users browser (if any).

         2. LoginCorrect(IN:un,pw;OUT:true/f alse). If the provided username- password pair is valid, the function returns true; otherwise, it returns false.

         3. GrantAccess (IN: UN, cookie). The function sends the cookie to the u s e r s b r o w s e r and t h e n enables access to the specified user account.

         4.M essage(IN: text). Shows a text message.

         5.ATT Challenge (OUT: Pass/Fail). Challenges the user with an ATT and returns Pass if the answer is correct; otherwise, it returns Fail. 6.ValidUsername(IN:un;OUT:true/fal se). If the p r o v i d e d username exists in the l o g i n system, the function returns true; otherwise, it returns false.

         7.Valid(IN:cookie,un,k1,state;OU T:Cookie ,true/false).

         First, t h e f u n c t i o n checks t h e validity of the cookie (if any) where it is considered invalid in the following cases: 1) the login username does not match the cookie username; 2) the cookie is expired; or 3) the cookie counter is equal to or greater than k1. The function returns true only when a valid cookie is received. If state ¼ true (i.e., the entered user credentials are correct, as in line 4 of Fig. 1), a new cookie is created (if cookies are supported in the login system) including the

         f o l l o w i n g information: user- name, expiry d a t e , a n d a counter of the number of failed login attempts (since the last successful login; initialized to 0 ). Notice that if s t a t e ¼ true, the function does not send the created cookie to the users browser. Rather, the c oo ki e is s e n t later by t h e GrantAccessðÞ function. If s t a t e ¼ false (i.e., the entered user credentials are incorrect, as in line 16 of Fig. 1) And a valid cookie is received, the c o o k i e counter is incremented by one and the cookie is sent back to the users browser. No action is performed for all the other cases.

   3. Decision Function for requesting ATTs

      Below we discuss issues related to ATT challenges as provided by the login server in Fig.1.The decision to challenge the user with an ATT depends on two f a c t o r s :

      1. whether the user has authenticated successfully from the same machine previously; and

      2. The total number of failed login attempts for a specific user account.

      1. Username Password pair is valid

         As in the condition in line 4, upon entering a correct username-password pair, the user will not be asked to answer an ATT challenge in the following cases:

         1. A valid cookie is received from the user machine (i.e., the function Valid returns true) and the number of failed login attempts from the user machines IP address for that username, F S[½srcIP, un], is less than k1 over a time period determined by t3 ;

         2. The user machines IP address is in the whitelist W and the number of failed login attempts from this IP address for that username, F S½srcI P ; un , is less than k1 over a time period determined by t3 ;

         3. The number of failed login

         attempts from any machine for that username, F T ½un , is below a threshold k2 over a time period determined by t2 .

         The last case enables a user who tries to

         login from a new machine/IP address for

         the first time before K2 is reached to proceed without an ATT. However, if the number of failed login attempts for the username exceeds the threshold k2 (default 3), this might indicate a guessing attack and hence the user must pass an ATT challenge.

      2. Username-Password Pair is Invalid Upon entering an incorrect username- password pair, the user will not be asked to answer an ATT challenge in the following cases:

         1. A valid cookie is received from the user machine (i.e., the function Valid returns true) and the number of failed login attempts from the user machines IP address for that username, F S½srcI P ; un , is less than k1 (line 16) over a time period determined by t3 ;

         2. The user machines IP address is in the whitelist W and the number of failed login attempts from this IP address for that username, F S½srcI P ; un , is less than k1 (line 16) over a time period determined by t3 ;

         3. The username is valid and the

            number of failed login attempts (from any machine) for t h a t u s e r n a me , F T ½un, is below a threshold K2 (line 19) over a time period determined by t2.

            A failed login attempt from a user with a valid cookie or in the whitelist W will not increase the total number of failed login attempts in the F T table since it is expected that legitimate users may potentially forget or mistype their password (line 16-18). Nevertheless, if the user machine is identified by a cookie, a corresponding counter of the failed login attempts in the cookie will be updated. In addition, the F S entry indexed by the

            {source IP address, username} pair w i l l also be incremented (line 17 ). Once the cookie counter or the corresponding F S entry hits or exceeds the threshold k1 (default value 30), the user must correctly answer an ATT challenge.

      3. Output Messages

PGRP shows different messages in case of incorrect {username, password} pair (lines

21 and 24) and incorrect answer to the given ATT challenge (lines 14 and 26). While showing a human that the entered pair is incorrect, an automated program unwilling to answer the ATT challenge cannot confirm whether it is the pair or the ATT that was incorrect. However, while this is more convenient for legitimate users, it gives more information to the attacker about the answered ATTs. PGRP can be modified to display only one message in lines 14, 21, 24, and 26 (e.g., login fails as in the PS and VS protocols) to prevent such information leakage.

1. SYSTEM RESOURCES

   In PGRP, three tables must be maintained. First the whitelist, W is expected to grow linearly with the number of users. At any given time, W contains a list of {source IP address, username} pairs that have been successfully authenticated in the last t1 units of time. Second, the number of entries in F T increases by one whenever a remote host makes a failed login attempt using a valid username, if the username is not already in F T , and the remote hosts IP address is not in W (or has no valid cookie). Therefore, unlike the VS protocol, the total number of valid usernames in the login server puts an upper bound on the number of entries in F T since a failed login attempt for a nonexistent username does not affect this table.

   A new entry is added to F S only when a valid{username, password} pair is provided from an IP address not used before for this username. Therefore, the number of entries in F S is proportional to the number of IP addresses legitimate users successfully authenticated from. Increasing t3 increases the number of

   entries in FS s i nc e t h e t a b l e entries l a s t

   longer. The number of entries in F S is expected to be close to the number of active users within the last t3 units of time.

   TBLE 1

   Comparison of Protocol limitations

2. CONCLUDING REMARKS

Online password guessing attacks on password-only systems have been observed for decades (see, e.g., [21]). Present day attackers targeting such systems are empowered by having control of thousand to million-node botnets. In previous ATT-based login protocols, there exists a security- usability trade-off with respect to the number of free failed login attempts (i.e., with no ATTs) versus user login convenience (e.g., less A T T s and o t h e r r e q u i r e m e n t s ). In contrast, PGRP is more restrictive against brute force and dictionary attacks w h i l e s a fe l y allowing a large number of free fa i l e d attempts for legitimate users. Our empirical experiments on two data sets (of one-year duration) gathered from operational network environments show that while PGRP is apparently more effective in preventing password guessing attacks (without answering ATT challenges), it also offers more convenient login experience, e.g., fewer ATT challenges for legitimate users even if no cookies are available. However, we r e i t e r a t e that no u s e r testing of PGRP has been conducted so far.

PGRP appears suitable for organizations of both small and l a r g e n u m b e r of user a c c o u n t s . The required system resources (e.g., memory space) are linearly proportional to the n u mb e r of users in a system. PGRP can also be used

with remote login services where cookies are not applicable (e.g., SSH and FTP).

ACKNOWLEDGEMENTS

The second author is supported by an NSERC postdoctoral fellowship and by N S E R C I S S N e t . The third author is Canada Research Chair in Authentication and Computer Security and acknowledges NSERC for funding the chair, and a Discovery Grant. Partial funding from NSERC ISSNet is also acknowledged.

REFERNCES

1. Amazon Mechanical Turk. https://www.mturk.com/mturk/, June 2010.

2. S.M. Bellovin, A Technique for Counting Natted Hosts, p ACM SIGCOMM Workshop Internet Measurement, pp. 267-272,2002

3. M. Casado and M.J. Freedman, Peering through the Shroud: The Effect of Edge Opacity on Ip-Based Client Identification, Proc. Fourth USENIX Symp. Networked Systems Design and Implementation (NDSS 07), 2007.

4. S. Chiasson, P.C. van Oorschot, and R. Biddle, A Usability Study and Critique of Two Password Managers, Proc. USENIX Security Symp., pp. 1-16, 2006.

5. D. Florencio, C. Herley, and B. Coskun, Do Strong Web Passwords Accomplish Anything?, Proc. USENIX Workshop Hot Topics in Security (HotSec 07), pp. 1-6, 2007.

6. K. Fu, E. Sit, K. Smith, and N. Feamster, Dos and Donts of Client Authentication on the Web, Proc. USENIX Security Symp., pp. 251-268, 2001.

7. P. Hansteen, Rickrolled? Get Ready for the Hail Mary Cloud!, http://bsdly.blogspot.com/2009/11/rickrol led-get-ready-for-hail-mary.html, Feb. 2010.

8. Y. He and Z. Han, User Authentication with Provable Security against Online Dictionary Attacks, J. Networks, vol. 4, no. 3, pp. 200- 207, May 2009.

9. T. Kohno, A. Broido, and K.C. Claffy, Remote Physical

   Device Fingerprinting, Proc. IEEE Symp.

   Security and Privacy, pp. 211-225,2005.

10. M. Motoyama, K. Levchenko, C. Kanich, D. Mccoy, G.M. Voelker, and S. Savage, Re: CAPTCHAs Understanding CAPTCHA- Solving Services in an Economic Context, Proc. USENIX Security Symp., Aug. 2010.

11. C. Namprempre and M.N. Dailey, Mitigating Dictionary Attacks with Text-Graphics Character Captchas, IEICE Trans. Fundamen- tals of Electronics, Comm. and Computer Sciences, vol. E90-A, no. 1, pp. 179-186, 2007.

12. Natl Inst. of Standards and Technology (NIST), Hashbelt.

http://www.itl.nist.gov/div897/sqg/dads/HTML/hashb elt.html,