Tuesday, July 31, 2018

The Five Finger Code Finder

This post is about a device I designed and built that can open Ford cars that have the Ford Securicode keyless-entry keypad.




The Five Finger Code Finder is an electromechanical device and software designed to efficiently find the PIN code that will unlock Ford automobiles equipped with a 5 button entry keypad. It can unlock a door in less than 11 minutes and on average takes less than four minutes.

I created a project page on the Hackaday.io site, and it was recently featured on the Hackaday.com Blog page, which generated a lot of traffic to the project page.

Its purpose is to demonstrate how the design of this system allows PIN codes to be found in a MUCH SHORTER TIME than would normally be required to brute force search and try all possible PINs. This system allows a good level of usability but in the process sacrifices security. The purpose of this project is to demonstrate how design decisions that put a priority on ease of use can greatly compromise the security of a system such as this.  The design of any security system is always a compromise between ease of use and how secure the system is. 

The Five Finger Code Finder uses an Arduino for control, a standard HD44780 compatible LCD, and five solenoids to press the keypad buttons in sequence.

This project builds on the previous work of Samy Kamkar and the authors of “The Car Hacking Handbook.” Samy discovered a method to quickly open garage door openers that use a remote with a fixed binary code set by dip switches. Despite the development of rather secure rolling code systems these remotes are still in wide use in situations such as apartment parking garages where a large number of remotes must operate the same door.

Samy discovered that the logic that checks for a code match rechecks the entire code sequence as each individual bit arrives, rather than waiting for a full code word to be received, and that there is no delay after checking for a match and no penalty for an incorrect match. If you have a 12 bit code the check system will check the first 12 bits for a match. If a 13th bit arrives, it will immediately check bits 2 through 13 for a match. If a 14th bit arrives, it will check bits 3 through 14, and so on. This facilitates much faster code searching as you have just checked three different 12 bit codes with only 14 bits sent.

The authors of “The Car Hackers Handbook” discovered that the entry keypads on Ford vehicles utilize this same shift by one and check for a match system. Also with no delays and no penalties for incorrect entries. In this case you have five keys to use in the code instead of just the ones and zeros of a binary code but the concept remains the same. In their book they published an optimal sequence for manually trying all possible codes as efficiently as possible. They state that one can enter this sequence manually in approximately 20 minutes and find the code to unlock a Ford vehicle with this system.  Personally I think 20 minutes is a bit optimistic as you'd have to be able to press about 3 buttons a second.  Maybe if you had someone reading the digits to you so you could keep your eyes on the keypad it might be possible.

Well, I’m to lazy to do that, and thought it would be a fun project to implement a machine that can enter the sequence automatically for me as quickly as the door keypad will recognize button presses.
 
Here's a picture of what I created.




Construction of the Five Finger Code Finder

To build this I mounted four push type solenoids from All Electronics (part number SOL-102) onto a piece of acylic sheet.  The unit attaches to the car door with the four magnets (part number MAG-149) on the screw feet.   The magnets have a countersunk hole in the center that allows them to be put onto a screw and held in place by a nut.  A second pair of nuts on each screw allow adjustment of the length of the magnetic feet to set the proper distance between the solenoids and the keypad on the car door.  Onto the acrylic sheet I mounted a perfboard with the electronics that make the system work.

The important components on the perfboard include a Arduino Pro Mini from Sparkfun Electronics, a standard character LCD (any Hitachi 44780 compatible one will do), a ULN2003 Darlington Transistor Array chip to drive the solenoids, and a standard 7805 regulator circuit to power the Arduino and LCD.   I also included 5 red indicator LEDs and series current limiting resistors to show which solenoids are powered as the device taps out the code sequence (who doesn't like blinky LEDs), two power switches to switch power to the Arduino and to the solenoids separately, a potentiometer to adjust the LCD contrast, and after I found out the two 9-volt batteries were not sufficient to power the solenoids, I added a couple terminals to connect a larger battery, and a diode to protect from reverse polarity if that external battery is connected improperly.  I also included three pushbuttons for control of the device, to allow the user to start and stop the operation, and jump forward and backward in the sequence.  (At a later date I may post a more detailed Bill of Materials and schematic if there is interest.)

The solenoids have very narrow pins on the pusher end which wouldn't press the buttons reliably by themselves, so I cut pieces from a wood dowel rod, drilled small holes into each one, and glued them onto the pins, so the solenoids would have "feet" that better matched the size of the buttons on the keypad.  When doing this it is critical to get all the feet glued onto the solenoids at exactly the same depth so they would all contact the buttons at the same time.  The rubber band you see in the picture is there to keep the solenoids held against the keypad buttons during operation because the solenoid pins are normally able to move loosely in the solenoid body.  The red sticks zip tied to the end solenoids allow adustment of the height of the rubber band behind the solenoids.



Software Development

All this hardware does nothing without some software for the Arduino.   Most of this was pretty easy given the ease of use of the Arduino programming environment.  All I had to do to make the LCD work was connect it by the method indicated in the LCD example code that comes in the Arduino programming environment, and the "Liquid Crystal" library included worked fine for writing text to the LCD.  The pushbuttons and solenoids were connected to digital inputs and outputs and can be read or written directly in the Arduino code.

I wrote some code that displays an introduction screen and tells the user to "Press Start" to start the door opening robot in operation.  Once that is done the first pushbutton can be used to stop the operation and the other two buttons will jump back or forward in the sequence, to allow the user to replay part of the sequence or jump forward if they wish to skip part of the sequence.   One area of improvment here would be better switch debouncing in the software.  Sometimes the switches do "double clicks."  I wasn't too concerned about that however, as this is a proof of concept project, not a polished finished product.

The biggest feature of the software is the number sequence used to open the door as quickly as possible.  It uses a special number sequence called a de Bruijn Sequence.  Dutch mathematician Nicolaas de Bruijn discovered a method to find a sequence of numbers where all the possible codes are included somewhere in the sequence with no wasted digits.  I'll discuss how this sequence speeds up the code entry later, but I had to figure out a way to generate this sequence and include it in the Arudino program.

I didn't want to just steal the number sequence out of the Car Hacker's Handbook -- that somehow felt like cheating, so I needed to find a way to generate the sequence.  The Wikipedia page has a piece of Python code that can generate de Bruijn sequences, which I adapted for my own use.  I modified it to generate a sequence for five digit codes on five keys, and to output that sequence with commas and spaces between each digit so I could paste it into the Arduino code.  The modified code is available here, from my Hackaday.io project page.

All I changed were the last few lines of code.  I changed the line line that reads
return "".join(alphabet[i] for i in sequence)
to add the comma and space as follows:
return ", ".join(alphabet[i] for i in sequence)

Then I deleted the two example lines that read
print(de_bruijn(2, 3))
print(de_bruijn("abcd", 2))

and replaced them with my own line that generates five digit codes with 1, 3, 5, 7, 9:
print(de_bruijn("13579", 5))

And it output the sequence in a format ready to be pasted into the Arduino code.

The next problem I found was that the Arduino programming environment didn't like the large size of the array of numbers for the de Bruijn sequence.  It turns out that without special tricks, it copies an array from program memory into RAM just to access it, and the Arduino Pro mini doesn't have enough RAM to even hold the whole sequence of 3129 digits.  I had to find a way to get the code to NOT copy the array to RAM and instead read it directly from program memory. 

The Arduino environment has a way to accomplish this.  There is a header file you can include called pgmspace.h that provides what's necessary.  Just add the line
#include <avr/pgmspace.h>
at the beginning of your code.  Then insert the keyword "PROGMEM" into your array declaration like so:
const PROGMEM char debruijn5of5[] = {1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 5, 1, 1, 1, 1, ...

But now that your array is stuck in program memory you can't just access it as you normally would.  In my case I had to use a function called pgm_read_word_near() to retrieve elements from my giant array of de Bruijn sequence digits, with the following line of code, where debruijn5of5 is the array name, i is the index into the array, and currentdigit is of course where I'm putting the retrieved array element:
currentdigit = pgm_read_word_near(debruijn5of5 + i);

The rest of the code is pretty straightforward.  Looping through the array, retrieving array elements, activating the matching solenoid, updating the LCD with the side scrolling history of the last digits tried and the count, and check for the user pushing buttons.



See it in Action

So by now, reading through all this, you probably want to see this thing working.  I have posted a video to my YouTube channel.  It was meant to stand on it's own, so it explains much of the same stuff I've said here, but you can see the device running:



 

The Theory Behind How de Bruijn Sequences, Shifting Digits, and Five Digit Keypads Make This Thing Work So Fast:

So if you've read this far you might be the type of person interested in some more in depth theory about how this device opens car doors so fast.  Again, some of this is covered in the video above, but I want this post to cover all the important information as well.

The first thing to consider is the keypad itself.  Ford went with a five button keypad.  Each key has two numbers on it, but that is just so you can use any code you want.  So let's compare five buttons to a more traditional ten-key keypad light you might have for a security system or one of those garage door opener keypads.

And to compare to the Ford system, let's say it also has a five digit code.  In this case you can have codes from 00000 to 99999, or 100000 different codes to test.  To show this mathematically, you have 10 digits to choose from for each of the 5 digit codes, so the number of possible codes is 10*10*10*10*10, which is 100000.  This is obvious since we are all familiar with our usual decimal numbering system, but let's apply that same math to the Ford five digit keypad.

You have only half as many keys, but that doesn't just cut the number of codes in half.  To find the number of codes for only five keys and five digits, we just solve 5*5*5*5*5, which is 3125.  There are only 3125 possible codes on a five digit keypad with a five digit code.  This is only three percent as many codes to test.  This one factor is what makes this possible to search all codes in a reasonable time.

So why would Ford do something that reduces the number of possible codes by 97 percent?  A ten digit keypad on your car door would cost more, be harder to use, and would be rather ugly.  When designing a security system you must create something people are willing to have and use.

The next thing to consider is what I call the "Shift and Check Again Process."  Each time you press a button on the keypad, the system combines that key with the previous four keys that were pressed to make a five digit code, and checks that against the codes that open the door.  It's like it drops the oldest digit, shifts everything over one digit, adds the new digit, and checks again.

So, or example, in a traditional system to check 5 codes you’d enter something like:
11111, 11112, 11113, 11114, 11115
Which is 25 total keypresses to check 5 codes and 15625 keypresses to check 3125 codes.

But with the "Shift and Check" system you could enter a series such as:

1, 9, 3, 5, 1, 1, 9, 3, 7, 1, 1, 9
And the system would check all of the following codes:
19351, 93511, 35119, 51193, 11937, 19371, 93711, 37119
 

So now you have checked 8 codes with only 12 presses instead of 40 because after the first four digits you are checking a 5 digit code with every key press.

So now all we need to do is find an optimal sequence of numbers where we are checking a new code on every key press, reusing the previous four digits each time, without wasting key presses on codes we already checked, and we drastically reduce the time to test all codes.


 
Why would Ford use this “shift and check on every key press” method?

It was necessary to do this to make the system easy to use when you make a mistake.

Think about what would happen if they only checked digits in groups of 5.  Say your code is 1 2 3 4 5 but you make a mistake and enter 1 2 2 and then stop. Then you then enter 1 2 3 4 5 to try and enter the right code.  What you have entered is 1 2 2 1 2 3 4 5.  If it waited for 5 digits it would only check 1 2 2 1 2 and it would be waiting for you to finish your next attempt starting with 3 4 5.


It is necessary to operate in this manner because there is no key on the pad to cancel an incorrectly entered code, and no enter key to tell the system when you are done entering a code.

So now back top what I said about finding the optimal sequnce that doesn't waste any digits.  It turns out mathemeticians have already solved this problem for us with something called a de Bruijn Sequence.


 

The De Bruijn Sequence

These sequences of numbers were named after Dutch mathematician Nicolaas de Bruijn who came up with the general theory to prove the existance of these sequences of numbers that are optimized to contain all the possible codes in the shortest sequence possible.  This is just what we need for this project, to open the car door in a short a time as possible.


From Wikipedia:  In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length k^n, which is also the number of distinct substrings of length n on A; de Bruijn sequences are therefore optimally short.
 

That might take a few read throughs to understand, but for our Ford door keypad the alphabet is “1 3 5 7 9."  For a five digit keypad k = 5, the number of keys.  For a five digit code n = 5 since n is the number of digits in the code.

Therefore the number of digits in the sequence is 5^5 or 3125.  The de Bruijn sequence is exactly what we need to enter all codes with the least key presses possible.

Actually takes 3129 key presses because the first four buttons pressed do not form a 5 digit code, so those digits have to be put back on the end of the sequence to actually be tested, like you are going around in a circle.  Note how Wikipedia says it’s a cyclic sequence.


 
Putting This All Together

The Five Finger Code Finder can almost press 5 keys per second (maybe it could go faster but I didn’t have time to test reliability of faster speeds).  Let's look at the time improvement for each factor above.

Starting with the normal 10 key pad like a security system might have, with 5 digit code, testing everything the hard way by entering each code in full, we have:
100000 codes with 5 digits each, or 500000 key presses.
500000 presses at 5 presses per second is 100000 seconds, which is almost 28 hours

Now with only a 5 key pad and 5 digit code, but still entering each code in full, separately,
3125 codes with 5 digits each is 15625 key presses.
15625 presses at 5 presses per second is 3125 seconds or 52 minutes.

The final piece of the puzzle, checking on every digit and using the de Bruijn Sequence, means we have:

3129 presses at 5 presses per second which 626 seconds.

This is how we can open any Ford car door in 10 minutes and 26 seconds or less. 

I made a YouTube video about all this theory:



So what are the lessons we learn from this project? 

Security is always a lesson in compromises.

Ford went with 5 digit keypad.
    • 10 digit keypad would cost more
    • 10 digit keypad would be big and ugly

Ford checks last five digits entered each time you press a key.
    • Needed for usability
    • No way to cancel a partially entered code and start over


It might sound all through this post like I am complaining about the lack of security in this system, but from a design and engineering standpoint I think Ford probably did this exactly correct.

These compromises were necessary to make a system that people would want and would use. Compromises in security for usability are often okay as long as you understand the tradeoffs.  And tradeoffs are necessary because people won’t use security that is too difficult. 



Countermeasures by Ford:
 
So I developed this project on my 2001 Ford Explorer.  Sometime since then Ford has anticipated this method of attack and developed a very effective countermeasure that I didn't know about until I traded my 2001 Explorer in and bought a 2017 Explorer.  It has a completely different keypad that uses capacitive touch sensing, so this version of the Five Finger Code Finder is not compatible, but even if I designed a new version it would be thwarted by the following feature I found in the owners manual:

Anti-Scan Feature

The keypad goes into an anti-scan mode if you enter the wrong code seven times.

This mode turns off the keypad for one minute and the keypad lamp flashes.

The anti-scan feature turns off after any of the following occur:
• One minute of keypad inactivity.
• You press the unlock button on the remote control.
• You switch your vehicle on.
• You unlock the vehicle using intelligent access. 



So Ford as anticipated the code searching process and simply made the system take a time out for a minute if you enter seven incorrect codes. They mean full five digit codes, so that means 35 keypresses and you wait a minute.  The system could be programmed to work with this countermeasure, trying 35 digits, then waiting a minute, then backing up 4 digits in the sequence to "re-prime" the shift and check system, then entering 31 more digits.  But the time this would add would make it take many hours to finish.


Video on Construction of the 5FCF Project:

So if you would like to build a device like this yourself, the third video in my series will be worth watching.  In it I discuss how I built the device, and the problems I encountered along the way, so you don't have to solve the same issues I had to solve.