## 2 Related Works
### Markov-Based Approaches & PCFG  
In the stochastic approach, a method incorporating the Markov model has been proposed. [PERSON] et al. proposed a method of generating a fake password (or password candidates) using the Markov model for the alphanumeric characters and the Turing machine for special symbols [21]. This method's the fundamental idea is that frequently used words and patterns are limited to easy-to-remember passwords; further, the passwords in this space are included in a specific probability distribution of alphanumeric combinations. [PERSON] et al. used the Markov model as a filter to eliminate the low-probability password candidates. Furthermore, they applied the rainbow table concept (time-space tradeoff) to speed up password cracking. Finally, to handle the passwords with special symbols, the Turing machine concept was adopted. Based on a password generation rule, various alphabets and numbers were combined into regular expressions, and the probability for each combination created was defined. This pioneering work was subsequently extended by [PERSON] et al. [15] and [PERSON] et al. [2].  
[PERSON] et al. [2] proposed an efficient password guesser based on [PERSON]'s model. This model was called the OMEN. Basically, OMEN aimed to improve the cracking speed ofNarayanan's model. It incorporated an improved enumeration algorithm called \"enumPwd\", which enabled it to produce candidates in order of probability by implementing multiple bins. In each bin, candidates of similar probabilities were stored.  
The most important aspect of these password guessing studies was incorporating the PCFG concept into the password-guessing method. PCFG was invented by [PERSON] et al. [22] originally as a password guesser. Current complex passwords have grammatical structure. This grammatical structure is a combination of alphanumerical sequences, special characters, and keyboard-walks. PCFG analyzes the grammatical structure of leaked passwords and calculates the distribution probability from these leaked passwords. For generating password candidates, PCFG uses the grammatical structure in order of the probability. Recently, several studies have improved upon the performance of the PCFG [23; 24; 25]. Based on common current password usage patterns and on government recommendations [26], password guessing must be able to produce grammatical structures that include not only simple alphabetical and numerical combinations but also complex combinations that include special characters and keyboard-walks. PCFG has enabled us to generate these complicated password patterns. In experiments, PCFG exhibited a higher cracking success rate than dictionary-based attacks using Hashcat built-in rules. This method could expand the cracking area of the password space effectively. [PERSON] et al. [24] focused on improving the cracking performance for keyboard-walk structures and employed a smoothing technique. In their experiments, they achieved good performance on cracking keyboard-walk patterned passwords. Furthermore, [PERSON] et al. proposed the use of PCFG as a target-oriented cracking approach [25].  
Finally, [PERSON] et al. [15] attempted to maximize the performance of the probability-based password cracking approaches through optimized configuration and usage. Additionally, they proposed a new way of measuring the password cracking performance. [PERSON] et al. categorized password guessing methods as whole-string or template-based. [PERSON] et al.'s model and OMEN were included in the whole-string models. PCFG was classed as a template-based model. [PERSON] et al. attempted to derive each model's best configuration and introduced the n-gram model for statistical language modeling into password modeling. In the experiments conducted by [PERSON] et al., in several cases, the whole-string Markov models outperformed PCFG. However, specific configurations, such as smoothing, enhanced the performance of PCFG in such a way that it outperformed the whole-string approach.