Todos los algos de hash se rompen ... entonces, ¿por qué no cambiar de bala dorada a disparo de dispersión? [duplicar]

1

A partir de esta mañana, cualquier hash SHA-1 puede colisionarse oficialmente por tan solo $ 110k en potencia de GPU en Amazon.

enlace

enlace

Obviamente, esto significa que para muchas aplicaciones, SHA-1 es completamente inútil y que en los próximos años habrá seguido el camino del MD5.

Pregunta :

Parece que con el tiempo decidimos que la mejor manera de hacer las cosas más seguras es crear algoritmos que necesiten cada vez más entropía de bits y más y más potencia de procesamiento de CPU, lo que parece una solución falsa.

Si la entropía de 128 bits es suficiente entropía (es decir, AES-128 es preferible a AES-256), ¿por qué no creamos algoritmos que puedan manejar mejor la entropía de 128 bits?

Además, en lugar de pasar a algoritmos en los que también se encontrarán fallas que aumentarán drásticamente la CPU, la memoria y los requisitos de almacenamiento (hay una GRAN diferencia entre el MD5 y el SHA-256 cuando se realiza la computación en un teléfono o una pi de frambuesa), ¿por qué no emparejamos dos algoritmos imperfectos juntos?

Por ejemplo: no podríamos ejecutar 512 bits a través del algoritmo MD5 y luego ejecutar esos mismos 512 bits a través de un SHA-1 y hacer un simple mux sobre el resultado combinado y aunque ambos algoritmos tienen ataques conocidos, la coincidencia de un atacante que encuentre cualquier conjunto de bits que se alinee en las tablas de ambos algoritmos parece que sería bastante seguro. O simplemente digiera el MD5 a la inversa en cada bloque y esparza algunos de los bits fuente anteriores cada n bloques: puede leer un bloque hacia adelante, invertir los bits, pasarlo al revés y luego continuar con el siguiente bloque y después de 16 bloques el enésimo bit de los bloques fuente originales, tal vez incluso tenga una ventana móvil en él, con menos de 1k de memoria en un momento dado.

Parece que estamos tratando de encontrar esta única solución matemática definitiva para entropiar a algo que podría resolverse mucho más simple con dos o tres soluciones matemáticas más simples que están fuera de banda entre sí y esto sería más rápido, más memoria eficiente, más almacenamiento eficiente y más seguro que cualquier algoritmo único.

¿Hay algún fallo en mi razonamiento?

Esto NO ES UN DUPLICADO

El otra pregunta es hablar sobre tomar el resultado final de un hash en serie con otro (enlace más débil):

f(g(x)) => y

Mi pregunta es sobre el uso de múltiples hashes simultáneamente en cada bloque para evitar debilidades (exclusión mutua de vulnerabilidades)

for n of x:
    f(x[n]) \
             (x[n]')XOR(x[n]'') => y
    g(x[n]) /

Debido a que la pregunta es diferente, las respuestas también son diferentes.

    
pregunta CoolAJ86 23.02.2017 - 18:23
fuente

2 respuestas

1

Primero, estás haciendo suposiciones sobre las propiedades de XORing dos resúmenes de hash. A menos que haya estudiado completamente Y analizado todas las implicaciones estadísticas de esta salida, potencialmente está creando un cifrado extremadamente débil. La lección número uno de criptografía es la siguiente: NO use cifrados hechos en casa. A menos que seas un criptógrafo muy experimentado, no entenderás todas las implicaciones de tus acciones.

Utilizamos funciones verificadas y estudiadas públicamente, como las familias sha2 y sha3, ¡porque conocemos sus propiedades! Fueron creados por expertos y analizados por los mejores matemáticos que tenemos. Los hemos creado de tal manera que actualmente no son computables dentro de un marco de tiempo razonable. Es decir, siempre que no se descubra algún "truco" matemático para hacer que nuestro hash sea fácil de calcular: simplemente podemos aumentar el tamaño de bits de nuestra clave tan pronto como el hash se aproxime a la capacidad de cálculo en un marco de tiempo razonable.

Tomemos un momento y recordemos lo que es un poco. Es un '1' o un '0'. Esto significa que tenemos 2 estados posibles. Veamos un ejemplo muy simplista: supongamos que tenemos una función hash con un tamaño de clave de 3. Ahora tenemos 2 ^ 3 = 8 estados posibles. Tamaño de clave de 4: 2 ^ 4 = 16 estados. Tamaño de clave de 5: 2 ^ 5 = 32 estados. ¿Notar un patrón? Cada vez que aumentamos el tamaño de la clave en 1 bit, estamos duplicando la cantidad de estados que potencialmente tenemos. Cuando llegamos a tamaños de clave más grandes, puedes ver el poder extremadamente simple de aumentar el tamaño de la clave. ¡Duplica el espacio que un atacante tiene que usar fuerza bruta para encontrar una colisión! ¡Este es un gran crecimiento para que un ataque tenga que computar! (Piense en tamaños de clave reales como 2 ^ 128 o 2 ^ 256, estos son números enormes) Sin embargo, sha2 y sha3 son algoritmos de hashing muy rápidos. Por lo tanto, para un usuario que lo calcula solo una vez, el pequeño aumento en el espacio de cómputo y almacenamiento es absolutamente reducido por el trabajo adicional que debe realizar un atacante. (Si tiene contraseñas de hash, DEBE usar una función de hash lenta como bcrypt)

¿Cuánto 'almacenamiento extra' estamos realmente hablando? Vayamos a un ejemplo extremo: la criptografía asimétrica (también llamada criptografía de clave pública), ya que requiere claves mucho más grandes que la criptografía simétrica. (NOTA: la entropía de esta función es muy diferente y no es comparable simplemente mirando los tamaños de los bits, pero para fines de almacenamiento, esto funcionará bien) La clave RSA más grande que se rompió fue de 768 bits, con 1024 teorizados como vulnerables. Entonces, comparemos una clave de 1024 bits y una clave de 4096 bits. Una clave de 1024 bits es de 128 bytes o 0.128 kb. Una clave de 4096 bits es 512 bytes o 0.512 kb. El costo de almacenarlos es tan ridículo debido a los costos actuales del disco duro que no se preocupa por nada. Vamos a probarlo. Según Forbes en 2016, el costo por GB fue de $ 0.033. Eso significa que el costo de almacenar una KB es de $ 0.000000033 / KB o $ 0.000000016896 para almacenar nuestra clave RSA de 4096 bits. (NOTA: estoy usando 1000 bits / kilobyte según la mayoría de los fabricantes de hardware). En cuanto a los pasos computacionales adicionales, el único lugar en el que esto importará es el hardware integrado o los sistemas extremadamente pequeños. Si la información que está transfiriendo necesita confidencialidad, entonces el tiempo adicional valdrá la pena. También hay hardware diseñado específicamente para la criptografía, por lo que no veo esto como un problema en aplicaciones reales de criptografía.

NOTA: Debido al teorema de cumpleaños, la cantidad realista de fuerza bruta que un atacante tendría que hacer solo sería la MITAD del tamaño de la clave. Por lo tanto, para una clave de 128 bits o un espacio de claves de 2 ^ 128, un atacante en realidad solo necesita fuerza bruta de 2 ^ 64 hashes para encontrar una colisión con una probabilidad del 99.7%.

¡En cuanto a tu idea de barajar la entrada leyendo bloques separados, hacia delante, hacia atrás, etc. que es similar a lo que ya están haciendo las funciones de hash SHA! Están creando permutaciones y sustituciones entre los datos de entrada para terminar con el resumen de hash de salida. Usan dos herramientas para hacer esto: s-box's (sustituciones) y p-box's (permutaciones). Son un poco más complejos que su ejemplo, pero su idea para mezclar los bits de entrada & ¡Mezclarlos es lo que hace que funcionen las funciones hash reales!

Estoy interesado en aprender más sobre esto, te sugiero que leas esto gratis & maravilloso libro de texto: Ingeniería de seguridad por Ross Anderson

    
respondido por el peevishprogrammer 24.02.2017 - 01:08
fuente
2

128 bits debería ser suficiente entropía - vea esta respuesta . Las computadoras cuánticas pueden cambiar esto, pero eso es aún teórico.

Parece ser (relativamente) bastante fácil diseñar un cifrado simétrico donde el único ataque efectivo es la fuerza bruta. AES ha resistido algunos años de criptoanálisis y hay muchos otros cifrados.

El cripto asimétrico generalmente necesita claves mucho más grandes para una seguridad equivalente.

Para los hashes, y específicamente para la resistencia a las colisiones, debemos preocuparnos por el ataque de cumpleaños . En términos generales, significa que un hash debe ser dos veces más largo que el cifrado simétrico equivalente. Entonces, SHA-256 es una buena opción para AES-128.

Debo señalar que tanto MD5 como SHA-1 tuvieron interrupciones criptográficas: los ataques son mejores que la fuerza bruta. SHA-1 es un hash de 160 bits, por lo que la fuerza bruta (con ataque de cumpleaños) requeriría 2 ^ 80 operaciones, pero el ataque publicado usó más como 2 ^ 64. Puede resultar que SHA-256 tenga debilidades criptográficas, pero tendrían que ser significativamente mejores que la fuerza bruta para que un ataque sea práctico.

    
respondido por el paj28 24.02.2017 - 00:14
fuente

Lea otras preguntas en las etiquetas