Generador de secuencias de De Bruijn para implementación de código de registro de desplazamiento de fuerza bruta más rápido

Generador de secuencias de De Bruijn para implementación de código de registro de desplazamiento de fuerza bruta más rápido

Nota importante: este artículo no pertenece a Our Code World de ninguna forma. El artículo es propiedad intelectual de Damir Vodenicarevic, un artículo alojado en su blog aquí (al menos solía serlo) . Como el sitio web de Damir ha estado inactivo durante algunas semanas debido a un certificado SSL desactualizado, decidí hacer una copia del artículo para mantener la información disponible para todos, ya que es difícil encontrar el tema que se discutirá en el artículo. (Una implementación de JavaScript del generador de secuencias De Bruijn). El contenido ha sido extraído de Wayback Machine.

Introducción

Algunos tipos de cerraduras de código de puerta digital miran los últimos 4 dígitos escritos por el usuario, los comparan con el código de puerta almacenado y, si coinciden, la puerta se desbloquea. Esto significa que cada vez que se ingresa un dígito, se prueba un código posible. Entonces, para descifrarlo probando todos los códigos posibles de 4 dígitos (fuerza bruta), no necesitamos escribir todos los códigos posibles (4 pulsaciones de botón por código), sino ingresar una secuencia inteligente que prueba un código (casi ) por botón pulsado. Esta secuencia es la secuencia de Bruijn.

En términos generales, las secuencias de De Bruijn son cadenas de caracteres en las que cada secuencia posible de n caracteres de un alfabeto dado (de tamaño k ) aparece una y solo una vez. Su longitud es kⁿ y son cíclicos. Esto significa que al escribir una secuencia de Bruijn de longitud kⁿ + (n - 1) (el último ciclo del código al comienzo de la secuencia) es posible descifrar el código, en comparación con nx kⁿ pulsaciones de botón probando cada código explícitamente.

Implementación

Las secuencias de De Bruijn se pueden generar usando algoritmos simples. Aquí hay una implementación de javascript de uno de ellos. Tenga en cuenta que el resto del último código se adjunta para evitar tener que obtener sus caracteres desde el principio de la secuencia.

Aquí está el código fuente javascript del generador de secuencia de Bruijn presentado arriba:

/*
  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;
}

Ejemplo

Para una combinación de un alfabeto de 3 caracteres (abc) con variaciones de 2, el código podría usarse así:

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

Y daría como resultado algo como:

a a b a c b b c c a 

Conclusión y técnicas de mitigación

El uso de secuencias de Bruijn acelera la fuerza bruta del teclado. Sin embargo, este enfoque no es milagroso: solo divide el número de caracteres a escribir por la longitud del código, y el número de intentos aún puede ser prohibitivo. Un escenario típico en el peor de los casos sería un diccionario de teclado completo 0123456789AB y una longitud de código de 5, que representa una secuencia de longitud 248836 y, en el peor de los casos, 35 horas de trabajo a una velocidad de 2 caracteres por segundo. Es mejor que sin las secuencias de De Bruijn (173 horas) pero sigue siendo bastante pesado.

Reducir el tamaño del diccionario disminuye drásticamente el tiempo de prueba y se puede lograr si las manchas son visibles en los dígitos que se utilizan realmente. Caso típico: código de longitud 4, manchas en los números 1, 2, 3 y 4 (este es el diccionario): la secuencia tiene entonces solo 259 caracteres y tarda unos 2 minutos en descifrarse en el peor de los casos.

Una idea para mitigar la fuerza bruta es agregar un botón para confirmar el código ingresado. En ese caso, se pierden las ventajas de las secuencias de De Bruijn y se debe realizar el forzado bruto. Un enfoque aún mejor es restablecer el registro de desplazamiento después de que se haya escrito un número de caracteres igual a la longitud del código, o después de un cierto retraso de inactividad, y esperar 1 segundo antes de permitir un reintento si el código es incorrecto.
La combinación de estas dos técnicas maximiza la seguridad al evitar también que se revele la longitud del código. Estas técnicas de mitigación ya están en uso por muchas cerraduras de código digital y deberían hacerlas bastante seguras siempre que estén limpias (sin manchas), que sus códigos sean lo suficientemente largos, no obvios y cambiados regularmente, y que no haya un simple ataque de canal lateral. (como mirar a alguien que escribe el código) está disponible.

Por favor, no uses esto para romper nada que no sea tuyo y no finjas que no te lo advertí.

Esto podria interesarte

Conviertete en un programador más sociable