21-01-2013, 12:03 PM
Revisiting Defenses Against Large-Scale Online Password Guessing Attacks
1Revisiting Defenses.pdf (Size: 2.57 MB / Downloads: 94)
Abstract
Brute 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 Turing 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 largescale
online dictionary attacks (e.g., from a botnet of hundreds of thousands of nodes). We propose 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 with two real-world datasets and find it more promising than existing proposals.
INTRODUCTION
Online guessing attacks on password-based systems are
inevitable and commonly observed against web applications
and SSH logins. In a recent report, SANS [20]
identified password guessing attacks on websites as
a top cyber security risk. As an example of SSH
password-guessing attacks, one experimental Linux honeypot
setup has been reported [18] to suffer on average
2,805 SSH malicious login attempts per computer
per day (see also [8]). 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 [19]. 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 lockedout,
delayed, or challenged to answer Automated Turing
Tests (ATTs, e.g., CAPTCHAs [24]). Consequently,
attackers often must employ a large number of machines
to avoid detection or lock-out. On the other hand, as
users generally choose common and relatively weak
passwords (thus allowing effective password dictionaries
[13], [25]), and attackers currently control large botnets
(e.g., Conficker [15]), online attacks are much easier
than before.
RELATED WORK
Although online password guessing attacks have been
known since the early days of the Internet, there is
little academic literature on prevention techniques. Account
locking is a customary mechanism to prevent
an adversary from attempting multiple passwords for
a particular username. Although locking is generally
temporary, the adversary can mount a DoS attack by
making enough failed login attempts to lock a particular
account. Delaying server response after receiving user
credentials, whether the password is correct or incorrect,
prevents the adversary from attempting a large number
of passwords in a reasonable amount of time for a particular
username. However, for adversaries with access to
a large number of machines (e.g., a botnet), this mechanism
is ineffective. Similarly, prevention techniques that
rely on requesting the user machine to perform extra
nontrivial computation prior to replying to the entered
credentials are not effective with such adversaries.
As discussed in Section 1, ATT challenges are used
in some login protocols to prevent automated programs
from brute force and dictionary attacks. Pinkas and
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.
Cookies vs. Source IP Addresses
Similar to the previous protocols, PGRP keeps track of
user machines from which successful logins have been
initiated previously. Browser cookies seem a good choice
for this purpose if the login server offers a web-based
interface. Typically, if no cookie is sent by the user
browser to the login server, the server sends a cookie
to the browser after a successful login to identify the
user on the next login attempt. However, if the user uses
multiple browsers or more than one OS on the same
machine, the login server will be unable to identify the
user in all cases. Cookies may also be deleted by users, or
automatically as enabled by the private browsing mode
of most modern browsers. Moreover, cookie theft (e.g.,
through session hijacking) might enable an adversary to
impersonate a user who has been successfully authenticated
in the past [7]. In addition, using cookies requires a
browser interface (which, e.g., is not applicable to SSH).
Usability Comments on ATT Challenges
Our main security goal is to restrict an attacker who is in
control of a large botnet from launching online singleaccount
or multi-account password dictionary attacks.
In terms of usability, we want to reduce the number
of ATTs sent to legitimate users as much as possible.
A user receives ATTs when the total number of failed
attempts exceeds threshold k2, and the login attempt is
initiated from (i) an unknown machine (i.e., no valid
cookies or white-listed IP addresses), or (ii) a known
machine from which the user has already failed k1 times.
System Resources
No lists are maintained in the PS protocol (see Algorithm
3), thus no extra memory overhead is imposed on
the login server. In the VS protocol (see Algorithm 4),
only FT is maintained. The number of entries in this
list grows linearly with unique usernames (both valid
and invalid) used in failed login attempts. An attacker
may try to exhaust a login server’s memory by failed
login attempts for many usernames. For any cookiebased
login protocol, the login server may also need
to store information regarding each generated cookie to
ameliorate cookie theft attacks [23]. Note that neither
the PS nor VS protocol uses IP addresses. The most
expensive server operation in PS, VS, and PGRP is
generating an ATT.
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 millionnode
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 ATTs and
other requirements). In contrast, PGRP is more restrictive
against brute force and dictionary attacks while safely
allowing a large number of free failed attempts for legitimate
users. Our empirical experiments on two datasets
(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 reiterate that no user-testing of PGRP has
been conducted so far.