# Password Similarity Using Probabilistic Data Structures
## 3 Password Similarity  
It is widely known that password reuse is a common behaviour which can turn into a threat if passwords get leaked online [13]. Password leaks are a common form of information leak that happens regularly ([[https://us.norton.com/internetsecurity-emerging-threats-2019-data-breaches.html](https://us.norton.com/internetsecurity-emerging-threats-2019-data-breaches.html)]([https://us.norton.com/internetsecurity-emerging-threats-2019-data-breaches.html](https://us.norton.com/internetsecurity-emerging-threats-2019-data-breaches.html))). A similar threat appears when users are allowed to choose a new password with little variations from the previous one (e.g., password2020 changing password from password2019). This behavior is tempting especially in corporate settings which enforce a policy of frequent password expiration. This can make brute force attacks very effective, since the new password is easily computed by a limited number of mutations starting from a dictionary of leaked ones. We can describe the password mutation as a perturbation of the password with slight variants. Tools such as password crackers or word-lists generators like cupp (A password generator based on personal and open source data: [[https://github.com/Mebus/cupp](https://github.com/Mebus/cupp)]([https://github.com/Mebus/cupp](https://github.com/Mebus/cupp))) or johntheripper (johntheripper is a common password cracker  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Peculiarity** & **RAPFOR [7]** & **SSDD [8]** & **Schnell et al. [5]** & **CTPH [9]** & **Our Method** \\ \hline Detect exact matches & & & & & \\ Detect similarities & & & & & \\ Can be (natively) encrypted locally & & & & & \\ Uses or can use secure hash function & & & & \\ Main focus & Crowdsourcing & Documents & Medical Records & Malware analysis & Passwords \\ Main technology & BF (binary) & BF + HE & BF & PHF & BF \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison between similar approaches. The \(\bullet\) symbol defines a full compliance to the row, the \(\bullet\) symbol denotes a partial compliance, and the \(\circ\) symbol denotes an absence of compliance to the row. The acronyms legend is the following one. BF: Bloom Filter, HE: Homomorphic Encryption, PHFs: Piecewise Hash Functions.  
and generator [[https://www.openwall.com/john/](https://www.openwall.com/john/)]([https://www.openwall.com/john/](https://www.openwall.com/john/))) implement various combination methods for password generation; passwords can also be generated by neural-based techniques such as adversarial generation [14]. Against these approaches, choosing a similar password is almost as insecure as choosing a dictionary password [15]. It is worth noticing that common methods to guide users to choose \"robust\" passwords are focused on avoiding the direct use of dictionary words. These methods have two shortcomings: users resort to variations that are easily discovered by mutation by the aforementioned tools, and there is no detection of password similarity when a password change is mandated.  
For the purpose of this work, password similarity can be informally defined as the structural similarity of the text composing two password being compared, i.e., it has nothing to do with the possible underlying meaning of the string. This definition of password similarity can be used to guarantee that a user is not recycling what, in terms of actual entropy, can be considered the same password every time. A straightforward method to detect password similarity over a meaningful time span would require saving old passwords in clear-text into a database, which is obviously a despicable approach. We propose a solution based on Bloom Filters that overcomes this shortcoming.