# Modified Password Guessing Methods Based on TarGuess-I

Authors: Zhijie Xie; Min Zhang; Yuqi Guo; Zhenhan Li; Hongjun Wang
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

TarGuess−I is a leading online targeted password guessing model using users’ personally identifiable information (PII) proposed at ACM CCS 2016 by Wang et al. It has attracted widespread attention in password security owing to its superior guessing performance. Yet, after analyzing the users’ vulnerable behaviors of using popular passwords and constructing passwords with users’ PII, we find that this model does not take into account popular passwords, keyboard patterns, and the special strings. The special strings are the strings related to users but do not appear in the users’ demographic information. Thus, we propose TarGuess−I+KPX, a modified password guessing model with three semantic methods, including (1) identifying popular passwords by generating top-300 lists from similar websites, (2) recognizing keyboard patterns by relative position, and (3) catching the special strings by extracting continuous characters from user-generated PII. We conduct a series of evaluations on six large-scale real-world leaked password datasets. The experimental results show that our modified model outperforms TarGuess−I by 2.62% within 100 guesses.


---

## Body

## 1. Introduction

Password-based authentication is still an essential method in cybersecurity [1]. To understand password security, people have gone through several stages, from some heuristic methods that lack theoretical foundations to those algorithms that conform to strict probability models [2]. Since the emergence of Markov-based [3, 4] and probabilistic context-free grammar- (PCFG-) based [5, 6] password guessing algorithms, trawling password guessing has been intensively studied [7–10]. Recently, several large-scale personal information database leakage events have caused widespread concern in the security community [11–14]. With the development of related researches, the targeted password guessing algorithms using users’ personally identifiable information (PII) have emerged [15–17].Das et al. [15] studied the threat posed by password reuse and proposed a cross-site cracking algorithm for the first time. However, without considering common popular passwords, this algorithm is not optimal. Li et al. [16] studied to what extent a user’s PII would affect password security and proposed a semantics-rich model, Personal-PCFG, which adopted with length-based PII matching and substitution. But it could not accurately capture the usage of users’ PII, thus greatly hindering the cracking efficiency. As a seminal work of password guessing, Wang et al. [17] put forward a framework, TarGuess, which systematically characterizes typical targeted guessing scenarios. It contains a type-based PII semantics-aware PCFG and recognitions of password reuse behaviors, both of which significantly outperform the former cracking algorithms. Their work has motivated successive new studies on password security [18–20] and even led the revision of the NIST SP800-63-3 [21, 22].TarGuess framework is proposed after an in-depth analysis of users’ vulnerable behaviors. The framework includes four password guessing models,TarGuess−I∼IV, for four attacking scenarios #1∼#4. TarGuess−I caters for scenario #1, where the attacker is equipped with the users’ explicit PII, such as name, birthday, and phone number. The users’ explicit PII can be easily obtained from the Internet [23] and can be the building blocks of passwords [17]. The rest three models required user information such as PII attributes that play an implicit role in passwords (e.g., gender and profession) and/or sister passwords that were leaked from the user’s other accounts. This work mainly focuses on scenario #1. As more users’ PII is being leaked these days, attacking scenario #1 becomes more practical.Wang et al. [17] showed that their TarGuess−I model is more efficient than previous algorithms using users’ PII to crack passwords, which can gain success rates over 20% with just 100 guesses. Whether it can continue to improve the success rate of guessing models has become a peer research hotspot [24]. After analyzing the users’ vulnerable behaviors in constructing passwords based on TarGuess−I, we find that there are some missing attributes in TarGuess−I. Therefore, based on TarGuess−I, we put forward three modified methods and conduct a series of experiments to examine their feasibility. In the end, we proposed a modified model: TarGuess−I+KPX, which includes our three improvements. Extensive evaluations have shown that, TarGuess−I+KPX outperforms its original model by 2.62% within 100 guesses.


### 1.1. Our Triple Contributions

This article is an extended version of the paper [25]. In this work, we make the following key contributions.


#### 1.1.1. A Modified Password Guessing Model

After analyses of the users’ vulnerable behaviors in constructing passwords on a total of 163,041,192 public leaked data based onTarGuess−I, we find that some effective semantic tags have not been testified and employed in TarGuess−I. To fill the gap, we make use of the adaptiveness of TarGuess−I PII tags and define three new tags: the popular password tag P, the keyboard pattern tag K, and the special string tag X. This gives rise to a variant of TarGuess-I, we call it TarGuess−I+KPX.


#### 1.1.2. An Extensive Evaluation

To demonstrate the feasibility of these incremental tags, we perform a series of experiments on six large-scale real-world leaked datasets. The experimental results show that our single-tag-modified models (TarGuess−I with each tag we defined individually) outperform TarGuess−I by 0.75% in optimal and 0.33% on average within 100 guesses. Particularly, our modified model TarGuess−I+KPX works best among the 10 models we experimented with. It can successfully crack a target user’s password with an optimal chance of 20.9% within 100 guesses when it gets the same users’ PII as TarGuess−I gets, which outperforms TarGuess−I by 2.62% (the target user is come from the four sites, see Table 1).Table 1
Statistics of the experimental result ofTarGuess−I+KPX model.
Training setTesting setGuess numberRn1010010310410∼100100∼103103∼104Avg12306Aipai0.0780.1530.2140.270-0.65%0.92%2.91%1.41%Dodon0.1250.2090.2700.3322.62%6.06%3.99%4.51%Senda0.1090.1950.2590.3200.72%4.25%2.11%2.68%Tinya0.1300.1980.2480.3161.52%3.47%1.90%2.46%YoukuAipai0.0750.1490.2110.259-0.75%0.47%3.39%1.42%Dodon0.1260.2060.2690.3212.16%5.73%4.56%4.54%Senda0.1070.1910.2560.3070.00%3.61%2.07%2.28%Tinya0.1300.1950.2410.3000.85%2.80%1.87%2.04%


#### 1.1.3. A New Insight

We propose a new method to modify the password guessing model: parsing the passwords into the special stringsX tag, such as anniversary dates or someone’s name, that do not appear in users’ demographic PII. It can be identified by adding incremental information to the model or refining the model recognitions of user-generated PII (such as e-mail addresses and user names). This method gives a new insight into targeted password guessing.


## 1.1. Our Triple Contributions

This article is an extended version of the paper [25]. In this work, we make the following key contributions.


### 1.1.1. A Modified Password Guessing Model

After analyses of the users’ vulnerable behaviors in constructing passwords on a total of 163,041,192 public leaked data based onTarGuess−I, we find that some effective semantic tags have not been testified and employed in TarGuess−I. To fill the gap, we make use of the adaptiveness of TarGuess−I PII tags and define three new tags: the popular password tag P, the keyboard pattern tag K, and the special string tag X. This gives rise to a variant of TarGuess-I, we call it TarGuess−I+KPX.


### 1.1.2. An Extensive Evaluation

To demonstrate the feasibility of these incremental tags, we perform a series of experiments on six large-scale real-world leaked datasets. The experimental results show that our single-tag-modified models (TarGuess−I with each tag we defined individually) outperform TarGuess−I by 0.75% in optimal and 0.33% on average within 100 guesses. Particularly, our modified model TarGuess−I+KPX works best among the 10 models we experimented with. It can successfully crack a target user’s password with an optimal chance of 20.9% within 100 guesses when it gets the same users’ PII as TarGuess−I gets, which outperforms TarGuess−I by 2.62% (the target user is come from the four sites, see Table 1).Table 1
Statistics of the experimental result ofTarGuess−I+KPX model.
Training setTesting setGuess numberRn1010010310410∼100100∼103103∼104Avg12306Aipai0.0780.1530.2140.270-0.65%0.92%2.91%1.41%Dodon0.1250.2090.2700.3322.62%6.06%3.99%4.51%Senda0.1090.1950.2590.3200.72%4.25%2.11%2.68%Tinya0.1300.1980.2480.3161.52%3.47%1.90%2.46%YoukuAipai0.0750.1490.2110.259-0.75%0.47%3.39%1.42%Dodon0.1260.2060.2690.3212.16%5.73%4.56%4.54%Senda0.1070.1910.2560.3070.00%3.61%2.07%2.28%Tinya0.1300.1950.2410.3000.85%2.80%1.87%2.04%


### 1.1.3. A New Insight

We propose a new method to modify the password guessing model: parsing the passwords into the special stringsX tag, such as anniversary dates or someone’s name, that do not appear in users’ demographic PII. It can be identified by adding incremental information to the model or refining the model recognitions of user-generated PII (such as e-mail addresses and user names). This method gives a new insight into targeted password guessing.


## 1.1.1. A Modified Password Guessing Model

After analyses of the users’ vulnerable behaviors in constructing passwords on a total of 163,041,192 public leaked data based onTarGuess−I, we find that some effective semantic tags have not been testified and employed in TarGuess−I. To fill the gap, we make use of the adaptiveness of TarGuess−I PII tags and define three new tags: the popular password tag P, the keyboard pattern tag K, and the special string tag X. This gives rise to a variant of TarGuess-I, we call it TarGuess−I+KPX.


## 1.1.2. An Extensive Evaluation

To demonstrate the feasibility of these incremental tags, we perform a series of experiments on six large-scale real-world leaked datasets. The experimental results show that our single-tag-modified models (TarGuess−I with each tag we defined individually) outperform TarGuess−I by 0.75% in optimal and 0.33% on average within 100 guesses. Particularly, our modified model TarGuess−I+KPX works best among the 10 models we experimented with. It can successfully crack a target user’s password with an optimal chance of 20.9% within 100 guesses when it gets the same users’ PII as TarGuess−I gets, which outperforms TarGuess−I by 2.62% (the target user is come from the four sites, see Table 1).Table 1
Statistics of the experimental result ofTarGuess−I+KPX model.
Training setTesting setGuess numberRn1010010310410∼100100∼103103∼104Avg12306Aipai0.0780.1530.2140.270-0.65%0.92%2.91%1.41%Dodon0.1250.2090.2700.3322.62%6.06%3.99%4.51%Senda0.1090.1950.2590.3200.72%4.25%2.11%2.68%Tinya0.1300.1980.2480.3161.52%3.47%1.90%2.46%YoukuAipai0.0750.1490.2110.259-0.75%0.47%3.39%1.42%Dodon0.1260.2060.2690.3212.16%5.73%4.56%4.54%Senda0.1070.1910.2560.3070.00%3.61%2.07%2.28%Tinya0.1300.1950.2410.3000.85%2.80%1.87%2.04%


## 1.1.3. A New Insight

We propose a new method to modify the password guessing model: parsing the passwords into the special stringsX tag, such as anniversary dates or someone’s name, that do not appear in users’ demographic PII. It can be identified by adding incremental information to the model or refining the model recognitions of user-generated PII (such as e-mail addresses and user names). This method gives a new insight into targeted password guessing.


## 2. Preliminaries

TarGuess−I is a targeted guessing model using users’ PII and builds on the PCFG-based algorithm. This section explicates what kinds of users’ vulnerable behaviors are considered in this work and gives a brief introduction to the PCFG-based algorithm and TarGuess−I.


### 2.1. Explication of Users’ Vulnerable Behaviors

Users’ vulnerable behaviors are the key influence factor of password crackability [26]. A series of related studies have been conducted since the pioneering work of Morris and Thompson in 1979 [27]. Part of the studies based on data analyses, such as [3, 12, 14, 28–31], the others based on user surveys, such as [15, 32–35]. In summary, the discovered users’ vulnerable behaviors can be classified into the following three categories.


#### 2.1.1. Popular Passwords

A large number of studies (such as [3, 14, 30]) have shown that users often choose simple words as passwords or make simple transformed strings to meet the requirements of the website password setting strategy, such as “123456a” meets the “alphanumeric” strategy. These strings, which are frequently used by users, called popular passwords. Furthermore, Wang et al. [36] have found that the Zipf distribution is the main cause of the aggregation of popular passwords.


#### 2.1.2. Password Reuse

After a series of interviews to investigate how users cope with keeping track of many accounts and passwords, Stobert and Biddle [32] point out that users have more than 20 accounts on average. It is fairly impossible for them to create a unique password for each account, so reusing passwords is a rational approach. At the same time, password reuse is a vulnerable behavior; the key is how to reuse.


#### 2.1.3. Passwords Containing Personal Information

Wang et al. [37] note that Chinese users tend to construct passwords with their pinyin name and relevant digits, such as phone number and birthdate, which are quite different from English users. They revealed a new insight into what extent users’ native languages influence their passwords and what extent users’ personal information plays a role in their passwords.Considering thatTarGuess−I caters for scenario #1, we only analyze the two categories of users’ vulnerable behaviors (i.e., popular passwords and password containing personal information).


### 2.2. PCFG-Based Password Guessing Algorithm

Weir et al.’s PCFG-based algorithm [5] has shown a great success in dealing with trawling guessing scenarios [17]. The context-free grammar in [5] is defined as G=V,Σ,S,R, where
(i)
V is a finite set of variables(ii)
Σ is a finite set disjoint from V and contains all the terminals of G(iii)
S is the start symbol and S∈V(iv)
R is a finite set of productions of the form: α⟶β, where α&β∈V∪ΣThe core assumption of the algorithm is the segments of letters, numbers, and symbols in a password which are independent with each other. Thus, inV set, except for S start symbol, there are only Ln letters, Dn digits, and Sn symbols tag sets, where n represents the segment length, such as L3 represents three-letter segments, and D4 represents four-digit segments.There are two phases in the algorithm, the training phase and the guess generation phase, as shown in Figure1. In the training phase, the password is parsed into the LDS segments based on the length and type to generate the password base structure (the start symbol S). Then, it counts the segment frequency table in each tag set and outputs the context-free grammar G. In the guess generation phase, passwords are derived by the grammar G and the segment frequency tables. The final guess candidates are arranged based on the probability multiplied by all the frequency of segments in the password.Figure 1
An illustration of PCFG-based algorithm.


### 2.3. TarGuess-I Model

TarGuess−I is a semantics-aware PCFG model built by the type-based PII tags, which are firstly proposed by Wang et al. Besides the three basic tags LDS in the PCFG-based algorithm, the grammar GI in TarGuess−I includes six PII tags (such as Nn name, Un user name, Bn birthday, Tn phone number, In id card, and En e-mail address). For each PII tag, its index number n is different from the LDS tags, which represents the type of generation rule for this PII. For example, N stands for name usage, while N1 stands for the full name, and N2 stands for the abbreviation of the full name (such as “Zhang San” abbreviated as “zs”). See Figure 2 for a specific description. The grammar GI is highly adaptive. It can be modified simply by adding incremental tags without changing the whole structure to confirm the function, which brings great convenience to our research.Figure 2
An illustration of TarGuess-I’s PII tags generation.As shown in Figure3, for each user, the segment frequency table of each PII tag is generated through the user’s PII. In the training phase, the password is firstly parsed with the PII segments into PII tags, and the rest of the segments are parsed into LDS tags. The guessing phase is similar to the PCFG-based algorithm, but a part of products are intermediate candidates consisting of PII tags (e.g., N3B5 and N31234). These intermediate candidates will be matched by the segments from users’ PII before be added to the final guess candidates.Figure 3
An illustration of TarGuess-I.


## 2.1. Explication of Users’ Vulnerable Behaviors

Users’ vulnerable behaviors are the key influence factor of password crackability [26]. A series of related studies have been conducted since the pioneering work of Morris and Thompson in 1979 [27]. Part of the studies based on data analyses, such as [3, 12, 14, 28–31], the others based on user surveys, such as [15, 32–35]. In summary, the discovered users’ vulnerable behaviors can be classified into the following three categories.


### 2.1.1. Popular Passwords

A large number of studies (such as [3, 14, 30]) have shown that users often choose simple words as passwords or make simple transformed strings to meet the requirements of the website password setting strategy, such as “123456a” meets the “alphanumeric” strategy. These strings, which are frequently used by users, called popular passwords. Furthermore, Wang et al. [36] have found that the Zipf distribution is the main cause of the aggregation of popular passwords.


### 2.1.2. Password Reuse

After a series of interviews to investigate how users cope with keeping track of many accounts and passwords, Stobert and Biddle [32] point out that users have more than 20 accounts on average. It is fairly impossible for them to create a unique password for each account, so reusing passwords is a rational approach. At the same time, password reuse is a vulnerable behavior; the key is how to reuse.


### 2.1.3. Passwords Containing Personal Information

Wang et al. [37] note that Chinese users tend to construct passwords with their pinyin name and relevant digits, such as phone number and birthdate, which are quite different from English users. They revealed a new insight into what extent users’ native languages influence their passwords and what extent users’ personal information plays a role in their passwords.Considering thatTarGuess−I caters for scenario #1, we only analyze the two categories of users’ vulnerable behaviors (i.e., popular passwords and password containing personal information).


## 2.1.1. Popular Passwords

A large number of studies (such as [3, 14, 30]) have shown that users often choose simple words as passwords or make simple transformed strings to meet the requirements of the website password setting strategy, such as “123456a” meets the “alphanumeric” strategy. These strings, which are frequently used by users, called popular passwords. Furthermore, Wang et al. [36] have found that the Zipf distribution is the main cause of the aggregation of popular passwords.


## 2.1.2. Password Reuse

After a series of interviews to investigate how users cope with keeping track of many accounts and passwords, Stobert and Biddle [32] point out that users have more than 20 accounts on average. It is fairly impossible for them to create a unique password for each account, so reusing passwords is a rational approach. At the same time, password reuse is a vulnerable behavior; the key is how to reuse.


## 2.1.3. Passwords Containing Personal Information

Wang et al. [37] note that Chinese users tend to construct passwords with their pinyin name and relevant digits, such as phone number and birthdate, which are quite different from English users. They revealed a new insight into what extent users’ native languages influence their passwords and what extent users’ personal information plays a role in their passwords.Considering thatTarGuess−I caters for scenario #1, we only analyze the two categories of users’ vulnerable behaviors (i.e., popular passwords and password containing personal information).


## 2.2. PCFG-Based Password Guessing Algorithm

Weir et al.’s PCFG-based algorithm [5] has shown a great success in dealing with trawling guessing scenarios [17]. The context-free grammar in [5] is defined as G=V,Σ,S,R, where
(i)
V is a finite set of variables(ii)
Σ is a finite set disjoint from V and contains all the terminals of G(iii)
S is the start symbol and S∈V(iv)
R is a finite set of productions of the form: α⟶β, where α&β∈V∪ΣThe core assumption of the algorithm is the segments of letters, numbers, and symbols in a password which are independent with each other. Thus, inV set, except for S start symbol, there are only Ln letters, Dn digits, and Sn symbols tag sets, where n represents the segment length, such as L3 represents three-letter segments, and D4 represents four-digit segments.There are two phases in the algorithm, the training phase and the guess generation phase, as shown in Figure1. In the training phase, the password is parsed into the LDS segments based on the length and type to generate the password base structure (the start symbol S). Then, it counts the segment frequency table in each tag set and outputs the context-free grammar G. In the guess generation phase, passwords are derived by the grammar G and the segment frequency tables. The final guess candidates are arranged based on the probability multiplied by all the frequency of segments in the password.Figure 1
An illustration of PCFG-based algorithm.


## 2.3. TarGuess-I Model

TarGuess−I is a semantics-aware PCFG model built by the type-based PII tags, which are firstly proposed by Wang et al. Besides the three basic tags LDS in the PCFG-based algorithm, the grammar GI in TarGuess−I includes six PII tags (such as Nn name, Un user name, Bn birthday, Tn phone number, In id card, and En e-mail address). For each PII tag, its index number n is different from the LDS tags, which represents the type of generation rule for this PII. For example, N stands for name usage, while N1 stands for the full name, and N2 stands for the abbreviation of the full name (such as “Zhang San” abbreviated as “zs”). See Figure 2 for a specific description. The grammar GI is highly adaptive. It can be modified simply by adding incremental tags without changing the whole structure to confirm the function, which brings great convenience to our research.Figure 2
An illustration of TarGuess-I’s PII tags generation.As shown in Figure3, for each user, the segment frequency table of each PII tag is generated through the user’s PII. In the training phase, the password is firstly parsed with the PII segments into PII tags, and the rest of the segments are parsed into LDS tags. The guessing phase is similar to the PCFG-based algorithm, but a part of products are intermediate candidates consisting of PII tags (e.g., N3B5 and N31234). These intermediate candidates will be matched by the segments from users’ PII before be added to the final guess candidates.Figure 3
An illustration of TarGuess-I.


## 3. Users’ Vulnerable Behaviors in Constructing Passwords

In this section, we analyze the users’ vulnerable behaviors based on real-world leaked data for inspiration to improveTarGuess−I. Because of the lack of studies on how Chinese users select passwords, we only focus on Chinese users. We dissect 163,041,192 leaked user passwords from the six websites (see Table 2) for analyzing. Hereinafter, the bold shorthand notation in the brackets of Table 2 represents the source of each dataset. The datasets were hacked by attackers or leaked by insiders and disclosed publicly on the Internet, and some of them have been used in the former research (as shown in Table 2). Due to the lack of datasets containing users’ PII, we choose the unique PII (e.g., e-mail address) in 12306 datasets to match passwords in other datasets. The sizes of matched datasets with PII from each dataset are shown in Table 2.Table 2
Basic information about our datasets.
Dataset∗Web serviceWhen leakedTotalWith PIIContentBe usedTianya (Tinya)Social forum201131,006,59028,158User name, PW, E-mail[12, 14, 38, 39]Dodonew (Dodon)E-commerce201116,258,89121,854User name, PW, E-mail[12, 14, 17, 39]Shengda (Senda)Game201115,313,33438,203User name, PW, E-mailNone12306 (12306)Train ticketing2014232,884232,884PW, E-mail, PII[16, 17]Aipai (Aipai)Video blogs20167,682,23227,917User name, PW, E-mailNoneYouku (youku)Audio visual201692,547,261134,863PW, E-mailNone∗Hereinafter, each data source is referred as the bold shorthand notations in the brackets.


### 3.1. Analysis of Popular Passwords

According to the occurrence frequency, the top-10 popular passwords in six filtered databases with the proportion of them are calculated, and the results are shown in Table3. It shows that 0.51% to 3.40% of users’ passwords can be cracked successfully by just using the top-10 popular passwords. Chinese users prefer simple combinations of numbers (such as “123456,” “111111,” “000000”) and the strings with the meaning of love (such as “5201314” and “woaini1314”). There are also some unique passwords in the top-10 list (such as “aptx4869” in Aipai and “7758521” in Youku). These passwords may come from the site’s name or culture or maybe come from a large number of “ghost accounts” held by a particular user of the website. Besides, the passwords constructed with the QWERTY keyboard pattern (such as “1q2w3e4r” and “1qaz2wsx”) also account for a certain proportion in the popular passwords.Table 3
Ranking and proportion of top-10 popular passwords.
RankAipaiTinyaSendaDodonYouku1230611q2w3e4r12345612345612345612345612345625201314111111111111111111a123456a12345631qaz2wsx0000005201314123456789111111123456a4qq1234561234567891234567895201314123456789woaini1314513145205201314123123123123520131452013146aptx48691231231q2w3e4ra123456123456a11111171q2w3e4r5t1qaz2wsx000000woaini1314123123qq1234568123456789a7758521a1234561314520123456789a1qaz2wsx9a1234567891314520qq123456123456a0000001q2w3e4r10abc123456666666woaini1314qq123456woaini1314123qwe%0.51%3.40%2.00%1.96%2.33%1.17%The statistical results of the component form of the top-104 popular passwords, which are analyzed by the PCFG-based algorithm, are shown in Table 4. It illustrates that, though the majority of popular passwords are composed of pure numbers, composite passwords (e.g., a password included multiple types of characters) also account for a considerable part, especially 45.81% in 12306 and 49.33% in Dodon.Table 4
Component form distribution of the top-104 popular passwords (Compos: composite).
FormAipaiTinyaSendaDodonYouku12306Alpha14.73%10.89%15.24%11.46%13.49%7.21%Digit59.52%63.12%66.07%39.17%65.9%46.93%Symbol0%0.05%0.02%0.01%0.08%0.05%Compos25.75%25.94%18.67%49.33%20.53%45.81%Since the grammarGI of TarGuess−I does not contain tags related to popular passwords, it could lower the success rate if the targeted users are likely to choose composite passwords. Because TarGuess−I is based on PCFG, which generates passwords according to the existing base structures generated from data and the elements in each set of tags. Thus, in the training phase, the model parses the composite password into LDS segments, and it might generate many invalid outputs at last, an illusion is shown in Figure 1. For instance, “1qaz2wsx,” a password constructed with keyboard patterns, which is the 3rd popular password in Aipai, will be parsed into D1L3D1L3 by TarGuess−I. Meanwhile, “1” ranks the first in the set of D1 tag, and “qaz” ranks the first in L3. Therefore, in the guessing phase, the first password output with the base structure D1L3D1L3 is “1qaz1qaz.” This password occupies a relatively small proportion in actual password distribution but ranks much higher in the output list, thus reducing the overall password guessing success rate. From this perspective, we come up with an idea to take popular passwords and the keyboard pattern into consideration for the training phase in TarGuess−I.By analyzing popular passwords, we find that there are two missing attributes in the grammarGI: the popular password tag P and the keyboard pattern tag K.


### 3.2. Analysis of Passwords Containing Personal Information

We adopt theTarGuess−I+PK model to analyze the datasets. TarGuess−I+PK is improved with the popular password tag P containing top-104 list and the keyboard pattern tag K. The rank of top-10 password base structures and the proportion of passwords containing PII tag or P tag are shown in Table 5. It indicates that about half of Chinese users generally construct passwords using PII or just choose popular ones. We speculate that the top-10 base structures of passwords should be related to the strings that are easy for users to remember. And we also find that some password base structures in the top-10 list are not relevant to users’ PII or containing P tag.Table 5
Top-10 base structures and proportion of the passwords containing PII andP tag.
RankAipaiTinyaSendaDodonYouku123061P1P1P1P1P1P12D7D6D7E1D6D63N2P1D7D8D7D7D74N2D7D8D6D6D8N2D65D8E1N2P1D8N2P1U16L1D7D10E1L1D7U1E17N2D6B8N2D7N2D7U3D88D6D9L1D7N2D6E1N2D79E1U3N2D6U1P1D3N2P110U1B1U3U3N2D6U3% of PII34.24%35.47%33.80%38.83%32.97%35.98%% ofP12.72%13.94%18.14%10.62%21.07%19.07%The strings which are accessible to memorize include users’ PII conversions, keyboard patterns, and popular passwords. They also include the user-created strings that have special meaning for the user but are no equal importance to other users, we call them “the special strings.” To give an example, we assume thatA user creates a string “080405” as his password, then “080405” shall be special for him. But for another user B, “080405” is nothing other than a common string; then, the probability of A’s password containing this string shall be different from B’s. Meanwhile, we cannot find the string “080405” in A’s or B’s demographic information (such as name, ID number, and telephone number). The special string cannot be extracted from the user’s demographic information but may appear in some like the prefix of e-mail addresses and user names that the user-created strings, or in user’s passwords from other servers.The parse of users’ PII inTarGuess−I also includes the user-generated strings, such as e-mail address En and user name Un. However, the analyses of these two user-generated strings are not sophisticated enough. Only three parse type (Entire E1&U1, the first letter segments E2&U2 and the first digit segments E3&U3) are proposed. The special strings for each user, as the above said, the probability distribution is different. If we use the original TarGuess−I model, because of the lack of recognition of the special string, most of these segments will be parsed into typical LDS tags, merging the user behavior characteristics, thus hinder the effectiveness of password cracking. Therefore, we consider adding the special string tag X to the grammar GI of TarGuess−I.We analyze the coverage of consecutive substrings of the e-mail address and user name in the password. The result is shown in Figure4. It reveals that a significant number of user passwords do overlap user-created strings; thus, it gives us a new hint that when an attacker obtains information about a user that is not public or very useful, they may turn that information into a special string to participate in password guessing. This idea may serve as a new direction for further research.Figure 4
Fraction of the special stringXn in the password.


## 3.1. Analysis of Popular Passwords

According to the occurrence frequency, the top-10 popular passwords in six filtered databases with the proportion of them are calculated, and the results are shown in Table3. It shows that 0.51% to 3.40% of users’ passwords can be cracked successfully by just using the top-10 popular passwords. Chinese users prefer simple combinations of numbers (such as “123456,” “111111,” “000000”) and the strings with the meaning of love (such as “5201314” and “woaini1314”). There are also some unique passwords in the top-10 list (such as “aptx4869” in Aipai and “7758521” in Youku). These passwords may come from the site’s name or culture or maybe come from a large number of “ghost accounts” held by a particular user of the website. Besides, the passwords constructed with the QWERTY keyboard pattern (such as “1q2w3e4r” and “1qaz2wsx”) also account for a certain proportion in the popular passwords.Table 3
Ranking and proportion of top-10 popular passwords.
RankAipaiTinyaSendaDodonYouku1230611q2w3e4r12345612345612345612345612345625201314111111111111111111a123456a12345631qaz2wsx0000005201314123456789111111123456a4qq1234561234567891234567895201314123456789woaini1314513145205201314123123123123520131452013146aptx48691231231q2w3e4ra123456123456a11111171q2w3e4r5t1qaz2wsx000000woaini1314123123qq1234568123456789a7758521a1234561314520123456789a1qaz2wsx9a1234567891314520qq123456123456a0000001q2w3e4r10abc123456666666woaini1314qq123456woaini1314123qwe%0.51%3.40%2.00%1.96%2.33%1.17%The statistical results of the component form of the top-104 popular passwords, which are analyzed by the PCFG-based algorithm, are shown in Table 4. It illustrates that, though the majority of popular passwords are composed of pure numbers, composite passwords (e.g., a password included multiple types of characters) also account for a considerable part, especially 45.81% in 12306 and 49.33% in Dodon.Table 4
Component form distribution of the top-104 popular passwords (Compos: composite).
FormAipaiTinyaSendaDodonYouku12306Alpha14.73%10.89%15.24%11.46%13.49%7.21%Digit59.52%63.12%66.07%39.17%65.9%46.93%Symbol0%0.05%0.02%0.01%0.08%0.05%Compos25.75%25.94%18.67%49.33%20.53%45.81%Since the grammarGI of TarGuess−I does not contain tags related to popular passwords, it could lower the success rate if the targeted users are likely to choose composite passwords. Because TarGuess−I is based on PCFG, which generates passwords according to the existing base structures generated from data and the elements in each set of tags. Thus, in the training phase, the model parses the composite password into LDS segments, and it might generate many invalid outputs at last, an illusion is shown in Figure 1. For instance, “1qaz2wsx,” a password constructed with keyboard patterns, which is the 3rd popular password in Aipai, will be parsed into D1L3D1L3 by TarGuess−I. Meanwhile, “1” ranks the first in the set of D1 tag, and “qaz” ranks the first in L3. Therefore, in the guessing phase, the first password output with the base structure D1L3D1L3 is “1qaz1qaz.” This password occupies a relatively small proportion in actual password distribution but ranks much higher in the output list, thus reducing the overall password guessing success rate. From this perspective, we come up with an idea to take popular passwords and the keyboard pattern into consideration for the training phase in TarGuess−I.By analyzing popular passwords, we find that there are two missing attributes in the grammarGI: the popular password tag P and the keyboard pattern tag K.


## 3.2. Analysis of Passwords Containing Personal Information

We adopt theTarGuess−I+PK model to analyze the datasets. TarGuess−I+PK is improved with the popular password tag P containing top-104 list and the keyboard pattern tag K. The rank of top-10 password base structures and the proportion of passwords containing PII tag or P tag are shown in Table 5. It indicates that about half of Chinese users generally construct passwords using PII or just choose popular ones. We speculate that the top-10 base structures of passwords should be related to the strings that are easy for users to remember. And we also find that some password base structures in the top-10 list are not relevant to users’ PII or containing P tag.Table 5
Top-10 base structures and proportion of the passwords containing PII andP tag.
RankAipaiTinyaSendaDodonYouku123061P1P1P1P1P1P12D7D6D7E1D6D63N2P1D7D8D7D7D74N2D7D8D6D6D8N2D65D8E1N2P1D8N2P1U16L1D7D10E1L1D7U1E17N2D6B8N2D7N2D7U3D88D6D9L1D7N2D6E1N2D79E1U3N2D6U1P1D3N2P110U1B1U3U3N2D6U3% of PII34.24%35.47%33.80%38.83%32.97%35.98%% ofP12.72%13.94%18.14%10.62%21.07%19.07%The strings which are accessible to memorize include users’ PII conversions, keyboard patterns, and popular passwords. They also include the user-created strings that have special meaning for the user but are no equal importance to other users, we call them “the special strings.” To give an example, we assume thatA user creates a string “080405” as his password, then “080405” shall be special for him. But for another user B, “080405” is nothing other than a common string; then, the probability of A’s password containing this string shall be different from B’s. Meanwhile, we cannot find the string “080405” in A’s or B’s demographic information (such as name, ID number, and telephone number). The special string cannot be extracted from the user’s demographic information but may appear in some like the prefix of e-mail addresses and user names that the user-created strings, or in user’s passwords from other servers.The parse of users’ PII inTarGuess−I also includes the user-generated strings, such as e-mail address En and user name Un. However, the analyses of these two user-generated strings are not sophisticated enough. Only three parse type (Entire E1&U1, the first letter segments E2&U2 and the first digit segments E3&U3) are proposed. The special strings for each user, as the above said, the probability distribution is different. If we use the original TarGuess−I model, because of the lack of recognition of the special string, most of these segments will be parsed into typical LDS tags, merging the user behavior characteristics, thus hinder the effectiveness of password cracking. Therefore, we consider adding the special string tag X to the grammar GI of TarGuess−I.We analyze the coverage of consecutive substrings of the e-mail address and user name in the password. The result is shown in Figure4. It reveals that a significant number of user passwords do overlap user-created strings; thus, it gives us a new hint that when an attacker obtains information about a user that is not public or very useful, they may turn that information into a special string to participate in password guessing. This idea may serve as a new direction for further research.Figure 4
Fraction of the special stringXn in the password.


## 4. Implementations of Modified Methods

After analyzing users’ vulnerable behaviors in constructing passwords in Section3, we find that TarGuess−I does not take into account three attributes, including popular passwords, keyboard patterns, and the special strings. Thus, we come up with three ideas for modifying TarGuess−I.
(1)
Add the popular password tagP to the grammar GI and apply the popular password list generated from a dataset similar to the target website(2)
Add the keyboard pattern tagK to the grammar GI and identify password segments with physical location sequence in QWERTY keyboard(3)
Add the special string tagX to the grammar GI and extracted continuous characters from the user-generated PIIFigure5 gives a brief explanation on how we try to modified TarGuess−I and generate TarGuess−I+KPX. In this section, we will study for the implementations of these modified methods.Figure 5
A testing case ofTarGuess−I+KPX and our modified methods for it. The parts highlighted in red are the semantic tags we added and the additional password structures the model recognized after adding the semantic tags.


### 4.1. Popular Passwords

Add the popular password tagP1 to the grammar GI, and the set of elements in P1 tag is a top-N popular password list based on the data statistics of similar websites. The number 1 in P1 has no meaning but to conform to the grammar format. The parse of P1 tag is shown in Figure 6.Figure 6
An illustration ofP1 tag parse.In the training phase, the top-N list is matched with the password data by a regular expression. If the match occurs, the occurrence of the corresponding password in P1 set is increased by 1. In the guess generation phase, the probabilities of containing P1 password structures are multiplied by the frequencies of the corresponding password in the element set of P1 as the final probabilities of output passwords.To find out whichN is the optimal parameter in setting the improved guessing model, we conduct a series of evaluations with top-N popular passwords based on 12306 data. Figure 7 is a contour plot displaying how top-N popular passwords influence the success rate. It can be seen that, within 100 guesses, the success rate increased slightly with the growing N, and the success rate is a bit higher with N⊆100∼103 under 100 guesses. Figure 8 shows the similarities of top-N popular passwords between two different services. The similarity fluctuates greatly within top-100, and it tends to a stable peak when N is around at 300, then gradually reduces as N continues to grow. With the exception of Aipai and 12306, the top-300 popular password list of each dataset has a similar top−300 list from another dataset (their similarity >60%). The dispersion of shared password fractions implies that different types of services do impact on top popular passwords. Based on the above experimental results, we set N=300 in the cross-site password guessing scenario.Figure 7
Experimental results of improved models with top-N popular passwords based on 12306 dataset. K represents the guess number. We use 60% of 12306 data for training and 40% for testing. Top-N popular password list is generated from the same service.Figure 8
Fraction of top-N passwords shared between two services. We use difflflib function in Python to calculate the similarity of the top-N popular passwords between each site.
(a)
With12306(b)
WithYouku(c)
WithDodon(d)
WithTinya(e)
WithSenda(f)
WithAipai


### 4.2. Keyboard Patterns

The process of keyboard patternKn is compliant with the left-hand side (LHS) principle. First, get the relative position of the character on the keyboard and then determine whether the latter character is adjacent to the previous character position. If the length of the string with adjacent characters len≥4, then divide the segment into the keyboard order Kn variable, where n=len. An illusion of the Kn process is shown in Figure 9.Figure 9
An illustration ofKn tags process.See Table6 for the password base structure ranking and proportion with keyboard pattern Kn tags in our experimental datasets. K8 represents the password generated by 8-length of keyboard patterns (such as “1qaz2wsx”). It should note that K4K4 is a password composed of 2 nonadjacent keyboard pattern strings, such as “1234asdf.” Table 6 shows that the proportion of the passwords containing keyboard patterns is 0.88% to 1.37% in our experimental datasets.Table 6
Ranking and proportion of the passwords containing keyboard pattern.struct: structure.
SourceAipaiTinyaSendaDodonYouku12306RankStructRankStructRankStructRankStructRankStructRankStructRank1K880K865K857K898K881K8712K4K4148K4K4150K4K4141K7184K6143K4K41523K10208K6200K10170K4K4190K4K4165K61754K9229K10204K6196K6228K7175K102165K5D3264L4K4341K9233K9273K10223K72356K4D4327K4D3386K7309K10343K9244K92647D5K4335K9391K4D4326K4D3353K5D3322K5D34118K7360K7424L4K4401K4D5423K4D5388K4D54939K6368D5K4450D5K4403D5K4489K4D4515K4D449510K4L5381D3K5663K5D3430K4D4523L4K4600L5K4620%1.37%0.97%1.21%0.88%1.19%1.22%


### 4.3. The Special Strings

Considering that only two user-generated PII is needed inTarGuess−I, e-mail addresses and user names, and the limitation of experimental resources, we only generated the elements of the special string Xn from these two PII. Since there are various and different ways for each user to generate special strings, it is difficult to categorize the generation methods of special strings uniformly and may cause sparse data. Therefore, n and m only classified according to the length of special strings and the position where the special string occurs. An illustration of the special string Xn process is shown in Figure 10.Figure 10
An illustration ofXn tags process.Figure11 shows the success rate of the X-tag-modified models compared to TarGuess−I. Each modified model has a different threshold number of the identification length for X tag. Unfortunately, we find that no matter how we change the threshold, the model with X tags does not work well. The reasons for the poor performance of the X tag may be as follows:
(1)
This semantic tag is originally based on incremental information to improve the targeted password guessing model, that is, the user’s other information besides users’ demographic PII (such as work number, home address, and lover’s name). However, due to the limitation of experimental conditions, we cannot obtain more incremental information, but can only make a finer segmentation from the user-generated PII (such as e-mail address and user name, which have been already analyzed inTarGuess−I)(2)
Our improved method of the special stringsX is not in line with the habit of users setting passwords. We divide the user-generated PII according to length and calculate the relative position of substrings (as shown in Figure 10), which is a length-based method. That was also confirmed by Wang et al. to be insufficient for the analysis of users’ behavioral characteristics. For a long user-generated PII string, this method generates too many invalid substringsFigure 11
A brief comparison of the lengthn that considered in X tag.In a real situation, if an attacker is about to attack a targeted user, he/she will do his/her best to obtain the information required for attacking. Therefore, the problem caused by reason 1 does not exist. What we do is highlight the threat that incremental information from users will help for targeted password guessing. And for reason 2, we deleted the relative positionm with low frequency in the training results, leaving the one with the largest proportion. Thus, we regenerate the implementation of X tag, and the experimental result is shown as the success rate of +X tag (filtered) in Figure 11. We will further study the implementation of X tag in the future.


## 4.1. Popular Passwords

Add the popular password tagP1 to the grammar GI, and the set of elements in P1 tag is a top-N popular password list based on the data statistics of similar websites. The number 1 in P1 has no meaning but to conform to the grammar format. The parse of P1 tag is shown in Figure 6.Figure 6
An illustration ofP1 tag parse.In the training phase, the top-N list is matched with the password data by a regular expression. If the match occurs, the occurrence of the corresponding password in P1 set is increased by 1. In the guess generation phase, the probabilities of containing P1 password structures are multiplied by the frequencies of the corresponding password in the element set of P1 as the final probabilities of output passwords.To find out whichN is the optimal parameter in setting the improved guessing model, we conduct a series of evaluations with top-N popular passwords based on 12306 data. Figure 7 is a contour plot displaying how top-N popular passwords influence the success rate. It can be seen that, within 100 guesses, the success rate increased slightly with the growing N, and the success rate is a bit higher with N⊆100∼103 under 100 guesses. Figure 8 shows the similarities of top-N popular passwords between two different services. The similarity fluctuates greatly within top-100, and it tends to a stable peak when N is around at 300, then gradually reduces as N continues to grow. With the exception of Aipai and 12306, the top-300 popular password list of each dataset has a similar top−300 list from another dataset (their similarity >60%). The dispersion of shared password fractions implies that different types of services do impact on top popular passwords. Based on the above experimental results, we set N=300 in the cross-site password guessing scenario.Figure 7
Experimental results of improved models with top-N popular passwords based on 12306 dataset. K represents the guess number. We use 60% of 12306 data for training and 40% for testing. Top-N popular password list is generated from the same service.Figure 8
Fraction of top-N passwords shared between two services. We use difflflib function in Python to calculate the similarity of the top-N popular passwords between each site.
(a)
With12306(b)
WithYouku(c)
WithDodon(d)
WithTinya(e)
WithSenda(f)
WithAipai


## 4.2. Keyboard Patterns

The process of keyboard patternKn is compliant with the left-hand side (LHS) principle. First, get the relative position of the character on the keyboard and then determine whether the latter character is adjacent to the previous character position. If the length of the string with adjacent characters len≥4, then divide the segment into the keyboard order Kn variable, where n=len. An illusion of the Kn process is shown in Figure 9.Figure 9
An illustration ofKn tags process.See Table6 for the password base structure ranking and proportion with keyboard pattern Kn tags in our experimental datasets. K8 represents the password generated by 8-length of keyboard patterns (such as “1qaz2wsx”). It should note that K4K4 is a password composed of 2 nonadjacent keyboard pattern strings, such as “1234asdf.” Table 6 shows that the proportion of the passwords containing keyboard patterns is 0.88% to 1.37% in our experimental datasets.Table 6
Ranking and proportion of the passwords containing keyboard pattern.struct: structure.
SourceAipaiTinyaSendaDodonYouku12306RankStructRankStructRankStructRankStructRankStructRankStructRank1K880K865K857K898K881K8712K4K4148K4K4150K4K4141K7184K6143K4K41523K10208K6200K10170K4K4190K4K4165K61754K9229K10204K6196K6228K7175K102165K5D3264L4K4341K9233K9273K10223K72356K4D4327K4D3386K7309K10343K9244K92647D5K4335K9391K4D4326K4D3353K5D3322K5D34118K7360K7424L4K4401K4D5423K4D5388K4D54939K6368D5K4450D5K4403D5K4489K4D4515K4D449510K4L5381D3K5663K5D3430K4D4523L4K4600L5K4620%1.37%0.97%1.21%0.88%1.19%1.22%


## 4.3. The Special Strings

Considering that only two user-generated PII is needed inTarGuess−I, e-mail addresses and user names, and the limitation of experimental resources, we only generated the elements of the special string Xn from these two PII. Since there are various and different ways for each user to generate special strings, it is difficult to categorize the generation methods of special strings uniformly and may cause sparse data. Therefore, n and m only classified according to the length of special strings and the position where the special string occurs. An illustration of the special string Xn process is shown in Figure 10.Figure 10
An illustration ofXn tags process.Figure11 shows the success rate of the X-tag-modified models compared to TarGuess−I. Each modified model has a different threshold number of the identification length for X tag. Unfortunately, we find that no matter how we change the threshold, the model with X tags does not work well. The reasons for the poor performance of the X tag may be as follows:
(1)
This semantic tag is originally based on incremental information to improve the targeted password guessing model, that is, the user’s other information besides users’ demographic PII (such as work number, home address, and lover’s name). However, due to the limitation of experimental conditions, we cannot obtain more incremental information, but can only make a finer segmentation from the user-generated PII (such as e-mail address and user name, which have been already analyzed inTarGuess−I)(2)
Our improved method of the special stringsX is not in line with the habit of users setting passwords. We divide the user-generated PII according to length and calculate the relative position of substrings (as shown in Figure 10), which is a length-based method. That was also confirmed by Wang et al. to be insufficient for the analysis of users’ behavioral characteristics. For a long user-generated PII string, this method generates too many invalid substringsFigure 11
A brief comparison of the lengthn that considered in X tag.In a real situation, if an attacker is about to attack a targeted user, he/she will do his/her best to obtain the information required for attacking. Therefore, the problem caused by reason 1 does not exist. What we do is highlight the threat that incremental information from users will help for targeted password guessing. And for reason 2, we deleted the relative positionm with low frequency in the training results, leaving the one with the largest proportion. Thus, we regenerate the implementation of X tag, and the experimental result is shown as the success rate of +X tag (filtered) in Figure 11. We will further study the implementation of X tag in the future.


## 5. Experiments

TarGuess−I is mainly used in online guessing scenarios, where the guess number allowed is the scarcest resource, while computational power and bandwidth are not essential. Therefore, we mainly evaluate the availability of the modified guessing models by the success rates r with guess number N.


### 5.1. Experiment Setup

To make our experiments as scientific as possible, we follow 3 rules.(1)
Training sets and testing sets are strictly separated(2)
The comparison experiments of the two models are based on the same training sets and testing sets(3)
The training sets shall be as large as possibleTo abide by rule 1 and rule 3, we chose the largest105 sized datasets 12306 and Youku as training sets and remove it from the testing list. Particularly, users’ passwords in each dataset are highly heterogeneous. The distribution of password semantics may greatly different between two sites even in distinct parts of the same dataset. Thus, the fraction of successfully cracked passwords in each dataset evaluated by different password guessing model may fluctuate greatly. To avoid the heterogeneity of datasets that may hinder our observation of the feasibility of improved methods, we use Monte Carlo method to randomly extract data and generate 10 testing sets from each dataset. The size of each testing set is 103. We applied these sets for every evaluation.Table7 shows the four-dimensional variables of the experiment setup. We build nine models by adding three improved tags individually or in combination to TarGuess−I (hereinafter referred to as “TG−I”). The four single-tag-modified models (e.g., TG−I+K, TG−I+X, TG−I+P, and TG−I+P′) are built to evaluate the validation of our three modified methods (e.g., the popular password tag P, the keyboard pattern tag K, and the special string tag X). To make our evaluations more realistic, we define two kinds of scenarios with P tags. In one optimal scenario (e.g., with P tag), attackers have got the target site’s top-300 popular password list for cracking. In the other scenario (e.g., with P' tag), which is more realistic, attackers are only able to crack the target site with similar top-300, from which we choose based on the analysis in Figure 8. The four combined-tag-modified models (e.g., TG−I+KP, TG−I+PX, TG−I+KX, TG−I+KP′X, and TG−I+KPX) are built to find out the optimal model and whether incremental attributes can improve the efficiency of password guessing. We set a total of 80 attacking scenarios based on these four-dimensional variables and conducted 10 experiments on each one.Table 7
Training and test settings for each attacking scenario under 9 models.
Password guessing modelTG−I∗,TG−I+K, TG−I+P, TG−I+P′,TG−I+X, TG−I+KP′, TG−I+P′X, TG−I+KX, TG−I+KPX,TG−I+KP′XTraining sets12306, YoukuTesting setsAipaiTinyaSendaDodonP′ tag with top-300#Senda’sYouku’sYouku’sSenda’sP tag with top-300Aipai’sTinya’sSenda’sDodon’s∗TG-I: TarGuess−I. The superscript of each model represents the improved tags it has added; #P′ tag is in the optimal condition that attackers have got the target site’s top-300 popular password list, while P tag is in the normal condition that attackers only have the similar site’s top-300 with target one.Figure12 shows the average of cracking success rate with guess number n evaluated by nine models trained from two sites and tested from four sites. As shown in the figure, the differences of cracking success rate in each model are not obvious if we just compare them with guess-number-graph like this. Thus, to make the experimental results easier to analyze, we calculate the relative values Rn between each model and original TG−I with guess number n, which:
(1)Rn=MeanrnTGi+−rnTGirnTGi×100%,where rnTGi+ is the success rate of improved model tested from (i)th testing set with guess number n, and rnTGi is that of TG-I.Figure 12
An average guess-number graph including nine models.


### 5.2. Experiment 1: Validation of the Modified Methods

To demonstrate the effectiveness of our modified methods, we compare the cracking success rate of the four single-tag-modified models (e.g.,TG−I+K, TG−I+X, TG−I+P, and TG−I+P′) with that of TG−I based on the testing data. The Rn-number-graphs of the four single-tag improved models are shown in Figure 13, and the average Rn statistics of them are shown in Table 8. As shown in the Table 8, except that the TG−I+P′ trained by Youku has an average Rn of 0.03% lower than TG−I within 100 guesses, the rest of the single-tag-modified models outperformed TG−I. They outperformed TG−I by 0.18%∼0.75% on average within 100 guesses. It proves the effectiveness of our three modified methods.Figure 13
Experimental results of four single-tag-modified models. Figures8(a)–8(d) represent the Rn of the four single-tag-modified models. The dotted line at 0% on the y-axis represents our reference baseline (i.e., the cracking success rate of TG-I).
(a)
TG−I+K(b)
TG−I+X(c)
TG−I+P′(d)
TG−I+PTable 8
Average ofRn statistics of Figure 13.
Training SetImproved ModelGuess number range10−100100−103103−10412306TG−I+K0.61%∼-0.43%0.18%0.72%∼0.35%0.56%1.14%∼0.88%0.98%TG−I+X1.53%∼-0.39%0.38%1.74%∼0.55%1.34%2.11%∼1.37%1.72%TG−I+P′1.07%∼-0.92%0.31%1.80%∼0.70%1.12%0.50%∼-0.70%-0.27%TG−I+P1.79%∼-0.31%0.75%2.88%∼1.31%2.20%1.96%∼0.11%0.80%YoukuTG−I+K0.75%∼-0.27%0.24%0.72%∼-0.02%0.51%1.10%∼0.66%0.97%TG−I+X1.70%∼-1.63%0.27%1.80%∼0.75%1.33%2.62%∼1.92%2.25%TG−I+P′0.78%∼-1.06%-0.03%0.99%∼0.28%0.68%0.30%∼-0.90%-0.47%TG−I+P2.05%∼-0.49%0.55%2.65%∼0.46%1.73%1.64%∼0.09%0.67%Figures13(a) and 13(b) show that, compared to TG−I, the guess performances of TG−I+K and TG−I+X models are magnified as the number of guesses increases. In the range of 10∼100 guesses, our modified models have no better performances than TG−I, and the cracking success rates of our models are even lower than TG−I under some guess numbers. For instance, when TG−I+X is evaluated using the Aipai datasets, the cracking success rate of TG−I+X is −2.4% (trained from 12306) lower than TG−I at 50 guesses and −3.2% (trained from Youku) lower than TG−I at 40 guesses. This is because the passwords containing K or X tag are relatively small in the overall password distribution, and the addition of the corresponding tag will only affect the lower-ranked candidate passwords. In addition, for TG−I+X, it also may be because the implementation of our X tag is still not consistent with the users’ behaviors. It causes the modified model to incorrectly generate the candidate passwords with a higher ranking. Nevertheless, as the number of guesses increases, the advantages of our model are reflected. In the guess range of 100∼103, the Rn of our models are slightly increased. And in the guess range of 103∼104, the cracking success rates of our models are significantly and stably better than TG−I. At the number of 104 guesses, compared with TG−I, the cracking success rates of TG−I+K are increased by 1.3% at most and 0.6% at least, and the cracking success rates of TG−I+X are increased by 3.4% at most and 0.4% at least. We find that these methods worked for trawling scenarios because it does increase the success rate of the modified models over 100 guesses.As shown in Figures13(c) and 13(d), the models with P tag significantly outperform TG−I between 100 and 103 guesses. In this range, the cracking success rates of TG−I+P′ are at most 2.7% (trained from 12306) and 2.2% (trained from Youku) higher than TG−I, and the cracking success rates of TG−I+P are at most 4.3% (trained from 12306) and 4.1% (trained from Youku) higher than TG−I. The reason for this is that popular passwords P1 rank first in the grammar GI, while the composite-form popular passwords are in the bottom half of the top-300 list. As the above said, composite-form popular passwords cause TG−I to produce invalid output.Particularly,TG−I+P′ has a lower guess success rate than TG−I within 100 guesses. It is because the tops of the top-300 popular password lists included in the P′ tag are different from these in the testing site. As a result, there are a few invalid outputs in the top 100 candidate passwords. It can be seen that there is no such phenomenon in the results of the TG−I+P models, which show that the models also have improvements within 100 guesses.Interestingly, there is an outlier curve in eachRn-number-graph at Figures 13(b)–13(d). Some curves are significantly higher than others, and some are significantly lower than others. The TG−I+X model has an average guess success rate of 2.6% higher than TG−I on the Dodon testing data, while it has an average of 1.0% higher than TG−I on the rest of testing data. The TG−I+P model (trained from Youku) shows a −4.8% lower success rate than TG−I on the Aipai testing data, while the worst guess performance for other testing data is −1.6% lower than TG−I. This phenomenon may be due to the different distribution of each password dataset. We find that there are a few “uncleaned” passwords data in Aipai’s popular password list and datasets, such as “0a2cb03c4dc29cfc0d56afa46ae8fd2e” ranked 20th in the top-300 list. Thus, these “uncleaned” popular password data may cause a reduction in the models’ success rate.


### 5.3. Experiment 2: Comparison and Evaluation of Modified Models

We evaluate each combined-tag-modified model to find out the optimal skim. Table9 calculates the average Rn compared each modified model with TG−I. TG−I+KPX modified with our three incremental tags has the best improvement effect (see Figure 14(f)).Table 9
Statistics ofRn of Figure 14.
Training setImproved modelGuess number range10−100100−103103−10412306TG−I+KP1.14%∼-0.92%0.33%1.75%∼0.77%1.10%0.51%∼-0.62%-0.19%TG−I+PX2.58%∼-1.01%0.59%3.41%∼1.21%2.70%2.60%∼1.04%1.56%TG−I+KX2.10%∼-0.77%0.50%2.23%∼0.93%1.90%3.07%∼2.32%2.67%TG−I+KP′X2.60%∼-1.01%0.62%3.33%∼1.20%2.69%2.57%∼1.15%1.61%TG−I+KPX2.27%∼-0.49%1.05%4.65%∼1.34%3.67%3.77%∼2.63%2.73%YoukuTG−I+KP0.82%∼-0.78%0.04%1.06%∼0.19%0.65%0.31%∼-0.71%-0.39%TG−I+PX1.37%∼-1.90%0.00%2.65%∼1.69%2.21%2.24%∼1.38%1.83%TG−I+KX2.11%∼-1.55%0.44%2.25%∼1.24%1.83%3.68%∼2.44%3.16%TG−I+KP′X1.54%∼-1.86%0.02%2.67%∼1.73%2.18%2.25%∼1.50%1.82%TG−I+KPX1.85%∼-1.13%0.56%4.44%∼1.96%3.15%3.77%∼2.63%2.97%Figure 14
Experimental results of five combined-tag-modified models and comparison of nine modified models. (a–e) TheRn of the five combined-tag-modified models; (f) the Rn comparison of ten modified models. The dotted line at 0% on the y-axis represents our reference baseline (i.e., the cracking success rate of TG-I).
(a)
TG−I+KP′(b)
TG−I+KX(c)
TG−I+P′X(d)
TG−I+KP′X(e)
TG−I+KPX(f)
AvgRn of the modified modelsIt can be seen in Figure14(f) that, by comparing TG−I+K, TG−I+X, and TG−I+KX models, the improvement effects of the modified models are magnified as the number of incremental tags increase. This phenomenon can also be seen by comparing TG−I+P′, TG−I+P′X, TG−I+KP′, and TG−I+KP′X models. However, we also find that the improvement effects of the combined-tag-modified models with P tag are not strongly correlated with the single-tag-modified models with X or K tag. This may because popular passwords account for a large proportion of the password distribution, and there is an obvious gap to the proportion of passwords containing the keyboard patterns or the special strings. Therefore, in terms of the degree of influence on the success rate of guessing, the influence of adding P tag is far greater than that of adding K or X tag.Table1 shows the guessing performance of TG−I+KPX evaluated based on each testing dataset. It can be seen that, except that the success rate of TG−I+KPX based on Aipai dataset is weaker than that of TG−I within 100 guesses, TG−I+KPX outperforms TG−I based on the other three testing datasets. The reason for the poor results of Aipai dataset has been mentioned in the analysis of TG−I+P′ in experiment 5.2. TG−I+KPX outperforms TG−I by 0.72%∼2.62% (trained from 12306) and 0.00%∼2.16% (trained from Youku) within 100 guesses.Table10 shows the top-10 base structure of candidate passwords generated by TG−I and TG−I+KPX and the proportions of base structures containing incremental tags in candidate passwords. It can be seen that TG−I+KPX generates nearly 10% more candidate passwords containing incremental tags than TG−I does. Meanwhile, the passwords with the top-10 base structure in Table 10 are very easy to be cracked by the targeted password guessing models. Therefore, we recommend users to avoid setting similar passwords.Table 10
Top-10 base structures of candidate passwords.
Rank12306YoukuTG−ITG−I+KPXTG−ITG−I+KPX1D64.603%P14.151%D67.411%P16.209%2D73.358%D63.747%D74.941%D65.387%3N2D62.519%D73.112%D82.498%D74.519%4U11.995%U11.995%N2D62.266%D82.343%5D81.959%D81.874%U12.169%U12.169%6E11.776%N2D61.845%U32.039%U31.985%7N2D71.719%E11.776%E11.733%E11.733%8A2D61.502%N2D71.457%A2D61.436%N2D61.580%9U31.466%U31.431%B11.350%B11.347%10N1D31.322%N1D31.203%D91.335%N11.217%%∗57.422%65.516%53.132%63.557%∗The proportions of the password base structures containing incremental tags (such as PII tags, K tag, and P tag) in candidate passwords.In all, the modified methods we proposed are effective. Our results reiterate the threat posed by users using popular passwords and keyboard mode passwords and highlight the threat of targeted password guessing. When an attacker gets more information about a user, the user’s password is more likely to be cracked. Our work implies that for important applications, a multifactor authentication scheme (e.g., [40–42]) is necessary.


## 5.1. Experiment Setup

To make our experiments as scientific as possible, we follow 3 rules.(1)
Training sets and testing sets are strictly separated(2)
The comparison experiments of the two models are based on the same training sets and testing sets(3)
The training sets shall be as large as possibleTo abide by rule 1 and rule 3, we chose the largest105 sized datasets 12306 and Youku as training sets and remove it from the testing list. Particularly, users’ passwords in each dataset are highly heterogeneous. The distribution of password semantics may greatly different between two sites even in distinct parts of the same dataset. Thus, the fraction of successfully cracked passwords in each dataset evaluated by different password guessing model may fluctuate greatly. To avoid the heterogeneity of datasets that may hinder our observation of the feasibility of improved methods, we use Monte Carlo method to randomly extract data and generate 10 testing sets from each dataset. The size of each testing set is 103. We applied these sets for every evaluation.Table7 shows the four-dimensional variables of the experiment setup. We build nine models by adding three improved tags individually or in combination to TarGuess−I (hereinafter referred to as “TG−I”). The four single-tag-modified models (e.g., TG−I+K, TG−I+X, TG−I+P, and TG−I+P′) are built to evaluate the validation of our three modified methods (e.g., the popular password tag P, the keyboard pattern tag K, and the special string tag X). To make our evaluations more realistic, we define two kinds of scenarios with P tags. In one optimal scenario (e.g., with P tag), attackers have got the target site’s top-300 popular password list for cracking. In the other scenario (e.g., with P' tag), which is more realistic, attackers are only able to crack the target site with similar top-300, from which we choose based on the analysis in Figure 8. The four combined-tag-modified models (e.g., TG−I+KP, TG−I+PX, TG−I+KX, TG−I+KP′X, and TG−I+KPX) are built to find out the optimal model and whether incremental attributes can improve the efficiency of password guessing. We set a total of 80 attacking scenarios based on these four-dimensional variables and conducted 10 experiments on each one.Table 7
Training and test settings for each attacking scenario under 9 models.
Password guessing modelTG−I∗,TG−I+K, TG−I+P, TG−I+P′,TG−I+X, TG−I+KP′, TG−I+P′X, TG−I+KX, TG−I+KPX,TG−I+KP′XTraining sets12306, YoukuTesting setsAipaiTinyaSendaDodonP′ tag with top-300#Senda’sYouku’sYouku’sSenda’sP tag with top-300Aipai’sTinya’sSenda’sDodon’s∗TG-I: TarGuess−I. The superscript of each model represents the improved tags it has added; #P′ tag is in the optimal condition that attackers have got the target site’s top-300 popular password list, while P tag is in the normal condition that attackers only have the similar site’s top-300 with target one.Figure12 shows the average of cracking success rate with guess number n evaluated by nine models trained from two sites and tested from four sites. As shown in the figure, the differences of cracking success rate in each model are not obvious if we just compare them with guess-number-graph like this. Thus, to make the experimental results easier to analyze, we calculate the relative values Rn between each model and original TG−I with guess number n, which:
(1)Rn=MeanrnTGi+−rnTGirnTGi×100%,where rnTGi+ is the success rate of improved model tested from (i)th testing set with guess number n, and rnTGi is that of TG-I.Figure 12
An average guess-number graph including nine models.


## 5.2. Experiment 1: Validation of the Modified Methods

To demonstrate the effectiveness of our modified methods, we compare the cracking success rate of the four single-tag-modified models (e.g.,TG−I+K, TG−I+X, TG−I+P, and TG−I+P′) with that of TG−I based on the testing data. The Rn-number-graphs of the four single-tag improved models are shown in Figure 13, and the average Rn statistics of them are shown in Table 8. As shown in the Table 8, except that the TG−I+P′ trained by Youku has an average Rn of 0.03% lower than TG−I within 100 guesses, the rest of the single-tag-modified models outperformed TG−I. They outperformed TG−I by 0.18%∼0.75% on average within 100 guesses. It proves the effectiveness of our three modified methods.Figure 13
Experimental results of four single-tag-modified models. Figures8(a)–8(d) represent the Rn of the four single-tag-modified models. The dotted line at 0% on the y-axis represents our reference baseline (i.e., the cracking success rate of TG-I).
(a)
TG−I+K(b)
TG−I+X(c)
TG−I+P′(d)
TG−I+PTable 8
Average ofRn statistics of Figure 13.
Training SetImproved ModelGuess number range10−100100−103103−10412306TG−I+K0.61%∼-0.43%0.18%0.72%∼0.35%0.56%1.14%∼0.88%0.98%TG−I+X1.53%∼-0.39%0.38%1.74%∼0.55%1.34%2.11%∼1.37%1.72%TG−I+P′1.07%∼-0.92%0.31%1.80%∼0.70%1.12%0.50%∼-0.70%-0.27%TG−I+P1.79%∼-0.31%0.75%2.88%∼1.31%2.20%1.96%∼0.11%0.80%YoukuTG−I+K0.75%∼-0.27%0.24%0.72%∼-0.02%0.51%1.10%∼0.66%0.97%TG−I+X1.70%∼-1.63%0.27%1.80%∼0.75%1.33%2.62%∼1.92%2.25%TG−I+P′0.78%∼-1.06%-0.03%0.99%∼0.28%0.68%0.30%∼-0.90%-0.47%TG−I+P2.05%∼-0.49%0.55%2.65%∼0.46%1.73%1.64%∼0.09%0.67%Figures13(a) and 13(b) show that, compared to TG−I, the guess performances of TG−I+K and TG−I+X models are magnified as the number of guesses increases. In the range of 10∼100 guesses, our modified models have no better performances than TG−I, and the cracking success rates of our models are even lower than TG−I under some guess numbers. For instance, when TG−I+X is evaluated using the Aipai datasets, the cracking success rate of TG−I+X is −2.4% (trained from 12306) lower than TG−I at 50 guesses and −3.2% (trained from Youku) lower than TG−I at 40 guesses. This is because the passwords containing K or X tag are relatively small in the overall password distribution, and the addition of the corresponding tag will only affect the lower-ranked candidate passwords. In addition, for TG−I+X, it also may be because the implementation of our X tag is still not consistent with the users’ behaviors. It causes the modified model to incorrectly generate the candidate passwords with a higher ranking. Nevertheless, as the number of guesses increases, the advantages of our model are reflected. In the guess range of 100∼103, the Rn of our models are slightly increased. And in the guess range of 103∼104, the cracking success rates of our models are significantly and stably better than TG−I. At the number of 104 guesses, compared with TG−I, the cracking success rates of TG−I+K are increased by 1.3% at most and 0.6% at least, and the cracking success rates of TG−I+X are increased by 3.4% at most and 0.4% at least. We find that these methods worked for trawling scenarios because it does increase the success rate of the modified models over 100 guesses.As shown in Figures13(c) and 13(d), the models with P tag significantly outperform TG−I between 100 and 103 guesses. In this range, the cracking success rates of TG−I+P′ are at most 2.7% (trained from 12306) and 2.2% (trained from Youku) higher than TG−I, and the cracking success rates of TG−I+P are at most 4.3% (trained from 12306) and 4.1% (trained from Youku) higher than TG−I. The reason for this is that popular passwords P1 rank first in the grammar GI, while the composite-form popular passwords are in the bottom half of the top-300 list. As the above said, composite-form popular passwords cause TG−I to produce invalid output.Particularly,TG−I+P′ has a lower guess success rate than TG−I within 100 guesses. It is because the tops of the top-300 popular password lists included in the P′ tag are different from these in the testing site. As a result, there are a few invalid outputs in the top 100 candidate passwords. It can be seen that there is no such phenomenon in the results of the TG−I+P models, which show that the models also have improvements within 100 guesses.Interestingly, there is an outlier curve in eachRn-number-graph at Figures 13(b)–13(d). Some curves are significantly higher than others, and some are significantly lower than others. The TG−I+X model has an average guess success rate of 2.6% higher than TG−I on the Dodon testing data, while it has an average of 1.0% higher than TG−I on the rest of testing data. The TG−I+P model (trained from Youku) shows a −4.8% lower success rate than TG−I on the Aipai testing data, while the worst guess performance for other testing data is −1.6% lower than TG−I. This phenomenon may be due to the different distribution of each password dataset. We find that there are a few “uncleaned” passwords data in Aipai’s popular password list and datasets, such as “0a2cb03c4dc29cfc0d56afa46ae8fd2e” ranked 20th in the top-300 list. Thus, these “uncleaned” popular password data may cause a reduction in the models’ success rate.


## 5.3. Experiment 2: Comparison and Evaluation of Modified Models

We evaluate each combined-tag-modified model to find out the optimal skim. Table9 calculates the average Rn compared each modified model with TG−I. TG−I+KPX modified with our three incremental tags has the best improvement effect (see Figure 14(f)).Table 9
Statistics ofRn of Figure 14.
Training setImproved modelGuess number range10−100100−103103−10412306TG−I+KP1.14%∼-0.92%0.33%1.75%∼0.77%1.10%0.51%∼-0.62%-0.19%TG−I+PX2.58%∼-1.01%0.59%3.41%∼1.21%2.70%2.60%∼1.04%1.56%TG−I+KX2.10%∼-0.77%0.50%2.23%∼0.93%1.90%3.07%∼2.32%2.67%TG−I+KP′X2.60%∼-1.01%0.62%3.33%∼1.20%2.69%2.57%∼1.15%1.61%TG−I+KPX2.27%∼-0.49%1.05%4.65%∼1.34%3.67%3.77%∼2.63%2.73%YoukuTG−I+KP0.82%∼-0.78%0.04%1.06%∼0.19%0.65%0.31%∼-0.71%-0.39%TG−I+PX1.37%∼-1.90%0.00%2.65%∼1.69%2.21%2.24%∼1.38%1.83%TG−I+KX2.11%∼-1.55%0.44%2.25%∼1.24%1.83%3.68%∼2.44%3.16%TG−I+KP′X1.54%∼-1.86%0.02%2.67%∼1.73%2.18%2.25%∼1.50%1.82%TG−I+KPX1.85%∼-1.13%0.56%4.44%∼1.96%3.15%3.77%∼2.63%2.97%Figure 14
Experimental results of five combined-tag-modified models and comparison of nine modified models. (a–e) TheRn of the five combined-tag-modified models; (f) the Rn comparison of ten modified models. The dotted line at 0% on the y-axis represents our reference baseline (i.e., the cracking success rate of TG-I).
(a)
TG−I+KP′(b)
TG−I+KX(c)
TG−I+P′X(d)
TG−I+KP′X(e)
TG−I+KPX(f)
AvgRn of the modified modelsIt can be seen in Figure14(f) that, by comparing TG−I+K, TG−I+X, and TG−I+KX models, the improvement effects of the modified models are magnified as the number of incremental tags increase. This phenomenon can also be seen by comparing TG−I+P′, TG−I+P′X, TG−I+KP′, and TG−I+KP′X models. However, we also find that the improvement effects of the combined-tag-modified models with P tag are not strongly correlated with the single-tag-modified models with X or K tag. This may because popular passwords account for a large proportion of the password distribution, and there is an obvious gap to the proportion of passwords containing the keyboard patterns or the special strings. Therefore, in terms of the degree of influence on the success rate of guessing, the influence of adding P tag is far greater than that of adding K or X tag.Table1 shows the guessing performance of TG−I+KPX evaluated based on each testing dataset. It can be seen that, except that the success rate of TG−I+KPX based on Aipai dataset is weaker than that of TG−I within 100 guesses, TG−I+KPX outperforms TG−I based on the other three testing datasets. The reason for the poor results of Aipai dataset has been mentioned in the analysis of TG−I+P′ in experiment 5.2. TG−I+KPX outperforms TG−I by 0.72%∼2.62% (trained from 12306) and 0.00%∼2.16% (trained from Youku) within 100 guesses.Table10 shows the top-10 base structure of candidate passwords generated by TG−I and TG−I+KPX and the proportions of base structures containing incremental tags in candidate passwords. It can be seen that TG−I+KPX generates nearly 10% more candidate passwords containing incremental tags than TG−I does. Meanwhile, the passwords with the top-10 base structure in Table 10 are very easy to be cracked by the targeted password guessing models. Therefore, we recommend users to avoid setting similar passwords.Table 10
Top-10 base structures of candidate passwords.
Rank12306YoukuTG−ITG−I+KPXTG−ITG−I+KPX1D64.603%P14.151%D67.411%P16.209%2D73.358%D63.747%D74.941%D65.387%3N2D62.519%D73.112%D82.498%D74.519%4U11.995%U11.995%N2D62.266%D82.343%5D81.959%D81.874%U12.169%U12.169%6E11.776%N2D61.845%U32.039%U31.985%7N2D71.719%E11.776%E11.733%E11.733%8A2D61.502%N2D71.457%A2D61.436%N2D61.580%9U31.466%U31.431%B11.350%B11.347%10N1D31.322%N1D31.203%D91.335%N11.217%%∗57.422%65.516%53.132%63.557%∗The proportions of the password base structures containing incremental tags (such as PII tags, K tag, and P tag) in candidate passwords.In all, the modified methods we proposed are effective. Our results reiterate the threat posed by users using popular passwords and keyboard mode passwords and highlight the threat of targeted password guessing. When an attacker gets more information about a user, the user’s password is more likely to be cracked. Our work implies that for important applications, a multifactor authentication scheme (e.g., [40–42]) is necessary.


## 6. Conclusion

Based on the well-known password guessing modelTarGuess−I and six real-world leaked password datasets, we conduct an in-depth analysis of users’ vulnerable password setting behavior and targeted password guessing. We find three missing elements in TarGuess−I and propose an improved model: TarGuess−I+KPX, which is capable of identifying popular passwords, keyboard patterns, and the special strings. Experimental results show that our improved model outperforms TarGuess−I by 2.62% within 100 guesses. We highlight the threat posed by targeted password guessing. Our modified idea of the special strings sheds new light on password guessing, but the implementation of this idea is not optimal. We will further study in this direction.



---

*Source: 8837210-2020-12-02.xml*