Brute-Forcing PIN Code Keypads Using Combinational Mathematics
by Alva Ray
Where I live - and probably in many parts of the world - most residential houses are guarded at entrance by the simple mechanism that is the four-digit PIN code. By pressing buttons on a numeric keypad in the correct order, the door will unlock, and all residents share that single code. Many of these numeric keypads have the same couple of flaws that make them more vulnerable to brute-force attacks: First, there is no confirmation button that needs to be pressed after having entered four digits. Second, the last four entered digits will always be accepted, instead of the pad resetting after an incorrect PIN code.
Now, brute-forcing a keypad of this kind only involves a maximum of 10,000 codes to begin with. While this may seem a large number, it's actually quite small compared to the possible number of combinations when brute-forcing, for example, a computer password. (A four-letter password using lowercase a-z means 456,976 combinations.) The big difference between brute-forcing a computer password and trying PIN codes on a physical keypad is, of course, that the latter can't easily be automated, meaning it will be very slow.
To go through all possible PIN codes, you could start at 0000, 0001, 0002, etc., and try them all in order. You would be looking at a maximum of 40,000 key presses, hoping for the correct PIN code to be early in the sequence. Being a skilled keypad operator able to try one PIN code per second, this method would still mean up to three hours of hard work and sore fingers.
But because of the flaws mentioned in the beginning, you don't have to press that many buttons. After having tried the first four PIN codes (0000, 0001, 0002, 0003) you have actually already tried ten different ones, since the pressed sequence also contained 0010, 0100, 1000, 0020, 0200, and 2000. By this principle, the number of required key presses is only a quarter of that initial 40,000. If you can keep up the same speed as previously, this means "only" about 40 minutes of work. However, the process in this case will probably be slower since the pressed sequence will not just be an ordered set of increasing numbers - something that otherwise favors physical brute-forcing since it can be carried out in a more systematic and thus faster fashion.
So, what shortened sequence might that be?
In other words, what is the shortest possible sequence of digits containing all of the four-digit PIN codes from 0000 to 9999? Luckily, combinatorial mathematics can answer that for us, in the form of so called "de Bruijn sequences." Named after the Dutch mathematician Nicolaas Govert de Bruijn, attributing it to Camille Flye Sainte-Marie, Tatyana Pavlovna Ehrenfest, and himself, such sequence is according to Wikipedia:
[A] cyclic sequence of a given alphabet A with size k for which every possible sub-sequence of length n in A appears as a sequence of consecutive characters exactly once."
In the case of keypad PIN codes, the alphabet has a length of ten (the digits 0-9) and the sub-sequence a length of 4.
Every de Bruijn sequence has a length of k^n, so this one will be 10,000 digits, plus an extra three zeroes at the end to cover all PIN codes, since the sequence is cyclic. Concluding this short mathematical excursion, all four-digit PIN codes can be expressed through a 10,003 digit number.
It turns out this string of numbers fits on approximately two A4 pages, meaning it could be printed double-sided on a single sheet, small enough to always be carried around in your toolbox/bag/wallet/pocket/hidden compartment. Any savants out there might find it useful to just memorize the whole thing. While still implying anywhere between one and several hours of number punching, this sequence will ensure the absolute minimum number of key presses.
Some possible scenarios: Finding yourself locked in, guessing a PIN code your only escape, this will definitely save you valuable time and oxygen. Forgetting or losing the PIN code to your rented storage space or garage, it will save you the money for having the code reset by an operator. You could even save some stamp money by delivering all your mail yourself! O.K., that last one was a joke, but you get the point.
Speaking of mail, the chances of hitting a correct PIN code early on in the sequence at any given residential house entrance are in fact higher than one in 10,000. At least over here, keypads accept additional PIN codes used exclusively by letter-carriers, codes that are often shared throughout entire neighborhoods. By going through the entire sequence on a less prominent keypad in your area, maybe in batches to avoid suspicion, you might find multiple working PIN codes. In that case, one of them is likely a service-type one - a skeleton key among PIN codes. Nota bene, you should not do this for any space you are not allowed access to in the first place, but that goes without saying.
I want to end this article with an idea for an invention:
It was said earlier that trying PIN codes on a physical keypad is not easily automated. However, it would be interesting to do just that, by building a small device with a set of mechanical "thumbs" that can be held against the keypad. It would then run through the optimal 10,003 digit PIN code sequence, pushing the buttons much faster than any human could.
If the device could try even just ten PIN codes per second, it would take at most 16 to 17 minutes to guess the right one. If lucky, and if there are multiple correct codes, it would take a much shorter time than that.
The device could be run by an Arduino board or similar, having some software on it that could calculate de Bruijn sequences itself given PIN code length, and remembering its position in the sequence when deactivated. If written so, and if activation of the device happens simply by pushing it against the keypad and deactivation occurs by releasing it, you would have a very stealthy piece of brute-force machinery.
You could visit a keypad for just a minute at a time over the course of several hours or even days, always continuing where you left off. Bonus points for coming up with some clever way to make the thumbs flexible enough to be fitted on any keypad layout (4-3, 5-2, etc.).
The advanced hardware hacker could even add a sensor to the device that can notice a green light, the common keypad mechanism for signaling that the correct PIN code was entered. With a built-in GPS and wireless, the device could save its location and the correct PIN code and, when connected to the Internet, report this data to a shared database.
Without further ado, and using some Python code found on Wikipedia, I've generated for you the 10,003 digits making up the shortest possible sequence containing all PIN codes between 0000 and 9999 exactly once.
Cut it out and save it, because you never know when it might come in handy: