¿Puede una red neuronal romper algoritmos de hash?

15

He estado leyendo un poco sobre redes neuronales y su capacidad para aproximarse a muchas funciones complejas.

¿Una red neuronal no sería capaz de romper un algoritmo de hash como SHA256?

Por ejemplo, supongamos que queremos entrenar a nuestra red para romper cadenas de 8 caracteres con hash. Podríamos pasar por todas las permutaciones y capacitar a la red, ya que conocemos las entradas y salidas esperadas. ¿Sería la red técnicamente capaz de descifrar una cantidad relativamente buena de hash SHA256 que se asignan a cadenas de 8 caracteres? ¿Se ha hecho esto previamente?

    
pregunta Omega 29.08.2016 - 07:32
fuente

6 respuestas

31

No.

Las redes neuronales son patrones de coincidencia. Son muy buenos emparejadores de patrones buenos , pero igual emparejadores de patrones. No más avanzados que los cerebros biológicos que pretenden imitar. Más minucioso, más incansable, pero no más sofisticado.

Los patrones deben estar allí para ser encontrados. Tiene que haber un sesgo en los datos para desentrañar. Pero los hash criptográficos están diseñados explícita y extremadamente cuidadosamente para eliminar cualquier sesgo en la salida. Ningún bit es más probable que cualquier otro, ninguna salida tiene más probabilidades de correlacionarse con una entrada determinada. Si tal correlación fuera posible, el hash se consideraría "roto" y un nuevo algoritmo tomaría su lugar.

Se han encontrado fallas en las funciones de hash anteriormente , pero nunca con la ayuda de una red neuronal. En cambio, ha sido con la aplicación cuidadosa de ciertos principios matemáticos.

    
respondido por el tylerl 29.08.2016 - 08:07
fuente
8

ACTUALIZA tu comentario:

  

Sé que sería computacionalmente inviable. Solo quería saber si sería teóricamente posible (no parece según tylerl)

Sí, dado el tiempo infinito y la energía infinita, una red neuronal podría romper el SHA256 . PERO (y creo que este es el punto que está haciendo @tylerl) porque las funciones hash no tienen patrones perceptibles, una red neuronal no podría hacer nada mejor que la fuerza bruta ingenua de construir una tabla de búsqueda al calcular el hash de cada posible cadena. Dicha tabla de búsqueda tendría más entradas (~ 2 256 ) que átomos en el planeta tierra (~ 2 166 ), al menos con nuestro nivel actual de tecnología. es "imposible" mantener esa tabla en la memoria o almacenarla en cualquier disco. De manera similar, para que su red neuronal tenga un desempeño notablemente mejor que un tirador de dados, la cantidad de neuronas que necesitaría probablemente también excedería la cantidad de átomos en el planeta.

Entonces, sí, es computacionalmente inviable, pero aún así es teóricamente posible. De hecho, en la criptografía en general es cierto que en siempre se puede forzar algo en teoría, pero decimos "suficientemente bien" cuando podemos demostrar que hacerlo requerirá más tiempo que la vida útil de la Universo y más energía que la contenida en el sol.

Creo que el contra-argumento es en respuesta a:

  

Podríamos a través de todas las permutaciones y capacitar a la red ya que conocemos las entradas y salidas esperadas.

1) ¿Es esto fundamentalmente diferente a una tabla de búsqueda?

2) SHA256 tiene un espacio de salida de 2 256 , y un espacio de entrada que es esencialmente infinito. Para referencia, se estima que el tiempo desde el big bang es de 5 mil millones de años, que es aproximadamente 1,577 x 10 27 nanosegundos, que es aproximadamente 2 90 ns. Por lo tanto, si cada iteración de entrenamiento toma 1 ns, necesitarías 2 166 edades del universo para entrenar tu red neuronal.

El punto aquí es que SHA256 tiene 2 256 salidas posibles, y 2 256 es realmente un gran número realmente .

    
respondido por el Mike Ounsworth 29.08.2016 - 17:46
fuente
7

Desde un ángulo diferente:
Podría reducirlo al problema abierto "¿existe un algoritmo eficiente para factorización de enteros ". Si tal algoritmo existe, una NN podría descubrirlo a través de búsqueda de prueba guiada , y podría usarse para socavar toda la seguridad .

    
respondido por el micimize 03.10.2017 - 20:05
fuente
4

"¿Puede una red neuronal convertirse en la 'función inversa' de una función hash?" Tal vez. No hay ninguna prueba matemática de que cualquier función hash dada, ya sea SHA o cualquier otra, carezca de patrones entre el dominio y la imagen. Como han señalado otros respondedores, las funciones hash están diseñadas explícitamente de modo que no se conocen cualidades conservadas. Si hay algún tipo de patrón, entonces, teóricamente, una red neuronal podría encontrarlo, pero estoy seguro de que se ha intentado antes y SHA todavía existe, por lo que podemos suponer que no tuvieron éxito. Podría mencionar que tendrías que probar esta 'falta de patrón' para cada función hash individualmente.

Pongo "función inversa" entre comillas porque las funciones hash deben ser sobreyectivas (sin embargo, la superjetividad generalmente no está probada formalmente) y, como tal, pueden tener dos números asignados al mismo número, por lo tanto, no hay un inverso verdadero. Sin embargo, la función inversa no necesita ser una función verdadera, en el sentido de que puede devolver un conjunto de números o una función que describe un conjunto de números. La función inversa de fuerza bruta de una función hash simplemente devolvería el dominio (por ejemplo, los números naturales), y una función inversa más sofisticada devolvería un subconjunto real del dominio.

En realidad, sería interesante entrenar una red neuronal: La NN devuelve una función como salida. La función tiene cierta densidad dentro de la imagen que se podría aproximar, cuanto menor sea la densidad, mayor será la recompensa. Ahora, para entrenar a la NN, debe ingresar f (x) y verificar si x < - {g (c) | c < - | N} mientras que g es la función que NN devuelve como salida.

    
respondido por el Mark I.O. 11.08.2017 - 03:50
fuente
3

La red neuronal o cualquier otro algoritmo de aprendizaje automático no es mágico, incluso si pudiera tener este aspecto. Al final, estos métodos son solo un conjunto de ecuaciones (es decir, matemáticas) para asignar la entrada a la salida y el aprendizaje es ajustar los parámetros de estas ecuaciones para que el resultado refleje los datos de entrenamiento lo mejor posible. De esta manera, intenta aprender la estructura inherente de los datos con la esperanza de que esta estructura sea la misma para la mayoría de las otras entradas posibles también. O en resumen: es solo matemáticas.

Si existiera una estructura tan inherente que permita un mapeo relativamente fácil desde el valor de hash al valor original o incluso si esto solo resultara en una gran reducción del espacio de búsqueda para hacer posible la fuerza bruta, entonces este hash no se consideraría una criptográfico fuerte hash. Y dado que no es necesario utilizar una red neuronal o similar para investigar este tipo de problemas, estoy bastante seguro de que esto está hecho y de que las redes neuronales no imponen ningún peligro nuevo.

    
respondido por el Steffen Ullrich 29.08.2016 - 08:01
fuente
3

No, Las redes neuronales usan fundamentalmente la optimización decente. Las redes neuronales son una familia interesante de funciones y en la práctica logramos optimizarlas bastante bien a pesar de no ser un problema convexo.

Para que una técnica de optimización de este tipo funcione, necesitamos una cantidad mínima de suavidad, necesitamos una noción de casi correcta. No tenemos esto con funciones hash criptográficas. Esperamos un solo giro de un bit para voltear la mitad de las salidas. En la mayoría de los lugares tenemos pequeños cambios que conducen a pequeños cambios, no tanto en la criptografía. Es por esto que las redes neuronales pueden aprender a invertir primitivas criptográficas.

    
respondido por el Meir Maor 03.10.2017 - 21:18
fuente

Lea otras preguntas en las etiquetas