Learning target
By the end of this lesson, you should be able to explain why random brute-force attempts are modeled using a geometric distribution, not just use the formula.
Recognize
One random attempt is a success/failure experiment.
Derive
Build \(P(X=k)\) from repeated failures followed by one success.
Interpret
Connect \(p\), \(E[X]\), and FSM design choices.
1. Start from what you already know: the FSM is deterministic
An FSM lock moves through states according to the input sequence. If the correct sequence is entered, it reaches the unlock state. If a wrong input is entered, it may reset or move to another state.
S0
2. One brute-force attempt has only two outcomes
When someone tries one complete sequence randomly, one of two things happens:
Failure
The guessed sequence is wrong, and the lock remains locked.
Success
The guessed sequence is correct, and the FSM reaches the unlock state.
This is exactly a Bernoulli trial: one trial with success or failure.
3. Define the random variable
Now we define:
Why is \(X\) random? Because we do not know which random attempt will be the correct one.
In this example, the first success happens on attempt 4, so \(X=4\).
4. Derive the distribution — do not just announce it
Let us build the probability step by step instead of memorizing the formula.
Unlock on attempt 1
Success immediately.
Unlock on attempt 2
Fail once, then succeed.
Unlock on attempt 3
Fail twice, then succeed.
The pattern is now visible:
5. Why this must be geometric
The brute-force process has the three defining properties of a geometric distribution:
Repeated trials
The attacker keeps trying complete sequences.
Constant success probability
Each random attempt has the same probability \(p\) of success.
Stop at first success
Once the lock opens, the brute-force process ends.
So the distribution is not chosen arbitrarily. It comes directly from the structure of the experiment.
6. Connect \(p\) to the FSM design
If each FSM step accepts an \(n\)-bit input, then each step has \(2^n\) possible input values. If the unlock sequence has length \(L\), the number of possible sequences is:
If only one sequence unlocks the FSM, then:
Therefore, the expected number of attempts is:
7. Interactive exploration
Move the sliders to see how FSM design affects brute-force probability and expected attempts.
The graph shows \(P(X=k)\) for the case where each attempt is independent and previous failed guesses may be repeated. Notice the long tail: early success is possible, but very late success is also possible.
8. The memoryless idea: when is the geometric model valid?
Think about this question:
The answer depends on the brute-force strategy.
Case A: random guessing with possible repetition
If every attempt is a fresh random guess, previous failures do not change the probability of the next attempt. A wrong guess may be tried again later.
This is the geometric model.
Case B: systematic guessing with memory
If every failed sequence is removed from the list, the probability of success increases after each failure. A wrong guess is never repeated.
This is not geometric.
9. Visual comparison: random attacker vs systematic attacker
Suppose there are \(N\) possible sequences and exactly one sequence unlocks the FSM. The distribution of \(X\) depends on how the attempts are generated.
| Attack model | What happens? | Distribution of \(X\) | Expected attempts |
|---|---|---|---|
| Random guessing (no memory / with replacement) |
Guesses are independent. Failed guesses may be repeated. | \(P(X=k)=\left(1-\frac{1}{N}\right)^{k-1}\frac{1}{N}\) | \(E[X]=N\) |
| Systematic guessing (with memory / without replacement) |
Failed guesses are remembered and removed from the list. | \(P(X=k)=\frac{1}{N},\quad k=1,2,3,\ldots,N\) | \(E[X]=\frac{N+1}{2}\) |
Why the first curve decreases
To succeed on attempt \(k\), the attacker must fail \(k-1\) times first. Each extra required failure multiplies the probability by a number smaller than 1.
Why the second distribution is flat
If the attacker tries every sequence exactly once in random order, the correct sequence is equally likely to be in position 1, 2, 3, ..., or \(N\).
10. When would it NOT be geometric?
This model depends on assumptions. It would not be geometric if:
No replacement
The attacker never repeats a previous guess, so \(p\) changes over time.
Learning attacker
The attacker learns from previous failures and improves guesses.
System lockout
The lock blocks attempts after a fixed number of failures.
11. Check your understanding
Q1. Why is the FSM deterministic but the brute-force analysis statistical?
The FSM transition is fixed for each input, but the input attempts are random. Therefore, the number of attempts until unlock is random.
Q2. What is the random variable \(X\)?
\(X\) is the number of complete attempts needed until the first successful unlock.
Q3. If there are 64 possible sequences, what is \(p\)?
\(p=1/64\).
Q4. If \(p=1/64\), what is the expected number of attempts?
\(E[X]=1/p=64\). This is a long-run average, not a guarantee.
Q5. What does \(P(X=5)\) mean?
It means the probability that the first successful unlock occurs exactly on the fifth attempt: four failures followed by one success.
Q6. Why is the formula \((1-p)^{k-1}p\)?
To unlock on attempt \(k\), the first \(k-1\) attempts must fail, and the \(k\)-th attempt must succeed.
Q7. If the attacker never repeats failed guesses, is \(X\) still geometric?
No. The geometric model requires a constant success probability. Without repeated guesses, after \(r\) failures the probability becomes \(1/(N-r)\), so it changes after each attempt. In that case, the correct sequence is equally likely to appear at any position from 1 to \(N\), so \(P(X=k)=1/N\).
Q11. What is the most important assumption?
Each attempt is independent and has the same probability of success \(p\).
Q11. What if the attacker never repeats a wrong guess?
Then the success probability changes after each failure, so the geometric model no longer applies exactly.
12. Local probability vs overall probability: what matters in engineering?
In the learning intruder case, two probabilities answer two different engineering questions.
Local view: what happens next?
After \(r\) failed non-repeated guesses, the remaining search space is smaller, so the probability of success on the next attempt increases.
This is useful during operation: should the attacker continue, stop, or change strategy?
Overall view: when will success happen?
Before the process starts, the correct sequence is equally likely to be in any position in the non-repeated search order.
This is useful for engineering analysis: expected attempts, risk, security comparison, and design decisions.
Final message
In engineering, many systems are deterministic in structure but statistical in operation because users, noise, faults, attacks, and environments are uncertain.