Once in a while when there is absolutely nothing on TV something tempts me to switch to Ancient Aliens. I need to learn to stay away from that show because it usually takes about 3 minutes before I want to reach into the TV and slap the stupid out of the people on that show.
Tonight one of the guys was making a big deal about how the pyramid of Giza is located at 29.9792 degrees North longitude, and the speed of light is 299792458 meters per second. He said these numbers being the same can't be a coincidence. Apparently he thinks the aliens that helped build it wanted it at that point because the coordinates match the speed of light.
Let's examine how many things are wrong with this idea. It's a long list...
First of all, the number for the speed of light is totally dependent on the units you use. Sure, it is 299792458 meters per second. It's also approximately 186,282 miles per hour, 1802613915490 furlongs per fortnight, and 10569718815 Smoots per minute.
But back to meters per second. Meters weren't defined as a unit of measurement until 1793. Ancient Egyptians didn't have meters for measurement.
Seconds were first used as a unit of time by either the ancient Greeks or ancient Babylonians, depending on which theory of their origin you believe. Either way, this was thousands of years after the pyramids were built.
So meters per second didn't exist as a unit of measurement to the ancient Egyptians, so the number 299792458 would have been meaningless to them as the speed of light even if they had known what the speed of light was.
So now, on to the system of latitude and longitude as a measure of position on Earth. Latitude and longitude use the idea of 360 degrees as divisions of angles in a circle. It seems nobody knows for sure when 360 degrees in a circle first came to be used but the most common belief pins this one on the ancient Babylonians again, long after the pyramids were built.
The idea of using degrees on a circle to measure position on Earth came centuries later than the invention of degrees as a unit of angle. According to Google "Eratosthenes in the 3rd century BCE first proposed a system of latitude and longitude for a map of the world."
So the idea of the pyramid of Giza being located at 29.9792 degrees north had no meaning until degrees in a circle and latitude and longitude were invented.
And last but NOT LEAST, ancient Egyptians didn't use the Arabic numerals "0123456789" for their numbering system because this system wasn't invented until about the year 500. So the numbers for "299792458" would have been nothing but meaningless scribbles to them. They used a system where they had separate hieroglyphs for 1, 10, 100, 1000, etc. And you used as many of each as you needed to add up to the quantity you wanted to represent.
You might claim that the ancient aliens that were visiting would know the speed of light in meters per second and therefore where to instruct the ancient Egyptians to put the pyramid. But that is also impossible, since meters, seconds, Arabic numerals, degrees, latitude, and longitude didn't exist then. They would have either used ancient Egyptian units of time, speed, and location, or used their own units.
I'm not even sure how to express my feelings about how a major TV network can put something like this on with zero critical thinking or logical reasoning applied to whether or not what they are saying makes an ounce or sense.
Friday, February 12, 2021
A Rant About the Complete Lack of Logical Reasoning on Ancient Aliens
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.
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.
Saturday, October 8, 2016
Hackaday.io Traveling Hacker Box Stops in North Dakota
The Hackaday.io Traveling Hacker Box recently arrived in the mostly rectangular state of North Dakota. It was full of numerous goodies that any reader of Hackaday would be interested in having.
The Hackaday Traveling Hacker Box is a box full of goodies useful to anyone who tinkers with electronics. Things like microcontroller development boards, LCD screens, ICs, and other parts. It is a project on the Hackaday.io site. Join the project and you might be able to receive the box, take some items you find useful, add some items for other people, and send it on to the next person in the chain.
Here are some photos of the stuff inside:
First we have a bunch of stickers.
A bare BeagleLogic PCB and LCD+CapTouch board, some sort of line scan CCD board, a bunch of random components, a couple motors, and a small LCD.
A couple of standard character LCDs and some LED assemblies.
A TI dev board, a couple LCDs, a PIC programmer, a busted reflow oven controller, MAX7219 based dot matrix LED kits, an NXP dev board, and some other miscellaneous stuff.
A large selection of various integrated circuits, some large green LEDs, vintage transistors.
A bunch of small plastic boxes of integrated circuits.
An MB Quart speaker crossover, Vivitar camcorder, Apple charger, Zune MP3 player, and a little orange rover car.
A bunch of Geppetto Electronics PCBs. Most unpopulated. A few GPS oscillators, AVR programmers, PiPower boards, Divide by 3 circuit.
A panel of Crazy Clock PCBs, and an empty panel of some other small PCB. Some smart cards to go with the card reader board, a Parallax RFID reader and an RFID card. Another programmer board, a Cypress PSOC development board, some addressable LEDs wired together, a motor, and some heat shrink.
What I took from the box:
The Parallax RFID card reader and RFID card. I’ve never done an RFID project so I thought this would be interesting.
The BeagleBone BeagleLogic PCB. I have a BeagleBone Black board that I haven’t done much with, so this could be an interesting project and a chance to learn more about the BeagleBone board.
One of the Max7219 LED dot matrix kits, some stickers, three Crazy Clock PCBs (there’s 24 left), and one of the USB ISP programmers.
One of the Geppetto Electronics GPS disciplined oscillator boards.
What I put in the box:
One of my favorite components for motor control or other high current designs is the IXYS IXFN200N07 MOSFET. This is not your average MOSFET. It’s rated for 70 Volts and 200 Amps. And that’s not just a theoretical die current that you can never achieve, like with these MOSFETs that claim ridiculous currents but come in a TO-220 package that can’t dissipate the heat that would be created if the leads into the part didn’t melt first. These IXYS parts come in a package called a SOT-227B, which sounds like another small surface mount package but it’s really a large block with screw terminals on the top. Not your average MOSFET.
Someone could build a really high current H Bridge to control a motor, or maybe a high current dummy load. Bolt them to an old computer CPU heatsink and you could control a lot of current.
I realized that not everything in the box has to be strictly electronic. So I added a small bag with an assortment of terminals. Also a few microswitches that maybe could be used as limit switches in a 3D printer or whatever motorized device ends up being controlled by those giant MOSFETs.
I threw in a webcam PCB. It’s probably not useful for anything but I like how you can see the whole sensor chip and the bond wires.
Also I threw in a couple PCBs with jacks for Left/Right audio, Composite video, and S-Video. Useful for any audio project or anything that needs a few RCA jacks.
And last, but not least, I threw in a back light inverter board. It’s an interesting design with a novel flat transformer. Maybe someone can use or misuse it for some sort of high voltage project.
Oh, I almost forgot that I added a nice Maxxon DC gear motor. And a couple packs of “screen wipes.” They are very nice for cleaning anything from your phone screen to camera lenses to the LCDs in the box.
The box had been crushed a bit in shipping so I decided to reinforce it a bit. I glued a layer of cardboard to the inside sides of the box, then glued pieces in the corners for double reinforcement. It should travel better now. I had thought about replacing the box but I thought it would be better to keep it going with all the tape and stuff on it as it adds character to the box.
I made a video of some of the contents of the box, discussed a few items, and showed what I took and what I put in:
Saturday, September 17, 2016
Unboxing Dell Inspiron 15 7000 Series Laptop Model 7569
Since unboxing videos seem to be popular on YouTube I did a video when I received my new Dell Inspiron 15-7569 laptop. I discuss what I was looking for when shopping for a new laptop, and how I ended up selecting this model, and my first impressions.
I had two specific requirements I was looking for. First was a 500GB or larger solid state hard drive. I'd never used a computer with an SSD before but I kept hearing that using an SSD makes a huge difference on how fast a computer runs. Turns out this was a hard requirement to meet at any reasonable price. I found many laptops with 250GB SSDs but few with 500GB or bigger.
The second requirement was a 15.6 inch HD screen with an IPS panel. My previous laptop, the Toshiba that is the subject of my hinge repair videos, has a 720 screen with a cheap panel. The viewing angle was so small that if you move a little bit up or down the top or bottom of the screen washes out or the colors go wrong. I was constantly adjusting the screen angle to make it look right, which may have contributed to wear on the hinges. I wanted something better this time. I had looked at laptops with HD screens in the local stores and text was much clearer and easier to read.
I also wanted a touch screen. Not sure why as I don't use it a lot, but I had one on the previous laptop. I figured a 2-in-1 would make the touch screen more useful since I could flip the screen back and use it as a tablet.
But this is where I found that laptop configurations are like car option packages. If you want a 500 GB SSD and an IPS HD screen, you also have to get the fast i7-6500U processor, 12GB of RAM, AC wireless, a back lit keyboard. All features that add to the price. I ended up spending much more than I had planned, but in this situation it's a bit of you get what you pay for. Watch the video below for more details...
I had two specific requirements I was looking for. First was a 500GB or larger solid state hard drive. I'd never used a computer with an SSD before but I kept hearing that using an SSD makes a huge difference on how fast a computer runs. Turns out this was a hard requirement to meet at any reasonable price. I found many laptops with 250GB SSDs but few with 500GB or bigger.
The second requirement was a 15.6 inch HD screen with an IPS panel. My previous laptop, the Toshiba that is the subject of my hinge repair videos, has a 720 screen with a cheap panel. The viewing angle was so small that if you move a little bit up or down the top or bottom of the screen washes out or the colors go wrong. I was constantly adjusting the screen angle to make it look right, which may have contributed to wear on the hinges. I wanted something better this time. I had looked at laptops with HD screens in the local stores and text was much clearer and easier to read.
I also wanted a touch screen. Not sure why as I don't use it a lot, but I had one on the previous laptop. I figured a 2-in-1 would make the touch screen more useful since I could flip the screen back and use it as a tablet.
But this is where I found that laptop configurations are like car option packages. If you want a 500 GB SSD and an IPS HD screen, you also have to get the fast i7-6500U processor, 12GB of RAM, AC wireless, a back lit keyboard. All features that add to the price. I ended up spending much more than I had planned, but in this situation it's a bit of you get what you pay for. Watch the video below for more details...
Saturday, July 9, 2016
Estes ProtoX Quadcopter Motor Replacement
In my latest YouTube video I show how to replace a damaged motor in an Estes ProtoX quadcopter. I received one as a gift, and bumped it into a wall when flying it and damaged one of the motors. The local RC hobby shop had replacements, so I picked up a set and filmed a video on how to remove the bad motor and replace it. Note that there are two kinds of motors, one rotates one way and the other rotates tbe other way. The direction of rotation is indicated by the color of the wires attached to the motor. One kind has white and black wires, the other has red and blue wires. You must use one of the same color wires when doing the replacement or the motor will spin the wrong way. Also, be sure to connect the wires with the proper polarity. On the white/black motors the white wire should be connected to the point on the PCB with the "+." On the red/blue motors, the red wire should be connected to the point marked with a "+."
Sunday, April 24, 2016
Battery Pack Failure Prevention
In my first YouTube video I showed the failure of a power tool battery pack that I had rebuilt with new cells I bought online. The cells have great capacity and long life, but they have one problem. The thin plastic heat shrink coating fails if the cells rub against each other, causing an internal short that causes the pack to overheat and fail.
In this video I show how I added paper separators between the cells to prevent the failures. I cut paper strips and slid them in between the cells of the existing packs, in a winding pattern, to prevent shorts. At the end I show how I wrapped every second cell with individual pieces of paper when I built a new battery pack.
In this video I show how I added paper separators between the cells to prevent the failures. I cut paper strips and slid them in between the cells of the existing packs, in a winding pattern, to prevent shorts. At the end I show how I wrapped every second cell with individual pieces of paper when I built a new battery pack.
Sunday, April 3, 2016
Craftsman Garage Door Opener Remote Repair
My Craftsman pocket size key chain garage door opener remote quit working. In this video I take it apart, diagnose the problem, and repair the remote. I also show how you can check if the remote is transmitting using a software defined radio dongle.
I found a bad solder joint, but the solder joint was not cracked, it looked more like the solder never properly flowed onto the part lead when it was soldered, so that was probably not the reason the remote quit working since it was likely manufactured that way and had been working for a couple years.
Shortly after I bought it, the little plastic loop on the corner where you attach your key ring broke off, as I am sure happens to every single one of these things ever manufactured, so I replaced it with a small loop of large paper clip wire that I bent into a loop shape. It turns out that one of the ends of the wire loop had been hitting the circuit board and wore through a trace. I show how to repair the trace, resolder the bad joint, and fix the problem with the wire loop so it doesn't happen again.
I found a bad solder joint, but the solder joint was not cracked, it looked more like the solder never properly flowed onto the part lead when it was soldered, so that was probably not the reason the remote quit working since it was likely manufactured that way and had been working for a couple years.
Shortly after I bought it, the little plastic loop on the corner where you attach your key ring broke off, as I am sure happens to every single one of these things ever manufactured, so I replaced it with a small loop of large paper clip wire that I bent into a loop shape. It turns out that one of the ends of the wire loop had been hitting the circuit board and wore through a trace. I show how to repair the trace, resolder the bad joint, and fix the problem with the wire loop so it doesn't happen again.
Subscribe to:
Posts (Atom)