A case for using only three different digits in keypad codes
Posted by Jonas Elfström Sun, 27 Sep 2009 19:02:00 GMT
Keypads have obvious security problems and keypads accepting a stream of digits with no # or enter in between, while checking for the four digit long code, are even worse.
The important part is to not leak the digits in the code by wear or intentional markings because if they leak it's suddenly very far from 10000 combinations.
If the "lock picker" only knows that the code contains four digits there are 10000 combinations. Keypads accepting a stream of digits can then be opened in a maximum of 10003 keystrokes using the De Bruijn sequence. That is still quite a lot.
Below is a Ruby implementation of the De Bruijn sequence.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
# De Bruijn sequence # Original implementation by Frank Ruskey (1994) # translated to C by Joe Sawada # and further translated to Ruby by Jonas Elfström (2009) @n=4 @k=10 @a=[0] @sequence=[] def debruijn(t, p, alike) if t>@n if @n%p==0 1.upto(p) {|j| @sequence<<@a[j]} end else @a[t]=@a[t-p] if @a[t]>0 debruijn(t+1,p,alike+1) else debruijn(t+1,p,alike) end (@a[t-p]+1).upto(@k-1) {|j| @a[t]=j debruijn(t+1,t,alike+1) } end end debruijn(1,1,0) print @sequence.join |
It's not uncommon to find keypads with 4 of the 10 keys worn down and if you do you can be pretty sure that the code contains those four different digits. The number of possible combinations are 4! = 4x3x2x1 = 24. I got curious to see if there's a kind of De Bruijn sequence for this that brings down the 4*24=96 keystrokes. By scribbling in a text editor I quickly realized there's not a clean sequence. Not clean in the way that a sequence following the rules can be created. Also it's probably even quite daunting to present it as mathematically dense and beautiful as the De Bruijn but that could be my less than great combinatorics speaking.
I made a quick and dirty brute force hack to try to find a shorter sequence.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
seq=[] 1.upto(4) {|a| 1.upto(4) {|b| 1.upto(4) {|c| 1.upto(4) {|d| seq << "%d%d%d%d" % [a,b,c,d] if !(a==b || a==c || a==d || b==c || b==d || c==d) }}}} s=seq[0] seq.delete_at(0) while (seq.length>0) next_code=(seq.select {|c| c[0..2]==s[-3..-1]}) if next_code.empty? next_code=(seq.select {|c| c[0..1]==s[-2..-1]}) if next_code.empty? next_code=(seq.select {|c| c[0]==s[-1]}) s+=next_code[0][1..3] seq.delete_at(seq.index(next_code[0])) else s+=next_code[0][2..3] seq.delete_at(seq.index(next_code[0])) end else next_code=(seq.select {|c| c[0..2]==s[-3..-1]}) s+=next_code[0][3].chr seq.delete_at(seq.index(next_code[0])) end end |
The above code takes the first code "1234" of the 24 and then searches the rest of the array for a code beginning with "234". It finds "2341" and adds "1" to the end of s and continues to look for "341" and so on. Relatively soon there is no three digit match and then it tries two digits and eventually even that fails and then it gets the first one digit match. The resulting sequence is:
123412314231243121342132413214321
From 96 to 33 keystrokes. Not as effective as De Bruijn but still significant. Unlike De Bruijn I have absolutely no proof that this is the shortest one possible but it seems likely. Also notice that in the middle of the sequence we find "3121" and "1213". Those break the criteria of four different digits but they seem to be necessary to be able to enter the reversed mode. Try reading the sequence forward and backwards to see what I mean.
If the code only contains two digits it's gets even more trivial to try them all. There are 14 possible codes and by compressing those to one sequence you get down to 20 keystrokes.
Things get a little more interresting if three buttons are worn. It turns out that the repeated digits can be placed in the code in six different ways.
0012,1002,1200,0102,0120,1020
That's 6x2x3=36 combinations and, maybe a little unintuitive, 12 more than if you are using four different digits. I compressed it down to 49 key strokes. Unlike the sequence for four different digits I can't find it with google and I know it's kind of security by obscurity but that could give a tiny amount of extra trouble to an attacker. I will not be the first one publishing it.
Be aware that if an attacker knows you are using a 0012-like code he gets a smaller space to search. 6x8x9x10=4320 instead of 10000. You have to weight the risk of button leaks against a code protocol leak.
