## Entering PIN without confirmation

16.06.2009 19:52

A brand of electronic locks marketed by a certain security company in Slovenia has a peculiar way of recognizing the correct code.

To unlock it, you need to enter a four digit PIN. However, instead of the usual way where you have to press a confirm key after entering four digits this one unlocks as soon as you enter the correct sequence.

So basically, if the correct code is 1-2-3-4, it will unlock after pressing 9-8-1-2-3-4, or whatever sequence of digits comes before the 1-2-3-4.

It's certain that such a design reduces the time needed to guess the right combination. In theory you can check a new combination for every keypress where a normal lock would require four plus one for confirmation. For example, entering 9-8-1-2-3-4 checks 9-8-1-2, 8-1-2-3 and 1-2-3-4 with 6 presses while a normal lock would require 15 presses).

I'm wondering. What is the optimum strategy for guessing the combination? Is the theoretical one combination per key possible? Or is there necessarily some overlap between sequences entered in this way?

In the general case of n digits and m places I'm picturing this as a directed graph with nm vertices, one for each possible combination, where each vertex has n outgoing edges (corresponding to n possible keys you can press next). So the problem translates to finding a Hamiltonian path in such a graph (which is a NP-complete problem in the general case).

Path for n=5 m=2

Path for n=2 m=3

I have been able to find nicely symmetrical paths for simple case of m = 2. At least from those examples it seems that you can construct the path incrementally, by first exhausting all combinations with n digits before moving to n + 1

It appears possible that an analogue way exists for more places, but I'm having problems drawing three and four-dimensional grids on paper.

Posted by | Categories: Ideas

For m=2 it can be easily generated using Fibonacci LFSR
http://en.wikipedia.org/wiki/LFSR

That mean that for arbitrary m this problem can be expressed as searching of primitive polynomials over GF(n^m)
http://en.wikipedia.org/wiki/Primitive_polynomial

Posted by Luka Rahne (via Facebook)

Interesting point.

Doesn't n have to be prime for a finite field of size n^m to exist? Does that mean that you can't have a maximum-length LFSR for an alphabet of 10 characters?

n has to be prime, to find primitive polynomials. But you can use two LFSRs together. For decimal numbers you need one of 2^m and one of 5^m

Period of both LFSR-s are now 10^m of both LFSRs. (you still have to add support for zeros in such LFSR, but this is trivial problem)

I also found my old Mathematica source which I was using working on generating such polynomials when working on cryptography support for embedded microprocessor.

If you are going to hack in beer store whit this I am comming for my share.

Posted by Luka Rahne (via Facebook)

No, nothing as practical as that :) Just curiosity.

But I'll buy you a beer anyway next time we meet.