1. Thougts about Passwords

1. Introduction

This Project is about making an educated guess to derive an unknown password based on hacked password lists (Google: “RockYou”). In this section we will introduce the mathematical framework to handle passwords and develop a simple brute force approach based on very unrealistic Assumptions. During this Project these Assumptions will then be weaken to derive in the end a clever method to guess passwords.

1.1. Formulation

Let $X \in \mathbb{X} \, ,X=x_1 x_2 x_3 \dots x_E$ be a password and the random variables $x_i \in \mathbb{A}, E \in \mathbb{N}^+$ the corresponding letters and password length. $\mathbb{X}$ is the space of all passwords and $\mathbb{A}$ corresponds to the used alphabet, for example if we allow only for lower case letters then $\mathbb{A} =\{a,b,c, \dots, y,z \}$ . As usual this forms a discrete probability space given by $(\mathbb{X}, P)$ .

2. First Attempts

2.1 A first naive approach

Let $X^* \in \mathbb{X}$ be the true password. The idea of a brute force search, where every possible password is successive tested, is then to assume that $\mathbb{P}(X^*=X) = \mathbb{P}(X^*=Y) \; \forall X^*,X,Y \in \mathbb{X}$ . This means that every possible password is equipropable and the testing order is thus irrelevant. It is obvious that this Assumption is not true in general.

2.2 A very simple Educated Guess Procedure

In the next step we will replace this assumption by some less strong assumptions:

E is distributed with distribution $f_E$ .
$x_i, \, i=1,\dots,E$ are independent and identically distributed random variables with distribution $f_x$ .
$x_i$ and $E$ are independent.

Under the given Assumptions the best way to “guess” the password is given by the following procedure. Since $x_i$ and $E$ are independent we can apply a two step procedure where we first draw some $\hat{E}$ using $f_E$ .Then each $x_i, \; i=1,\dots,\hat{E}$ is independently drawn using $f_x$ . Since $f_E$ and $f_x$ are unknown they have to be estimated from hacked passwords list which we will denote as $\mathbb{L} \subset \mathbb{X}$ .

2.2.1 Checking the password security

Under the given Assumptions it is also possible to estimate the “safeness” of given password $X^*$ . Mathematically this means 1 minus the probability that a certain password is “guessed” by the procedure. The first part, the probability that the “correct” password length is “guessed” is simply given by $P(E=E^*)=f_E(E^*)$ . The second part can be understood as $E$ urn draws with replacement of an urn containing the elements of $\mathbb{A}$ where the probability to draw a certain element $x$ is given by $f_x(x)$ . Thus $P(x_1= x^*_1, \dots, x_E = x^*_E |E=E^*)= \prod_{i=1}^{E^*} f_x(x_i^*)$ . Accordingly by Bayes’ theorem: $1 -P(x_1 \dots x_E = x^*_1 \dots x^*_E \cap E=E^* )=1- f_E(E^*) \prod_{i=1}^{E^*} f_x(x_i^*)$ as security index.

2.2.2 Density Estimators

A very simple estimator $\hat{f}_E$ is based on counting the length of all passwords in $\mathbb{L}$ . The corresponding estimator is then given by $\hat{f}_E(E^*)= \frac{\# (X \in \mathbb{L} |E=E^*)}{\# \mathbb{L}}$ and accordingly $\hat{f}_x(x^*)= \frac{ \sum_{k=1}^\infty \# (X \in \mathbb{L} |x_k=x^*)}{ \sum_{k=1}^\infty k \cdot \# (X \in \mathbb{L} |E = k) }$ .

338