Brute Forcing a Car Door with Math
by Br@d
I have a vehicle that has a keypad on the door to unlock it.
When the correct five numbers (ranging from 0-9) are entered, the doors unlock. In a perfect world, I would be pretty comfortable with this feature given that 1045 means that there are up to 100,000 different key combinations. A thief would need to try all of these to gain access to my vehicle without breaking a window or setting off an alarm.
Since these 100,000 codes are five digits long, a thief could potentially have to press 500,000 keys (100,000 * 5) before finding the correct one.
Overall, it sounds pretty safe and very unlikely that they will guess your code, right? Wrong!
Upon further inspection, I discovered that it is far too easy to crack the code.
In the following paragraphs, I will describe how I was able to figure out a method to easily and reliably crack the code on my own vehicle. Before I go any further, it is time for the obligatory disclaimer:
Simply put, don't be evil or stupid. You are responsible for your own actions. The purpose of this article is to share knowledge and bring awareness to some flaws in the design of these systems.
The first flaw in the perceived difficulty is the number of keys used to determine the number of possible unique codes. Initially, I conjectured that there are 100,000 possible codes that could be used to unlock the door.
This came from the fact that the keypad lists the numbers 0-9. However, I have yet to see a vehicle with ten buttons; most have five buttons with two numbers on each. In my case, the first button is numbers 1 and 2, while the last is 9 and 0 (you can fill in the blanks).
Adjusting to account for five buttons rather than ten, we discover that our 100,000 codes have been drastically reduced to a mere 3125 (55). In turn, this also drops the 500,000 key presses down to only 15,625 (3125 * 5).
But wait, it gets worse...
When playing with the keypad on my vehicle, I noticed that there was no means to "submit" the PIN when entered. As soon as the correct five-key combination was pressed, the doors would automatically unlock.
This means that you can press many wrong keys prior to entering the right ones, and it will still unlock when the right sequence is entered. This seems like a major design flaw and got me thinking that there is probably a more efficient method to exploit rather than trying all 3125 combinations one after another.
It would take just over two hours of endless pressing at a rate of two keys per second:
With a potential waiting time of 17 plus hours:
Although not all vehicles have a timeout function.
This is where my research introduced me to the de Bruijn sequence (en.wikipedia.org/wiki/De_Bruijn_sequence).
In a nutshell, the de Bruijn sequence is an algorithm that creates a continuous string based on the inputted values and covers every possible combination without repeating any of them. In my case, I am dealing with a five-digit PIN that consists of five possible keys.
For example, the string 1234567890 would require you to press ten keys, but actually cover six different five-digit codes:
Saving you the time of having to enter 20 of the needed keys (5 * 6 = 30, 30 - 10 = 20).
The codes for the vehicle are expressed by ten numbers (0-9), but only five different keys are needed to perform a very basic conversion to use the de Bruijn sequence.
Instead of thinking of the values of 0-9, I needed to perceive the codes as key presses. This means that the:
At this point, having reduced the input values down to five digits (0-4), I would love to tell you that I wrote some amazing script to generate the sequence needed for my scenario, but why reinvent the wheel?
Instead, I used my Google-Fu to find an online generator (www.hakank.org/comb/debruijn.cgi).
To use this generator, you simply enter the number of possible digits (1-10) for the k value (five in my example) and the length of the code for n (again, five in my case).
Once the values are submitted, the sequence is generated. The following output is the 3129-digit string that covers all 3125 possible codes (15,625 key presses) based on my five-digit and five keycode requirements:
This beautiful string of numbers might be a bit much for the average mortal to memorize, but it can easily be printed on a single side of a sheet of paper using a decent sized font.
The average person should be able to enter this sequence in 26 minutes or less, given an average of two keys pressed per second:
Unfortunately, most cars that have these door keypads have some form of timeout system in place, but there are a number of vehicles from the mid-2000s and earlier that didn't have that option.
My vehicle (a 2015 Ford) does have a timeout of around 60 seconds, but it only kicks in after 35 keys have been pressed. By breaking the sequence down to 35-digit long chunks you could go through the process in 90 attempts (3129 / 35 = 89.4).
However, the whole idea behind using the de Bruijn sequence is to cover all possible combinations in a single string. To ensure that no combinations are missed, the string not only needs to be broken down into 35-digit-long segments, but we need to start each line with the last four digits of the previous one.
To solve this new requirement, I had to get a little help from the forums (as my scripting skills are still extremely noobish). The end result was this little pearl of script that takes 35 character length sub-strings from the sequence, where each sub-string starts 31 characters on from the start of the previous sub-string:
#!/usr/bin/perl my $sequence = "000001000020000300004000110001200013000140002100022000230002400031000320003300034000410004200043000440010100102001030010400111001120011300114001210012200123001240013100132001330013400141001420014300144002010020200203002040021100212002130021400221002220022300224002310023200233002340024100242002430024400301003020030300304003110031200313003140032100322003230032400331003320033300334003410034200343003440040100402004030040400411004120041300414004210042200423004240043100432004330043400441004420044300444010110101201013010140102101022010230102401031010320103301034010410104201043010440110201103011040111101112011130111401121011220112301124011310113201133011340114101142011430114401202012030120401211012120121301214012210122201223012240123101232012330123401241012420124301244013020130301304013110131201313013140132101322013230132401331013320133301334013410134201343013440140201403014040141101412014130141401421014220142301424014310143201433014340144101442014430144402021020220202302024020310203202033020340204102042020430204402103021040211102112021130211402121021220212302124021310213202133021340214102142021430214402203022040221102212022130221402221022220222302224022310223202233022340224102242022430224402303023040231102312023130231402321023220232302324023310233202333023340234102342023430234402403024040241102412024130241402421024220242302424024310243202433024340244102442024430244403031030320303303034030410304203043030440310403111031120311303114031210312203123031240313103132031330313403141031420314303144032040321103212032130321403221032220322303224032310323203233032340324103242032430324403304033110331203313033140332103322033230332403331033320333303334033410334203343033440340403411034120341303414034210342203423034240343103432034330343403441034420344303444040410404204043040440411104112041130411404121041220412304124041310413204133041340414104142041430414404211042120421304214042210422204223042240423104232042330423404241042420424304244043110431204313043140432104322043230432404331043320433304334043410434204343043440441104412044130441404421044220442304424044310443204433044340444104442044430444411111211113111141112211123111241113211133111341114211143111441121211213112141122211223112241123211233112341124211243112441131211313113141132211323113241133211333113341134211343113441141211413114141142211423114241143211433114341144211443114441212212123121241213212133121341214212143121441221312214122221222312224122321223312234122421224312244123131231412322123231232412332123331233412342123431234412413124141242212423124241243212433124341244212443124441313213133131341314213143131441321413222132231322413232132331323413242132431324413314133221332313324133321333313334133421334313344134141342213423134241343213433134341344213443134441414214143141441422214223142241423214233142341424214243142441432214323143241433214333143341434214343143441442214423144241443214433144341444214443144442222232222422233222342224322244223232232422333223342234322344224232242422433224342244322444232332323423243232442332423333233342334323344234242343323434234432344424243242442433324334243432434424433244342444324444333334333443343433444343443444440000"; my $length = length $sequence; for (my $i = 0; $i < $length; $i += 31) { print substr($sequence, $i, 35) . "\n"; }The output from this script produced 100 strings of 35 characters and a single 29 character string, making a total of only 3506 total key presses - a far cry from the original 15,625 needed to enter every possible code.
This takes the original 29 minutes or less for vehicles without the timeout function to approximately 2 hours and 9 minutes, which is a tenth of the time that it would take without the sequence and no timeout!
(35 characters at a rate of two per second = 17.5 seconds plus the 60 second timeout = 77.5 seconds multiplied by 101 attempts = 7827.5 minus the last 60 seconds = 7767.5 divided by 60 = 129.45 minutes or two hours and nine minutes).
I am sure that there are many of you reading this and thinking, "Hey, this is pretty cool, but also impractical" and you do have a valid point.
The average crook is not going to stand by a car door for 30 to 120 minutes. They are going to do a smash and grab. However, if you think in a more devious and targeted way, there are numerous uses for this besides car theft.
For example, if the target has a high-ranking position at Evil Corp, you can do your recon and figure out what they drive and where they park. You might want to gain access to their vehicle to scope it out for other valuable info or to plant a bug, but you do not want to tip them off (smashed window).
You can use as many of the segments at a time as you feel safe doing during the business day to gain access. If you do not succeed on the first try, you can return on another day and continue right where you left off.
I hope that you have found this little write-up informative.
Until next time, happy hacking.
Code: brute-force.pl