¿Cómo se puede aplicar un algoritmo a la ingeniería inversa?

Question

Me pregunto cómo se hace para revertir un algoritmo, como uno para almacenar inicios de sesión o códigos PIN.

Digamos que tengo una cantidad de datos donde:

7262627 -> ? -> 8172 

5353773 -> ? -> 1132 

etc Esto es sólo un ejemplo. O di una cadena hexagonal que se transforma en otra.

&h8712 -> &h1283 o algo así.

¿Cómo empiezo a descubrir qué es ese algoritmo? ¿Dónde comienza uno?

¿Empezarías a probar diferentes turnos, xors y esperar que algo se destaque? Estoy seguro de que hay una mejor manera ya que esto parece apuñalar en la oscuridad.

¿Es prácticamente posible realizar ingeniería inversa de este tipo de algoritmo?

Disculpe si esta es una pregunta estúpida. Gracias por su ayuda/punteros.

Answer 1

¿Es incluso posible la ingeniería inversa de este tipo de algoritmo?

Es posible con un algoritmo defectuoso y suficientes pares cifrados/no encriptados, pero un algoritmo bien diseñado puede eliminar la posibilidad de hacerlo.

Answer 2

Probablemente, no se puede. Supongamos que la función de transformación es conocida, algo así como

function hash(text): 
    return sha1("secret salt"+text) 

Pero la "sal secreta" no se conoce, y es criptográficamente fuerte (un entero muy grande, al azar). Nunca se podría forzar en bruto la sal secreta incluso de una gran cantidad de pares de texto cifrado y crypttext.

De hecho, si se sabía que la función hash precisa utilizada era una de las dos funciones igualmente potentes, nunca se podía obtener una buena idea de cuál se estaba utilizando.

Answer 3

Hay algunas cosas que la gente trata:

• obtener el código fuente, o desmonte un ejecutable.
• Adivina, basado en las funciones hash que otras personas usan. Por ejemplo, un hash que consta de 32 dígitos hexadecimales podría ser una o más repeticiones de MD5, y si puede obtener un solo par de entrada/salida, entonces es bastante fácil confirmarlo o refutarlo (aunque vea "sal", más abajo) .
• Analice estadísticamente una gran cantidad de pares de entradas y salidas, buscando cualquier tipo de patrón o correlaciones, y relacione esas correlaciones con las propiedades de las funciones hash conocidas y/o las posibles operaciones que el diseñador del sistema podría haber utilizado. Esto está más allá del alcance de una técnica única, y en los dominios del criptoanálisis general.
• Pregunta al autor. Los sistemas seguros generalmente no confían en el secreto de los algoritmos hash que usan (y generalmente no permanecen seguros por mucho tiempo si lo hacen). Sin embargo, los ejemplos que das son bastante pequeños, y el uso de contraseñas seguras siempre implicaría una sal, que aparentemente tuyo no contiene. Entonces, quizás no estemos hablando del tipo de sistema en el que el autor confía en hacer eso.

En el caso de un hash donde la salida tiene solo 4 dígitos decimales, puede atacarlo simplemente construyendo una tabla de cada entrada de 7 dígitos posible, junto con su valor hash. A continuación, puede invertir la tabla y tiene su operación de eliminación de hash (de uno a muchos). Nunca necesita saber cómo se calcula realmente el hash. ¿Cómo se obtienen los pares de entrada/salida? Bueno, si un extraño puede de alguna manera especificar un valor que se va a aplicar a hash, y ver el resultado, entonces tienes lo que se llama un "texto plano elegido", y un ataque que depende de eso es un "ataque de texto plano elegido". Entonces, un hash de 7 dígitos -> 4 dígitos sería muy débil si se usara de una manera que permitiera que los ataques de texto claro elegidos generaran muchos pares de entrada/salida. Me doy cuenta de que es solo un ejemplo, pero también es solo un ejemplo de una técnica para revertirlo.

Tenga en cuenta que la ingeniería inversa del hash, y en realidad invertirlo, son dos cosas diferentes. Podría darse cuenta de que estoy usando SHA-256, pero eso no lo ayudaría a revertirlo (es decir, dado un resultado, resuelva el valor de entrada). Nadie sabe cómo revertir completamente SHA-256, aunque, por supuesto, siempre hay tablas de arcoiris (ver "sal", arriba) <conspiracy> Al menos nadie admite que lo hacen, por lo que no nos sirve ni a ti ni a mí. </conspiracy>

Answer 4

Apuñalar en la oscuridad lo llevará a la locura. Hay algunos algoritmos que, dado el conocimiento actual, no se puede esperar para deducir el funcionamiento interno de entre ahora y el final [predicho] del universo sin conocer los detalles exactos (que pueden incluir claves privadas o estado interno). Por supuesto, algunos de estos algoritmos son los fundamentos de la criptografía moderna.

Si sabes de antemano que hay un patrón por descubrir, a veces hay formas de acercarte a esto. Por ejemplo, si el conjunto de datos contiene varios valores de entrada que se diferencian por 1, comparar los valores de salida correspondientes:

 
7262627 -> 8172 
7262628 -> 819 
7262629 -> 1732 
... 
7262631 -> 3558 

Aquí es bastante clara (dado unos cuantos minutos y una calculadora) que cuando la entrada se incrementa en 1, el la producción aumenta en 913 módulo 8266 (es decir, un simple linear congruential generator).

Differential cryptanalysis es una técnica relativamente moderno utilizado para analizar la fortaleza de cifrado por bloques de cifrado, basándose en una idea similar, pero más complejo para el que se conoce el algoritmo de cifrado, pero se asume que la clave privada no es . Los bloques de entrada que difieren entre sí por un solo bit se consideran y el efecto de ese bit se rastrea a través del cifrado para deducir la probabilidad de que cada de salida bit se "voltee" como resultado.

Otras formas de abordar este tipo de problema serían observar los extremos (valores mínimos, máximos), distribución (que conduce a frequency analysis), dirección (¿los números siempre aumentan? Disminuyen?) Y (si esto está permitido) considerar el contexto en el que se encontraron los conjuntos de datos. Por ejemplo, algunos tipos de códigos PIN siempre contienen un dígito repetido para que sean más fáciles de recordar (no estoy diciendo que un código PIN pueda necesariamente ser deducido de cualquier otra cosa, solo que un dígito repetido es uno menos dígito a ¡Preocúpate!).