Research And Implementation Of PCFG Dictionary Parallel Generation Method

Password is still an important authentication technology.In recent years,the password database of many websites has been leaked,providing researchers with a large number of real password data.The analysis of a large number of real passwords shows that the passwords generated by users are not random,and they have strong regularity.Finding the inherent regularity and constructing a more efficient cracking dictionary can more effectively solve the problem of weak generalization ability of passwords in the dictionary deformation method.There are two main factors to evaluate password guessing method: cracking rate and dictionary generation speed.The former reflects the ability to crack the target password when the number of guesses is specified;The latter reflects the performance of generating guessing password sequence of specified times,which is related to its practical application ability.Weir et al's password cracking system based on PCFG is an important supplement to the dictionary based password cracking method.The Monte Carlo method proposed by dell'amico et al can calculate the password strength without too much computational effort.At present,probabilistic context free grammar(PCFG)has a high cracking rate in practical applications.However,due to the slow speed of dictionary generation using PCFG method,which is only50 K / s,and the dictionary can only be generated offline and then put into the actual cracking computing system,it is difficult to use large-scale dictionaries for guessing.Therefore,how to improve the dictionary generation method and improve the speed of PCFG dictionary generation has good theoretical and practical value.In this thesis,we use Weir's method of password structure generation based on PCFG and dell'amico's method of predicting the number of guesses by probability to propose a dictionary generation method which can be accelerated by parallel method,so as to improve the speed of dictionary generation by PCFG method,and the speedup ratio can reach853-1276.This thesis uses PCFG's password structure generation method to create PCFG's password structure set by training rockyou and other real plaintext passwords.After sampling the set,the Monte Carlo method is used to process the samples.After improvement,the relationship between the number of guesses and the corresponding probability is obtained.According to the generated rule structure,the Cartesian product of vocabularies is obtained after the vocabularies are extracted according to the probability,and the result is written to disk to generate PCFG dictionary.In the process,the parallel method is used to optimize the generation speed.Because the vocabulary generated by PCFG method is generated in probability non ascending order,it can not be strictly guaranteed after optimization by this method,but it can be improved by multi-level dictionary method to make it basically orderly.