Brute Forcing a Car Door with Math

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 10^5 means that there are up to 100000 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 100000 codes are 5 digits long a thief could potentially have to press 500000 keys (100000 * 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 100000 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 10 buttons; most have 5 buttons with 2 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 5 buttons rather than 10, we discover that our 100000 codes have been drastically reduced to a mere 3125 (5^5).  In turn, this also drops the 500000 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 were no means to “submit” the PIN when entered. As soon as the correct 5 key combination was pressed, the doors would automatically unlock. This means that you can press many wrong keys prior to entering to 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 2 hours of endless pressing at a rate of 2 keys per second (15625 / 2 seconds = 7812.5, 7812.5 / 3600 (seconds in an hour) = 2.17 hours) with a potential waiting time of 17 plus hours (3125 / 3 failed attempts before the timeout is invoked = 1041.66 * 60 second timeout = 62499.6,  62499.6/ 3600 = 17.361 hours) although not all vehicles have a timeout function.  This is where my research introduced me to the De Bruijn Sequence (https://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 5-digit PIN that consists of 5 possible keys. For example, the string 1234567890 would require you to press 10 keys but actually cover 6 different 5-digit codes:

12345
23456
34567
45678
56789
67890

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 10 numbers (0-9) but only 5 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 [1/2] button now has a value of “0”, the [3/4] is now “1”, [5/6] gets “2”, [7/8] is now “3” and finally [9/0] is represented as a “4”.

At this point, having reduced the input values down to 5 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 http://www.hakank.org/comb/debruijn.cgi.  To use this generator, you simply enter the number of possible digits (1-10) for the “k” value (5 in my example) and the length of the code for “n” (again 5 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 (15625 key presses) based on my 5-digit and 5 keycode requirements:

000001000020000300004000110001200013000140002100022000230002400031000320003300034000410004200043000440010100102001030010400111001120011300114001210012200123001240013100132001330013400141001420014300144002010020200203002040021100212002130021400221002220022300224002310023200233002340024100242002430024400301003020030300304003110031200313003140032100322003230032400331003320033300334003410034200343003440040100402004030040400411004120041300414004210042200423004240043100432004330043400441004420044300444010110101201013010140102101022010230102401031010320103301034010410104201043010440110201103011040111101112011130111401121011220112301124011310113201133011340114101142011430114401202012030120401211012120121301214012210122201223012240123101232012330123401241012420124301244013020130301304013110131201313013140132101322013230132401331013320133301334013410134201343013440140201403014040141101412014130141401421014220142301424014310143201433014340144101442014430144402021020220202302024020310203202033020340204102042020430204402103021040211102112021130211402121021220212302124021310213202133021340214102142021430214402203022040221102212022130221402221022220222302224022310223202233022340224102242022430224402303023040231102312023130231402321023220232302324023310233202333023340234102342023430234402403024040241102412024130241402421024220242302424024310243202433024340244102442024430244403031030320303303034030410304203043030440310403111031120311303114031210312203123031240313103132031330313403141031420314303144032040321103212032130321403221032220322303224032310323203233032340324103242032430324403304033110331203313033140332103322033230332403331033320333303334033410334203343033440340403411034120341303414034210342203423034240343103432034330343403441034420344303444040410404204043040440411104112041130411404121041220412304124041310413204133041340414104142041430414404211042120421304214042210422204223042240423104232042330423404241042420424304244043110431204313043140432104322043230432404331043320433304334043410434204343043440441104412044130441404421044220442304424044310443204433044340444104442044430444411111211113111141112211123111241113211133111341114211143111441121211213112141122211223112241123211233112341124211243112441131211313113141132211323113241133211333113341134211343113441141211413114141142211423114241143211433114341144211443114441212212123121241213212133121341214212143121441221312214122221222312224122321223312234122421224312244123131231412322123231232412332123331233412342123431234412413124141242212423124241243212433124341244212443124441313213133131341314213143131441321413222132231322413232132331323413242132431324413314133221332313324133321333313334133421334313344134141342213423134241343213433134341344213443134441414214143141441422214223142241423214233142341424214243142441432214323143241433214333143341434214343143441442214423144241443214433144341444214443144442222232222422233222342224322244223232232422333223342234322344224232242422433224342244322444232332323423243232442332423333233342334323344234242343323434234432344424243242442433324334243432434424433244342444324444333334333443343433444343443444440000

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 2 keys pressed per second (3129/2= 1564.5/60 = 26.075).  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 2000’s and earlier that did 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 digits long segments, but we need to start each line with the last 4 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 = “<copy the sequence here>”;

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 (see below), 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 rate of 2 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 2 hours and 9 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-120 minutes, they are going to do a smash and grab. However, if you think more devious and targeted 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.

Script Output:
00000100002000030000400011000120001
00013000140002100022000230002400031
00310003200033000340004100042000430
04300044001010010200103001040011100
11001120011300114001210012200123001
30012400131001320013300134001410014
00142001430014400201002020020300204
02040021100212002130021400221002220
22200223002240023100232002330023400
34002410024200243002440030100302003
20030300304003110031200313003140032
00321003220032300324003310033200333
03330033400341003420034300344004010
40100402004030040400411004120041300
13004140042100422004230042400431004
10043200433004340044100442004430044
00444010110101201013010140102101022
10220102301024010310103201033010340
03401041010420104301044011020110301
03011040111101112011130111401121011
10112201123011240113101132011330113
01134011410114201143011440120201203
12030120401211012120121301214012210
22101222012230122401231012320123301
33012340124101242012430124401302013
20130301304013110131201313013140132
01321013220132301324013310133201333
13330133401341013420134301344014020
40201403014040141101412014130141401
14014210142201423014240143101432014
20143301434014410144201443014440202
02021020220202302024020310203202033
20330203402041020420204302044021030
10302104021110211202113021140212102
21021220212302124021310213202133021
30213402141021420214302144022030220
02204022110221202213022140222102222
22220222302224022310223202233022340
23402241022420224302244023030230402
04023110231202313023140232102322023
20232302324023310233202333023340234
02341023420234302344024030240402411
24110241202413024140242102422024230
42302424024310243202433024340244102
41024420244302444030310303203033030
30303403041030420304303044031040311
03111031120311303114031210312203123
31230312403131031320313303134031410
14103142031430314403204032110321203
12032130321403221032220322303224032
40323103232032330323403241032420324
03243032440330403311033120331303314
33140332103322033230332403331033320
33203333033340334103342033430334403
44034040341103412034130341403421034
10342203423034240343103432034330343
03434034410344203443034440404104042
40420404304044041110411204113041140
11404121041220412304124041310413204
32041330413404141041420414304144042
40421104212042130421404221042220422
04223042240423104232042330423404241
42410424204243042440431104312043130
31304314043210432204323043240433104
31043320433304334043410434204343043
30434404411044120441304414044210442
04422044230442404431044320443304434
44340444104442044430444411111211113
11131111411122111231112411132111331
13311134111421114311144112121121311
13112141122211223112241123211233112
31123411242112431124411312113131131
11314113221132311324113321133311334
13341134211343113441141211413114141
41411422114231142411432114331143411
34114421144311444121221212312124121
41213212133121341214212143121441221
12213122141222212223122241223212233
22331223412242122431224412313123141
31412322123231232412332123331233412
34123421234312344124131241412422124
21242312424124321243312434124421244
12443124441313213133131341314213143
31431314413214132221322313224132321
23213233132341324213243132441331413
14133221332313324133321333313334133
41334213343133441341413422134231342
13424134321343313434134421344313444
34441414214143141441422214223142241
22414232142331423414242142431424414
44143221432314324143321433314334143
41434214343143441442214423144241443
14432144331443414442144431444422222
22223222242223322234222432224422323
23232232422333223342234322344224232
42322424224332243422443224442323323
33232342324323244233242333323334233
42334323344234242343323434234432344
23444242432424424333243342434324344
43442443324434244432444433333433344
33443343433444343443444440000