# Password Similarity Using Probabilistic Data Structures
## 4 Experimental Analysis  
The specified method to check password similarity was been implemented in C language. The hash functions used was the standard OpenSSL ([[https://www.openssl.org/](https://www.openssl.org/)]([https://www.openssl.org/](https://www.openssl.org/))) implementations of hash functions, in this case MD5. The system was checked on a Ubuntu 18.04 system running in a VirtualBox virtual machine with 2 virtual CPUs and 1 GB of memory. The hypervisor ran over an Intel core i7-8700 cpu which clock frequency runs at 3.2 GHz, and the host was used exclusively to run the test VM. The random data were provided by /dev/urandom to avoid blocking behaviour [42] and read to generate random hash functions. We used the following queries used to check the filter:1. \(\beta\gets Create(\Gamma,\kappa)\)
2. \(Insert(\beta,AAAAA)\)
3. \(Insert(\beta,BBBB)\)
4. \(Check(\beta,AAAAA)\)
5. \(Check(\beta,CCCC)\)
6. \(Check(\beta,BBBB)\)  
In this case the hash dimension seemed not to influence the performances of the filter. The computational load was dominated by the generation of the salt string. The performance of the salt string generation presented in Figure 5 is the average of the results of five runs of experiments, in which the size of the salt changed from 1 (really easy to brute-force) to 1000 (really hard to brute-force). As shown in the graph, the performance decreased linearly when the salt size increased. This happened because a single random character of the salt must be multiplied by the number of hash functions present in the filter. The \(QInsert\) and \(Distance\) performances were evaluated using the following querying pattern:  
1. \(\beta_{1}\gets Create(\Gamma,\kappa)\)
2. \(QInsert(\beta_{1},thisismypassword,2)\)
3. \(\beta_{2}\gets Create(\Gamma,\kappa)\)
4. \(QInsert(\beta_{2},thisismypassword,2)\)
5. \(\beta_{3}\gets Create(\Gamma,\kappa)\)
6. \(QInsert(\beta_{3},thisismypassword,2)\)
7. \(Distance(\beta_{1},\beta_{2})\)
8. \(Distance(\beta_{1},\beta_{3})\)  
In this test run, as in the _Insert_ evaluation, the computational load was dominated by the filter generation. This system was also tested using ca. 5000 credentials from real-world leaked institutional logins. Data were clustered and analyzed using the filter, to observe which values were correctly identified as similar. The graph in Figure 5 represents the analysis of the filter's precision. The graph also shows the edit distance between the various strings. The plots in Figure 6a-d are the experimental confirmations of the sizing criteria presented in Section 3.2. These graphs were generated using different credentials from the ones in Figure 5a,b, to confirm the general applicability of the filter. The data set was generated taking the common password database rockyou.txt (The one available in Kali Linux Distribution, [[https://www.kali.org/](https://www.kali.org/)]([https://www.kali.org/](https://www.kali.org/)), under /usr/share/wordlists/rockyou.txt.gz), inserting in the filter 5000 random-chosen credentials, and comparing them with 5000 other credentials randomly generated using a password generator tool such as APG [43]. As clearly highlighted from the graphs, there was not a big performance gap  
Figure 5: Speed of initialization of the filter and performances compared to edit distance. (**a**) Creation time of the filter changing the size of the salt strings. (**b**) Performances of the filter compared to the edit distance applied to the password data set. between the two algorithms used, the secure cryptographic hash function SHA512 and the insecure MD5. Furthermore, the behaviour of the system respects the previously described formulae: a bigger filter size reduced the probability of a false positive. The hash functions number had a different impact on the scheme: it could degrade the performances if we chose a non-optimal number of functions.