Here’s the detail we left out: In order to contain every possible subsequence, you have to consider the De Bruijn sequence as a cycle.
So if we use the last bit and then start over with the first two bits, now we have 100.
We also have to wrap around to find 110.
So in our attack on 4-digit pass codes we might need to enter as many as 10,003 digits.
The De Bruijn sequence has kn symbols, but to attack a pass code of length n on an alphabet of k symbols we might have to enter kn + n – 1 symbols.
Using De Bruijn sequences cuts the amount of work necessary to perform a brute force attack by about n; it would be exactly n if it weren’t for accounting for the need to possibly wrap around and reuse the first few symbols.
If someone added an “enter” key to the keypad and required the user to enter exactly four digits at a time, this would increase the effort of a brute force attack by a factor of approximately 4, increasing from 10,003 keys to 40,000 keys.
But this requires the user to enter five keys rather than four, the last one being the enter key.
If the designer increased the pass code length to five digits that could occur at any time, then a brute force attack using De Bruijn sequences would take 100,004 keys.
Increasing the pass code length by one increases the difficulty of a brute force attack more than requiring a terminator key would.
This is true in general when the alphabet size k is larger than the pass code length n.
Suppose you have an alphabet of size k and are using pass codes of length n with no terminator.
Requiring a terminator multiplies the difficulty of a brute force attack by n, but requiring one more character in pass codes multiplies the difficulty by k [1].
Increasing the alphabet size also increases security.
So instead of using #, for example, as an enter key, a designer could use it as a possible pass code symbol.
It could still appear at the end of a pass code, but it could also appear anywhere else, increasing the number of possible pass codes.
Related posts Probability of long runs Passwords and power laws Self-punctuating codes [1] To be precise, a brute force attack on keys of length n using De Bruijn sequences takes kn + n – 1 symbols.
Adding a terminator changes the brute force difficulty to n kn.
Requiring one more symbol in a pass code instead changes it to kn+1 + n.
So roughly n kn versus k kn.
If k > n, multiplying by k makes a bigger increase than multiplying by n.
.