Demonstration: Designing a Combination Lock

A combination lock is the classic first state machine, and for good reason. It sees one key at a time, so it has to remember something, and what it remembers is exactly what a state is.

The specification is one sentence: the door opens when someone types the code. Getting the forward path right takes a minute. Everything else in this demonstration is about the keys that are not the code, which is where real designs go wrong.

How to use it

The demonstration has five steps, and the code you choose in step 1 carries through all of them.

1 States asks how many states a three-digit lock needs. 2 Wrong keys has a table: for each state and each wrong key, you choose where the lock goes. Try it on the keypad, then press Test every sequence. The lock is checked against every possible run of keys, and if it fails, you are shown the shortest sequence that catches it, which you can replay.

3 Encoding builds your lock with two flip-flops and with four, and counts the gates. 4 Moore or Mealy puts both kinds of lock on a timing diagram. 5 Brute force attacks the lock you built.

Design a Combination Lock

Four states and a keypad. Then find out what happens when someone types it wrong, or tries every code.

derekmolloy.ie

1 States2 Wrong keys3 Encoding4 Moore or Mealy5 Brute forceCode 3-1-4

A lock opens when someone types the code. It sees one key at a time, so it has to remember how far through the code it is. Each thing it might need to remember is a state. Pick a code, then decide how many states the lock needs.

Code3-1-41-1-21-2-17-7-7Choose your own

States

34101,000

In each state one key is right and moves the lock forward. Every other key is wrong, and you decide where each wrong key sends the lock. The obvious answer is back to S0. Fill in the table, try the keypad, then test the lock against every possible sequence of keys.

In state	Key 1	Key 3	Key 4	Any other key
S0 nothing yet	S0S1S2	right key, to S1	S0S1S2	S0S1S2
S1 "3" typed	right key, to S2	S0S1S2	S0S1S2	S0S1S2
S2 "31" typed	S0S1S2	S0S1S2	right key, to OPEN	S0S1S2

In OPEN, any key relocks the door and returns to S0.

1234567890

Locked

Reset

Keys you press appear here, with the state each one leaves the lock in.

Test every sequenceAll wrong keys to S0

Four states need to be stored somehow. Binary encoding numbers them and uses two flip-flops. One-hot gives each state its own flip-flop, exactly one of which is ever set. Here is the same lock built both ways.

Your step 2 lock does not pass yet, so this is built from a working lock for 3-1-4. Fix step 2 and these will be built from yours.

The keypad gives one line per key: K1, K3, K4 for the code digits, and KX, which is one NOR gate meaning "a key that is not in the code". Every flip-flop provides its output and its complement, so complements are free. Identical product terms are built once and shared.

Binary

S0 = 00S1 = 01S2 = 10OPEN = 11

D1 = Q1·Q0·K1 + Q1·Q0·K4

D0 = Q0·K3 + Q1·K3 + Q1·Q0·K4

DOOR = Q1·Q0

2

Flip-flops

7

Gates

17

Gate inputs

One-hot

S0 = 0001S1 = 0010S2 = 0100OPEN = 1000

D(S0) = S0·K1 + S2·K1 + OPEN·K1 + OPEN·K3 + S0·K4 + S1·K4 + OPEN·K4 + KX

D(S1) = S0·K3 + S1·K3 + S2·K3

D(S2) = S1·K1

D(OPEN) = S2·K4

DOOR = OPEN

4

Flip-flops

15

Gates

38

Gate inputs

For this lock, binary needs fewer gates (7 against 15). Binary always wins on flip-flops, two against four. One-hot wins on effort: every equation can be written straight off the state diagram, one term per arrow into a state, with no minimising, and the door is driven directly by the OPEN flip-flop. That is why FPGA tools, where flip-flops are plentiful, choose one-hot by default. The catch is robustness: four flip-flops have sixteen patterns and only four of them are states.

A Moore lock opens in a state of its own, so the door depends only on the state. A Mealy lock has no OPEN state: the door is driven by S2 together with the last key, so it can change as soon as the key goes down. The lock is clocked, and each key is registered at the next rising clock edge after it is pressed. Move the slider to change when in the clock cycle the keys are pressed.

Key pressed30% into the cycle

Moore: four states. The door opens on the clock edge that registers the last key, 0.70 of a cycle after the press, and stays open until the next key. It is a flip-flop output, so it is clean and the same width whenever the key is pressed.

Mealy: three states, one fewer. The door opens the moment the key goes down, with no wait for the clock, but closes on the very next edge when the lock returns to S0. It is open for 0.70 of a cycle. Its width depends on when a person pressed a key.

Someone without the code tries them all. The lock you built in step 2 opens whenever the last three keys match, whatever came before them. That was the right answer for a forgetful user. Here is what it does for an attacker.

Attack 3-1-4Every three-digit code in turn, against one long sequence that contains every code exactly once.

Code length

3 digits4 digits6 digits

Lockout

NoneAfter 3After 5

Locked for

30 s5 min1 hour

Lock	Best attack	Worst case
Your step 2 lock: watches the last keys typed This lock never knows where an attempt starts, so it cannot count failures. A lockout cannot be added.	de Bruijn sequence	8 min
Checks every block of 3 keys, then starts again A de Bruijn sequence no longer helps, because a code split across two blocks is never checked.	every code in turn	25 min
Block lock with a lockout Locks for 5 min after 3 wrong codes in a row, which needs a counter of failures.	every code in turn, waiting out each lockout	28.2 h

Two keys a second, worst case. The average is half of each.

Making the lock forgiving made it weaker. Overlap handling lets every keypress test a new code, which cuts the attack to about a third. The fix is not more digits but a different machine: one that knows where an attempt starts and ends can count wrong attempts, and only that machine can have a lockout.

Walkthrough

Step 1: Count what the lock must remember

With the code 3-1-4, choose each number of states in turn. Four is the answer for this design: nothing typed yet, one digit right, two digits right, and open. The lock never needs to know which wrong keys were pressed, only how much of the code has just been typed.

Step 2: Send every wrong key back to the start, then test it

Open 2 Wrong keys. Every cell starts at S0, which is what most people would choose. Type 3, 1, 4 on the keypad and the door opens. Now press Test every sequence.

It fails on 3 3 1 4. After the first 3 the lock is in S1. The second 3 is wrong, so it goes back to S0 and the 3 is thrown away. But that 3 was the start of the code. Change the cell for S1 on key 3 to S1 and test again.

Keep going until the test passes, then try 1-1-2, 1-2-1 and 7-7-7. Each one fails in its own way, except 7-7-7, where sending every wrong key to S0 is already correct.

The rule underneath every fix is the same: after a wrong key, ask how much of the code the last few keys could still be the start of.

Step 3: Compare the encodings

Open 3 Encoding. Binary stores four states in two flip-flops. One-hot uses four, one per state. Read the one-hot equations: each term is one arrow on the state diagram, written down directly. Then compare the gate counts, which are computed from the lock you built.

Step 4: Watch the door open

Open 4 Moore or Mealy. The Moore lock opens on the clock edge after the last key and stays open. The Mealy lock has no OPEN state, so it needs one state fewer. Its door opens the instant the key goes down, but closes on the next edge.

Move the slider towards 95%. The Moore door does not change shape. The Mealy door shrinks to a sliver, because its width depends on when a person happened to press the key.

Step 5: Attack it

Open 5 Brute force and press Attack. Trying codes one at a time takes up to 3,000 keypresses. A de Bruijn sequence contains every three-digit code as overlapping windows, and it opens your lock in at most 1,002. The overlap handling that made the lock forgiving in step 2 is what lets every single key test a new code.

Then look at the table. Only a lock that checks fixed blocks of keys knows when an attempt has failed, so only that lock can have a lockout.

Check your understanding

Quiz

Select 0/1

Why does a lock for a three-digit code need four states?

derekmolloy.ie

Quiz

Select 0/1

The code is 3-1-4. The lock sends every wrong key back to S0. Someone types 3 3 1 4. What happens?

derekmolloy.ie

Quiz

Select 0/1

A Mealy version of the lock opens the door from S2 when the last key is pressed. Why can its door pulse be very short?

derekmolloy.ie

Quiz

Select 0/1

Why is a lock that handles overlapping keys correctly easier to brute-force?

derekmolloy.ie

Concept Match

Match each design choice to its consequence

derekmolloy.ie

Wrap-up

The forward path through a state machine is the easy part. Nearly all of the design is in the arrows nobody draws first.

1. A state records what the machine must remember to decide what to do next, and nothing more.
2. Every state needs an arrow for every input. For a sequence detector, a wrong input goes to the longest part of the sequence that the latest inputs could still be the start of.
3. Test against every sequence, not just the intended one. The shortest failing sequence is usually only one key longer than the code.
4. Binary encoding saves flip-flops. One-hot encoding saves design effort and drives outputs directly.
5. Moore outputs are clean and clock-aligned. Mealy outputs are faster but take their timing from the inputs.
6. Security is a property of the whole machine. A lockout needs a lock that knows when an attempt has ended.