# A Survey on Password Guessing

Lam Tran<EMAIL_ADDRESS>0000-0002-8080-7271 Kongju National
UniversityKongjuSouth Korea ,  Thuc Nguyen<EMAIL_ADDRESS>0000-0003-0524-8841 Ho Chi Minh University of ScienceHo Chi MinhVietnam ,
Changho Seo<EMAIL_ADDRESS>0000-0002-0779-3539 Kongju National
UniversityKongjuSouth Korea ,  Hyunil Kim<EMAIL_ADDRESS>0000-0002-4018-4540 Kongju National UniversityKongjuSouth Korea and  Deokjai
Choi<EMAIL_ADDRESS>0000-0001-9502-9882 Chonnam National
UniversityGwangjuSouth Korea

(2022)

###### Abstract.

Text password has served as the most popular method for user authentication so
far, and is not likely to be totally replaced in foreseeable future. Password
authentication offers several desirable properties (e.g., low-cost, highly
available, easy-to-implement, reusable). However, it suffers from a critical
security issue mainly caused by the inability to memorize complicated strings
of humans. Users tend to choose easy-to-remember passwords which are not
uniformly distributed in the key space. Thus, user-selected passwords are
susceptible to guessing attacks. In order to encourage and support users to
use strong passwords, it is necessary to simulate automated password guessing
methods to determine the passwords’ strength and identify weak passwords. A
large number of password guessing models have been proposed in the literature.
However, little attention was paid to the task of providing a systematic
survey which is necessary to review the state-of-the-art approaches, identify
gaps, and avoid duplicate studies. Motivated by that, we conduct a
comprehensive survey on all password guessing studies presented in the
literature from 1979 to 2022. We propose a generic methodology map to present
an overview of existing methods. Then, we explain each representative approach
in detail. The experimental procedures and available datasets used to evaluate
password guessing models are summarized, and the reported performances of
representative studies are compared. Finally, the current limitations and the
open problems as future research directions are discussed. We believe that
this survey is helpful to both experts and newcomers who are interested in
password security.

password strength, password guessing, password metering, password
authentication, password security, password recovery

††copyright: acmcopyright††journalyear: 2022††doi:
00.0000/1122445.1122456††ccs: Security and privacy Authentication††ccs:
Security and privacy Social aspects of security and privacy

##  1\. Introduction

Text password has served as the most popular user authentication method so
far. The attempted user is verified by checking whether he knows the password
(i.e., secret text string) previously registered by the legitimate user
(Lamport, 1981). Password offers a low-cost, highly available, easy-to-
implement, and reusable authentication mechanism. However, due to the
inability to memorize high-entropy strings, users usually select easy-to-
memorize passwords (e.g., simple, familiar strings) (Ur et al., 2015a; Bonneau
and Shutova, 2012; Wang et al., 2019; Wei et al., 2018; Yang et al., 2021;
Shay et al., 2010), and use similar passwords for different services (Pearman
et al., 2017; Haque et al., 2013; Gaw and Felten, 2006). So, human-chosen
passwords are not uniformly distributed in the exponentially large key space,
but relatively gather in few clusters. Thus, the real-world passwords are
effectively modeled by attacker, making the authentication systems susceptible
to guessing attacks. As a result, password is usually the weakest point in the
whole security chain (Taneski et al., 2019).

Despite the notorious weaknesses, it is not likely that passwords will be
replaced in a foreseeable future (Clair et al., 2006; Herley and Van Oorschot,
2011; Bonneau et al., 2015). Thus, significant effort has been invested in
improving password strength against guessing attacks. In the early time,
password policy was widely adopted to prevent users from using weak passwords.
A password policy consists of a set of heuristic rules specifying some
properties that a password must satisfy (e.g., having at least $8$ characters,
containing both lower-case and upper-case letters) (Summers and Bosworth,
2004; Wang and Wang, 2015). However, prior studies showed that password policy
could not improve the password strength in practice as the users tend to
bypass policies with some tricks such as using some common patterns (e.g.,
first character as an upper-case letter) (Ur et al., 2015a), including
personal information (e.g., birth dates, name, email…) (Veras et al., 2012;
Wang et al., 2019; Bonneau et al., 2012; Bryant et al., 2006; Krishnamurthy
and Wills, 2009), using same/similar passwords for multiple services (Stobert
and Biddle, 2014; Wash et al., 2016; Haque et al., 2013; Gaw and Felten, 2006;
Habib et al., 2018), using leet speak (e.g., “$\mathsf{password}$” to
“$\mathsf{p4s5w0rd}$”) (Golla et al., 2016). An over-strictly policy, on the
other hand, leads to impossible-to-memorize passwords, and users will store
them somewhere which causes other security issues (Zhao and Yue, 2013; Gaw and
Felten, 2006; Stobert and Biddle, 2018; Inglesant and Sasse, 2010). Moreover,
password policies are also unable to educate the users on how weak their
passwords are and how to construct strong passwords.

In order to encourage and provide soundness advice that supports users to use
strong passwords, it is necessary to simulate automated password guessing
attacks, to measure how strong a password is and which weakness it suffers (Ur
et al., 2015b; Melicher et al., 2016). In other words, simulating password
guessing (as close as possible to the real attacker’s behavior) is critical to
ensure the security of passwords against real guessing attacks. Specifically,
such password guessing methods can be used to construct a proactive password
strength meter that detects weak passwords in the password registering step
(Kelley et al., 2012; Golla and Dürmuth, 2018). The administrators can also
rely on that password guessing method to periodically evaluate the password
strength of existing accounts. Since the first official report of Morris et
al. (Morris and Thompson, 1979), many password guessing studies have been
proposed in the literature. In the early stage, the research effort mainly
focused on discovering the potential information sources that can assist in
providing high-hitting-chance guesses (e.g., dictionary (Bonneau and Shutova,
2012; Chou et al., 2013), keyboard (Schweitzer et al., 2011; Li et al., 2014),
leaked password database (Zhang et al., 2010), language property (Li et al.,
2014)). The later works leveraged modern machine learning and deep learning
techniques to develop more sophisticated and robust password guessing methods
(e.g., Probabilistic Context-free Grammar (Weir et al., 2009; Chou et al.,
2013), Markov chain (Narayanan and Shmatikov, 2005; Dürmuth et al., 2015),
Long Short-term Memory Network (Xu et al., 2017; Fang et al., 2018),
Generative Adversarial Network (Hitaj et al., 2019; Guo et al., 2021a)).
Despite the merits of existing studies, the automated password guessing models
are still far from the real-world attacker.

With the increase of data breaches occurring continuously (see Table 1 for
examples), educating user on password composition to improve the resistance
against guessing attack is more critical. For the advancement of a research
topic, literature reviews are necessary to provide important concepts and
summarize the existing advances of the topic. This allows newly participated
researchers to quickly obtain background knowledge, identify gaps, and avoid
duplicative studies. Moreover, understanding how the password guessing methods
work also helps the administrator develops effective defensive mechanisms.
However, little effort has been invested in the task of providing a systematic
review of the password guessing studies. Motivated by that, in this study, we
conduct a systematic survey on existing password guessing studies that
provides not only an overview of the research field, but also the detail of
each subsequent approach. Specifically, this survey aims to answer the
following questions. (Q1) What are the ethical uses of password guessing in
practice, and how can a password guessing model be used to improve the
security of password authentication? (Q2) What information sources can be
inferred to construct a password guessing model? In other words, what are the
vulnerabilities in the password composing behavior of users that enable
effective password guessing? (Q3) Which algorithms have been developed to
produce candidate passwords from the information sources? (Q4) How are the
effectiveness (i.e., performance) and reliability of existing password
guessing models? How are they evaluated? (Q5) What are the open challenges
that need more future research attention? The answers of these questions form
the main contributions of this survey, which are outlined as follows:

  * •

We conduct the first comprehensive and systematic review of all password
guessing studies proposed in the literature from 1979 to 2022.

  * •

We briefly summarized the evolution of password guessing and present its
ethical applications.

  * •

We conduct a methodology map of password guessing models to provide an
overview of the research field.

  * •

We systematically present each existing strategy and technique for password
guessing.

  * •

We also present the available datasets and procedures for evaluating a
password guessing model. Then, the performance of representative researches
are summarized.

  * •

Finally, the current limitations in password guessing approaches and the open
problems as future research directions are then discussed.

The remaining parts of the paper are organized as follows. In Section 2, we
briefly summarize the evolution of password guessing techniques, discuss the
ethical applications, and review the related works of password security
research. Section 3 presents a systematic review of existing password guessing
studies. In this section, we propose a methodology map to provide an overview
of password guessing methods. Then, each approach depicted on the map is
described in detail. In Section 4, we discuss the remaining challenges and
open problems that need more future research effort. Finally, a conclusion is
drawn in Section 5.

Table 1. Some of recent data breaches that include passwords (source: https://haveibeenpwned.com/) Service | Leaked | No. of | Data |  Other Information
---|---|---|---|---
Time | Records | Type |
BrandNew Tube111https://brandnewtube.com/ | Aug, 2022 |  $350$K | Plaintext |  Email, gender, IP address, private message, username
START222https://start.ru/ | Aug, 2022 |  $44$M | Hashed |  Email, country
SitePoint333https://www.sitepoint.com/ | June, 2020 |  $1$M | Hashed |  Email, IP address, name, username
Tuned Global444https://www.tunedglobal.com/ | Jan, 2021 |  $985$K | Plaintext |  Email, names, physical addresses, phone number
Unico Campania555https://www.unicocampania.it/ | Aug, 2020 |  $166$K | Plaintext |  Email address
Vakinha666https://www.vakinha.com.br/ | Jun, 2020 |  $4.77$M | Hashed |  Email, IP address, name, birth date, Phone number
Vedantu777https://www.vedantu.com/ | Jul, 2019 |  $687$K | Hashed |  Email, gender, IP address, name, phone number, spoken language…

##  2\. History and Related Work

In this section, we briefly present the evolution history of password guessing
research. Then, we introduce some ethical applications of password guessing in
practice. Finally, we discuss existing surveys on related research of password
security.

###  2.1. The Evolution of Password Guessing

Password guessing attack has been used in practice for a long time
(Miljanovic, [n. d.]). The first official report of password guessing was
conducted by Morris and Thompson in 1979 (Morris and Thompson, 1979) which
described how to guess hashed passwords using common words in dictionaries and
some simple mangling rules. After that, dictionary-based password guessing was
widely used as the core component for proactive password checking (e.g.,
(Bishop, 1990; Spafford, 1992; Bergadano et al., 1998)) to prevent users from
choosing weak passwords. Oechslin et al. (Oechslin, 2003) presented the
rainbow table attack which pre-computed hash values of a large number of
candidate passwords, then used such hash values to match with the attacked
passwords’ hash values. By pre-computing the hash table, this approach is much
faster compared to computing the hash value online, especially in the old
days, when the processing speed was slow and the passwords were protected by
storing their hashed values. However, the later systems mostly combined a
salted value with a password before hashing (Scarfone and Souppaya, 2009).
That made the rainbow table attack become inapplicable. So, the password
guessing strategy was changed to producing high-matching-chance guesses by
studying how user select their passwords.

Observing that the distribution of letters in passwords is inherited from the
distribution of letters in the user’s native language, Narayanan et al.
(Narayanan and Shmatikov, 2005) proposed the first probabilistic approach
which used Markov chain (Fine et al., 1998) to model the password distribution
from dictionary words. This is also the first machine learning-based password
guessing model, which opened a brand new approach for this research. Weir et
al. (Weir et al., 2009) proposed a new password guessing approach by using
probabilistic context-free grammar (PCFG) to model the password distribution
from a real password database. This is also the first study that used real
passwords as the referenced information to construct a password guessing
model. After this study, real passwords leaked from some services and
published on the Internet were widely used for this task. Besides, some other
information sources have been confirmed to be useful for password guessing
(e.g., keyboard pattern (Chou et al., 2012; Kävrestad et al., 2020), language
property (Rao et al., 2013; Veras et al., 2014; Zhang et al., 2020b)). Thus,
the later password guessing model usually utilized multiple information
sources (e.g., (Houshmand et al., 2015; Fang et al., 2018; Cheng et al.,
2021)). Recently, the success of deep learning techniques in other areas
attracted the attention of the password security community. Melicher et al.
(Melicher et al., 2016) proposed the first deep learning-based password
guessing model which used Long Short-term Memory (LSTM) network to estimate
the password distribution from a leaked password database. This approach
quickly attracted more effort (e.g., (Xu et al., 2017; Fang et al., 2018;
Zhang et al., 2018; Li et al., 2019)). Deep Generative Networks were also
presented and showed promising performance (e.g., Generative Adversarial
Networks (Hitaj et al., 2019; Pasquini et al., 2021b; Guo et al., 2021a)).
Some studies proposed hybrid approaches that combined deep learning and
conventional techniques (e.g., (Zhang et al., 2020c, 2018; Liu et al., 2018))
to leverage the advantages of both directions.

###  2.2. Application of Password Guessing

Password guessing has served as the heart of several password security
applications (e.g., password strength meter, password-enhanced advisor, lost
password recovery). A password strength meter (PSM) provides an estimated
score (in graphical or text form) that reasonably reflects the strength of a
user-selected password against a guessing attack (Golla and Dürmuth, 2018).
PSMs are widely deployed in practice to encourage users to use strong (i.e.,
hard-to-guess) passwords (Carnavalet and Mannan, 2015; Golla and Dürmuth,
2018; Pereira et al., 2020). A PSM can operate in two modes: proactive and
reactive. A proactive PSM is activated at the time users register or change
their passwords. The new passwords must satisfy the minimum strength assessed
by the PSM to be used. A reactive PSM is periodically launched to check for
weak passwords over all the accounts, usually performed or scheduled by the
administrator. It has been shown that PSMs influence users’ choices when
composing passwords (Proctor et al., 2002; Egelman et al., 2013; Ur et al.,
2012). However, early PSM mostly relied on common sense and experts’ opinions
to design some password policies (e.g., (Helkala, 2011)). Such approaches do
not actually improve the password’s strength (Campbell et al., 2011; Inglesant
and Sasse, 2010; Lee et al., 2022). In order to create positive impacts, it is
critical that the strength estimated by the PSMs closely reflects the effort
needed by the attacker to break the password (Weir et al., 2010; Kelley et
al., 2012; Golla and Dürmuth, 2018). An ineffective guessing technique would
overestimate the password strength and allow weak passwords to be used. This
implies that a practical PSM should be built on top of a password guessing
model that closely simulates real-attack strategies used in practice
(Dell’Amico and Filippone, 2015; Golla and Dürmuth, 2018).

Password-enhanced advisors (PEAs) are PSMs that additionally suggest stronger
passwords (e.g., (Huh et al., 2015; Ur et al., 2017; Melicher et al., 2017)),
or give actionable feedback (i.e., guidance) (Kim et al., 2014; Ur et al.,
2017; Zhang-Kennedy et al., 2013; Woo and Mirkovic, 2018) from the user-
inputting passwords. It has been shown that the detailed feedback from PEA
help users to create more secure passwords than the PSM with only a strength
indicator, without significant impact on password memorability (Ur et al.,
2017; Shay et al., 2015). In order to construct an effective PEA, it is
necessary to identify the strength of an inputting password as well as
understand its weakness (i.e., how a practical password guessing method can
crack it) to suggest improvements. Moreover, besides metering and identifying
the weakness of input passwords, a PEA must ensure that suggested passwords or
the passwords produced from the advice could not be effectively modeled by the
attacker. Again, a solid background of password guessing attacks is necessary
to validate the security impacts of PEAs.

Besides using for user authentication, password is widely used for protecting
sensitive data stored on personal devices using modern encryption techniques
(Aumasson, 2017). When losing a password, it is unable to retrieve the
encrypted data. In addition, the user is unable to reset the password by
contacting the administrator like online service authentication. In this case,
password recovery tools built from the password guessing technique are useful.

###  2.3. Related Work

Up to the present, passwords have served as the key components in most
security infrastructures. In addition, despite the merits of the security
community, a new mechanism that can totally replace the password is not likely
to be available in near future (Clair et al., 2006; Herley and Van Oorschot,
2011; Bonneau et al., 2015). Thus, password security has received significant
research attention. The behaviors of user in composing and managing passwords
have been analyzed thoroughly. It has been shown that the passwords chosen by
users are far from random, as users usually compose them from memorable words
(Bonneau and Shutova, 2012; Kuo et al., 2006; Rao et al., 2013), user
information (Veras et al., 2012; Wang et al., 2019; Bonneau et al., 2012;
Bryant et al., 2006; Krishnamurthy and Wills, 2009), and keyboard pattern
(Schweitzer et al., 2011; Yang et al., 2021). In order to bypass the password
policy, some common patterns are usually adopted to compose passwords (e.g., a
special symbol or sequence of numbers are often appended after a dictionary
word; if there is an upper-case letter, it is often the first letter of the
word) (Tatlı, 2015). Managing multiple passwords for different services is
even more challenging for users. Thus, a large number of users added simple
modifications to create new passwords or completely reused their passwords
across different services (Stobert and Biddle, 2014; Wash et al., 2016; Haque
et al., 2013; Gaw and Felten, 2006). In addition, the password also reflects
the category of the service (i.e., name of the service or semantic information
is usually included in the passwords) (Wei et al., 2018).

To prevent the user from using weak passwords, significant research effort has
been invested in designing password guessing and password metering methods.
Along with the original research, some literature and experimental reviews on
these topics were also published (e.g., PSM (de Carné de Carnavalet and
Mannan, 2014; Yang et al., 2016; Hu, 2017; Golla and Dürmuth, 2018), password
guessing (Han et al., 2014; Zhang et al., 2020a; Yu, 2022)). De et al. (de
Carné de Carnavalet and Mannan, 2014) presented experimental analyses on $13$
password checkers used by $11$ well-known web services (i.e., Apple, Dropbox,
Drupal, eBay, FedEx, Google, Microsoft, PayPal, Skype, Twitter, and Yahoo) to
study their behaviors. The study showed that these meters were highly
inconsistent (i.e., they output different scores for the same password; weak
passwords were scored strong, or even very strong). Yang et al. (Yang et al.,
2016) provided a summarization of existing password strength meters proposed
in the literature (e.g., (Castelluccia et al., 2012; Ma et al., 2014; Ur et
al., 2015b; Weir et al., 2010; Wheeler, 2016)), and conducted experimental
analyses with real password datasets. Hu et al. (Hu, 2017) reviewed various
metrics that are used to measure password strength. They also presented a
comparison on the strengths and weaknesses of each metric. Golla et al. (Golla
and Dürmuth, 2018) proposed a set of requirements that a strength meter needs
to fulfill to accurately measure password strength. They also defined a number
of tests to validate these requirements. Then, the proposed requirements and
tests were used to validate the accuracy of $19$ existing password strength
meters.

Few surveys of password guessing studies have been presented in the
literature. Han et al. (Han et al., 2014) conducted a short survey on password
guessing and the countermeasure methods proposed before 2014. Zhang et al.
(Zhang et al., 2020a) briefly reviewed the password guessing and metering
research which leveraged deep learning techniques to generate the guesses. Yu
et al. (Yu, 2022) also summarized the password guessing studies that adopted
deep learning techniques. Besides, some studies conducted large-scale
experimental analyses on the performance of existing password guessing methods
with large password datasets (e.g., (Ji et al., 2015; Biesner et al., 2021;
Shi et al., 2021)). Despite their merits, answers of the questions raised in
Section 1 could not be found in such surveys. These surveys mostly focused on
summarizing each existing research separately without providing a systematic
overview of password guessing studies. They also lack several important
aspects that needed to be considered when constructing a password guessing
model (e.g., input data, experimental procedure, evaluation dataset, guessing
performance). Moreover, some important studies were not included (e.g., (Wang
et al., 2016b; Zhang et al., 2020c)).

##  3\. Systematic Review of Password Guessing

###  3.1. Systematic Overview

Figure 1. The systematic overview of existing password guessing models.

A systematic overview of existing password guessing approaches is depicted in
Figure 1. Overall, constructing a password guessing model involves performing
three main tasks: (a) identifying the security model; (b) acquiring the useful
referenced information; (c) and designing a password generating method. First,
to identify the security model, two questions need to be answered regarding
the attack settings: (i) the model will operate in online or offline mode; and
(ii) the model will guess the passwords of a targeted user or a group of
users. The answers of these questions decide the reference information that
needs to be obtained and the suitable password generating algorithms. Second,
some information sources are gathered, which will be inferred to generate the
candidate passwords for guessing. Third, the algorithm for generating
candidate passwords is designed, which can range from mangling rules to
machine learning, or deep learning techniques. Some models only output the
guessing passwords, meanwhile, some additionally provide the probability of
the candidate passwords to enable trying the high-likelihood passwords first.
Table 2 presents an overview of the setting, referenced information, and
password generation algorithm of each password guessing study proposed in the
literature. In the following sections, we discuss existing password guessing
approaches based on the above principles in detail.

###  3.2. Security Model

When constructing a password guessing model, it is important to specify two
settings of the attack: online or offline, targeted or trawling.

####  3.2.1. Online or Offline

Depending on the attack’s purpose and condition, password guessing could be
either performed in online or offline mode. Each mode faces different
challenges, and usually adopts dedicated strategies. The online password
guessing tries to authenticate as the claimed user (i.e., the user being
attacked) to a system by guessing the password of that user. To perform this
mode, the attacker needs to repeatedly interact with the targeted system until
success. In this scenario, the attacker is limited by the number of guesses
which usually can not exceed some threshold configured by the target system.
When continuously producing a certain number of incorrect guesses, the
targeted account, or the attacker’s IP address may be locked forever or during
a specific time (Alsaleh et al., 2011). In addition, online guessing usually
targets a remote host, thus, the attacking time is slowed down by the network
delay. So, the overall strategy used in this mode is to pick the most likely
password first. And most of the attacker’s efforts are to determine such
passwords. The common approach is exploiting the target’s information such as
user ID, birthdate, and leaked passwords of the targeted user (e.g., (Zhang et
al., 2010; Li et al., 2016; Wang et al., 2016b; Pal et al., 2019; Zhang et
al., 2020c)).

On the other hand, offline password guessing attempts to crack unknown
passwords when the password hashes or databases are accessible. Because of
requiring the hashed value, offline password guessing is only applicable in
some special situations (e.g., the target’s password file is leaked), thus, is
not considered a real security threat nowadays. In practice, this attack mode
is commonly used by the legitimate user to recover his lost password, or the
administrator to check the password strength of the users (e.g., proactive
password checking (Kelley et al., 2012; Ur et al., 2015b; Melicher et al.,
2016; Wang et al., 2016a)). In this mode, the attacker has several important
advantages. First, the attack is not slowed down by the delay of network
transmission. Second, the limitation of guessing times is also relaxed to be
bounded by the computation capability, so, millions of guesses can be
attempted until the correct password is found. As a result, the generic
strategy of this mode is to build a password generating model which encodes as
much as possible the password space from several information sources (e.g.,
dictionary (Narayanan and Shmatikov, 2005; Chou et al., 2013; Rao et al.,
2013), leaked password (Weir et al., 2009; Zhang et al., 2010; Chou et al.,
2013; Das et al., 2014; Li et al., 2014; Dürmuth et al., 2015; Xu et al.,
2017; Zhang et al., 2018; Fang et al., 2018; Liu et al., 2018; Hitaj et al.,
2019; Li et al., 2019; Zhang et al., 2020c; Xia et al., 2019; Zhang et al.,
2020b; Pasquini et al., 2021b, a; Guo et al., 2021b, a; Zhou et al., 2022),
keyboard pattern (Chou et al., 2013; Li et al., 2014; Houshmand et al., 2015),
language (Li et al., 2014)). Then, the built model is used to generate the
guessed passwords, usually in the order of decreasing probability. The model’s
effectiveness is decided by not only the hitting chance of candidate
passwords, but also the number of unique candidates the model can generate.

####  3.2.2. Targeted vs Trawling

Typically, a password guessing session could be configured to target a
specific user (i.e., targeted) or a group of users (i.e., trawling). The
targeted guessing is usually performed when the attacked user has been
specified (e.g., attacking an online account, or recovering the user’s lost
password). The overall strategy of this setting is to try the passwords that
are likely to be used by the targeted user. So, it is crucial to examine in-
depth all the information about the user such as leaked passwords, user
personal information, and password reuse behavior. Such information has been
shown to effectively narrow down the guessing space and produce the guess with
a high-hitting chance (Zhang et al., 2010; Das et al., 2014; Wang et al.,
2016b; Li et al., 2016; Pal et al., 2019; Zhang et al., 2020c; Xie et al.,
2020).

The trawling attack, on the contrary, aims to identify as much as possible the
passwords of a group of users. Nowadays, online services usually require the
user identity along with the corresponding password to authenticate the
claimer. Thus, trawling password guessing has limited applications in
practice. It is just applicable when the password storage/hashed values have
been compromised. Most of the existing trawling password guessing is used for
e.g., proactive password checking (Melicher et al., 2016), or adversarial
modeling-based password metering (Melicher et al., 2016; Wheeler, 2016; Pal et
al., 2019). For this mode, the use of personal information of a specific user
(e.g., birthdate, email) is not effective. Instead, this mode focuses on the
passwords that are likely to be used by many users by examining the password
distribution of a group of users or inferring some related information sources
(e.g., leaked password dataset, dictionary, common words).

In practice, when interacting with a remote server/service to authenticate as
a claimed user (online mode), the attacker has to submit the identity of the
claimed user first, then provide the guessed password. This means, the online
password guessing can only target a specific user for each guess. Thus, the
online mode is performed only for the targeted attack (i.e., the online mode
cannot go with the trawling attack). On the other hand, the trawling attack is
only performed in offline mode, in which the model just tries to guess as many
passwords as possible given a set of hashed passwords. So, in most of the
studies, online guessing and targeted attack refer to the same scenario when
the guessed passwords are used to crack a specific account, and the number of
attempts is restricted by the setting of the targeted service. Also, the
trawling and offline are used to indicate the scenario in which the guessed
passwords can be used to compromise many passwords from their hashed values,
and the attack is just limited by the computational capability of hardware. In
this paper, we use online and targeted interchangeably, and so on for trawling
and offline.

Table 2. An overall summary on the security model, information source, password generating algorithm, and the output of the existing password guessing studies. Study | Mode | Referenced Information | Generation Algorithm
---|---|---|---
Online |  Offline |  Dictionary |  Leaked Password |  Keyboard Pattern |  User Information |  Language |  Password Policy
Narayanan et al., 2005 (Narayanan and Shmatikov, 2005) |  | $\checkmark$ | $\checkmark$ |  |  |  | $\checkmark$ |  | Markov
Weir et al., 2009 (Weir et al., 2009) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ |  |  |  |  | PCFG
Zhang et al., 2010 (Zhang et al., 2010) | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  |  |  |  | Mangling Rule
Chou et al., 2012 (Chou et al., 2012) |  | $\checkmark$ |  |  | $\checkmark$ |  |  |  | Dictionary
Chou et al., 2013 (Chou et al., 2013) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  |  |  | PCFG
Rao et al., 2013 (Rao et al., 2013) |  | $\checkmark$ | $\checkmark$ |  |  |  | $\checkmark$ |  | Mangling Rule
Das et al., 2014 (Das et al., 2014) | $\checkmark$ |  |  | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  | Mangling Rule
Veras et al., 2014 (Veras et al., 2014) |  | $\checkmark$ | $\checkmark$ |  |  |  | $\checkmark$ |  | PCFG
Li et al., 2014 (Li et al., 2014) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  | PCFG
Durmuthet al., 2015 (Dürmuth et al., 2015) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | Markov
Houshmand et al., 2015 (Houshmand et al., 2015) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  | PCFG
Tatli et al., 2015 (Tatlı, 2015) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  |  |  | Mangling Rule
Wang et al., 2016 (Wang et al., 2016b) | $\checkmark$ |  | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ | PCFG
Li et al., 2016 (Li et al., 2016) | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  |  | PCFG
Melicher et al., 2016 (Melicher et al., 2016) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | LSTM
Xu et al., 2016 (Xu et al., 2017) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | LSTM
Zhang et al., 2018 (Zhang et al., 2018) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | PCFG $\&$ BiLSTM
Fang et al.,2018 (Fang et al., 2018) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  | LSTM
Liu et al., 2018 (Liu et al., 2018) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | PCFG $\&$ LSTM
Hita et al., 2019 (Hitaj et al., 2019) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | GAN
Pal et al., 2019 (Pal et al., 2019) | $\checkmark$ |  |  | $\checkmark$ |  |  |  |  | Encoder - Decoder (RNN)
Li et al., 2019 (Li et al., 2019) |  | $\checkmark$ |  | $\checkmark$ |  |  | $\checkmark$ |  | BiLSTM
Xia et al., 2019 (Xia et al., 2019) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | PCFG $\&$LSTM
Luo et al., 2019 (Luo et al., 2019) |  | $\checkmark$ |  | $\checkmark$ |  | $\checkmark$ |  |  | LSTM
Zhang et al., 2020 (Zhang et al., 2020c) | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  | $\checkmark$ |  |  | PCFG $\&$ LSTM
Zhang et al., 2020 (Zhang et al., 2020b) |  | $\checkmark$ |  | $\checkmark$ |  |  | $\checkmark$ |  | LSTM
Pasquini et al., 2021 (Pasquini et al., 2021b) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | GAN-WAEs, WAE
Pasquini et al., 2021 (Pasquini et al., 2021a) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ |  |  |  |  | Mangling Rule $\&$ CNN
Guo et al., 2021 (Guo et al., 2021a) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | GAN
Cheng et al., 2021 (Cheng et al., 2021) |  | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\checkmark$ |  | $\checkmark$ |  | PCFG
Zhou et al., 2022 (Zhou et al., 2022) |  | $\checkmark$ |  | $\checkmark$ |  |  |  |  | GAN

###  3.3. Referenced Information

Textual passwords have been shown not to be random due to the inability of the
human to memorize complicated strings, but they usually contain some
identifiable information (e.g., personal information (Bryant et al., 2006;
Wang et al., 2019; Veras et al., 2012; Bonneau et al., 2012), service
information (Wei et al., 2018), keyboard pattern (Schweitzer et al., 2011),
linguistic properties (Bonneau and Shutova, 2012; Rao et al., 2013)). In
addition, passwords (used for different services) of a user are usually
identical or share some commonality (Florencio and Herley, 2007; Haque et al.,
2013; Wash et al., 2016; Pearman et al., 2017; Gaw and Felten, 2006). Thus,
instead of guessing passwords randomly, most existing models exploited some
information sources to infer the password distribution and produce high-
likelihood guesses. This section summarizes the common information sources
that have been exploited to construct password guessing models.

####  3.3.1. Dictionary

Dictionary has been used for textual password guessing from a very early time,
with the first official report presented by Morris and Thompson in (Morris and
Thompson, 1979). In that study, hashed values were directly computed from
words in some dictionaries, and matched with the hashed passwords. Despite the
simplicity, this approach showed alarming results when it cracked one-third of
$3,289$ passwords in a very short time processing and limited computing
resource. They additionally suggested some simple methods to extend the word
list by using backward-spelled words, first/last names, street names, city
names, valid license plate numbers, telephone numbers, etc. The success of
dictionary-based password cracking comes from the fact that meaningful words
are much easy to be memorized than random character sequences. Thus, entire or
part of passwords is usually constructed from ordinary or well-known words
(Bonneau and Shutova, 2012). Besides directly using the words from
dictionaries as the guessed passwords, some studies applied mangling rules to
turn each ordinary word into a group of related words for guessing (Chou et
al., 2013; Wang et al., 2016b; Pasquini et al., 2021a; Wheeler, 2016). This
strategy is used in practical password recovery tools such as Hashcat (Steube,
[n. d.]), John the Ripper (Peslyak, [n. d.]). Moreover, some password guessing
models were built by capturing the letter distribution of a dictionary with
native language processing techniques (e.g., Markov (Narayanan and Shmatikov,
2005; Wang et al., 2016b), Parts of Speech Tagging (Rao et al., 2013),
Probabilistic Context Free Grammar (PCFG) (Veras et al., 2014; Houshmand et
al., 2015; Wang et al., 2016b; Li et al., 2016)).

####  3.3.2. Real Password

Table 3. The popular leaked password databases that have been used to construct password guessing models. (Note that, as passwords are sensitive, we do not include the download links of these datasets. Most of them are available on the Internet.) Dataset | Leaked | No. of | Data | Language | User | Used in
---|---|---|---|---|---|---
Time | Passwords | Type | Info | Study
000webhost | Oct, 2015 | $15,251,073$ | Plaintext | Chinese | Email | (Wang et al., 2016b; Cheng et al., 2021)
12306 | 2014 | $\sim 130,000$ | Plaintext | Chinese | Name; | (Wang et al., 2016b; Li et al., 2016; Zhang et al., 2020c, b)
real ID
126 | Dec, 2011 | $6,392,568$ | Plaintext | Chinese | Email | (Wang et al., 2016b)
178.com | Dec, 2011 | $\sim 9,072,824$ | Plaintext | Chinese | Username | (Li et al., 2014)
7k7k | 2011 | $19,138,270$ | Plaintext | Chinese | Email | (Li et al., 2014)
Animoto | Aug, 2020 | $\sim 8\cdot 10^{6}$ | Hashed | English | User info | (Pasquini et al., 2021a)
Clixsense | $-$ | $1,628,894$ | Plaintext | English | $-$ | (Li et al., 2019; Cheng et al., 2021)
CSDN | Dec, 2011 | $\sim 6,428,629$ | Plaintext | Chinese | Email, | (Li et al., 2014; Wang et al., 2016b; Zhang et al., 2020b, 2018; Fang et al., 2018; Cheng et al., 2021)
Username
Dodonew | Dec, 2011 | $\sim 16,258,891$ | Plaintext | Chinese | Email | (Wang et al., 2016b; Zhang et al., 2018, 2020b; Cheng et al., 2021)
Duduniu | 2011 | $16,282,969$ | Plaintext | Chinese | Username | (Li et al., 2014)
Duowan | 2018 | $\sim 4,982,730$ | Plaintext | Chinese | User ID, Email, | (Cheng et al., 2021)
& Hashed | User name
Facebook | $-$ | $-$ | Plaintext | $-$ | Email | (Dürmuth et al., 2015; Xu et al., 2017; Fang et al., 2018)
Finnish | $-$ | $38,432$ | Plaintext | Finland | None | (Weir et al., 2009)
&Hashed
Hotmail | 2009 | 8,930 | Plaintext | English | None | (Pasquini et al., 2021b)
JingDong | $-$ | $390,000$ | Plaintext | Chinese | $-$ | (Zhang et al., 2018)
LinkedIn | 2012 | $\sim 60,065,486$ | Hashed | English | Email | (Hitaj et al., 2019; Xia et al., 2019; Pasquini et al., 2021b, a; Zhou et al., 2022)
MyHeritage | Oct, 2017 | $92,283,889$ | Hashed | $-$ | Email | (Pasquini et al., 2021a)
MySpace | 2006 | $37,000$ | Plaintext | English | None | (Weir et al., 2009; Chou et al., 2013; Dürmuth et al., 2015; Xu et al., 2017)
$\sim 67,042$ | (Pasquini et al., 2021b; Li et al., 2019; Xia et al., 2019)
Netease | Oct, 2015 | $1,220,088,121$ | Plaintext | $-$ | $-$ | (Zhang et al., 2020b)
Phpbb | Jan, 2009 | $\sim 184,380$ | Plaintext | English | None | (Chou et al., 2013; Li et al., 2019; Xia et al., 2019; Zhang et al., 2018; Pasquini et al., 2021b, a)
RockYou | 2009 | $\sim 32,603,388$ | Plaintext | English | None | (Chou et al., 2013; Wang et al., 2016b; Li et al., 2019; Xia et al., 2019)
(Li et al., 2014; Tatlı, 2015; Dürmuth et al., 2015; Guo et al., 2021b;
Pasquini et al., 2021b; Cheng et al., 2021)
(Xu et al., 2017; Zhang et al., 2018; Fang et al., 2018; Hitaj et al., 2019;
Pasquini et al., 2021a; Zhou et al., 2022)
Rootkit | Feb, 2011 | $69,418$ | Plaintext | English | User info | (Wang et al., 2016b)
SilentWhisper |  | $\sim 7,480$ | Plaintext | $-$ | None | (Weir et al., 2009)
Tianya | Dec, 2011 | $30,179,474$ | Plaintext | Chinese | Username | (Li et al., 2014)
Xato | Feb, 2015 | $9,997,772$ | Plaintext | English | $-$ | (Wang et al., 2016b)
Xiaomi | May, 2014 | $8,281,385$ | Hashed | Chinese | $-$ | (Wang et al., 2016b)
Yahoo | July, 2012 | $442,837$ | Plaintext | English | Username | (Li et al., 2014; Zhang et al., 2018; Wang et al., 2016b; Li et al., 2019)
Youku | 2016 | $100,759,591$ | Plaintext | Chinese | Email | (Pasquini et al., 2021b, a)
Zomato | May, 2017 | $17,000,000$ | Hashed | $-$ | Email | (Pasquini et al., 2021b, a)
Zooks | Jan, 2020 | $\sim 2.9\cdot 10^{7}$ | Plaintext | $-$ | User info | (Pasquini et al., 2021a)
‘$-$’: the corresponding information was not specified.

Real-world password (aka, leaked password, disclosed password) datasets, which
were hacked by attackers or were privately collected inside an organization
(for research), have been shown as the most effective information source to
build password guessing models. The effectiveness of this approach comes from
two facts: (i) users usually use the same or similar passwords for different
services (Gaw and Felten, 2006; Florencio and Herley, 2007; Haque et al.,
2013; Stobert and Biddle, 2014; Wash et al., 2016; Pearman et al., 2017); (ii)
some common passwords are widely used by many users (e.g.,
“$\mathsf{123456}$”, “$\mathsf{111111}$”, “$\mathsf{password}$”) (Wang et al.,
2016b; Han et al., 2015). A leaked password dataset reveals various kinds of
sensitive information which is useful to construct effective password guessing
models such as user behavior on password forming, password policy, and user
information. Such observations were confirmed firstly by Weir et al. in (Weir
et al., 2009). In that study, the authors leveraged leaked passwords to derive
the underlying structures (i.e., grammar) of these passwords with PCFG, then,
used such structures to generate the guessed passwords. Their experiments
showed an improved performance of $28\%$ to $129\%$ over the pure dictionary-
based password guessing with John the Ripper. After that, using leaked
passwords available on the Internet for constructing password guessing models
received more research attention. MySpace was one of the first leaked password
datasets that has been used for password guessing research. The dataset was
collected by a fishing attack in 2006, comprised of about $37,000$ to $67,042$
plaintext passwords of MySpace’s users, later, used in some password guessing
studies (e.g., (Weir et al., 2009; Chou et al., 2013; Dürmuth et al., 2015; Xu
et al., 2017; Pasquini et al., 2021b; Li et al., 2019; Xia et al., 2019)).
However, the dataset does not contain other information (e.g., username,
email…) of the leaked accounts. RockYou is a dataset consisting of more than
$32$ million passwords of a company named Rockyou, leaked in 2009, and later,
used in many researches (e.g., (Chou et al., 2013; Wang et al., 2016b; Li et
al., 2019; Xia et al., 2019; Li et al., 2014; Dürmuth et al., 2015; Guo et
al., 2021b; Pasquini et al., 2021b; Xu et al., 2017; Zhang et al., 2018; Fang
et al., 2018; Hitaj et al., 2019; Pasquini et al., 2021a; Zhou et al., 2022)).
Like MySpace, all the passwords of Rockyou were originally stored in
plaintext, but there was no additional information (e.g., username, email…) of
the users. LinkedIn is another leaked password dataset of English-speaking
users which consists of more than $60$ million salted passwords along with the
user’s emails. The plaintext passwords of this dataset were obtained by using
John the Ripper and HashCat to recover from the salted values. Thus, this
dataset only contains passwords that are crackable by rule-based tools. CSDN
is a leaked password dataset comprised of more than $6$ million passwords of
Chinese-speaking users (programmers) leaked in 2011. Along with the leaked
passwords, this dataset also contains other types of information such as
username, and email address. Instead of using leaked passwords of other users,
Zhang et al. (Zhang et al., 2010) measured the security of new passwords of a
group of users when their old passwords were given. They leveraged a password
database of their university community that consisted of $51,141$ unsalted MD5
passwords from $10,374$ users. Their experiment showed alarming security risks
when the old passwords were leaked. Specifically, with the offline guessing
setting, about $41\%$ of new passwords were cracked based on the old passwords
in under $3$ seconds. For the online setting, about $17\%$ of accounts can be
broken within $5$ guesses. Furthermore, the effectiveness of using leaked
passwords was also confirmed in targeted guessing attacks (e.g., (Pal et al.,
2019; Wang et al., 2016b)). Besides the above datasets, many other real
password databases of different sites have been leaked, and then, leveraged
for password guessing studies (Table 3).

Although rich information could be inferred from a leaked password dataset,
using such datasets to construct a password cracking model has several
challenges. First, the adopted password policies (e.g., password length,
character set…) strongly impact the password distribution created by the user
(Proctor et al., 2002; Ur et al., 2012; Shay et al., 2015). Thus, in order to
construct an effective password guessing model, the referenced password
dataset should share as much as possible some commonalities with the targeted
passwords in terms of password policy and other factors (e.g., language).
However, such a requirement is not easy to fulfill because password policies
(and other factors) are diverse between different organizations. Moreover,
most of the leaked databases do not contain the adopted password policies that
users had to follow when creating them. Second, these leaked databases were
illegally obtained and distributed, thus, there is no assurance regarded to
the reliability of these data. Fractions of passwords could be fake records,
or from dummy accounts which can create biases for password studying.

####  3.3.3. User Information

It has been widely studied that user usually constructs their passwords from
some familiar information sources, and personal information (e.g., birthdate,
name, email…) are the most common (Wang et al., 2019; Veras et al., 2012;
Bonneau et al., 2012; Bryant et al., 2006). Thus, the personal information of
the targeted user has been exploited as a reliable source for guessing the
passwords of that user, especially effective in targeted guessing attacks (Li
et al., 2016; Wang et al., 2016b). Li et al. (Li et al., 2016) considered six
types of common personal information including name, birthdate, email address,
phone number, account name, and ID number to construct a password guessing
model with PCFG (so, called personal-PCFG). Their experiment on 000webhost
dataset demonstrated that: in offline mode, the personal-PCFG model cracked
passwords much faster than PCFG; and in online mode, it achieved a higher
success rate. Wang et al. (Wang et al., 2016b) considered different types of
personal information (e.g., old password, name, birthdate, phone, gender,
age…), and incorporated them with other information sources (e.g., dictionary,
leaked password) to build an online targeted password guessing model, named
TarGuess. Zhang et al. (Zhang et al., 2020c) constructed a hybrid model that
combined TarGuess (Wang et al., 2016b) (which fully exploited personal
information) with Long Short-term Memory (LSTM) network to enable the
generation of a large number of passwords. Their experiment showed that, in
the offline setting, the proposed architecture can successfully crack more
passwords than using each individual model. Overall, personal information has
been shown highly effective and is the mandatory source for constructing a
targeted password guessing model.

####  3.3.4. Keyboard Pattern

Typing with a special pattern on the keyboard can generate character sequences
that look random because they do not follow common character orders such as
alphabet, numeric, or language dictionary words. The user usually adopted a
keyboard pattern (e.g., “$\mathsf{zxcvbn}$”, “$\mathsf{1qa2ws3ed4rf}$”) when
creating a password, as the obtained string looks like a strong password, and
is easy for the user to reproduce (e.g., (Schweitzer et al., 2011; Li et al.,
2014; Yang et al., 2021)). From that observation, several studies have
exploited the common keyboard patterns for password guessing (e.g., (Kävrestad
et al., 2020; Chou et al., 2012; Chou et al., 2013; Houshmand et al., 2015;
Wheeler, 2016; Fang et al., 2018)). In (Chou et al., 2012), the authors
described a framework to model the passwords formed by the adjacent keys
(e.g., “$\mathsf{gbnjuy}$”) and parallel keys (e.g., “$\mathsf{tregfd}$”).
That framework also supports modeling the passwords generated when using
printable keys with functional keys (e.g., “$\mathsf{@\\#\$QWE}$”). The
keyboard patterns then were widely combined with other information sources
such as dictionaries and leaked passwords to increase the guessable password
space (Chou et al., 2013; Houshmand et al., 2015; Wheeler, 2016; Cheng et al.,
2021).

####  3.3.5. Auxiliary Information

Besides the above information sources, some other information could be used to
narrow down the guessing space and improve the hitting chance of the candidate
passwords (e.g., native language, password policy). Many studies have
confirmed that passwords inherit many properties of the language spoken by the
user. For instance, to guess the password of a Chinese user, it is more
effective to use a Chinese dictionary (e.g., Pinyins) than using an English
dictionary, and vice versa (Li et al., 2014; Fang et al., 2018; Zhang et al.,
2020b, c; Cheng et al., 2021). Moreover, passwords (especially the long ones)
were commonly composed with the semantic patterns of spoken language inside.
This fact enables the adoption of Part-of-speech (POS) tagging (Voutilainen,
2003) to exploit the semantic patterns of spoken language inside the passwords
to improve the guessing effectiveness (Rao et al., 2013; Veras et al., 2014).
Besides language, password creation policy is also the important information
that effectively assists in the generation of high-hitting-chance candidate
passwords (Wang et al., 2016b). Setting certain policies is a common method
employed by many services/applications in order to prevent the user from using
a weak password. It is straightforward that, those passwords which do not
satisfy the policies of a target service, should not be used for guessing
because the users can not use such passwords on that service.

###  3.4. Password Generation Algorithm

Upon gathering the referenced information, an algorithm is used to generate
candidate passwords. In the early time, mangling rules based on common sense
and experts’ knowledge are used. The later studies leveraged machine learning
and deep learning to automatically infer the password distribution and
generate guesses. This section covers different approaches of password
generation proposed in the literature.

####  3.4.1. Mangling Rule

Mangling rule is known as the earliest and most popular password guessing
approach. A mangling rule defines a transformation on one or multiple input
strings (i.e., passwords, dictionary words) to produce new passwords. For
example, applying the rule “capitalize the first letter” to “$\mathsf{lucky}$”
will output “$\mathsf{Lucky}$”. This strategy exploits the fact that users
tend to (i) follow common patterns to compose passwords, and (ii) adopt a
predictable pool of mangling functions to create new passwords from the old
ones (when changing passwords). Mangling rule attack is simple and easy to
implement, yet, it poses a substantial threat to password security. Moreover,
it can be processed in parallel, and easy for upgrading (e.g., adding new
words or rules is easier compared to re-training a machine learning or deep
learning model). However, the effectiveness of this strategy completely
depends on the input word list and the mangling rules. While the input word
list could be easy to obtain from dictionaries, common words (e.g., street
name, person name), or leaked passwords, manually defining the mangling rules
is a time-costing task and requires experts’ knowledge. For example, the
mangling rules used in popular password guessing tools like Hashcat, John the
Ripper have been conducted through continuous updating for a long time. To
provide an effective guess, the mangling rules should capture the users’
behavior in composing or reusing the passwords. Thus, instead of manually
designing such rules, some studies suggest inferring the rules from the leaked
passwords. Zhang et al. (Zhang et al., 2010) proposed the first strategy to
learn them automatically from the leaked passwords. Specifically, their method
requires the knowledge of several old passwords of the targeted user. From
these passwords, the mangling behavior of the targeted user is inferred and
used to guess the future password. Das et al. (Das et al., 2014) surveyed the
password reuse behavior of a group of volunteers. The mangling rules were
derived from the reuse behavior and used to predict the future password of the
observed user. Tatli et al. (Tatlı, 2015) manually examined the leaked
password datasets to identify the common patterns (i.e., composing rules) that
users usually followed when composing passwords (e.g., a special symbol
(exclamation mark, dot…) or sequence of numbers are often appended after a
dictionary word; if there is an upper-case letter, it is often the first
letter of a dictionary word). They divided the identified patterns into $10$
categories as appending, prefixing, inserting, repeating, sequencing,
replacing, reversing, capitalizing, special-format, and mixed Patterns. Then,
they developed pbp-generator (pattern-based password generator), a tool to
generate candidate passwords from the identified patterns and given
dictionaries.

While most of the prior researches focused on generating effective rules by
investigating the password-forming behavior of users, Pasquini et al.
(Pasquini et al., 2021a) proposed Adaptive Mangling Rule (AdaMs) which paid
attention to the later step as optimizing the combination between mangling
rules and words. AdaMs relied on intuition as “users usually select a
dictionary word first, then the mangling rule conditioned on the word”. Each
mangling rule is only applicable on a small subset of words (i.e., combining
the rule on these words will produce guessing hits with high probability),
strictly defined by the users’ habits on password composing. In other words,
each pair of mangling rule and word has a certain compatible level decided by
the user’s behavior. Instead of applying all mangling rules to all dictionary
words, the authors used residual neural network (He et al., 2016) to model the
compatibility. Only the pairs having sufficient compatibility are used for
guessing. To train the deep network, a set of mangling rules $\mathcal{R}$, a
set of words $\mathcal{W}$, and a set of leaked passwords $\mathcal{X}$ are
required. For each word $w_{i}\in\mathcal{W}$, the deep network outputs a
compatibility vector

(1)
$\mathbf{y}_{i}=\begin{bmatrix}y_{i1}&\ldots&y_{ij}&\ldots&y_{i|\mathcal{R}|}\end{bmatrix},$

where $y_{ij}=\mathsf{P}(r_{j}(w_{i})\in\mathcal{X})$ is the compatibility of
$r_{j}$ and $w_{i}$ (i.e., the probability of applying rule $r_{j}$ on the
word $w_{i}$ will result to a password in the set $\mathcal{X}$). Upon
training, the model is used to estimate the compatibility of a set of rules
given a dictionary word $w_{i}$. Given a set of compatibility vector
$\mathbf{y}_{i}$, the rule $r_{j}$ is applied to $w_{i}$ if $y_{ij}>\delta$,
where $\delta\in[0,1)$ is a threshold defined by the user.

####  3.4.2. Markov Model

Before the emergence of deep learning techniques, Markov model was known as
the most dominant approach for natural language processing. From the
observation that users usually form the password from their native language
for easy memorizing (Bonneau and Shutova, 2012; Rao et al., 2013), some
studies proposed using Markov model for password guessing (e.g., (Narayanan
and Shmatikov, 2005; Dürmuth et al., 2015; Guo et al., 2021b)). The core
concept of Markov-based password guessing is to exploit the interconnection
between consecutive characters in the passwords to predict the next character
based on previous characters (i.e., conditional characters). This is inspired
by the fact that adjacent letters in human-generated passwords are not
independently chosen, but follow certain regularities inherited from human
languages (e.g., in English, “$\mathsf{th}$” is much more likely than
“$\mathsf{tq}$”, and the letter “$\mathsf{e}$” is likely to be after
“$\mathsf{th}$”). Specifically, for a password of length $m$ (denoted as
$c_{1}c_{2}\ldots c_{m}$), the Markov model estimates its occurrence
probability as

(2) $\mathsf{P}(c_{1}c_{2}\ldots c_{m})=\mathsf{P}(c_{1}c_{2}\ldots
c_{n})\prod_{i=n+1}^{m}\mathsf{P}(c_{i}|c_{i-n+1}\ldots c_{i}),$

where $n$ defines the number of historical characters used to predict the next
character, which is also referred to as the order of the model. The
combination of $n$ history characters and the predicted character forms
$(n+1)$-gram fragment, and the described model is also known as $(n+1)$-gram
Markov model. Before using for password guessing, the initial probabilities
$\mathsf{P}(c_{1}c_{2}\ldots c_{n})$ and the transition probabilities
$\mathsf{P}(c_{i}|c_{i-n+1}\ldots c_{i})$ are inferred from the real password
dataset through a training process. Specifically, given a training dataset,
each password is split into multiples $(n+1)$-gram fragments. All the
$(n+1)$-gram fragments (obtained from all passwords) are grouped by the
conditional characters (i.e., the first $n$ characters of each fragment).
Then, the probability of each $(n+1)$-gram (considered within each group) is
estimated. Figure 2 depicts an example of training a $2$-order Markov model
for password guessing.

Narayanan et al. (Narayanan and Shmatikov, 2005) conducted the first study
that uses Markov model for password guessing. They proposed Markovian filter
which captures the similarity between passwords and user’s native language.
Such filters are used to efficiently enumerate all candidate passwords of a
given length accepted by a deterministic automaton without searching through
the entire password space. Durmuth et al. (Dürmuth et al., 2015) proposed OMEN
(Ordered Markov ENumerator) - a Markov-based password generative model that
enumerates passwords in the order of decreasing probability. While the prior
studies used Markov model for trawling password guessing, Wang et al. (Wang et
al., 2016b) showed that Markov model is also effective for targeted password
guessing when it is trained with the targeted user’s personal information.
Recently, Guo et al. (Guo et al., 2021b) proposed dynamic Markov model to
address the problem of high repetition rate in prior Markov-based password
guessing models. Upon generating a candidate password for guessing, the
dynamic Markov model reduces the probability of this password. Thus, the
likelihood of generating this password in subsequent attempts is reduced.

Figure 2. The overall training process of a 3-gram Markov-based password
guessing model.

####  3.4.3. Probabilistic Context Free Grammar

Probabilistic Context Free Grammar (PCFG) has been widely used for modeling
natural language (e.g., (Knight and Graehl, 2005)). Several works have shown
that, PCFG is also effective for password guessing (Weir et al., 2009; Chou et
al., 2013; Li et al., 2014; Veras et al., 2014; Houshmand et al., 2015; Li et
al., 2016; Cheng et al., 2021). This approach is inspired from the observation
that user usually follows typical patterns when composing passwords to comply
with stringent password creation policies (e.g., must include letter, digit,
and special symbol). For instance, “$\mathsf{password123!@\\#}$” and
“$\mathsf{secret214!()}$” share the same pattern as a letter string followed
by some digits, and ended with special symbols. This is similar to the fact
that a typical English sentence usually consists of a subject, a verb, and an
object. PCFG approach tries to model such password patterns (structures) from
the real password dataset. Such patterns are then used to generate candidates
for password guessing.

The first PCFG-based password guessing model was proposed by Weir et al. in
(Weir et al., 2009). A PCFG is defined by a quintuple
$\mathcal{G}=(P,\mathcal{N},\mathcal{T},\mathcal{R},\mathsf{p})$, where
$\mathcal{N}$ is a set of non-terminals (aka, variables), $P\in\mathcal{N}$ is
the start symbol, $\mathcal{T}$ is a set of terminals, $\mathcal{R}$ is a set
of production rules $\mathcal{N}\rightarrow(\mathcal{N}\cup\mathcal{T})^{*}$,
and $p$ is a function that gives the probability of each rule in $\mathcal{R}$
such that, for any non-terminal $X\in\mathcal{N}$, the sum of probabilities
associated with all rules having $X$ in the left side is $1$ (i.e., $\forall
X\in\mathcal{N}$,
$\sum\limits_{\alpha\in(\mathcal{N}\cup\mathcal{T})^{*}}p_{(X\rightarrow\alpha)}=1$).
The set of variables (non-terminals) $\mathcal{N}$ specify the character types
from which the passwords are constructed. The model in (Weir et al., 2009)
supports 3 types of basic characters as alphabet letters (no discrimination
between lowercase and uppercase letters), digits, and special symbols. The
variable set is defined as $\mathcal{N}=\\{P,L,D,S\\}$, where $L$ represents
the alphabet letter (i.e., $\\{\mathsf{a,b,c\ldots}\\}$), $D$ means the number
digit (i.e., $\\{\mathsf{0,1,2\ldots}\\}$), and $S$ stands for the special
symbol (i.e., $\\{!@\\#\ldots\\}$). Each variable is subscripted by an integer
number to specify the character length. A group of passwords having the same
structure is represented by a non-terminal form (i.e., a string that contains
at least 1 non-terminal). For instance, the non-terminal form
$L_{5}D_{2}S_{1}$ represents the passwords formed from $5$ alphabet letters,
$2$ digits, and $1$ special symbol. The start symbol $P$ is a special
variable, representing all the passwords that can be generated by the PCFG.
The actual password is represented by a terminal form. A production rule
transforms a non-terminal form to either a terminal or another non-terminal
form. Given a non-terminal form, production rules are recursively applied
until only the terminals are left. Each production rule has an associated
probability of occurrence such that the sum of probabilities associated with
all rules having the same left side is $1$. The probability of a terminal/non-
terminal form is the product of probabilities of all the rules used in its
derivation. For example, given a PCFG depicted in Figure 3, the non-terminal
form $L_{5}43*$ represents all passwords having $5$ alphabet letters followed
by the digit string $43$ and the symbol $*$. This non-terminal form can be
derived from $P$ via a chain of production rules $P\rightarrow
L_{5}D_{2}S_{1}$; $D_{2}\rightarrow 43$; and $S_{1}\rightarrow*$, (i.e.,
$P\rightarrow L_{5}D_{2}S_{1}\rightarrow L_{5}43S_{1}\rightarrow L_{5}43*$).
The probabilities associated to the rules are $\mathsf{P}_{(P\rightarrow
L_{5}D_{2}S_{1})}=0.2$, $\mathsf{P}_{(D_{2}\rightarrow 43)}=0.33$, and
$\mathsf{P}_{(S_{1}\rightarrow*)}=0.4$. Then, the probability of the non-
terminal form $L_{5}43*$ is computed as
$\mathsf{p}_{(L_{5}43*)}=\mathsf{p}_{(P\rightarrow
L_{5}D_{2}S_{1})}\cdot\mathsf{p}_{(D_{2}\rightarrow
43)}\cdot\mathsf{p}_{(S_{1}\rightarrow*)}=0.2\cdot 0.33\cdot 0.4=0.0264$.

A PCFG-based password guessing model operates in two phases as follows.
Training: Given a training dataset (e.g., leaked passwords dataset), this
phase infers the base structures (i.e., non-terminal forms), the set of
production rules, and the probabilities of each entity. Specifically, each
password in the training set is parsed to identify the types of characters
(e.g., letters, digits, special symbols). Then, the base structures and
production rules are recorded, and their corresponding probabilities are
estimated. In addition, the probabilities of digit strings and special strings
are also computed. However, in most existing models, the learning phase does
not include determining probabilities of the alphabet non-terminal strings
(i.e., $L$), but treats them like terminal strings. Generating: A dictionary
is fed into the trained PCFG to generate the candidate passwords, usually in
the decreasing order of probability. The probabilities associated to the
generated passwords could be computed in either pre-terminal probability order
or terminal probability order (Weir et al., 2009). With the pre-terminal
order, the probability of a password is determined only from the probability
of the non-terminal form that the password is derived from (e.g.,
$\mathsf{p}_{(peter43*)}=\mathsf{p}_{(L_{5}43*)}$). On the other hand, by the
terminal order, the probability of a password is computed from both the non-
terminal form and the probability of the alphabet string (e.g.,
$\mathsf{p}_{(peter43*)}=\mathsf{p}_{(L_{5}43*)}\cdot\mathsf{p}_{(peter)}$).
This approach requires the probability of alphabet string which could be
obtained in several ways as assigning equal probability to all words having
the same length; assigning based on the frequency according to some prior
sources like language statistics, or leaked password statistics. Figure 3
depicts an example of PCFG described in (Weir et al., 2009), in which the pre-
terminal order is used to compute the probabilities of the generated
passwords.

Inspired by the work of Weir et al. (Weir et al., 2009), several improvements
of PCFG-based password guessing model have been proposed (e.g., (Chou et al.,
2013; Li et al., 2014; Veras et al., 2014; Houshmand et al., 2015; Li et al.,
2016; Cheng et al., 2021)). Specifically, Chou et al. (Chou et al., 2013) use
additional variables to enable the modeling of lowercase, uppercase letters,
and keyboard patterns. Li et al. (Li et al., 2014) improve the traditional
PCFG by inserting Pinyins into the dictionary. Thus, the model is able to
guess Chinese passwords. Their work also allows modeling both uppercase and
lowercase letters. The study of Houshmand et al. (Houshmand et al., 2015)
proposes two improvements. First, they use a new variable $K$ to model the
keyboard pattern (e.g., “$\mathsf{asdfgh}$”, “$\mathsf{zaqwsx}$”). Such
patterns could not be generated using the method described in (Weir et al.,
2009). Second, they support modeling passwords with multi-word phrases (e.g.,
“$\mathsf{iloveyou}$”, “$\mathsf{tingting}$”) and non-dictionary alphabet
patterns (e.g., “$\mathsf{abcdef}$”, “$\mathsf{xxyyzz}$”) by additionally
adopting several variables. Veras et al. (Veras et al., 2014) proposed a
password guessing model by using PCFG built on top of Part of Speech Tagging
(Voutilainen, 2003). Specifically, they applied Part of Speech Tagging to
segment the passwords into semantic and syntactic categories instead of only
semantic as in (Weir et al., 2009). The syntactic categories clearly specify
the role of a word in the spoken language (e.g., “$\mathsf{love}$” can be
either a verb or a noun depending on its role in a given clause). This helps
further narrow down the search space when performing a guessing attack. In
their PCFG, the terminal symbols $\mathcal{T}$ include the source corpora
(i.e., dictionary word) and the learned gap segments (i.e., unknown word,
sequence of special symbols). And the set of semantics (e.g., number, special
symbols) and syntactic categories of identified words (e.g., noun, verb,
adjective) form the non-terminal set $\mathcal{N}$. Li et al. (Li et al.,
2016) propose personal-PCFG which additionally employs several variables to
model different kinds of personal information (e.g., $A$ for account identity,
$B$ for birthdate, $C$ for phone number, $E$ for email address, $I$ for
identifier number, and $N$ for personal name). While most prior studies
focused on enhancing the variable set to model different types of passwords,
Cheng et al. (Cheng et al., 2021) focus on improving the semantic parsing step
(i.e., splitting the training password into segments). Specifically, semantic
parsing requires effectively identifying the words inside passwords. In the
prior approaches, this task is done by matching the possible substrings of the
passwords with a list of standard words (e.g., dictionary, keyboard pattern,
popular words). For the word that is not included in the list, it can not be
identified by matching. The parsing method in (Cheng et al., 2021) addresses
this problem through an iterative process that updates the list of standard
words with new words identified in the training passwords. To identify new
words, they use the concepts of cohesion and freedom of words which were
proposed in (He and Zhu, 2001). The cohesion evaluates the internal
association of a given string. A complete word should have large cohesion. On
the other hand, freedom measures the independence of a substring from its
context. Large freedom means the string likely composes of several words. Wang
et al. (Wang et al., 2016b) proposed TarGess framework which consists of four
targeted password guessing models (named TarGuess I to TarGuess VII) based on
PCFG to address different practical scenarios of targeted password guessing.
TarGuess-I aims to online guess a targeted user’s password by exploiting some
personal information of that user (e.g., name, birthday, not gender). The
TarGuess-II algorithm guesses a user’s password given a leaked password of
that user. TarGuess-III and IV used both one leaked password and some personal
information of a user to guess the unknown password of that user. The authors
also noted that the ideas of these models can be implemented using other
algorithms (e.g., Markov).

Figure 3. An illustration training and generating password following the PCFG
model proposed by Wei et al. (Weir et al., 2009), whereas, the probabilities
of generated passwords are computed according to the pre-terminal probability
order.

####  3.4.4. Deep Learning

Inspired by the success of deep learning in different fields (e.g.,
Agriculture (Kamilaris and Prenafeta-Boldú, 2018), Medical (Litjens et al.,
2017), Robotics (Károly et al., 2020)), many studies have adopted deep
learning techniques to password guessing (e.g., Recurrent Neural Network (Xu
et al., 2017; Fang et al., 2018; Luo et al., 2019; Zhang et al., 2020b),
Generative Adversarial Network (Hitaj et al., 2019; Guo et al., 2021a;
Pasquini et al., 2021b), Convolutional Neural Network (Pasquini et al.,
2021a), Transformer (Li et al., 2019)).

Recurrent Neural Network: Recurrent neural network (RNN) refers to a class of
artificial neural networks that are specialized for sequential data (e.g.,
time-series signals, natural language data). An RNN processes the sequential
data step-by-step in a way that the output of a step is affected by both the
input of that step and the outputs of previous steps. It is well-known that
standard RNN suffers from the vanishing gradient problem and is ineffective
for modeling long sequential data (Hochreiter, 1998). Long Short-Term Memory
(LSTM) is an RNN architecture specifically designed to address the vanishing
gradient problem (Hochreiter and Schmidhuber, 1997). Inspired by the success
of LSTM in various sequential data types, some studies adopted LSTM for
password modeling (e.g., (Melicher et al., 2016; Xu et al., 2017; Fang et al.,
2018; Li et al., 2019; Luo et al., 2019; Zhang et al., 2020b)).

The first LSTM-based password model was proposed by Melicher et al. (Melicher
et al., 2016). In that study, the password guessing task is performed by using
an LSTM network (having a 3-layer LSTM and 2 fully connected layers) to
repeatedly predict the next character of the password given preceding
character(s). For example, to generate the password “$\mathsf{pass12}$”, the
LSTM first predicts the probability of ‘$\mathsf{p}$’. Then, it uses
‘$\mathsf{p}$’ to forecast the occurrence of ‘$\mathsf{a}$’. Then,
“$\mathsf{pa}$” is used to predict ‘$\mathsf{s}$’. The process is repeated
until the password-ending symbol is encountered. To be processed by LSTM, each
character of a password is transformed into a numerical vector using one-hot
encoding. For example, to represent a character from the space of $26$
alphabet letters and $10$ number digits, a vector of length $36$ is used, in
which the value of component indexed by the character is $1$ and all other
components are $0$. In this case, the output (at each step) of LSTM is also a
vector of length $36$. Each component of the output vector contains the
predicted probability of the corresponding character. The probability of the
predicted password is the production of all characters’ probabilities. Figure
4 illustrates an example of generating the password “$\mathsf{pass12}$” using
LSTM. Fang et al. (Fang et al., 2018) proposed another password guessing model
by combining semantic analysis and LSTM. Specifically, before processing by
LSTM network, the training passwords are split into segments by their semantic
(e.g., dictionary word, keyboard pattern, number, special symbol). Then, the
segments are used as the basic data for each step of LSTM (instead of
characters as in (Melicher et al., 2016)). The idea of combining semantic
analysis and LSTM was also used in (Zhang et al., 2020b) to target the Chinese
passwords. In that study, the Chinese syllabus is used to parse the training
passwords to obtain the password structures and segments. Then, the segments
and structures were used for training the LSTM network. Luo et al. (Luo et
al., 2019) proposed an LSTM-based password guessing that works on frames of
fixed length. In each step, this LSTM receives a segment of $T$ characters as
input, and uses it to guess the next character of the password, where $T$ is
the model parameter specified by the user. The output of each step is also a
segment of $T$ characters, in which, the last character is the predicted one,
and the first $T-1$ characters are the last $T-1$ characters of the input. For
example, given a password as “$\mathsf{passw12}$” and $T=3$, the first step of
LSTM will get “$\mathsf{pas}$” as input and output “$\mathsf{ass}$”. In the
second step, “$\mathsf{ass}$” is input to get “$\mathsf{ssw}$”. The process is
repeated to complete all characters of the password. In addition, the model
also integrates the group information of the targeted user (e.g., game,
programmer, marriage, writing, social) to enhance the hitting probability. Li
et al. (Li et al., 2019) proposed an improved RNN model for password guessing
with Bidirectional LSTM (BiLSTM). Bidirectional RNN processes the information
flow in both the backward and forward directions (Schuster and Paliwal, 1997).
Thus, the model is capable of incorporating information from both the past and
the future to produce more meaningful features at each step. Besides, the
authors leveraged and transformed the learned knowledge in BERT (Bidirectional
Encoder Representations from Transformer) (Devlin et al., 2018) to their model
using knowledge distillation (Hinton et al., 2015).

Pal et al. (Pal et al., 2019) proposed pass2path, an LSTM deep network
following the Encoder-Decoder architecture (Sutskever et al., 2014), to model
the user’s behavior on reusing passwords. This study introduced a different
approach compared to prior methods which mostly focused on modeling password
distribution. Specifically, given a password, pass2path produces some
transformation paths that users will likely perform in practice in order to
get new passwords. Each transformation path involves a sequence of
substituting, inserting, or deleting a character of the password to obtain a
new password. The pass2path’s architecture comprises two main sub-networks: an
Encoder and a Decoder, each one is a 2-layer LSTM with residual connections.
The operation of pass2path is similar to a typical seq2seq model (Sutskever et
al., 2014). Given an input password (each password’s character is represented
by a one-hot encoding vector), the Encoder maps it to a latent vector denoted
as $\mathbf{v}_{0}$. Then, the Decoder gets $\mathbf{v}_{0}$ and a special
beginning-of-sequence symbol as the inputs, to output a probability
distribution over the set of transformations. The most probable transformation
is selected and fed to the Decoder in the next iteration to get the next
transformation set, until the end-of-sequence symbol is returned. To obtain a
set of transformation paths, beam search (Wilt et al., 2010) of size $q$ is
used (at each step $q$ most probable transformations are used). The obtained
transformation paths are then applied to the password to generate the
candidate passwords.

Figure 4. An example of using LSTM proposed in (Melicher et al., 2016) to
generate the password “$\mathsf{pass12}$”. In each step, the network outputs
one character (represented by a one-hot encoding vector) which is used as the
input of next step to generate next character.

Deep Generative Models: Deep generative models (DGMs) are neural networks
trained to parametrize the distribution of unknown high-dimensional data,
given a set of training data samples. Upon successfully training, the DGMs can
be used to generate new samples that comply with the learned data
distribution. There are two common approaches for training a DGM: Generative
Adversarial Networks (GAN) (Goodfellow et al., 2014) and Autoencoder (AE)
(Kingma and Welling, 2013).

Generative Adversarial Network (GAN) is a generic architecture for training a
generative model, proposed by Ian Goodfellow et al. (Goodfellow et al., 2014).
Given a training dataset
$\mathcal{X}=\\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\\}$, GAN
can automatically discover the regularities or patterns in a training dataset
$\mathcal{X}$ such that the trained model can generate new data samples that
have the same distribution as the training set. GAN’s architecture involves
two sub-networks: the generator and the discriminator. The generator takes as
input a fixed-length random vector $\mathbf{z}$ and tries to create a faked
data sample that is as close to the real in $\mathcal{X}$ as possible. The
discriminator tries to discriminate whether a given data sample is real or
generated by the generator. In the training process, the task of data
distribution estimation to parametrize the generator is transformed into the
binary classification problem which discriminates the real and fake data
samples, performed by the discriminator. Formally, the generator and
discriminator are trained simultaneously following a minimax game with the
loss function:

(3)
$\min\limits_{\theta_{G}}\max\limits_{\theta_{D}}E_{\mathbf{x}}[\log(\mathsf{f}(\mathbf{x};\theta_{D}))]+E_{\mathbf{z}}[\log(1-\mathsf{f}(\mathsf{g}(\mathbf{z};\theta_{G});\theta_{D}))],$

where $\theta_{G}$ and $\theta_{D}$ mean the parameters of the generator and
discriminator, respectively; $\mathsf{f}(\mathbf{x};\theta_{D})$ represents
the probability estimated by the discriminator that a real data $\mathbf{x}$
is real; $\mathsf{g}(\mathbf{z};\theta_{G})$ means generating a fake data
sample by the generator when inputting a random vector $\mathbf{z}$; and
$\mathsf{f}(\mathsf{g}(\mathbf{z};\theta_{G});\theta_{D}))$ represents the
probability estimated by the discriminator that the fake data is real. Once
trained, the generator can output the data samples that have the same
distribution as the training set $\mathcal{X}$ when a random vector is fed as
its input.

Autoencoder: Autoencoder is another deep generative model that comprises two
deep networks: an encoder and a decoder. The encoder network maps the input
data $\mathbf{x}$ into a vector $\mathbf{z}$ in latent space which is usually
smaller than the data space. The decoder gets the latent vector $\mathbf{z}$
and tries to obtain a reconstructed version $\mathbf{x}^{\prime}$. Basically,
an AE network is optimized by minimizing the distance between a reconstructed
vector $\mathbf{x}^{\prime}$ and its original version $\mathbf{x}$,

(4)
$\min\limits_{\theta_{E},\theta_{D}}\sum_{x\in\mathcal{X}}\mathsf{d}(\mathbf{x},\mathbf{x}^{\prime}),$

where $\theta_{E}$ and $\theta_{D}$ respectively mean the parameters of the
encoder and decoder, $\mathcal{X}$ are the training dataset, and $\mathsf{d}$
is the desired distance measurement function. Once trained, the decoder can be
used as a deep generator network which gets a latent vector as input and
outputs a data sample. However, the basic AE architecture as described above
is unable to produce new content. So, several regularization methods have been
proposed, which force the latent space to follow a chosen prior distribution
(e.g., Variational Autoencoder (VAE) (Kingma and Welling, 2013), Adversarial
Autoencoder (AAE) (Makhzani et al., 2015), Wasserstein Autoencoder (WAE)
(Tolstikhin et al., 2017)).

(a)

(b)

Figure 5. The generative models for password guessing. (a) Generative
Adversarial Network. After training, the Generator is used to sample new
passwords for guessing; (b) Autoencoder. Upon trained, the Decoder can
generate candidate passwords.

Inspired by the success of DGMs on various tasks, several DGMs have been
proposed for password guessing (e.g., GAN-based models (Hitaj et al., 2019;
Guo et al., 2021a; Pasquini et al., 2021b; Zhou et al., 2022), AE-based models
(Pasquini et al., 2021b)). In such studies, the leaked passwords are used to
train a deep generative network following GAN or AE. Figures 5 illustrate the
use of GAN and AE for training a deep password generator. Upon training, the
generator (GAN) or decoder (AE) is used to sample the candidate passwords.
Hitaj et al. (Hitaj et al., 2019) proposed PASSGAN which is the first password
guessing model using GAN to autonomously learn the password distribution from
a leaked password dataset. In that study, the authors followed the improved
Wasserstein GANs (IWGAN) (Gulrajani et al., 2017), and used the stack of 5
residual blocks (He et al., 2016) as the backbones for the generator and
discriminator. The model was trained with the leaked password dataset. To be
processed by the deep model, each character was represented by a one-hot
encoding vector. Then, each password was represented by a matrix formed from
the one-hot encoding vectors of its characters. However, only passwords of
$10$ characters or less were considered in that study. Guo et al. (Guo et al.,
2021a) proposed PGGAN which aimed to address the high duplication rate (i.e.,
some passwords are repeatedly generated) in the existing GAN-based password
guessing models. The PGGAN architecture composes of the generator,
discriminator, and controller. The functions of the generator and
discriminator are similar to those in the original GAN. The controller
receives an input string which is either a password from the generator or a
random-generated string, and tries to tell the origin of this string. By
combining the feedback from the discriminator and controller, the generator is
trained to output the passwords that are close to the distribution of training
dataset and also close to the uniform distribution. The above goals contradict
each other, thus, a suitable balance should be specified. Zhou et al., (Zhou
et al., 2022) proposed G-Pass which is another GAN-based password generation
model. G-Pass used LSTM network for the generator, and multiple convolutional
layers with multiple filter sizes for the discriminator. In addition, they
used Gumbel-Softmax (Jang et al., 2016) to address the difficulty of gradient
computing when working with categorical data (e.g., characters of passwords).
Pasquini et al. (Pasquini et al., 2021b) proposed two deep generative models,
one used improved Wasserstein GAN (Gulrajani et al., 2017), and another relied
on Wasserstein Autoencoders (Tolstikhin et al., 2017). To overcome the problem
of discrete representation of the characters, they used stochastic smoothing
which adds small-magnitude noise to the one-hot-encoding vector of each
character. The authors also utilized the geometric relation of vectors in the
latent space to propose the concept of password locality. Specifically, in the
latent space, vectors of different classes of passwords are organized into
different zones. This enables conditional password guessing, which allows the
generation of passwords in a specific class by inputting vectors from a
specific zone in the latent space.

####  3.4.5. Hybrid Model

There are several hybrid approaches that combined different techniques to
build a password guessing model (e.g., PCFG and BiLSTM (Zhang et al., 2018);
GENPass (PCFG and LSTM) (Liu et al., 2018; Xia et al., 2019), PaMLGuess (PCFG
and LSTM) (Zhang et al., 2020c)). Zhang et al. (Zhang et al., 2018) proposed a
password guessing model by combining PCFG and BiLSTM. In the training phase,
PCFG was used to parse the passwords to a collection of basic structures (non-
terminal forms) and strings (common words) sorted by probability. The strings
were used to train a BiLSTM network. In the password generating process, the
strings generated by BiLSTM were combined with the password structures
(obtained from the training phase) to sample candidate passwords. The authors
in (Liu et al., 2018; Xia et al., 2019) proposed GENPass, a password
generation method built from the ideas of PCFG and LSTM. GENPass is designed
to generate a generic candidate password list which is learned from different
leaked datasets. First, the combination of PCFG and LSTM (called PL) was used
to learn, then generate passwords following a specific dataset. Using PCFG,
the pre-terminal form of each training password was obtained (e.g.,
$S_{1}L_{4}D_{3}$ from “$\mathsf{!pass135}$”) (see Section 3.4.3). From the
pre-terminal forms, an LSTM network was trained to generate high-probable pre-
terminal forms for password guessing. Each PL model was trained separately
using its own dataset. Upon being trained, all the PL models were combined
(i.e., their outputs were fused to provide a generic list of the generated
non-terminal forms). In this step, a discriminator module is used to filter
the passwords that do not have a consistent probability of appearance in all
the PL models. Zhang et al. (Zhang et al., 2020c) combined Targess I (PCFG)
(Wang et al., 2016b) and LSTM to construct a password guessing model. Given
the training password dataset, the basic password structures and the strings
(words) were extracted according to the variables defined in Targess I. The
strings were used to train LSTM network. For generating the candidate
passwords, the LSTM network samples new strings which will be fed to the
password structures.

###  3.5. Guessing Performance

This section discusses the performance of existing password guessing models.
First, we summarize methods and procedures used to experimentally evaluate the
guessing performance of existing studies. Then, we present the criteria and
metrics used in the evaluation. Finally, we summarize the experimental
guessing performances reported in the original papers.

####  3.5.1. Evaluation Method

To evaluate the performance of a password guessing model, a set of passwords
$\mathcal{T}$ were used as the targets to be attacked. As passwords are
extremely sensitive, it is impractical to collect and establish public
benchmark datasets by leveraging contributions from volunteers. Users may
contribute unrealistic passwords (i.e., those that they do not actually use)
which raises a concern about the reliability of research. Moreover, it is also
challenging to manage and share the collected datasets so that they are only
used for research. Most existing studies leveraged the real password datasets
leaked by some attacks and made public on the Internet. There are a large
number of leaked password datasets, each one can have thousands to millions of
real passwords which have served as an irreplaceable source for password
modeling research (see Section 3.3.2 for the list of these datasets). However,
only relying on the leaked password datasets faces several limitations (see
4). Some studies leveraged the real password datasets obtained from their
organizations (e.g., ONYEN from California University (Zhang et al., 2010),
CMU password dataset (Mazurek et al., 2013)). Such datasets usually contain
additional user information such as email, user ID. However, these datasets
could not be shared for public research due to user privacy.

Given a target set $\mathcal{T}$, the guessing model (under evaluation) will
generate candidate passwords to be tried against $\mathcal{T}$. Depending on
the security model (i.e., online or offline), the subsequent evaluation
procedure will have some differences. For an offline password guessing model,
a sequence of candidate passwords $\mathcal{S}=\\{s_{1},s_{2},\ldots,s_{N}\\}$
are generated (usually following the order of descending probability, i.e.,
$\mathsf{p}_{(s_{1})}>\mathsf{p}_{(s_{2})}>...>\mathsf{p}_{(s_{N})}$). Then,
each candidate password in $\mathcal{S}$ is attempted against all the
passwords in $\mathcal{T}$. After each iteration, the matched passwords in
$\mathcal{T}$ are removed from the set (and are considered cracked). The
number of cracked passwords (after trying all candidate passwords) is used to
determine the model performance. As the offline password attack does not limit
the number of trials, a large number of candidate passwords (e.g., millions of
passwords) can be generated, depending on the model’s capability.

In the online setting, the procedure is slightly different. For each target
$t$ in $\mathcal{T}$, the model will generate a sequence of candidate
passwords $\mathcal{S}^{t}=\\{s^{t}_{1},s^{t}_{2},\ldots,s^{t}_{n}\\}$, also
following the descending probability order. However, $\mathcal{S}^{t}$ are
usually generated by leveraging both the global and target’s information. The
global information is similar for all targets (e.g., password policy, native
language) while the target’s information is different for each user (e.g.,
name, birthdate, old password, password-forming behavior). So, the password
sequences used to attack different targets are not guaranteed to be similar.
Moreover, for an online attack, the number of candidates is usually small
(e.g., 5).

####  3.5.2. Evaluation Criteria

A password guessing model can be evaluated based on several criteria such as
guessing performance, running time, generation capacity, duplicate rate, and
model size.

Guessing Performance: (i.e., guessing accuracy) is the most important
criterion to evaluate a password guessing model. Several metrics have been
defined for this purpose. The most common one is the $\beta$-success rate
which was formally described by Boztas (Boztas, 1999). $\beta$-success rate
shows the expected ratio of passwords being cracked when guessing with $\beta$
candidates generated by the guessing model. Let $p_{i}$ be defined as
$p_{i}=\frac{|\hat{\mathcal{T}}_{i}|}{|\mathcal{T}|}$, where
$\hat{\mathcal{T}}_{i}$ means a subset of $\mathcal{T}$ which are cracked by
the guess $i$. Then, the $\beta$-success rate is determined by:

(5) $\lambda_{\beta}(\mathcal{T})=\sum_{i}^{\beta}p_{i}.$

From the definition, $\lambda_{\beta}(\mathcal{T})$ was originally designed
for the evaluation of an offline model as it is computed by accumulating the
success rates when using a (fixed) sequence of candidate passwords to guess a
set of targets $\mathcal{T}$. In practice, $\lambda_{\beta}(\mathcal{T})$ can
also be used to measure the performance of an online model. In this setting,
it is determined by

(6)
$\Lambda_{\beta}(\mathcal{T})=\frac{|\hat{\mathcal{T}}_{(\beta)}|}{|\mathcal{T}|},$

where $\hat{\mathcal{T}}_{\beta}$ is the set of users cracked within $\beta$
guesses. Overall, $\Lambda_{\beta}(\mathcal{T})$ can be used to measure the
performance of both the online and offline models, and has been widely used in
prior password guessing research. The main difference between two settings is
how to determine the set of users cracked within $\beta$ guesses (i.e.,
$\hat{\mathcal{T}}_{\beta}$). In the online mode, a sequence of $\beta$
candidate passwords is optimally generated for each targeted user in
$\mathcal{T}$. So, there could be $|\mathcal{T}|$ different sequences being
generated. On the other hand, the offline setting uses only one sequence of
passwords to attack all passwords in $\mathcal{T}$. In addition, $\beta$ is
usually small (e.g., $\beta=3$, $\beta=5$) for the online setting while it can
reach thousands of million in an offline attack. Note that, in most existing
password guessing studies, $\beta$-success rate was represented in form of
percent, instead of the ratio.

Another metric used to evaluate the guessing performance is $\alpha$-work-
factor, first formalized by Pliam (Pliam, 2000), which shows the fixed number
of guesses (per account) required to crack $\alpha$ passwords in
$\mathcal{T}$:

(7)
$\mu_{\alpha}(\mathcal{T})=\min\\{j\bigg{\rvert}\sum_{i=1}^{j}p_{i}\geq\alpha\\},$

where $p_{i}$ is the fraction of passwords in $\mathcal{T}$ cracked by the
guess $i$. Similar to $\beta$-success rate, the $\alpha$-work-factor can be
used either online or offline as explained above.

Running Time: measures how long the model needs to generate a candidate
password. In the case of online password guessing, only a small number of
guesses are allowed. Moreover, the password generation time is much smaller
compared to the network delay (online guessing usually targets a remote
service). Thus, the running time is not important and is mostly ignored for an
online password guessing model. However, this criterion is worth considering
for an offline model due to several reasons. First, an offline password
cracking model usually performs millions of guesses. Second, the cracking
speed mainly relies on the password generation speed and the operation of
hashing, however, no network delay. Third, one of the main uses of an offline
guessing model is proactive password checking which usually runs on the client
side having low computing resources. Thus, having a low running time is a
considerable advantage of an offline password guessing model.

Other Criteria: besides, there are several other criteria that need to be
aware of when designing a password guessing model.

Model size is an important criterion when using the password guessing model as
a proactive password checker deployed on the client side (Wheeler, 2016). The
small-size model can be quickly transferred to and installed in the client
device. Moreover, such models are also ideal for mobile devices which usually
have low storage capacity.

Generation capacity refers to the number of unique passwords a model can
generate. A password guessing model has an upper bound $B$ on the number of
unique passwords that it can generate (e.g., $B=10^{10}$). Upon reaching this
limitation, some models can not generate any more new candidate passwords
without changing their referenced information (e.g., Markov, PCFG, mangling
rule). On the other hand, some models will generate repeated passwords upon
reaching their upper bound (e.g., GAN-based model) As an online attack is
limited by a small number of guesses, the generation capacity is mostly
ignored when designing an online password guessing model. However, offline
password guessing is only limited by computing speed and generation capacity.
So, besides arranging the candidate passwords in the decreasing order of
hitting chances, the offline password guessing model also notices the
generation capacity. This could be enhanced by increasing the amount of
referenced information, or the model parameters.

Duplicate rate: refers to the portion of passwords that the model generates
more than once (i.e., the passwords that are repeatedly produced by the
model). In the online attack, a small number of candidate passwords with high
hitting-chance are generated. Thus, there is no duplication on the generated
passwords. In the offline setting, the model can produce millions of passwords
and duplication is easy to occur. The duplicate passwords prolong the
attacking time and reduce the guessing performance. Thus, some studies are
also aware of reducing the duplicate rate of the generated candidate passwords
(Guo et al., 2021a).

####  3.5.3. Evaluation Results

Table 4. Experiment procedure and reported performance of the existing online password guessing models. Method | Target Set | Referenced Data | No. Guesses |  $\beta$-success Rate
---|---|---|---|---
Global |  (§)Target’s Infor | $(\beta)$ | $(\Lambda_{\beta})$
Zhang et al. (Zhang et al., 2010) |  $7,752$ users | $-$ | P | $5$ | $0.13$
of ONYEN | $20$ | $0.28$
Personal PCFG |  $50\%$ of |  $50\%$ of | N, B, E, | $5$ | $0.048$
Li et al. (Li et al., 2016) | 12306 | 12306 | A, H, I
Das et al. (Das et al., 2014) |  $3,463$ passwords | $-$ | P | $10$ | $0.1$
of 10 sites
TarGuess-I | 50% of | 50% of | B, N, E, | $5$ | $0.085$
Wang et al. (Wang et al., 2016a) | 12306 | 12306 | A, H, I
TarGuess-II |  $308,045$ by |  $66,573$ by | P | $5$ | $0.065$
Wang et al. (Wang et al., 2016a) | $\text{Dodonew}\cap\text{CSDN}$ | $126\cap\text{CSDN}$
TarGuess-III |  $308,045$ by |  $66,573$ by | P, N, B, | $5$ | $0.066$
Wang et al. (Wang et al., 2016a) | $\text{Dodonew}\cap\text{CSDN}$ | $126\cap\text{CSDN}$ | H, I
TarGuess-IV |  $308,045$ by | $66,573$ | P, N, B, | $5$ | $0.076$
Wang et al. (Wang et al., 2016a) | $\text{Dodonew}\cap\text{CSDN}$ | $126\cap\text{CSDN}$ | H, I, G
Pass2Path |  $29.2$ mils |  $146.4$ mil | P | $10$ | $0.099$
Pal et al. (Pal et al., 2019) | users | passwords | $10^{2}$ | $0.0131$
Pass2Path |  $15,776$ users of |  $146.4$ mil | P | $10$ | $0.033$
Pal et al. (Pal et al., 2019) | Cornell Uni | passwords
PaMLGuess |  $50\%$ of |  $50\%$ of | P | $10^{2}$ | $0.135$
Zhang et al. (Zhang et al., 2020c) | 12306 | 12306 | $10^{3}$ | $0.18$
‘$\cap$’ means merging $2$ datasets to get the users having passwords in both
datasets
(§)Target’s Infor: ‘P’ - leaked password; ‘N’ - name; ‘B’ - birthdate; ‘E’ -
email;
‘A’ - account name, ‘H’ - phone number, ‘I’ - government issued number.

In this section, we summarized the performance reported in existing password
guessing models which are categorized into two groups: online and offline.
Note that, to be unified, we used $\beta$-success rate (see 3.5.2) to describe
the guessing performance. For the studies that used other metrics, we convert
the reported performance to $\beta$-success rate (if possible) or provide
additional notice. In addition, we used $\Lambda_{\beta}$ as the notation of
$\beta$-success rate (instead of $\Lambda_{\beta}(\mathcal{T})$) also for
simplicity.

Online Model: Evaluating the performance of an online password guessing model
is such a challenging task due to the inability to collect benchmark datasets.
This comes from the fact that most online guessing models require the leaked
passwords and personal information of the targeted user to guess the unknown
passwords of that user. However, in practice, such information is extremely
sensitive, and almost impossible to be obtained from the volunteers. Most
leaked password datasets have one password per user, and none or very little
user information, thus, are not suitable for evaluating the online guessing
models. As a result, each study tried to obtain the evaluation dataset in a
different way (e.g., using private database, combining different datasets)
which is hard to reproduce or compare.

Zhang et al. (Zhang et al., 2010) used a dataset containing $51,141$ hashed
passwords from $10,374$ inactive users of the ONYEN service888ONYEN service,
The University of California, where each user had $4$ to $15$ passwords. They
first used various password cracking methods (e.g., Hashcat (Steube, [n. d.]),
John the Ripper (Peslyak, [n. d.])) to crack and obtain $31,075$ plaintext
passwords of $7,936$ users. Then, they used $7,752$ users who had at least two
cracked passwords for their experiment. With each user, given a password, they
applied some mangling functions to get the unknown passwords of that user. On
average, the reported performance is $\Lambda_{5}=0.13$ and
$\Lambda_{13}=0.18$ (i.e., $13\%$ of passwords can be guessed within $5$
attempts, and $18\%$ with $10$ attempts). Li et al. (Li et al., 2016)
evaluated their model on the 12306 dataset. This dataset contained more than
$130,000$ passwords (along with some information such as user name, the
government-issued unique ID number) leaked from the official site of an online
railway ticket reservation in China999https://www.12306.cn/index/. They used
half of the dataset for training the PCFG (i.e., global data), and evaluated
the trained model with the remaining half. To guess the password of a user,
they fed that user’s personal information (i.e., target’s data) to the PCFG’s
grammar to generate the candidate passwords. They reported that their model
achieved the performance as $\Lambda_{5}=0.048$. Instead of using passwords
leaked from a service/organization, some studies combined datasets leaked from
different sources to obtain new datasets having multiple leaked passwords per
each user (e.g., (Das et al., 2014; Wang et al., 2016b)). For instance, Das et
al. (Das et al., 2014) created a password dataset having user information and
at least two passwords by combining the leaked datasets of $10$ sites (about
$7,962,678$ passwords). Then, they filtered and obtained a dataset of $6,077$
users who had at least two passwords used for different sites. Furthermore,
they removed all identical password pairs. After all, the remaining dataset
has only users that used different passwords for different sites ($\approx
3,463$ users). Given a leaked password of a user, they performed some
transformations to generate candidate passwords to guess the unknown passwords
of that user. They reported that their method could achieve the performance as
$\Lambda_{10}=0.1$ when guessing the nonidentical passwords. Wang et al. (Wang
et al., 2016b) also combined different leaked password databases to create
sets of users having multiple passwords on different sites, then used these
sets to evaluate their online password guessing models (i.e., TarGuess-I, -II,
-III, -IV) under different scenarios (see Table 4 for representative results).
Overall, their guessing performance on normal users was $\Lambda_{100}=0.73$,
and $\Lambda_{100}=0.32$ for security-savvy users. Pal et al. (Pal et al.,
2019) used a database consisting of $463$ million unique passwords of $1.1$
billion unique emails leaked from multiple sites (e.g., LinkedIn, Myspace,
Badoo, Yahoo, Twitter, Zoosk, Neopet, etc). The authors performed some data
cleansing steps (e.g., remove dummy accounts, discard passwords in hex
characters, etc), then, merged the accounts to find a set of passwords
belonging to an individual user. Finally, they formed a dataset that includes
users having at least two passwords. From the obtained dataset, they used
$146.4$ million passwords ($116.8$ million users) for training and $42$
million passwords ($29.2$ million users) for testing. On average, without
counting the cracked passwords which appeared in the training set, their
method achieved the $\Lambda_{10}$, $\Lambda_{10^{2}}$, and $\Lambda_{10^{3}}$
as $0.099$, $0.131$, and $0.158$, respectively. The $\Lambda_{\beta}$
increased to $0.448$, $0.467$, and $0.483$ when including the passwords
appeared in both training and testing sets. When using multiple leaked
passwords (at least $2$), the achieved performance was
$\Lambda_{10^{3}}=0.23$, without counting the repeated passwords. They
additionally evaluated their model on the real email accounts of Cornell
University, with the support of the IT Security Office of Cornell University
(ITSO). Cornell University adopted the password policy that required forming a
password from at least $8$ characters of more than three classes chosen from
upper-case, and lower-case letters, digits, and symbols. The experiment on
$15,776$ valid emails of Cornell accounts showed that the pass2path could
crack $3.3\%$ of accounts within $10$ guesses. Zhang et al. (Zhang et al.,
2020c) also used the 12306 dataset to evaluate the PaMLGuess model. They also
trained their model with $50\%$ dataset and tested on the remaining $50\%$.
The reported performances were $\Lambda_{100}=0.135$ and
$\Lambda_{10^{3}}=0.18$. We summarize in Table 4 the reported performance of
existing online password guessing models.

Offline Model: The offline password guessing models were evaluated on a large
number of leaked password datasets available on the Internet (see 3.3.2).
However, these datasets were obtained by illegal attacks and leaked to the
public under different versions. There is no official organization responsible
for maintaining and validating the content of such datasets. Then, each study
may use a different data cleaning process. Thus, the datasets that were
actually used for evaluation in each study are not identical. Moreover,
depending on each approach, the process of password generating may require
additional information sources (e.g., dictionary, keyboard pattern, user
information…). So, we try to include as much as possible the important
information involved in the experiment of each study to provide a detailed
picture of the evaluation. The experimental guessing performances of
representative offline password guessing studies were summarized in Table 5.

Table 5. Experimental settings and performances of the offline password guessing models. Study |  Method | Referenced Data |  (§)Attacked | No. Guesses |  $\beta$-success Rate | Note
---|---|---|---|---|---|---
|  | Password |  (†)Others | Set | $(\beta)$ | $(\Lambda_{\beta})$ |
Narayanan et al., 2005 (Narayanan and Shmatikov, 2005) |  Mangling Rules | $-$ | L | $142$ | $2B$ | $0.676$ |
Weir et al., 2009 (Weir et al., 2009) |  PCFG | $\text{MS}_{(33.5K)}$ | D | $\text{MS}_{(33.5K)}$ | $37.8M$ | $0.329$ |
|  | $\text{MS}_{(33.5K)}$ | $\text{SW}_{(33.5K)}$ | $37.8M$ | $0.069$ |
|  | $\text{FN}_{(15.7K)}$ | $\text{MS}_{(33.5K)}$ | $37.8M$ | $0.069$ |
|  | $\text{FN}_{(15.7K)}$ | $\text{FN}_{(22.7K)}$ | $37.8M$ | $0.069$ | unav
Zhang et al., 2010 (Zhang et al., 2010) |  Mangling rules | $\text{OY}_{(7.7K)}$ | D | $\text{OY}_{(\approx 20K)}$ | 3 seconds | $0.41$ | pri
Rao et al., 2013 (Rao et al., 2013) |  POS | $-$ | L | $1434$ | $2,500B$ | $0.18$ | una -spe
Veras et al., 2014 (Veras et al., 2014) |  PCFG | $\text{RY}_{(32M)}$ | D, L | $\text{LI}_{(5.8M)}$ | $3B$ | $0.28$ |
|  | $\text{RY}_{(32M)}$ | $\text{MS}_{(49.6K)}$ | $3B$ | $0.74$ |
Li et al., 2014 (Li et al., 2014) |  PCFG | $\text{RY}_{(2M)}$ | D, K, L | CS | $10M$ | $0.127$ |
|  | $\text{DU}_{(2M}$ | CS | $10M$ | $0.173$ |
Durmuthet al., 2015 (Dürmuth et al., 2015) |  Markov | $\text{RY}_{(30M)}$ | $-$ | $\text{RY}_{(2.6M)}$ | $1B$ | $0.69$ |
|  | $\text{RY}_{(30M)}$ | $\text{MS}_{(50K)}$ | $1B$ | $0.65$ |
|  | $\text{RY}_{(30M)}$ | FB | $1B$ | $0.6$ |
Li et al., 2016 (Li et al., 2016) |  PCFG | $\text{OT}_{(50\%)}$ | D, U | $\text{OT}_{(50\%)}$ | $2M$ | $0.49$ |
Zhang et al., 2018 (Zhang et al., 2018) |  PCFG& BiLSTM | $\text{DO}_{(14M)}$ | $-$ | $\text{DO}_{(2M)}$ | $10M$ | $0.35$ |
|  | $\text{RY}_{(25M)}$ | $\text{RY}_{(7M)}$ | $10M$ | $0.53$ |
|  | RY | DO | $10M$ | $0.355$ |
|  | DO | RY | $10M$ | $0.49$ |
|  | DO | $\text{CS}\cup\text{JD}$ | $10M$ | $0.38$ |
|  | RY | $\text{PB}\cup\text{YH}$ | $10M$ | $0.56$ |
|  | DO | $\text{PB}\cup\text{YH}$ | $10M$ | $0.315$ |
|  | RY | $\text{CS}\cup\text{JD}$ | $10M$ | $0.47$ |
Xia et al., 2019 (Xia et al., 2019) |  GAN | MS | $-$ | MS | $10M$ | $0.556$ |
|  | PB | PB | $10M$ | $0.579$ |
|  | $\text{MS}\cup\text{PB}$ | $\text{RY}_{(10\%)}$ | $1000B$ | $0.34$ |
|  | $\text{MS}\cup\text{PB}$ | $\text{LI}_{(10\%)}$ | $1000B$ | $0.22$ |
Hita et al., 2019 (Hitaj et al., 2019) |  GAN | $\text{RY}_{(80\%)}$ | $-$ | $\text{RY}_{(1.98M)}$ | $10B$ | $0.26$ |
Zhang et al., 2020 (Zhang et al., 2020c) |  PaLSTM | $\text{OT}_{(50\%)}$ | U | $\text{OT}_{(50\%)}$ | $2M$ | $0.255$ |
Zhang et al., 2020 (Zhang et al., 2020b) |  CSNN | $\text{NE}_{(20.63M)}$ | $-$ | OT | $1M$ | $0.135$ |
|  | $\text{NE}_{(20.63M)}$ | DO | $1M$ | $0.22$ |
|  | $\text{NE}_{(20.63M)}$ | CS | $1M$ | $0.31$ |
to be continued
Table 6. (continued) Experimental settings and performances of the offline password guessing models. Study |  Method | Referenced Data |  (§)Attacked | No. Guesses |  $\beta$-success Rate | Note
---|---|---|---|---|---|---
|  | Password |  (†)Others | Set | $(\beta)$ | $(\Lambda_{\beta})$ |
Pasquini et al., 2021 (Pasquini et al., 2021b) |  GAN | RY | D | LI | $10B$ | $0.62$ |
|  | RY | YK | $10B$ | $0.61$ |
|  | RY | ZO | $10B$ | $0.68$ |
Pasquini et al., 2021 (Pasquini et al., 2021a) |  AdaMs | MH | D | AN | $10^{11}$ | $0.83$ |
|  | MH | PB | $10^{11}$ | $0.85$ |
|  | MH | RY | $10^{11}$ | $0.83$ |
|  | ZK | AN | $8\cdot 10^{10}$ | $0.4$ |
|  | ZK | PB | $4\cdot 10^{10}$ | $0.37$ |
|  | ZK | RY | $6\cdot 10^{10}$ | $0.395$ |
|  | ZK | MH | $10^{11}$ | $0.44$ |
|  | YK | AN | $8\cdot 10^{10}$ | $0.52$ |
|  | YK | PB | $10^{11}$ | $0.53$ |
|  | YK | RY | $5\cdot 10^{10}$ | $0.48$ |
|  | YK | MH | $10^{11}$ | $0.52$ |
|  | RY | AN | $9\cdot 10^{10}$ | $0.62$ |
|  | RY | PB | $6\cdot 10^{10}$ | $0.62$ |
|  | RY | MH | $3\cdot 10^{11}$ | $62.5$ |
Guo et al., 2021 (Guo et al., 2021a) |  GAN | $\text{RY}_{(17M)}$ | $-$ | $\text{RY}_{(4.3M)}$ | $100M$ | $0.932$ |
|  | $\text{CS}_{(3.6M)}$ | $\text{CS}_{(900K)}$ | $100M$ | $0.256$ |
Cheng et al., 2021 (Cheng et al., 2021) |  WordPCFG | $\text{RY}_{(50\%)}$ | D, K, L | $\text{RY}_{(50\%)}$ | $1B$ | $0.726$ |
|  | $\text{WH}_{(50\%)}$ | $\text{WH}_{(50\%)}$ | $1B$ | $0.351$ |
|  | $\text{CL}_{(50\%)}$ | $\text{CL}_{(50\%)}$ | $1B$ | $0.518$ |
|  | $\text{CS}_{(50\%)}$ | $\text{CS}_{(50\%)}$ | $1B$ | $0.523$ |
|  | $\text{DO}_{(50\%)}$ | $\text{DO}_{(50\%)}$ | $1B$ | $0.586$ |
|  | $\text{DW}_{(50\%)}$ | $\text{DW}_{(50\%)}$ | $1B$ | $0.632$ |
Zhou et al., 2022 (Zhou et al., 2022) |  GAN | $\text{RY}_{(4.8M)}$ | $-$ | $\text{RY}_{(1.2M)}$ | $1B$ | $0.248$ |
|  | $\text{RY}_{(4.8M)}$ | $\text{LI}_{(2.56M)}$ | $1B$ | $0.162$ |
(†)Other data: ‘D’- dictionary; ‘K’- keyboard; ‘U’- user information; ‘L’-
language property; ‘R’- password policy.
(§)Dataset: ‘AN’- Animoto; ‘CL’- Clixsense; ‘CS’- CSDN; ‘DO’- Dodonew; ‘DU’-
Duduniu; ‘DW’- Duowan; ‘FB’- Facebook;
‘FN’- Finnish; ‘JD’- JingDong; ‘LI’- LinkedIn; ‘MH’- MyHeritage; ‘MS’-
MySpace; ‘NE’- Netease; ‘OT’- 12306; ‘OY’- ONYEN;
‘PB’- PhbBB; ‘RY’- Rockyou; ‘SW’- SilentWhisper; ‘WH’- 000webhost; ‘YK’-
Youku; ‘ZK’- Zooks; ‘ZO’- Zomato.
AB means entire dataset abbreviated by “AB”, e.g., RY means entire Rockyou
dataset.
$\text{AB}_{(p\%)}$ means $p\%$ of dataset abbreviated by “AB”, e.g.,
$\text{RY}_{(50\%)}$ means $50\%$ of Rockyou dataset.
$\text{AB}_{(N)}$ means $N$ passwords in dataset abbreviated by “AB”, e.g.,
$\text{RY}_{(5M)}$ means $5$ million passwords of Rockyou dataset.

##  4\. Future Research

With the emergence of machine learning and artificial intelligence techniques,
the arts of password guessing have significantly improved and achieved a
higher level compared to the beginning state, thanks to prior research
efforts. There are several limitations and unsolved works for future research:

  * •

(i) Improving Guessing Performance: Overall, the guessing performance of
current solutions highly relied on the training dataset, information source,
and user configuration. Such solutions require expertise with a solid
background to operate. A fully automatic setting is overwhelmed by a real
attacker. Moreover, the guessing techniques used by the attackers continuously
evolve and get smarter over time. Thus, there is always a need to improve the
guessing performance, especially for automatic launching.

  * •

(ii) Targeted Guessing and Metering: Most existing studies focused on offline
password guessing, and only a few online guessing models were proposed in the
literature. However, in practice, offline password guessing only poses
security concerns in limited scenarios (e.g., password database is leaked)
which mainly comes from the misconfiguration of the security administrator
(Florêncio et al., 2014). The online/targeted attack can threaten any public
services or personal devices which are protected by weak passwords. Similarly,
most current password strength meters employ trawling password guessing to
evaluate the strength of an input password. It means each password is decided
with a fixed strength regardless of who is going to use it. However, it is
easy to see that, a weak password of a user (e.g., having personal information
of this user) could be a strong password for some others. Thus, it is
inappropriate to apply the same strength values for all users, and we need
personalized password strength meter.

  * •

(iii) Benchmark Datasets: Most existing password guessing models were
evaluated using the leaked password datasets available on the Internet or
private datasets that could not be shared for public research. There is no
official organization that maintains standard datasets for research purposes.
This raises several obstacles which restrain the research activities. First,
the time used for collecting and preprocessing datasets is increased. Second,
as these datasets are not maintained by any official organization, the
reliability of new research can not be guaranteed. However, unlike other
fields, it is challenging to collect and maintain such datasets, mainly caused
by the extreme sensitivity of passwords. Some mechanisms need to be designed
to ensure that the passwords and other information contained in the dataset
only can be used for ethical research.

  * •

(iv) Measuring the Security Impacts of Password Strength Meter and Password
Advisor: It has been shown that users are influenced by the password strength
meter/password advisor (Proctor et al., 2002; Egelman et al., 2013; Ur et al.,
2012). This raises a question: “is it possible for the attacker to infer or
narrow down the guessing space by studying the employed PSM/PA model?”.
Specifically, under a PSM, the user will not be able to use some passwords
that are considered weak. Thus, it is straightforward that attackers will not
try with such passwords. For the password advisor, it would be a security
problem if the model generates advice that always suggests user some
identifiable or repeated password patterns. The attacker could generate high-
hitting-chance guesses when trying with the passwords suggested by the
advisors. Existing studies have exploited password policy to narrow down the
guessing space in targeted password attacks (Wang et al., 2016b). However, it
is still an open question regarding the use of PSM/PA for password guessing.

  * •

(v) Password Strength Meter/Password Advisor Based on the Strategy of
Attacker: It is not a new approach that a defensive team try to learn the
attacker’s strategies and establish appropriate counters. However, in password
security, most PA/PSM enhances the password strength by exploiting the
weaknesses in the password composing behavior of the user. We suggest a new
direction to construct PA/PSM that learns the strategies used by the real
attackers, and recommends the user use passwords that are beyond the
expectation of the attacker. We believe that this approach is promising to
improve password strength against guessing attacks. In addition, it should
have a mechanism to protect the behavior of the PA/PSM, so that the attacker
could not learn and adapt to his strategy.

  * •

(vi) Metric to Evaluate the Performance of PSM/PA: Different PSM/PA approaches
have been proposed in the literature and deployed in practice (e.g.,
heuristics (Wheeler, 2016; Burr et al., 2018), PCFG (Houshmand and Aggarwal,
2012), neural network (Melicher et al., 2017; Ur et al., 2017)). It has been
shown that such PSMs/PAs have a significant impact on the password selection
of users (Ur et al., 2012; Egelman et al., 2013; Tan et al., 2020). However,
most existing PSM/PA studies focused on proposing metrics and methods to
measure the strength of passwords, it is still an open problem regarding how
to measure the accuracy of a PSM/PA (Golla and Dürmuth, 2018). The current
state-of-the-art PSMs score passwords inconsistently (Golla and Dürmuth, 2018;
Pereira et al., 2020). Most existing studies evaluated their methods by
heuristic rules designed by common sense and experts’ knowledge with some
representative examples. We are lacking a sound metric to determine the
accuracy of a PSM. Thus, it is also unable to compare different PSMs/PAs and
find a suitable model for a specific application. It is crucial to establish
standard methods and metrics to verify the performance of a PSM/PA. This
allows overall comparison to determine a suitable PSM/PS for a specific
purpose. Moreover, it also enables validating the performance of a new
proposed PSM.

##  5\. Conclusion

With the explosion of modern technology, smart devices (e.g., laptop, smart
phone, smart watch) become so popular and common with everyone nowadays. These
devices usually contain a wide range of user information and mostly are
connected with sensitive personal online accounts (e.g., Internet banking,
online shopping, email). So, designing mechanisms to ensure that unauthorized
users could not access such information/services is more critical than ever.
Despite the emergence of other non-password authentication approaches,
password is still a widely used authentication method. In order to encourage
and support users to select strong passwords, many password security solutions
have been proposed in the literature. Among them, simulating password guessing
attacks plays a crucial role in designing such solutions. To summarize the
achievement of existing password guessing methods, we surveyed all password
guessing studies published in the literature from 1979 to 2022. From the
survey, we draw several conclusions:

  * •

A large number of techniques have been adopted for password guessing ranging
from heuristic to machine learning and deep learning. They were designed to
output candidate passwords ordered by the likelihood of being chosen by the
user by modeling the user behavior in password selection.

  * •

Constructing a robust password guessing model involves not only designing a
password generating algorithm that can closely simulate the attacker’s
strategies, but also collecting and aggregating a large number of unstructured
data (e.g., leaked passwords, user information, native language property,
keyboard patterns).

  * •

As passwords are extremely sensitive, it is unable to construct a password
dataset from volunteers. Thus, the real password datasets that have been
leaked by some attacks were widely used to evaluate the performance of
password guessing models.

  * •

Passwords are still at a high risk of guessing attacks. To further improve the
password strength against guessing attacks, we suggested several open research
directions (see Section 4).

##  6\. Acknowledgments

This work was supported in part by the Institute of Information &
Communications Technology Planning & Evaluation (IITP) grant by the Korean
Government, Ministry of Science and ICT (MSIT) under Grant 2020-0-00126.

## References

  * (1)
  * Alsaleh et al. (2011) Mansour Alsaleh, Mohammad Mannan, and Paul C Van Oorschot. 2011\.  Revisiting defenses against large-scale online password guessing attacks.  _IEEE Transactions on dependable and secure computing_ 9, 1 (2011), 128–141.
  * Aumasson (2017) Jean-Philippe Aumasson. 2017\.  _Serious cryptography: a practical introduction to modern encryption_.  No Starch Press.
  * Bergadano et al. (1998) Francesco Bergadano, Bruno Crispo, and Giancarlo Ruffo. 1998\.  High dictionary compression for proactive password checking.  _ACM Transactions on Information and System Security (TISSEC)_ 1, 1 (1998), 3–25.
  * Biesner et al. (2021) David Biesner, Kostadin Cvejoski, Bogdan Georgiev, Rafet Sifa, and Erik Krupicka. 2021.  Advances in Password Recovery Using Generative Deep Learning Techniques. In _International Conference on Artificial Neural Networks_. Springer, 15–27.
  * Bishop (1990) Matt Bishop. 1990\.  _A proactive password checker_.  National Aeronautics and Space Administration.
  * Bonneau et al. (2015) Joseph Bonneau, Cormac Herley, Paul C Van Oorschot, and Frank Stajano. 2015.  Passwords and the evolution of imperfect authentication.  _Commun. ACM_ 58, 7 (2015), 78–87.
  * Bonneau et al. (2012) Joseph Bonneau, Sören Preibusch, and Ross Anderson. 2012\.  A birthday present every eleven wallets? the security of customer-chosen banking pins. In _International Conference on Financial Cryptography and Data Security_. Springer, 25–40.
  * Bonneau and Shutova (2012) Joseph Bonneau and Ekaterina Shutova. 2012.  Linguistic properties of multi-word passphrases. In _International Conference on Financial Cryptography and Data Security_. Springer, 1–12.
  * Boztas (1999) S Boztas. 1999.  Entropies, guessing, and cryptography.  _Department of Mathematics, Royal Melbourne Institute of Technology, Tech. Rep_ 6 (1999), 2–3.
  * Bryant et al. (2006) Kay Bryant, John Campbell, et al. 2006\.  User behaviours associated with password security and management.  _Australasian Journal of Information Systems_ 14, 1 (2006).
  * Burr et al. (2018) William E Burr, Donna F Dodson, and W Timothy Polk. 2018\.  Electronic Authentication Guideline: NIST SP 800-63 Ver. 1.0 (2004) to 800-63-2 (2013).
  * Campbell et al. (2011) John Campbell, Wanli Ma, and Dale Kleeman. 2011.  Impact of restrictive composition policy on user password choices.  _Behaviour & Information Technology_ 30, 3 (2011), 379–388.
  * Carnavalet and Mannan (2015) Xavier De Carné De Carnavalet and Mohammad Mannan. 2015.  A large-scale evaluation of high-impact password strength meters.  _ACM Transactions on Information and System Security (TISSEC)_ 18, 1 (2015), 1–32.
  * Castelluccia et al. (2012) Claude Castelluccia, Markus Dürmuth, and Daniele Perito. 2012.  Adaptive password-strength meters from markov models.. In _NDSS_.
  * Cheng et al. (2021) Haibo Cheng, Wenting Li, Ping Wang, and Kaitai Liang. 2021\.  Improved Probabilistic Context-Free Grammars for Passwords Using Word Extraction. In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2690–2694.
  * Chou et al. (2012) Hsien-Cheng Chou, Hung-Chang Lee, Chih-Wen Hsueh, and Fei-Pei Lai. 2012.  Password cracking based on special keyboard patterns.  _International Journal of Innovative Computing, Information and Control_ 8, 1 (2012), 387–402.
  * Chou et al. (2013) Hsien-Cheng Chou, Hung-Chang Lee, Hwan-Jeu Yu, Fei-Pei Lai, Kuo-Hsuan Huang, Chih-Wen Hsueh, et al. 2013\.  Password cracking based on learned patterns from disclosed passwords.  _IJICIC_ 9, 2 (2013), 821–839.
  * Clair et al. (2006) Luke St Clair, Lisa Johansen, William Enck, Matthew Pirretti, Patrick Traynor, Patrick McDaniel, and Trent Jaeger. 2006\.  Password exhaustion: Predicting the end of password usefulness. In _International Conference on Information Systems Security_. Springer, 37–55.
  * Das et al. (2014) Anupam Das, Joseph Bonneau, Matthew Caesar, Nikita Borisov, and XiaoFeng Wang. 2014.  The tangled web of password reuse.. In _NDSS_ , Vol. 14. 23–26.
  * de Carné de Carnavalet and Mannan (2014) Xavier de Carné de Carnavalet and Mohammad Mannan. 2014.  From very weak to very strong: Analyzing password-strength meters. In _Network and Distributed System Security Symposium (NDSS 2014)_. Internet Society.
  * Dell’Amico and Filippone (2015) Matteo Dell’Amico and Maurizio Filippone. 2015.  Monte Carlo strength evaluation: Fast and reliable password checking. In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_. 158–169.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Dürmuth et al. (2015) Markus Dürmuth, Fabian Angelstorf, Claude Castelluccia, Daniele Perito, and Abdelberi Chaabane. 2015\.  OMEN: Faster password guessing using an ordered markov enumerator. In _International symposium on engineering secure software and systems_. Springer, 119–132.
  * Egelman et al. (2013) Serge Egelman, Andreas Sotirakopoulos, Ildar Muslukhov, Konstantin Beznosov, and Cormac Herley. 2013.  Does my password go up to eleven? The impact of password meters on password selection. In _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems_. 2379–2388.
  * Fang et al. (2018) Yong Fang, Kai Liu, Fan Jing, and Zheng Zuo. 2018\.  Password guessing based on semantic analysis and neural networks. In _Chinese Conference on Trusted Computing and Information Security_. Springer, 84–98.
  * Fine et al. (1998) Shai Fine, Yoram Singer, and Naftali Tishby. 1998.  The hierarchical hidden Markov model: Analysis and applications.  _Machine learning_ 32, 1 (1998), 41–62.
  * Florencio and Herley (2007) Dinei Florencio and Cormac Herley. 2007.  A large-scale study of web password habits. In _Proceedings of the 16th international conference on World Wide Web_. 657–666.
  * Florêncio et al. (2014) Dinei Florêncio, Cormac Herley, and Paul C Van Oorschot. 2014.  An $\\{$Administrator’s$\\}$ Guide to Internet Password Research. In _28th large installation system administration conference (LISA14)_. 44–61.
  * Gaw and Felten (2006) Shirley Gaw and Edward W Felten. 2006.  Password management strategies for online accounts. In _Proceedings of the second symposium on Usable privacy and security_. 44–55.
  * Golla et al. (2016) Maximilian Golla, Benedict Beuscher, and Markus Dürmuth. 2016\.  On the security of cracking-resistant password vaults. In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_. 1230–1241.