5
$\begingroup$

I'm writing something where a character needs to crack a file. Brute force is the only option, and restricting the search space is the only way not to spend eternity on it.

The problem

  • Our hero does not know $l$, the length of the password, but he estimates that it's at least 12 characters long.
  • The alphabet of the search space is uppercase English letters (26), lowercase English letters (26), digits (10), and special characters (33), for a total size of 95 characters.
  • Our hero assumes the password isn't stupid, so he rules out all passwords that do not:
    • contain at least an uppercase character
    • contain at least a lowercase character
    • contain at least a digit
    • contain at least a special character
  • Also, our hero can reasonably guess $k<l$ different characters of the passwords. He knows they are letters, but they can be either upper- or lowercase, and he does not know where they are in the password.

The reasons don't matter here, but I need to show the password in the novel; this means that I'd rather be careful with its length, the number of known characters, and to an extent, the speed of the computer used to decrypt the file. This is sci-fi we're talking about, so I do have quite some wiggle room in terms of computing speed (whatever it is, it's gonna be faster than any real supercomputer), but if I'm not careful I might still pick a password that would require a ridiculously fast computer to crack in the short time I need (days); that's why I need to calculate the size of the search space I outlined above, so I can tweak $k$ (known characters) and $l$ (password length) to establish a reasonable computing speed even for fiction.

Here's my math. I don't trust myself very much on it so I'd like a sanity check.

As said, our hero will check all passwords of length 12 and above. For a generic password of length $l$ with an alphabet of size 95, the search space $N$ should be

$$N = 95^l,$$

because each and every of the $l$ characters can take any of the 95 possible values. However, since our hero is checking all passwords of length 12 and above, the search space gets larger:

$$N = \sum_{n = 12}^{l} 95^n$$

However, our hero knows that $k$ characters of the password are for sure six different English letters, either uppercase or lower case, though he doesn't know where they are in the password. This means that, of the $l$ characters of the password, only $l-k$ can take any of the 95 values of the alphabet; the remaining $k$ characters can take only fewer. The first of these $k$ characters can have any of 12 values (6 letters $\times$ 2 formats, upper or lowercase); the second can have only 10 (one letter in both its variants has already been chosen), the third only 8, and so on. This parameter depends on $k$, and we call it $\gamma_k$:

$$\gamma_k = \prod_{n = 0}^{k-1} (l-2n)$$

So, for a password of fixed-length $l$ with $k$ known characters, you'd expect the search space to be

$$N_k = \gamma_k\sum_{n = 12 - k}^{l-k} 95^n,$$

but that doesn't take into account the fact that the $k$ known characters could be placed anywhere in the password. The first one could be placed in $l$ different ways; the second in $l-1$, and so on, meaning that the actual search space should be

$$N_k = \gamma_k\sum_{n = 12 - k}^{l-k}\frac{(n+k)!}{n!} 95^n.$$

This space is HUGE, but our hero can still reduce it down to $N_k^R < N_k$ thanks to the rules outlined above. To compute $N_k^R$, I reasoned as follows.

The way $N_k$ has been built, at least 6 characters are letters; this means that it's not accounting for any passwords made only of digits, of symbols, or a combination of the two; this kind of password is excluded from the search as per our rules, but we don't need to worry about them because $N_k$ already excludes them. However, we do need to rule out passwords that are purely alphabetical, or alphanumeric without special characters, or "alphaspecial" without digits. We also need to rule out passwords where letters are all lowercase or all uppercase.

The number of purely alphabetic passwords given that we known $k$ characters should be

$$A_k = \gamma_k\sum_{n = 12 - k}^{l-k}\frac{(n+k)!}{n!} 54^n,$$

where 54 is 26 + 26, that is an alphabet of only uppercase and lowercase letters. $A_k$ is also accounting for any purely alphabetic passwords that are all uppercase or all lowercase. but not for passwords that include upper- or lowercase letters AND digits or special characters.

To account for the latter, we can compute the number of passwords such that:

  • If they contain letters, they're all uppercase
  • Can contain digits or special characters.

This number should be

$$U_k^M = k!\sum_{n = 12 - k}^{l-k}\frac{(n+k)!}{n!} 69^n,$$

where $k!$ replaces $\gamma_k$ because the $k$ known letters can only be uppercase, and hence the first can be chosen in $k$ different ways, the second in $k-1$, etc; the remaining letters can't be uppercase, and hence the alphabet they're drawn from consists of only 69 characters rather than 95.

The size of the set of passwords such that they can contain digits or special characters, and if they contain letters these are all lowercase, is identical, but we denote it as $L_k^M$ for clarity.

Now, we can shrink $N_k$ by subtracting these numbers from it, but there's a small issue: among the passwords that $U_k^M$ and $L_k^M$ are counting, there also are passwords that are purely alphabetical, which are already accounted for by $A_k$, so we need to add them back lest subtracting them twice. These passwords are

$$U_k = L_k = k!\sum_{n = 12 - k}^{l-k}\frac{(n+k)!}{n!} 26^n,$$

that is, purely alphabetical passwords where all characters are either uppercase ($U_k$) or lowercase ($L_k$).

Ultimately, I think the reduced space should be

$$N_k^R = N_k - L_k^M - U_k^M - A_k + L_k + U_k.$$

Questions

  1. Do you agree this is how you compute what I need? Am I leaving anything out\doing anything wrong?
  2. I implemented this thing in JavaScript to figure out the best values for $k$ and $l$ (as well as the speed of the decrypting computer). Somehow, it turns out that the larger k is, the longer it takes to decrypt the file, i.e. the more characters you know, the more difficult it is to find the right password, which sounds absurd. This might be because:
    1. My implementation is wrong somewhere.
    2. My math is wrong somewhere.
    3. Knowing what characters are in the password without knowing where they are is effectively worse than not knowing them, because even though $k$ characters have fewer possible values, you need to try them in every possible place and this might end up requiring more attempts than just traditional brute-force. What I'd need from you guys is help determining whether this a math issue or not--if it's not, it's a code problem and I will deal with that on a different SE.
$\endgroup$
1
$\begingroup$

In your expression for $N_k$, you need another factor of $k!$ in the denominator. This is because the order of the $k$ locations you choose does not matter. This partially explains why your numbers are too large.

Still, your method of computing $N_k$ is still fundamentally flawed. The problem is that you are first choosing where the known characters will go, then choosing the remaining characters arbitrarily. However, if the remaining characters also happen to contain the known characters, then that password will be counted multiple times by your procedure.

Let me make some simplifying assumptions:

  • assume the password length is known to be exactly $l$. This makes the protagonist's job only negligibly easier, since the vast majority of passwords will have the maximum length.

  • forget the requirements of at least one lowercase, uppercase, number and symbol. Again, these do not restrict the number of passwords too much.

The number of possible passwords is now simply $95^l$. It turns out that the number of passwords which contain $k$ given distinct letters, whose cases are unknown, is the following: $$ \sum_{j=0}^k(-1)^j\binom{k}j(95-2j)^l=95^l-k\times 93^l+\binom{k}2\times 91^l-\dots $$ This is a type of complimentary counting; we take all $95^l$ passwords, and for each of the $k$ known letters, you subtract the passwords which do not contain that letter. This explains the first two terms; the higher order terms correct for double counting in a precise way. This is called the principle of inclusion exclusion.

Let's look at an extreme example. Suppose the length of the password is $12$, and $8$ characters are known distinct letters. Then \begin{align} \text{total # passwords} &= 95^{12} &\approx 2^{78.8} \\ \text{reduced # passwords} &= \sum_{j=0}^8(-1)^j\binom{8}j(95-2j)^{12} &\approx 2^{58.0} \end{align} So the number of bits of security went down from $78.8$ to $58$.

$\endgroup$
2
  • $\begingroup$ FYI, there's a typo in the formula, it should be (-1)^j. Also there's a 9 in in your example with should be 8, I think. Other than that, this worked like a charm! $\endgroup$
    – Nicola
    Sep 21 '20 at 18:01
  • $\begingroup$ @Nicola Thank you, fixed! $\endgroup$ Sep 21 '20 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.