CN106803035A - A kind of password conjecture set creation method and password cracking method based on username information - Google Patents

Abstract

The invention discloses a password guessing set generation method and a password cracking method based on user name information. The password cracking method of the present invention is as follows: 1) perform word segmentation and semantic structure labeling respectively on the user name and password in the leaked data training set, and calculate the semantic similarity of the user name and password; wherein, the semantic similarity includes the semantic structure similarity and semantic fragment similarity; 2) apply the semantic similarity to the PCFGs grammar, that is, construct the PCFGs grammar based on the semantic similarity; 3) generate the password guessing set according to the descending order of probability according to the PCFGs grammar constructed in step 2); 4) according to The set of password guesses is used for password cracking. The invention utilizes the fragment similarity and structural similarity of the user name and the password to understand the composition semantics of the password, thereby generating a password guessing set and improving the efficiency of password cracking.

Description

A password guessing set generation method and password cracking method based on user name information

technical field

The invention relates to a password guessing set generation method and a password cracking method based on user name information.

Background technique

For a long time, traditional brute force cracking methods have been used to crack passwords, but this method does not conduct in-depth analysis of passwords, so that the effect and efficiency are not satisfactory.

In some new approaches, ideas and tools from natural language processing are applied to cryptanalysis and cracking. This method regards passwords as some form of natural sentences, which are composed of a series of fragments according to a certain hierarchical structure. Fragments that appear in passwords are usually words, dates, or other meaningful strings in the dictionary, and the combined structure of these fragments often reflects certain fixed patterns. You can use NLTK (Natural Language Toolkit) and WordNet tools to perform word segmentation, part-of-speech tagging, and semantic category tagging on passwords. Then, Probability Context-Free Grammars (PCFGs) in natural language processing are used to learn the grammatical rules for generating passwords, and generate password guess sets in descending order of probability. However, when the attacked website contains many weak passwords, this method proves to be less efficient. In addition, when it is used to crack Chinese website passwords, the cracking efficiency of this method is also poor, because its word segmentation system cannot effectively segment Chinese pinyin.

The main problem with this approach is that it fails to adequately analyze the semantic content of the cipher and the syntax between semantic categories, and fails to assign appropriate probabilities to the words in the dictionary used.

Contents of the invention

The purpose of the present invention is to apply the ideas and tools in the field of natural language processing to the field of cryptanalysis and cracking, decompose and analyze the user name, extract fragments and structural features, and use the fragment similarity and structural similarity of the user name and password to understand The composition semantics of the password, which speeds up the speed of password cracking, is a password guessing set generation method and a password cracking method based on user name information.

In order to use the information contained in the username to improve the efficiency of password cracking, the present invention provides a password guessing generator based on PCFGs and capable of extracting semantic similarity between usernames and passwords, referred to as a password guessing generator based on semantic similarity.

Technical scheme of the present invention is:

A password guessing set generation method based on user name information, the steps of which are:

1) Segment the user name and password in the leaked data training set and mark the semantic structure respectively, and calculate the user name and password.

The semantic similarity of code; Wherein, described semantic similarity comprises semantic structure similarity and semantic fragment similarity;

2) Apply the semantic similarity to the PCFGs grammar, that is, construct the PCFGs grammar based on the semantic similarity;

3) According to the PCFGs grammar constructed in step 2), password guessing sets are generated in descending order of probability.

A password cracking method based on user name information, the steps of which are:

1) Carry out word segmentation and semantic structure labeling respectively to the username and password in the leaked data training set, and calculate the semantic similarity of username and password; wherein, the semantic similarity includes semantic structural similarity and semantic fragment similarity;

2) Apply the semantic similarity to the PCFGs grammar, that is, construct the PCFGs grammar based on the semantic similarity;

3) According to the PCFGs grammar constructed in step 2), password guessing sets are generated in descending order of probability;

4) Perform password cracking according to the password guessing set.

Further, the method of constructing PCFGs grammar based on semantic similarity is as follows: according to the semantic structure similarity of username and password, the password structure with different distributions selected by usernames with different semantic structures is obtained, and the password structure is used as the non-terminal structure of PCFGs grammar ; According to the similarity of the semantic segment of the user name and password, select the semantic segment in the user name and add it to the terminal word set of the PCFGs grammar used to generate the password, and obtain the terminal word set of the PCFGs grammar.

Further, for a segment in the password, if the segment appears in the user name of the leaked data training set, the frequency of the segment in the leaked data training set is multiplied by a probability coefficient α, and the frequency expanded by α times is accumulated to The original frequency of the segment in the terminal word set is used as the new frequency of the segment; if the segment is not contained in the terminal word set, the segment and its frequency information are added together in the terminal word set; Then update the probability distribution of the terminal words in the terminal word set.

Further, the implementation method of step 3) is: a priority queue is established for each non-terminal structure, and the priority queue is used to store the password guesses generated by the corresponding non-terminal structure in descending order of probability; The first element of the queue is traversed to find the password with the highest probability, and the password is dequeued and output to the password guessing set, and then the next password lookup is performed until the number of passwords in the password guessing set reaches the specified value.

Further, the user name and password are marked according to the semantic category word segmentation and semantic structure; wherein, the semantic category includes pinyin name, pinyin abbreviation, pinyin name, pinyin surname, pinyin phrase, other pinyin, English phrase, English name, English Words, other letters, numeric dates, other numbers, single character repetition, string repetition, keyboard equidistant jumps, adjacent characters on the same line of the keyboard, adjacent characters on different lines of the keyboard, and other special symbols.

Further, the measure index of the similarity of the semantic segment includes #1 to #7 seven measure indexes; wherein, the #1 index indicates that the user name contains the semantic category; the #2 index indicates that the user password contains the semantic category; Index #3 indicates that the characters of the semantic category in the username and password are exactly the same; indicator #4 indicates that the characters of the semantic category in the username and password are the same but have case differences; indicator #5 indicates that the characters in the username are characters in the password substring; #6 indicator means that the password is a substring of the user name; #7 indicator means that #2 indicator is satisfied but #3 to #6 indicators are not met.

Further, the leaked data training set is selected from public leaked data sets on the Internet.

The present invention mainly comprises two aspects: (1) at first carry out the analysis and the extraction of user name password similarity to Internet public leakage data set; (2) improve PCFGs algorithm, utilize semantic structure and fragment similarity between user name and password in password Guesses are being generated, and password guesses are generated in strict descending order of probability.

Usually, the leaked password set is usually accompanied by the leak of some other user information, such as username. The user name is regarded as an abstract symbol representing the user's identity in the online world, and together with the corresponding password, it constitutes a barrier to protect the user's privacy in the online world. The creation of user names can reflect some habits and tendencies of users when creating network passwords. After analyzing the leaked password set, we found that Chinese online community users tend to use pinyin and numbers in their usernames and passwords, and pinyin names are very common in usernames. For example: a user whose username is "xiaoming19860805" and whose password is "xm0805" (xm is the pinyin abbreviation of xiaoming). This user uses a pinyin name in their username and the corresponding abbreviation in their password. The date "19860805" appears in the username, while part of the date "0805" is used in the password. Structurally speaking, both the user name and password of this user use the pattern of pinyin name followed by date. Since a set of usernames and passwords are created by the same user, this habit and tendency is likely to be used in the creation of passwords, so in-depth analysis of the composition of usernames can help us better understand the password creation process, thereby More effective password cracking.

Based on the PCFG grammar, the present invention proposes a password generation algorithm capable of extracting and utilizing the semantic structure and fragment similarity between user names and passwords. The password cracking method flow chart of this invention is shown in Figure 1, and it comprises the following contents:

1) Word segmentation and semantic structure annotation are carried out for username and password, respectively, and the measurement index of semantic similarity between username and password is given. Two types of semantic similarity are defined: semantic structure similarity and semantic fragment similarity;

2) Construct PCFGs grammar based on semantic similarity, and generate password guess sets strictly in descending order of probability;

4) Perform password cracking according to the password guessing set.

Based on the experimental results on large-scale public datasets, the effectiveness of the proposed password guess generator based on semantic similarity is proved.

Eighteen semantic categories are defined for Chinese Pinyin, English words, numbers and special symbols (see Table 1). Based on the Contemporary Corpus of American English corpus, Ziguang Pinyin Input Method Pinyin Dictionary, Webster's English Dictionary, and 31 regular expressions for extracting digital dates, the user name and password were segmented, and then the semantic category of the word segmentation results was marked.

Table 1 shows the 18 semantic categories and their simplified representations

Semantic similarity analysis: For the similarity of semantic structure, user names are grouped according to the semantic structure, and the selection of password semantic structure of different groups of users is counted to obtain the probability distribution of different user name password structures. Further analyze the semantic segment similarity of the user name and password, and define seven indicators #1 to #7 to measure the similarity of the semantic segment, and calculate the corresponding ratio according to each indicator, as shown in Table 2. The name contains the semantic category in the left column, and its ratio is the percentage of the number of users who meet the index to the total number of users. The #2 index indicates that the user password also contains this semantic category, and the ratio is the number of users who meet the index. Percentage of the number of semantic category users. For users who meet the #2 indicator, that is, the user name and password contain corresponding semantic categories, the four indicators #3 to #7 carry out further similarity analysis on the content of their user name and password. Index #3 indicates that the character content of the semantic category in the username and password is exactly the same, and its ratio is the percentage of users meeting the indicator to the number of users meeting the indicator #2; indicator #4 represents the character content of the semantic category in the username and password There is only a difference in uppercase and lowercase, and the ratio is the percentage of the number of users who meet the index to the number of users who meet the #2 index; #5 index means that the user name character is a substring of the password character, and the ratio is the number of users who meet the index account for the number of users who meet #2 The percentage of the number of target users; the opposite of the #6 indicator means that the password is a substring of the user name, and the ratio is the percentage of the number of users who meet the indicator to the number of users who meet the #2 indicator; #7 indicates that the #2 indicator is met but not # For indicators 3 to #6, the ratio is the percentage of the number of users who meet the indicator to the number of users who meet the indicator #2.

Table 2 shows the analysis of seven indicators for the similarity of semantic fragments in the leaked dataset

The password guessing generator based on semantic similarity of the present invention mainly comprises the following steps:

1) Segment the user name and password according to the semantic category to obtain the structure and fragments of the user name and password, respectively count the structure and fragments of the user name, the frequency of the structure and fragments of the password, and divide by the respective totals to calculate the probability.

2) Apply semantic similarity to PCFGs grammar: aiming at semantic structure similarity, train users with different semantic structures to select password structures with different distributions. When generating password guesses, adjust it according to the username structure to be cracked. According to the corresponding password structure, the non-terminal structure of PCFGs is obtained; for the semantic segment similarity, the semantic segment of the user name obtained in step 1 is merged with the semantic segment of the password, and an adjustable weight is set for the terminal word probability in the user name parameter, to get the terminal word set of PCFGs; the weight parameter is obtained through experiments, such as traversing 1 to 500, and selecting the parameter with the best experimental effect.

3) After the PCFGs grammar is established, the next step is to generate password guess sets in descending order of probability. The present invention designs a new password guessing generating function Generating_Guesses. The main idea is to establish a priority queue for each non-terminal structure. This priority queue can generate and store password guesses strictly in descending order of probability for the corresponding non-terminal structures. When finally generating password guesses, all priority The first element of the super-level queue (that is, the password with the highest probability in the queue) is traversed to find the password with the highest probability, and the password is dequeued and output to the password guessing set, and then the next password search is performed until the password guessing set is set When the number reaches the specified value, the guess set is constructed.

The above step (2) "applying semantic similarity to PCFGs grammar" is the core of the present invention. The application of semantic structure similarity and semantic content similarity will be described in detail below.

Semantic structure similarity means: users with different username structures have differences in password structure selection, users with the same username structure tend to choose similar password structures; users tend to use the same semantic category between their username and password , even username and password have exactly the same semantic structure. When conducting a cross-site attack, the attacker has the username and password of compromised website A, and the username of attacked website B. Therefore, in order to apply the semantic structure similarity, the PCFGs trained on the A data set should use the user name information of the B website to modify the user name derivation rules and probabilities: the probability distribution of the non-terminal structure of the user name should be in the user name data of the B website on for training. The non-terminal structure probability distribution of the password derived from the non-terminal structure of the user name and the probability distribution of the terminal words of the password are completed on the data set A. Because the password information of website B cannot be obtained, this kind of training is based on the semantic similarity conclusion: users who use the same username structure tend to choose a similar password structure. Then the use of passwords of certain types of users on website A can reflect the use of passwords of such users on website B to a certain extent. For example: record the PCFGs trained on the 12306 data set as PCFGs|Dist.(US_12306), and use the leaked data set information of 12306 to attack CSDN, the probability distribution of the non-terminal structure of the user name, and the probability distribution of the terminal words of the user name It should be recalculated using CSDN username data. The new PCFGs obtained are denoted as PCFGs|dist(US_CSDN), and the flow chart is shown in Figure 2.

Define PW _i =<ps _i1 , ps _i2 , . . . >. PW _i represents a collection of password structures used by users whose username structure is us _i . According to the semantic structure similarity, users with the same username structure tend to choose a similar password structure, and it can be determined that the password structure of the user whose username structure is us _i obeys the password structure distribution ps _{i of us i .} Then if the user name structure us _i is used more frequently in the username of the attacked website than in the training set, the related password structure ps _ij will be given a higher probability. The specific password structure probability calculation formula is as follows (taking 12306 attacking CSDN as an example):

F(ps _j )|dist(US _CSDN )＝∑ _i F(us _i )*F(ps _j |(US_12306，us _i )) (1)

In formula (1), F(.) represents the probability function, F(ps _j |(US_12306, us _i )) represents the user group whose username structure is us _i in the 12306 data set, and the probability of choosing the password structure ps _j ( That is, the probability of the non-terminal structure in the priority queue), ps _j is the global password structure distribution.

Semantic fragment similarity means that users tend to use the same or similar semantic content in usernames and passwords. First, multiply the frequency of the semantic segment words in the user name in the training set by a probability coefficient α, and add the frequency expanded by α times to the original frequency of the word in the password terminal word set ∑ set as the new frequency of the word . If the semantic segment word is not included in the password terminal word set Σ, then the word is added to Σ together with the frequency information as a new terminal word. The larger the α value, the greater the frequency of the word in the password terminal word set Σ, which results in the expansion of the frequency of the word when generating the password. The above operations change the number and frequency of words in the password terminal word set Σ, and then carry out probability normalization to obtain the probability distribution of terminal words in the final set Σ.

Compared with prior art, effect of the present invention:

In order to evaluate the cracking method of the present invention based on the semantic similarity of username and password, we conducted comparative experiments on different data sets with the traditional PCFG grammar constructed by Weir and the current mainstream password cracking software John the Ripper. The sources of the experimental data set include CSDN, Sina Weibo, Duduniu, 178, 7k7k, and 17173 leaked account and password sets, totaling 51 million accounts. Due to computer performance limitations, the number of password guesses in each experiment was limited to 100 million.

Figure 3 shows the impact of semantic structure similarity on password cracking efficiency. All methods use the CSDN leaked password set as the training set, and attack the Sina Weibo password set. In the first 10,000,000 guesses, although the ratio of finally guessed passwords is similar, the guessing success rate growth rate of the method Sim_PCFG_on_LD of the present invention is obviously higher than Weir's PCFG (Weir_PCFG_on_LD) and John the Ripper software (JtR_with_Mangling). To guess 31.3% of the passwords, the number of guesses required by the methods JtR_with_Mangling, Weir_PCFG_on_LD and Sim_PCFG_on_LD of the present invention are: 1.73*10 ⁶ , 2.32*10 ⁶ and 1.30*10 ⁶ . This experiment shows that the method using semantic structure similarity can improve the speed of password cracking.

Figure 5 is the graph of the experimental results comparing the probability coefficient α. The CSDN leaked password set is also used as the training set, and the Sina Weibo password set is attacked. Select the results with α values of 1, 4, 15 and 500 for display. It can be seen from the figure that when the value of α is 4, it has the best performance in terms of efficiency and effect.

Figure 4 is an experimental diagram of the influence of semantic segment similarity on password cracking efficiency. The leaked password sets of 17173 and Sina Weibo were targeted respectively, and all methods were trained on the other four data sets to conduct cross-attacks on 17173 and Sina Weibo. As can be seen from the attack graph for 17173, depending on the selected training set, Sim_PCFG_on_LDU4, which utilizes two semantic similarity methods, increases the number of successful password guesses by about 14.0% to 25.5% compared with Weir's PCFG method, which is higher than John the Ripper improved roughly 55.3 percent to 81.6 percent. Among the four attacks on Sina Weibo, the cracking efficiency of the method Sim_PCFG_on_LDU4 is better than that of Weir and John the Ripper in all three attacks. The exception occurs in the attack that uses the password leaked from the Duduniu website as the training set. After comparing the leaked password sets of Duduniu and Sina Weibo, it was found that the two datasets had 88.8% of the same usernames and passwords. Such a high degree of coincidence makes Weir's method more efficient in this attack, because Weir's PCFG method generates fewer new passwords different from the training set than the method Sim_PCFG_on_LDU4, so that the distribution of the password guessing set is similar to the original training set more similar.

Description of drawings

Fig. 1 is the flowchart of password cracking method of the present invention;

Figure 2 is the training process of PCFG (Sim_PCFG) based on semantic similarity on the 12306 data set;

Figure 3 is the impact of semantic segment similarity on password cracking efficiency;

Figure 4 shows different training sets attacking 17173 and Sina Weibo

(a) training set 178 and test set 17173, (b) training set 7k7k and test set 17173, (c) training set csdn and test set 17173, (d) training set dodonew and test set 17173, (e) training set 178 and test set sinaweibo, (f) training set 7k7k and test set sinaweibo, (g) training set csdn and test set sinaweibo, (h) training set dodonew and test set sinaweibo;

Figure 5 shows the performance comparison of different probability coefficient α values.

detailed description

Take the CSDN leaked password library as the training set, the 12306 leaked database as the target set, and the LDU4 method (the probability coefficient α value is 4) as an example:

1) Extract password structure S ₁ and fragment T ₁ from the CSDN database, extract user name structure S ₂ and fragment T ₂ from the 12306 database;

2) Add S ₂ to S ₁ , S ₁ directly adds the frequency of each structure in S ₂ , and then globally counts the probability of each structure;

3) Add T ₂ to T ₁ , T ₁ directly adds the frequency of each terminal word in T ₂ multiplied by 4, and then globally counts the probability of each terminal word;

4) Add the Contemporary Corpus of American English corpus, Ziguang Pinyin Input Method Pinyin Dictionary, Webster's English Dictionary and other dictionaries to T ₁ . At this point, the S and T of PCFGs are generated, and then sorted according to the probability from large to small.

An example of the result of S is as follows:

An example of the results of T is as follows:

5) Generate a global priority queue, and calculate the probability of selecting the highest probability terminal word combination for each structure, and the largest in the queue is the password guess with the highest probability. The structure with the highest probability in the global priority queue is "K_CONTINUOUS", the terminal word with the highest probability is "123456789", and the probability of guessing the first output password is 0.0567154276067*0.217089432985=0.012312320020632619. Then output password guesses in descending order of probability.

6) Generate 100 million password guessing sets, and compare the target set 12306 at the same time to see if it can be hit, and output the number of times and hit rate every 10,000 password guesses as the experimental results. Such as:

10000,0.153374333063

20000,0.177067680864

...

99990000,0.538215278411

100000000,0.538219720953.

Claims (8)

1. a kind of password based on username information guesses set creation method, and its step is：

1) participle and semantic structure mark are carried out respectively to the user name in leak data training set, password, user name, close is calculated The Semantic Similarity of code；Wherein, the Semantic Similarity includes semantic structure similitude and semantic segment similitude；

2) Semantic Similarity is applied in PCFGs grammers, i.e., PCFGs grammers is built based on Semantic Similarity；

3) according to step 2) build PCFGs grammers, according to probability descending generation password conjecture collection.

2. a kind of password cracking method based on username information, its step is：

1) participle and semantic structure mark are carried out respectively to the user name in leak data training set, password, user name, close is calculated The Semantic Similarity of code；Wherein, the Semantic Similarity includes semantic structure similitude and semantic segment similitude；

2) Semantic Similarity is applied in PCFGs grammers, i.e., PCFGs grammers is built based on Semantic Similarity；

3) according to step 2) build PCFGs grammers, according to probability descending generation password conjecture collection；

4) guess that collection carries out password cracking according to the password.

3. method as claimed in claim 1 or 2, it is characterised in that the method that PCFGs grammers are built based on Semantic Similarity For：According to user name, the semantic structure similitude of password, the distribution obtained selected by the user name of different semantic structures is different Cryptography architecture, using cryptography architecture as PCFGs grammers nonterminal structure；According to user name, the semantic segment similitude of password, The semantic segment chosen in user name is added in the terminal set of words of the PCFGs grammers for generating password, obtains PCFGs languages The terminal set of words of method.

4. method as claimed in claim 3, it is characterised in that for the fragment in password, if the fragment appears in leakage In the user name of data training set, then the frequency by the fragment in leak data training set is multiplied by a probability coefficent α, and will Expand α times of frequency and be added to new frequency in the terminal set of words in the original frequency of the fragment as the fragment；If institute State in terminal set of words without the fragment, then the fragment and its frequency information are added in the terminal set of words together；So The probability distribution of terminal word in the terminal set of words is updated afterwards.

5. method as claimed in claim 3, it is characterised in that the step 3) implementation method be：It is each nonterminal knot Build and found a priority query, the priority query is used to store the password that corresponding nonterminal structure is generated by probability descending Conjecture；Then first element to all priority queries is traveled through, and finds out the password of maximum probability, and the password is gone out into team Arrange output and guess collection to password, then carry out password lookup next time, until password conjecture concentrates password quantity to reach setting.

6. method as claimed in claim 1 or 2, it is characterised in that to user name, password according to semantic classes participle and semanteme Structure is marked；Wherein, the semantic classes include phonetic name, phonetic initials, phonetic name, phonetic surname, phonetic phrase, its His phonetic, English phrase, english name, English word, other letters, alphanumeric data, other digital, single character repetition, words Symbol string is repeated, keyboard equidistantly jumps, same line character is adjacent on keyboard, different line characters are adjacent on keyboard and other special symbols Number.

7. method as claimed in claim 6, it is characterised in that the measurement index of the semantic segment similitude includes #1 to #7 Seven measurement indexs；Wherein, the semantic classes is contained in #1 index expressions user name；Contain in #2 index expression user ciphers The semantic classes；The character content of the semantic classes is identical in #3 index expression username and passwords；#4 indexs are represented The character content of the semantic classes is identical in username and password but has capital and small letter to distinguish；It is close that #5 indexs represent user name character The substring of code character；#6 indexs represent the substring that password is user name；The representative of #7 indexs meets #2 indexs and is but unsatisfactory for #3 to #6 Index.

8. method as claimed in claim 1 or 2, it is characterised in that the leak data training set is disclosed selected from internet Leak data collection.