2
$\begingroup$

I'm doing a password cracking challenge right now, and I know several restrictions of the password.

  • The password is 8 characters long
  • The first character is a lowercase letter, the second character is a digit
  • The seventh and eighth characters are both lowercase letters
  • The remaining characters (third, fourth, fifth, sixth) are all uppercase letters, EXCEPT for one, which is a lowercase letter, and another, which is a digit.

I'm considering taking two approaches to cracking this password: a masked brute-force approach and a hybrid rules/brute force approach.

The masked brute force approach would see me processing a maximum of $$26\times10\times62\times62\times62\times62\times26\times26 \approx \bf{2.597\times10^{12}},$$ candidates, which for a decent GPU processing at $8000 \text{ kH/s}$ would take around 90 hours.

This approach doesn't take advantage of the knowledge that the third, fourth, fifth, and sixth characters can only contain one digit and one lowercase letter, so I figured I could optimize this brute force approach by generating a much more restricted set of candidates and using rules to generate possibilities based on that.

I did this by generating a list of $26*10*26*26*26*26*26*26 \approx 8*10^{10}$ candidates, using lowercase letters for the first, seventh, and eighth characters, a digit for the second character, and uppercase letters for the third, fourth, fifth, and sixth characters. This list of candidates is then put through a list of 120 rules (40 possible permutations of a random digit in positions 3, 4, 5, or 6 times 3 possible ways to lowercase a singe remaining letter) which cover all combinations of one added digit + one lowercase character, giving me $8*10^{10} * 120 = 9.6*10^{12}$ total candidates.

My question is:

How is it possible that the first, brute-forced list, including candidates that could not possibly be correct (too many lowercase chars or digits), is smaller by almost four times than the tailored list that should exclusively contain candidates that fit the restrictions?

Am I unknowingly creating tons of duplicates, or did I make a mistake somewhere in my math that I missed?

$\endgroup$
6
  • $\begingroup$ Well, your second computation ignores the case of the letters. As there are two choices for case, the $26's$ should be $52's$. $\endgroup$
    – lulu
    Oct 3, 2020 at 17:09
  • $\begingroup$ The second computation purposely only calculates lowercase letters in the first, seventh, and eighth positions, and uppercase letters in the third, fourth, fifth, and sixth positions; since we know there can only be one lowercase letter in positions three, four, five, and six, and one of those has to be a digit, there are only three possible ways for each candidate's case to be toggled (which is why I used rules to calculate those instead, and why the second computation's intermediate value is multiplied by 120 to get the final result.) $\endgroup$
    – A. Vance
    Oct 3, 2020 at 17:12
  • $\begingroup$ I think it isn't clear what your two cases are counting. There are so many options involved. $\endgroup$
    – lulu
    Oct 3, 2020 at 17:14
  • $\begingroup$ The two cases are counting possible password candidates for breaking a password that matches the given restrictions. $\endgroup$
    – A. Vance
    Oct 3, 2020 at 17:18
  • $\begingroup$ Yes, but there are so many options that it isn't clear which restrictions you are following at any time. Just say exactly what rules you are following for the first count, and what rules you are following for the second count. $\endgroup$
    – lulu
    Oct 3, 2020 at 17:21

2 Answers 2

3
$\begingroup$

I'll focus only on the third, fourth, fifth and sixth characters, as the rest is the same in both cases.

In your first approach, where you overestimate the number of passwords, you simply consider all options for all four characters, yielding $$(26+26+10)^4=62^4,$$ options. In your second approach, which is less clear, you start from $26^4$ options, suggesting $4$ characters and then consider some permutations: You consider $40$ options for the digit, and then $3$ options for the lowercase letter, yielding $$26^4\times40\times3.$$ But then you should have started with only $3$ characters, i.e. with $26^3$ instead of $26^4$.

A more structured approach would be to first choose the positions of the digit and the lowercase letter; there are $4\times3=12$ options. Then choose $2$ uppercase letters, $1$ lowercase letter and a digit, yielding $$12\times26^3\times10.$$

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the edit! This helped me realize where I was wrong; I'm going to try generating the list of candidates in a different way, choosing where the digits are first. $\endgroup$
    – A. Vance
    Oct 3, 2020 at 19:57
0
$\begingroup$

Consider only the $4$ central characters in your second calculation. Start by creating all possible upper-case four-letter strings, $AAAA, AAAB, AAAC, \dots, AAAZ, \dots, ZZZY, ZZZZ$.

Next, for each of the generated strings, replace one of the letters with a digit. As an example, consider only replacing the last letter with the digit $1$.

The above sequence becomes $AAA1, AAA1, AAA1, \dots, AAA1, \dots, ZZZ1, ZZZ1$, and it's easy to see that it is checking the same case several times. Ultimately, this leads to more checks overall.

It's not simply $26$ times as may checks though, because strings such as $aaa1, bbb1, 1111, a1Z1$ and many, many more are no longer checked.

$\endgroup$

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.