Found a Bit of a Bug - An Easy Fix But Hard to Find

A project log for Five Finger Code Finder

A device to quickly crack PIN codes on Ford automobiles with a PIN entry keypad, and to demonstrate the shortcomings of this system.

carl-smithCarl Smith 06/16/2018 at 19:590 Comments

So I found a small issue with my code that I need to fix.  The fix is incredibly easy but took hours to figure out.  I was making up some materials for a YouTube video explaining how the system works, when I realized that something not quite right.  When you have a 5 digit code with 5 keys, there are 3125 different codes to test.  The DeBrujin sequence is 100% efficient at reusing past digits, so I am supposed to be testing a full 5 digit code with each keypress.  Yet I realized something.  The first four keypresses are not actually testing a code because you haven't completed entering a five digit code until you've pressed five digits.   So since the first four digits are wasted, it should take 3129 keypresses to test all 3125 codes.   Something is not quite right here, since there are only 3125 digits in the sequence output by the python code I found on Wikipedia.

So apparently I am not testing 4 of the possible codes.   After a bit of puzzling about how this could be possible I gave up and decided to brute force figure out which ones were missing.  I altered the Wikipedia code to output each digit followed by a newline so I could import into rows in Libreoffice Calc.   I wrote a formula to create a column with each code that is tested by each digit - stripping the left digit and adding the new digit to the right end.   Then I wrote another piece of code to generate a list of all possible codes.  I pasted that list into the spreadsheet and wrote a lookup formula to indicate if each one was found in the first list generated by the sequence.   It found four missing codes.

When I looked at the four codes that were missing it suddenly became evident what was going on.  The four codes are 91111, 99111, 99911, and 99991.  I looked for where these should be in the sequnce and noticed that the sequence ends with five nines and starts with five ones.  To actually finish the sequence you have to connect the end to the beginning and continue for four more digits.   Those first four digits that don't test anything would be testing the four missing codes if you were continually going around the sequence in a circle.

So all I have to do to fix the problem is add four nines to the start or four ones to the end of the sequence and it will test those four missing codes.  I haven't updated the code yet but I know it will work fine when I do.  Someday I'll get around to uploading the code to the project page.  And making those YouTube videos...