Password-space combinatorics and cracking time

The question, set up precisely

A site requires passwords of exactly 10 characters, drawn from four classes:

• 26 lowercase letters,
• 26 uppercase letters,
• 10 digits,
• 32 special characters — the printable ASCII punctuation, which is four separate ranges: codes 33–47 (15 characters), 58–64 (7), 91–96 (6) and 123–126 (4). Add them: $15+7+6+4=32$.

The alphabet is therefore $26+26+10+32=94$ characters. The rule also requires at least one character from each of the four classes. How many passwords satisfy it?

Why $94^{10}$ is the wrong answer

$94^{10}$ counts every string of ten characters over the alphabet. It is the count with no composition requirement, and it includes strings the rule forbids — aaaaaaaaaa, PASSWORD12, anything with no special character at all. A requirement removes strings; it never adds any. So the answer must be smaller than $94^{10}$, and any method that produces a bigger number has the logic inverted.

The other tempting move is worse because it looks like counting. "Pin one position for each required class, then fill the rest freely": $10\times 9\times 8\times 7\times 94^6$, or the sloppier $4\times 94^9$. Both overcount massively, because a password containing three digits is produced many times over — once for each choice of which digit was 'the' required one. Choosing positions and then filling them freely double-counts, and there is no clean way to divide the duplication out.

Inclusion–exclusion, worked

Count the complement instead. Let $A_1$ be the set of length-10 strings containing no lowercase letter, $A_2$ no uppercase, $A_3$ no digit, $A_4$ no special. A string is bad exactly when it lies in at least one $A_i$; every other string satisfies the rule. Inclusion–exclusion gives the good count directly as an alternating sum over which classes are omitted:

$$N=\sum _{S\subseteq \{1,2,3,4\}}(-1{)}^{|S|}{\left(94-\sum _{i\in S}{c}_i\right)}^{10}$$

where $c_i$ is the size of class $i$. There are $2^4=16$ subsets. Read the sum term by term:

• $|S|=0$ — one term, $+94^{10}$: every string.
• $|S|=1$ — four terms, subtracted. Drop lowercase and $94-26=68$ characters remain, so $-68^{10}$; drop uppercase, $-68^{10}$; drop digits, $-84^{10}$; drop specials, $-62^{10}$.
• $|S|=2$ — six terms, added back, because a string missing both lowercase and digits was subtracted twice above. Example: $+(94-26-10{)}^{10}=+58^{10}$.
• $|S|=3$ — four terms, subtracted again. Example, keeping only the specials: $-32^{10}$.
• $|S|=4$ — one term, $+0^{10}=0$: no characters left, no strings.

Running the sum gives

$$N=32,333,391,317,360,640,000\approx 3.23\times 10^{19}$$

against $94^{10}=53,861,511,409,489,970,176\approx 5.39\times 10^{19}$. The composition rule admits 60.03% of the unrestricted space — a reassuring sanity check, since the answer is smaller than $94^{10}$ but the same order of magnitude. If your inclusion–exclusion produces a ratio outside roughly 0.5 to 0.7 here, you have dropped a term or flipped a sign.

Notice what the rule cost the defender. Insisting on all four classes threw away 40% of the space — while, in exchange, removing the all-lowercase passwords that attackers try first. That trade is the honest argument for composition rules, and it is a much weaker argument than most policies assume.

From a count to a time

A count is not an answer to "how long would this take?" until you state a rate. That is the marked step, and leaving it implicit is the commonest way to lose marks on this question.

At $10^9$ guesses per second — a defensible figure for one well-equipped attacker with GPU hardware:

$$\frac{3.2333\times 10^{19}}{10^9}=3.2333\times 10^{10}\text{seconds}$$

A year is $365\times 24\times 3600=31,536,000$ seconds, so that is about 1,025 years. Raise the rate a thousandfold to $10^{12}$ guesses per second — a serious distributed effort — and the same space falls in about 1.03 years. Drop it to $10^6$ and it is over a million years. Three orders of magnitude in the rate move the answer by three orders of magnitude in the time, which is why the rate must be stated rather than assumed.

Two honest qualifications belong in any full answer.

First, the figure is the time for an exhaustive search of the whole space, so on average you succeed in half of it. Second, and far more important: no real attacker searches uniformly. Human password choice is enormously skewed, and modern cracking orders its candidates by that skew, using Markov models and probabilistic context-free grammars trained on leaked password corpora. Measured against a policy of exactly this kind, over 10% of real passwords fell within $10^{10}$ guesses and nearly 40% within $10^{13}$ — numbers that bear no relation at all to $3.23\times 10^{19}$. The combinatorial count is an upper bound on the work, and effective entropy in practice runs under about 10 bits online and around 20 bits offline.

There is a companion trap worth naming, because it turns the whole calculation into theatre. If passwords are generated by a program whose pseudorandom generator is seeded from a 15-bit value, then no matter how large the nominal password space is, there are only $2^{15}=32,768$ distinct passwords the program can ever emit. The search space is the seed space. Counting the alphabet in that situation answers a question nobody asked.