Probabilistic context-free grammar based password cracking: Attack, defense and applications

Passwords are critical for security in many different domains such as social networks, emails, encryption of sensitive data and online banking. Human memorable passwords are thus a key element in the security of such systems. It is important for system administrators to have access to the most powerful and efficient attacks to assess the security of their systems more accurately. The probabilistic context-free grammar technique has been shown to be very effective in password cracking. In this approach, the system is trained on a set of revealed passwords and a probabilistic context-free grammar is constructed. The grammar is then used to generate guesses in highest probability order, which is the optimal off-line attack. The initial approach, although performing much better than other rule-based password crackers, only considered the simple structures of the passwords. This dissertation explores how classes of new patterns (such as keyboard and multi-word) can be learned in the training phase and can be used to substantially improve the effectiveness of the probabilistic password cracking system. Smoothing functions are used to generate new patterns that were not found in the training set, and new measures are developed to compare and improve both training and attack dictionaries. The results on cracking multiple datasets show that we can achieve up to 55% improvement over the previous system. A new technique is also introduced which creates a grammar that can incorporate any available information about a specific target by giving higher probability values to components that carry this information. This grammar can then help in guessing the user's new password in a timelier manner. Examples of such information can be any old passwords, names of family members or important dates. A new algorithm is described that given two old passwords determines the transformations between them and uses the information in predicting user's new password.;A password checker is also introduced that analyzes the strength of user chosen passwords by estimating the probability of the passwords being cracked, and helps users in selecting stronger passwords. The system modifies the weak password slightly and suggests a new stronger password to the user. By dynamically updating the grammar we make sure that the guessing entropy increases and the suggested passwords thus remain resistant to various attacks. New results are presented that show how accurate the system is in determining weak and strong passwords.;Another application of the probabilistic context-free grammar technique is also introduced that identifies stored passwords on disks and media. The disk is examined for potential password strings and a set of filtering algorithms are developed that winnow down the space of tokens to a more manageable set. The probabilistic context-free grammar is then used to assign probabilities to the remaining tokens to distinguish strings that are more likely to be passwords. In one of the tests, a set of 2,000 potential passwords winnowed down from 49 million tokens is returned which identifies 60% of the actual passwords.