De Bruijn Sequence Generator for Faster Shift Register Code Bruteforcing with JavaScript

Introduction

Some types of digital door code locks look at the last 4 digits typed by the user, compare them to the stored door code and if they match, the door unlocks. This means that every time a digit is entered, one possible code is tested. So in order to crack it by testing all the possible 4-digit codes (bruteforcing), we don't need to fully type every possible code (4 button pushes per code), but to enter a clever sequence that tests one code (almost) per button pushed. This sequence is the de Bruijn Sequence.

Roughly speaking, De Bruijn sequences are character strings in which every possible sequence of n characters from a given alphabet (of size k) appears once and only once. Their length is kⁿ and they are cyclic. This means that by typing a de Bruijn sequence of length kⁿ + (n - 1) (the last code cycles to the beginning of the sequence) it is possible to crack the code, as compared to n x kⁿ button presses by testing every code explicitly.

Implementation

De Bruijn sequences can be generated using simple algorithms. Here is a javascript implementation of one of them. Note that the remainder of the last code is appended to avoid having to get its characters from to the beginning of the sequence.

Here is the javascript source code of the de Bruijn sequence generator presented above:

/*
  De Bruijn sequence generator javascript implementation
  Code written by Damir Vodenicarevic (https://damip.net) in march 2017.
  This work is licensed under a Creative Commons Attribution 4.0 International License.
  http://creativecommons.org/licenses/by/4.0/
*/

//Inspired by Frank Ruskey's Combinatorial Generation
//Parameters:
//  alphabet [string]: each character is an element of the alphabet
//  wordlength [positive integer]: length of a word
var debruijn = function (alphabet, wordlength) {
    var k = alphabet.length;
    var n = wordlength;
    if (k <= 0 || n <= 0) return '';
    var a = []; for (var i = 0; i < k * n; ++i) a[i] = 0;
    var res = [];
    var db = function (t, p) {
        if (t > n) {
            if (n % p == 0) {
                for (var i = 1; i <= p; ++i)
                    res += alphabet[a[i]] + ' ';
            }
        }
        else {
            a[t] = a[t - p];
            db(t + 1, p);
            for (var j = a[t - p] + 1; j < k; ++j) {
                a[t] = j;
                db(t + 1, t);
            }
        }
    }
    db(1, 1);

    //// Extra code to avoid having to cycle for the last word
    //Note: remove this part to get an actual de Bruijn sequence
    var extra = '';
    for (var i = 0, nremain = wordlength - 1; nremain > 0; i += 2, --nremain)
        extra += res[i % res.length] + ' ';
    res += extra;
    ////

    return res;
}

Example

For a combination of an alphabet of 3 characters (abc) with variations of 2, the code could be used like this:

console.log(debruijn("abc", 2));

And it would output something like:

a a b a c b b c c a 

Conclusion and mitigation techniques

Using de Bruijn sequences accelerates keypad brute-forcing. However, this approach is not miraculous: it only divides the number of characters to type by the length of the code, and the number of trials may still be prohibitive. A typical worst-case scenario would be a full keypad dictionary 0123456789AB and a code length of 5, which represents a sequence of length 248836, and at worst 35 hours of work at a rate of 2 characters per second. It's better than without de Bruijn sequences (173 hours) but still pretty heavy.

Reducing the dictionary size dramatically decreases the trial time and can be achieved if stains are visible on the digits that are actually used. Typical case: code of length 4, stains on numbers 1,2,3, and 4 (this is the dictionary): the sequence is then only 259 characters long and takes about 2 minutes to crack in the worst case.

An idea to mitigate brute-forcing is to add a button to confirm the entered code. In that case, the advantages of de Bruijn sequences are lost, and raw brute-forcing must be performed. An even better approach is to reset the shift register after a number of characters equal to the code length has been typed, or after a certain delay of inactivity, and wait 1 second before allowing a retry if the code is wrong.
Combining both these techniques maximizes the security by also preventing the code length from being disclosed. These mitigation techniques are already in use by many digital code locks and should make them pretty safe provided that they are cleaned (no stains), that their codes are long enough, non-obvious and regularly changed, and that no simple side-channel attack (like looking at someone typing the code) is available.

Please do not use this to break anything that is not yours and don't pretend I didn't warn you.