[Security] The Security of Modern Password Expiration: An Algorithmic Framework and Empirical Analysis



The practice of regularly expiring passwords has been a sta-ple of computer security administration for over a quarter century (e.g., [5]). With few exceptions (e.g., [24, 3]), this practice is nearly universally accepted as a basic tenet by which systems should be protected, the common wisdom being:

Changing passwords frequently narrows the window within which an account is usable to an attacker be-fore he has to take additional steps to maintain access. ... Password expiration does not offer any benefit when Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

an attacker wants to do all of the damage that he’s go-ing to do right now. It does offer a benefit when the attacker intends to continue accessing a system for an

extended period of time.[2] At this level of specificity, such an argument is unquestionably sound. However, the process of reducing such intuition to a rea-sonable password expiration policy would ideally be grounded in measurements of what “additional steps” the policy hoists on an attacker, so as to be certain that these “additional steps” are an im-pediment to his continued access. Unfortunately, even to this day, the security community has yet to provide any such easurements.

In this paper we provide the first analysis of which we are aware of the effectiveness of expiring passwords. Using a datasetof pass-word histories for over 7700 defunct accounts at our institution, we assess the success with which an attacker with access to one pass-word for an account can break a future password for that account, in either an offline fashion where the attacker can test many password guesses or an online one where the attacker is limited to onlya few.

Central to our analysis is the development of at ransf orm - based al-gorithmic framework that an attacker can employ for breaking fu-ture passwords given preceding ones. Transform-based algorithms build from the presumption that a typical user will generateher next password by making systematic modifications to her current one (i.e., by applying primitivet ransf orm s). The conjecture that users tend to generate future passwordsbased on old passwords is by no means new. The best evidence we have found in the literature to support this conjecture is a studyof pass-word systems reported by Adams and Sasse [1], comprising 139 responses to a web-based questionnaire and 30 semi-structured in-depth nterviews. The hazard of primary concern in this paper was documented there as follows:

Some users devise their own methods for creating mem-orable multiple passwords through related passwords (linking their passwords via some common element) — 50% of questionnaire respondents employed this method. Many users try to comply with security rules by varying elements in these linked passwords (name1, name2, name3, and so forth).

Although Adams and Sasse reveal that 50% of questionnaire re-spondents reported “linking their passwords via some comment el-ement”, it is left nresolved as to whether these linkages are typ-ically of such a trivial variety. After all, many semantic linkages (e.g., passwords developed from the first names of the members of a family with which the user is acquainted) may not be nearly so simple to exploit in an automated fashion, while still representing “related passwords” to the user. Quantifying the pervasiveness of easily exploited linkages between old and new passwords is at the heart of what we explore in this paper.

Specifically, we consider the challenge of attacking futurepass-words from past ones for the same accounts using a transform-based search strategy. Our key algorithmic contribution isshowing that an optimal strategy for searching out new passwords from old ones (in our transform-based framework) is NP-hard to evelop — one of the few pieces of good news we have to offer defenders — but is also efficiently approximable. We then apply this approxi-mation algorithm to our dataset to generate approximately optimal search strategies, and demonstrate the effectiveness of those search strategies in breaking future passwords from past ones.

The high-order results of our study are alarming, albeit notsur-prising in light of previous conjectures. We show, for example, that by instantiating our transform-based algorithmic framework with a particular class of transforms, we can break future passwords from past ones in 41% of accounts on average in an offline attack with expected effort of under 3 seconds per account on a 2.67GHz pro-cessor. We also show that we can break 17% of accounts on av-erage in an online attack, with fewer than 5 online guesses inex-pectation. Our study additionally reveals a complex relationship between the susceptibility of accounts to transform-basedattacks and the strengths of passwords chosen in those accounts. In other results, our study reveals that the previous use of syntactic trans-forms in selecting passwords is a strong indicator of their future use: among accounts exhibiting such a previous use of transforms from a class that we will define, we can break future passwords from past ones using the same class of transforms in 63%of ac-counts on average in an offline attack with a similar level of effort.

We also study particular subclasses of transforms; here theresults are as much curious as they are alarming. For example, the past substitution of characters by their “leet” equivalents (orvice versa) or by characters residing on the same keyboard keys (e.g., “3” by “#”) signals the future use of such substitutions in only5%of ac-counts, but predicts the future use of a broader class of substitutions (that we will define) in75%of accounts.To summarize, the contributions of our paper are as follows.We provide an algorithmic framework for attacking future passwords from expired ones, show that finding the optimal search order in

that framework is NP-hard, and provide an efficient algorithm for generating an approximately optimal search order (§3). We then apply these results to a large, real-world dataset to provide the first analysis of the utility of password expiration for its intended pur-pose (§4). We close with a discussion of the implications of our study (§5) and then conclude (§6). k< � d h � �� nt-size: medium; ">by instantiating our transform-based algorithmic framework with a



particular class of transforms, we can break future passwords from past ones in 41% of accounts on average in an offline attack with expected effort of under 3 seconds per account on a 2.67GHz pro-cessor. We also show that we can break 17% of accounts on av-erage in an online attack, with fewer than 5 online guesses inex-pectation. Our study additionally reveals a complex relationship between the susceptibility of accounts to transform-basedattacks and the strengths of passwords chosen in those accounts. In other results, our study reveals that the previous use of syntactic trans-forms in selecting passwords is a strong indicator of their future

use: among accounts exhibiting such a previous use of transforms from a class that we will define, we can break future passwords from past ones using the same class of transforms in 63%of ac-counts on average in an offline attack with a similar level of effort.

We also study particular subclasses of transforms; here theresults are as much curious as they are alarming. For example, the past substitution of characters by their “leet” equivalents (orvice versa) or by characters residing on the same keyboard keys (e.g., “3” by “#”) signals the future use of such substitutions in only5%of ac-counts, but predicts the future use of a broader class of substitutions(that we will define) in75%of accounts.

To summarize, the contributions of our paper are as follows.We provide an algorithmic framework for attacking future passwords from expired ones, show that finding the optimal search order in that framework is NP-hard, and provide an efficient algorithm for generating an approximately optimal search order (§3). We then apply these results to a large, real-world dataset to provide the first nalysis of the utility of password expiration for its intended pur-pose (§4). We close with a discussion of the implications of our study (§5) and then conclude (§6).

Comments

Popular posts from this blog

[Hack crack] Tổng hợp Google Dork

[Security] Internet blackout scheduled in protest of SOPA