Los ataques de colisión son una preocupación importante en el ámbito de la criptografía. En determinadas circunstancias, un atacante puede utilizarlos para socavar la seguridad que otorgan las firmas digitales, lo que les permite hacer que los datos parezcan fraudulentos como si se hubiera verificado su integridad y autenticidad. Esto significa que los ataques de colisión pueden eludir los mecanismos de seguridad en los que confiamos para mantener seguro nuestro mundo en línea.
Pero antes de que pueda comprender realmente qué es un ataque de colisión, primero debes entender qué es realmente una colisión. Para hacer eso, debemos dar un paso más atrás y ponerte al día con el hashing.
Indice
¿Qué es hash?
Una función hash criptográfica es un algoritmo que tiene una serie de propiedades específicas que resultan increíblemente útiles en el mundo de la criptografía. Toman una entrada, a menudo llamada mensaje, que luego se ejecuta a través de la función hash, lo que da como resultado la salida, un hash, que a veces también se denomina resumen de mensaje.
También hay funciones hash que no son criptográficas, que son algoritmos más simples que a menudo se usan en el almacenamiento y la recuperación de datos. Sin embargo, estos son tangenciales a los ataques de colisión, por lo que no nos molestaremos en discutirlos en profundidad.
Las propiedades de las funciones hash criptográficas incluyen:
- Son deterministas: cuando la misma entrada se ejecuta a través de una función hash dada, siempre da como resultado exactamente el mismo resultado, cada vez.
- Toman entradas de datos de tamaño arbitrario y siempre generan una cadena de longitud fija: una función hash puede aceptar datos de cualquier tamaño, desde un solo carácter hasta una enciclopedia llena de palabras. No importa cuánto tiempo dure la entrada, la salida de una función hash determinada siempre tiene la misma longitud.
- Son unidireccionales: es fácil tomar una entrada, ejecutarla a través de la función hash y luego averiguar cuál es el hash coincidente para esa entrada. Sin embargo, no es factible tomar un hash y luego averiguar cuál fue la entrada original del hash. Por ‘unidireccional’, queremos decir que solo es práctico calcular una función hash en una dirección, no en la otra.
- Se pueden calcular rápidamente: para que las funciones hash sean prácticas, necesitamos que puedan convertir rápidamente la entrada de un mensaje en un hash. Serían mucho menos útiles si el proceso tomara demasiado tiempo y requiriera una cantidad sustancial de recursos computacionales.
- Los cambios menores en la entrada dan como resultado cambios significativos en la salida: incluso si dos entradas son idénticas excepto por un solo carácter, una función hash criptográfica entregará hashes que parecen no tener casi nada en común.
- No es factible encontrar dos entradas diferentes que den como resultado el mismo resultado: para garantizar la seguridad en las aplicaciones de las funciones hash, no debe ser factible que un atacante encuentre dos entradas diferentes que produzcan el mismo hash. Cuando se encuentran dos entradas con el mismo hash, se denomina colisión.
Entonces, las funciones hash criptográficas tienen todas estas propiedades mágicas, pero ¿cómo se ven realmente?
Te daremos una demostración rápida con una calculadora de hash en línea. La herramienta web que hemos vinculado toma entradas, las ejecuta a través de SHA-256, que es la función hash estándar de oro, y luego entrega un hash de 256 bits.
Puedes probarlo con cualquier entrada que desees, pero analizaremos algunos solo para demostrar algunas de las propiedades clave. Cuando ejecutamos «What is hash?» a través de la calculadora, nos da un hash de:
2da0ed1070f7e7306a23785422576c864bdec63a6032482badc26fc5102f9a9c
El hash está en hexadecimal, que es simplemente una forma diferente de contar. En lugar de usar el sistema al que estamos acostumbrados, que tiene 10 números diferentes (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), el hexadecimal tiene 16 (0, 1, 2, 3, 4 , 5, 6, 7, 8, 9, a, b, c, d, e, f). El hash tiene 64 caracteres y, en notación hexadecimal, cada carácter tiene cuatro bits. Esto significa que el hash tiene una longitud de 256 bits.
Probemos una entrada diferente, solo el carácter único, «a». Cuando calculamos el hash, obtenemos:
ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb
Ten en cuenta que aunque las entradas tenían diferencias de tamaño significativas, las salidas tienen la misma longitud, 64 caracteres o 256 bits. Como dijimos, una de las propiedades de una función hash criptográfica es que aceptan entradas de cualquier longitud y siempre entregan una salida de longitud fija. Podrías intentar ingresar un libro completo en SHA-256, y aún así terminarías con un hash de 256 bits.
Ahora vamos a demostrar cómo incluso un ligero cambio en la entrada da como resultado un hash enormemente diferente. Tomemos nuestra entrada anterior, «What is hash?», pero cambiemos el signo de interrogación por un signo de exclamación, «¡What is hash!» Es un cambio relativamente insignificante, ¿verdad? Bueno, veamos qué obtenemos cuando lo lanzamos a través de la función hash:
02a3603765eb85b8aa96aa8c18df75675a0670b33eb2c306e54d13a2baabffa5
Si comparas este hash con el primero, verás que los dos básicamente no tienen nada en común. Esta es una parte importante de las funciones hash criptográficas, y esta propiedad se conoce como efecto avalancha.
Si has probado la calculadora tu mismo, habrás visto que estos hashes se calculan rápidamente. También puedes probar la misma entrada una y otra vez y verás que la función hash también es determinista: siempre obtendrás el mismo resultado para una entrada determinada.
Es un poco más difícil demostrarte que SHA-256 es una función unidireccional y que es casi imposible averiguar la entrada original si todo lo que tienes es el hash. También es un desafío mostrarte que es inviable encontrar dos entradas diferentes que den como resultado el mismo hash. Solo tendrás que confiar en nosotros en estas propiedades, ya que son fundamentales para el proceso de diseño de funciones hash criptográficas seguras.
Usos de los hashes
A estas alturas, probablemente tengas una idea de cómo son las funciones hash y qué pueden hacer, pero ¿cuál es el punto de convertir una entrada en un revoltijo de números y letras?
Bueno, resulta que todas esas propiedades son bastante útiles y los hash se implementan en una variedad de sistemas más grandes. Para comprender adecuadamente los peligros de los ataques de colisión, es importante comprender dónde se usa realmente el hashing criptográfico.
Firmas digitales
Una aplicación común es en firmas digitales. Si el remitente de un mensaje quiere probar que realmente vino de él y no de un impostor, y además que el mensaje no ha sido modificado después de haber sido enviado, puede hacerlo con una firma digital. Estos involucran certificados y algoritmos de clave pública como RSA además de hashing.
La versión corta de las firmas digitales es que la autenticidad y la integridad se pueden verificar si el remitente ejecuta su mensaje a través de una función hash criptográfica y luego lo ejecuta a través de un cálculo junto con su clave privada. El remitente luego envía este resultado como la firma digital junto con su mensaje al destinatario.
Cuando el destinatario recibe el mensaje, puede verificar su integridad y autenticidad ejecutando el mensaje a través de una función hash para obtener un hash del mensaje. Luego toman la firma digital que recibieron del remitente y realizan algunos cálculos con la clave pública del remitente.
Luego pueden comparar este resultado con el hash del mensaje que acaban de calcular. Si el mensaje que recibió el destinatario ha conservado su integridad y autenticidad, entonces estos dos valores deben ser iguales.
Hash de contraseña
Otro ejemplo es el hashing de contraseñas. Si una empresa almacena tu contraseña como texto sin formato, si un pirata informático ingresa y roba su base de datos de contraseñas, tendrá acceso a esa contraseña. El pirata informático puede simplemente mirar la base de datos y luego usar las contraseñas de texto sin formato para iniciar sesión en cualquier cuenta que desee, incluida la tuya.
Por lo tanto, almacenar contraseñas como texto sin formato es terrible para la seguridad , porque no podemos garantizar que podamos mantener las bases de datos de contraseñas fuera del alcance de los piratas informáticos.
Afortunadamente, las funciones hash criptográficas nos brindan una solución mucho mejor. Permiten a los desarrolladores verificar contraseñas sin tener que almacenar la contraseña como texto sin formato en una base de datos. Como mencionamos, es básicamente imposible encontrar dos entradas diferentes que den como resultado el mismo hash, y tampoco es factible tomar un hash y luego averiguar cuál fue la entrada inicial.
Esto significa que cuando configuras una cuenta y escribes tu nombre de usuario y contraseña, los desarrolladores pueden codificar tu contraseña de inmediato y solo almacenar el hash, nunca el texto sin formato de tu contraseña. Cada vez que inicias sesión, simplemente cifran tu contraseña tan pronto como la ingresas y luego la comparan con el hash que han almacenado en la base de datos.
Si los dos coinciden, los desarrolladores asumen que ingresaste la misma contraseña en ambas ocasiones y que, por lo tanto, es el mismo usuario. Por lo tanto, te otorgan acceso a tu cuenta, todo sin saber cuál es realmente tu contraseña.
Si un pirata informático roba una base de datos de hashes de contraseñas, es mucho más difícil para ellos abusar de ellos que si hubieran robado las contraseñas en texto sin formato. Debido a la naturaleza de las funciones hash criptográficas seguras y al hecho de que es muy poco probable que dos entradas diferentes den como resultado el mismo hash, no tenemos que preocuparnos demasiado de que un atacante abuse del sistema e ingrese una contraseña incorrecta que aún resulte en el hash coincidente.
Otros usos
Los hashes criptográficos tienen una variedad de otros usos. Éstos incluyen:
- Códigos de autenticación de mensajes (MAC)
- Sistemas de prueba de trabajo de cadena de bloques
- Huella digital de datos
- Checksums que detectan corrupción de datos.
¿Qué es una colisión?
A estas alturas, sabemos que los hashes son realmente útiles. También mencionamos brevemente en la introducción que las colisiones son una amenaza en ciertos escenarios donde se implementan funciones hash criptográficas. Pero, ¿qué es realmente una colisión?
¿Recuerdas que dijimos que debería ser inviable que dos entradas diferentes en una función hash criptográfica den como resultado el mismo hash?
Bueno… una colisión es cuando las cosas no salen según lo planeado, y dos entradas separadas en realidad dan como resultado el mismo valor hash. Como hemos dicho, se supone que esto no debe suceder, y puede ser increíblemente problemático si sucede. Cuando las colisiones son prácticas, permiten a los atacantes socavar por completo los aspectos de integridad y autenticación de las firmas digitales. Esto puede conducir a todo tipo de problemas, incluido el fraude y permitir que los atacantes se abran paso a través de los sistemas de seguridad existentes.
Te contaremos un pequeño secreto: en realidad, es imposible diseñar una función hash para evitar colisiones por completo.
Esto se debe al principio del casillero. En el contexto de hashing, básicamente establece que si hay más entradas que hashes posibles, entonces algunas entradas deben dar como resultado los mismos hashes.
Como hemos dicho, los hashes en SHA-256 tienen una longitud de 256 bits. Esto significa que existe un tamaño máximo que puede tener un hash SHA-256, de la misma forma que si el cuentakilómetros de tu coche solo tiene seis dígitos, el valor máximo que puede mostrar es 999.999. Si hay un tamaño máximo de hash, también significa que hay un número limitado de posibles hash.
Para muchos de nosotros, es difícil imaginar qué tan grande es 256 bits. Si tuvieras que contar todos los hashes SHA-256 hexadecimales posibles, llegarías al siguiente número en decimal:
115.792.089.237.316.195.423.570.985.008.687.907.853.269.984.665.640.564.039.457.584.007.913.129.639.936
Es un número realmente grande, pero aún es un número que podemos escribir y mostrar en una línea o dos.
Ahora, pensemos en todas las posibles entradas diferentes que podríamos ejecutar a través de SHA-256. Cualquier cosa, desde «0» a un diccionario completo o las obras completas de Shakespeare. Realmente, las posibilidades son infinitas. Esto nos lleva a una conclusión problemática: infinito es mucho más grande que el número de 256 bits que escribimos anteriormente. De acuerdo con el principio del casillero, el hecho de que tengamos entradas infinitas pero un número limitado de hashes posibles significa que cada hash debe tener muchas entradas diferentes que puedan producirlo.
¿Significa esto que todo lo que hemos hablado está construido sobre una base débil y que todo está a punto de desmoronarse en cualquier momento?
No necesariamente.
Habrás notado que nunca dijimos que una función hash criptográfica no puede tener dos entradas separadas que den como resultado la misma salida. En cambio, dijimos que no es factible (o básicamente imposible) encontrar dos entradas diferentes que den como resultado la misma salida.
Realmente no importa si hay un montón de colisiones de hash diferentes que son teóricamente posibles. En aras de la seguridad, lo realmente importante es que no es práctico para nadie encontrar estas colisiones de hash. Las posibles colisiones pueden flotar en el éter todo lo que quieran, pero no pueden causarnos ningún problema si la gente no puede encontrarlas.
Por lo tanto, el objetivo de una función hash criptográfica segura es no estar completamente libre de colisiones. Esto sería una tontería porque el principio del casillero demuestra que es matemáticamente imposible. En cambio, solo queremos que las funciones hash criptográficas como SHA-256 sean resistentes a las colisiones, lo que hace que sea increíblemente difícil para cualquiera encontrar estas colisiones.
La paradoja del cumpleaños
Para determinar qué tan seguro es un algoritmo hash, necesitamos comprender qué tan probables son las colisiones. Una de las principales complicaciones es que en realidad son mucho más probables de lo que te diría tu intuición. La mejor demostración de esto es la paradoja del cumpleaños.
Supongamos que eliges una muestra aleatoria de personas y estás interesado en encontrar personas dentro de esa muestra que compartan el mismo cumpleaños. Probablemente necesitarías más de cien para tener una oportunidad de encontrar una coincidencia, ¿verdad? Después de todo, hay 365 días en un año.
No, con solo 23 personas, ya tienes más del 50 % de probabilidad de que dos personas del grupo compartan cumpleaños.
¿Pero como puede ser esto?
Probablemente estés pensando en ello de la misma manera que la mayoría de nosotros, en el sentido de que estás pensando en encontrar una coincidencia para una fecha específica, o un individuo específico dentro de la muestra, en lugar de mirarlo para ver si hay dos personas dentro de la muestra que comparten un cumpleaños.
Demostremos la diferencia entre estas dos formas diferentes de verlo. Si Jose nació el 1 de enero y desea formar una muestra lo suficientemente grande como para que haya más del 50 por ciento de posibilidades de que alguien comparta su cumpleaños el 1 de enero, entonces su intuición es correcta. Necesitaría unas 183 personas en esa muestra para que haya un 50 por ciento de posibilidades de coincidencia.
Pero no estamos buscando una coincidencia específica en la paradoja del cumpleaños, estamos buscando cualquier coincidencia. Con 23 personas, en realidad tenemos muchas combinaciones diferentes posibles. No solo estamos verificando si Jose tiene el mismo cumpleaños que cualquiera de las otras 22 personas, sino también si cada uno de ellos comparte el mismo cumpleaños que cualquier otra persona del grupo. Cuando realmente analizas los números, llegas a lo siguiente:
(23×22)/2 = 253
Así que son 253 emparejamientos de un grupo de 23 personas. Dado que solo hay 365 días en un año, este número de emparejamientos nos lleva a una probabilidad mucho mayor que el 50 por ciento.
Claro, la paradoja del cumpleaños no garantiza que alguien tenga cumpleaños coincidentes, solo que las posibilidades de que ocurran cumpleaños coincidentes son mucho más altas de lo que podríamos haber pensado intuitivamente.
La paradoja del cumpleaños se relaciona directamente con la probabilidad de colisiones de hash.
En realidad, la posibilidad es mucho mayor, porque estamos buscando cualquier posible colisión, no solo una colisión específica para un determinado hash.
Entonces, ¿cuál es la oportunidad?
Sin la paradoja del cumpleaños, habríamos esperado encontrar un hash coincidente después de recorrer el 50 por ciento de las combinaciones totales. En resumen, esto es después de intentar 2 255 hashes.
Con la paradoja de cumpleaños, podemos usar la siguiente fórmula para calcular aproximadamente cuántos hashes tendríamos que recorrer antes de llegar a la misma probabilidad de encontrar una coincidencia:
2 (m/2)
Donde m = el tamaño de bit del hash.
Por lo tanto, cuando ejecutamos los números para la longitud de hash de 256 bits de SHA-256, obtenemos:
2 (256/2)
2 (128)
Entonces, en SHA-256, el ataque de cumpleaños ha reducido la cantidad de hashes para pasar de 2 255 a 2 128. Si no estás muy familiarizado con este tipo de matemáticas, es fácil pensar que el ataque de cumpleaños solo lo reduce a la mitad. En realidad, la diferencia es mucho mayor.
El siguiente número es 2 255 escrito en notación decimal:
57.896.044.618.658.097.711.785.492.504.343.953.926.634.992.332.820.282.019.728.792.003.956.564.819.968
Y lo siguiente es 2 128
340.282.366.920.938.463.463.374.607.431.768.211.456
Como puedes ver, hay magnitudes de diferencia entre los dos números, por lo que el ataque de cumpleaños hace que sea mucho más fácil para un atacante encontrar un hash coincidente de lo que esperaba.
Con esto en mente, la regla general es que un hash de 256 bits como SHA-256 se reduce a 128 bits de seguridad cuando se consideran ataques de cumpleaños en lugar de fuerza bruta. De la misma manera, los 128 bits de MD5 se reducen a 64 bits contra ataques de cumpleaños.
¿Qué es un ataque de colisión?
Un ataque de colisión es simplemente cuando un atacante encuentra una de estas colisiones y la usa para socavar la seguridad que se suponía que proporcionaba el hash.
Ejemplos
Estos son algunos ejemplos comunes de ataques de colisión:
Ataques de colisión de inicio libre
Los ataques de colisión de inicio libre son posibles en funciones hash que se basan en la construcción de Merkle-Damgard. Esto significa que MD5, SHA-1 y SHA-2 son vulnerables, pero no SHA-3, que está diseñado con una estructura de esponja.
En circunstancias normales, en la primera ronda de una función hash de Merkle-Damgard, las entradas son un conjunto de vectores de inicialización predefinidos, así como el primer bloque de datos del mensaje.
Una colisión de inicio libre es diferente, porque implica permitir que un atacante elija sus propios vectores de inicialización. Esto les permite reducir la seguridad de la función hash. ¿Por qué alguien haría eso? Los investigadores lo hacen en el laboratorio, porque les permite jugar con las funciones hash y les brinda una mayor comprensión de sus debilidades.
Estos no son ataques prácticos contra la implementación de una función hash segura, porque en realidad, un atacante no puede elegir los vectores de inicialización. Sin embargo, son importantes para poder comprender las deficiencias de una función hash determinada y para desarrollar mejores funciones hash criptográficas en el futuro.
Ataque de colisión clásico
En un ataque de colisión clásico, el objetivo es encontrar dos mensajes diferentes que den como resultado el mismo hash.
Por lo tanto, un ataque de colisión clásico involucra a un atacante que encuentra dos mensajes donde el mensaje x no es igual al mensaje y, pero el hash de x es igual al hash de y.
Las posibilidades de un ataque de colisión exitoso no solo dependen del tamaño del hash, sino también de cualquier posible debilidad en la función hash criptográfica. Como discutimos, incluso si una función hash no tiene debilidades conocidas, todavía tenemos que preocuparnos por los ataques de cumpleaños, en lugar de solo los ataques de fuerza bruta, que son mucho más difíciles porque requieren que un atacante ejecute sistemáticamente cada combinación individual hasta que encuentre una colisión
Las ramificaciones de los ataques de colisión clásicos
Cuando miramos la ecuación H(x) = H(y), puede ser difícil ver lo que esto realmente significa para la seguridad. Hagámoslo más concreto con un ejemplo.
Digamos que Jane trabaja en una empresa y quiere hacerse rica rápidamente. Digamos que recibe recibos de pago por $1,000 en formato PDF cada semana. Cada semana, su jefe firma digitalmente los cheques de pago para que la nómina sepa que son legítimos.
La firma digital del jefe se habrá basado en un hash del pdf de la nómina. Así que Jane toma el documento de su nómina de $1,000 y comienza a jugar con él. Primero, cambia $1,000 a $1,000,000. Pero cuando aplica el hash a este documento, el hash ya no coincidirá con la firma digital porque el documento ha cambiado. Si intenta que la nómina se pague, cuando vayan a verificar la firma verán que no coincide y que la nómina es ilegítima.
Pero Jane es demasiado inteligente para que su artimaña sea reventada de esa manera, por lo que vuelve a jugar con el documento. Comienza a experimentar con diferentes fuentes, diferentes tamaños, cambia los márgenes, cambia el color, cambia la redacción y mil cambios menores más. Ella procesa repetidamente el documento para ver si los cambios le brindan una coincidencia. Eventualmente, después de innumerables cambios y mucho café, ocurre un milagro y el hash es exactamente el mismo que el hash de la nómina original de $1,000.
Todos estos cambios han sido relativamente menores. Incluso las cosas que solo modifican marginalmente la apariencia del documento darán como resultado hashes completamente diferentes, por lo que ha podido construir un documento que parece legítimo, pero en realidad no lo es.
Todo lo que tiene que hacer Jane es llevar esta versión de su recibo de pago de $1,000,000 a la nómina junto con la firma digital original. Cuando van a verificar la firma digital, todo funciona. Les parece legítimo, y no les pagan lo suficiente como para molestarse en hacer preguntas, por lo que aprueban el cheque de pago de un millón de dólares de Jane. Cuando el departamento de contabilidad se da cuenta del engaño astuto de Jane, ella ya está en la playa bebiendo mojitos en un país sin extradición.
Es un ejemplo un poco exagerado, pero demuestra la amenaza subyacente de los ataques de colisión clásicos. Cuando son posibles, permiten que un atacante socave la integridad y autenticidad de las firmas digitales, lo que les permite causar todo tipo de problemas, como cometer fraude. Esta es la razón por la que nuestros algoritmos de hashing criptográfico deben ser resistentes a las colisiones.
Ataques de colisión de prefijo elegido
Los ataques de colisión de prefijo elegido son otro tipo de colisión al que son vulnerables las funciones hash de Merkle-Damgard. Son significativamente más desafiantes, pero en circunstancias en las que son posibles representan una amenaza mucho mayor que los ataques de colisión clásicos.
En contraste con los ataques de colisión clásicos que describimos anteriormente, una colisión de prefijo elegido implica restricciones adicionales. En lugar de solo poder encontrar posibles colisiones, el atacante debe poder encontrar colisiones que involucren dos prefijos especificados previamente.
El adversario recibe dos prefijos de mensaje, lo que básicamente significa que recibe dos cadenas de datos separadas. Luego, se reta al adversario a encontrar un mensaje separado para cada prefijo, donde las combinaciones de prefijo y mensaje comparten el mismo hash. No vamos a mentir, esto puede ser un poco difícil de entender si no te gusta la criptografía.
Las ramificaciones de los ataques de colisión con prefijo elegido
El resultado de un ataque de colisión de prefijo elegido es muy similar al de los ataques de colisión clásicos. Esencialmente, un atacante puede socavar las medidas de autenticación e integridad, lo que le permite cometer fraude y engaño, tal como lo demostramos en la sección Las ramificaciones de los ataques de colisión clásicos.
La principal diferencia es que las colisiones de prefijo elegido son mucho más difíciles de lograr debido a las restricciones adicionales. Sin embargo, cuando son posibles, es mucho más fácil para un atacante construir documentos que produzcan hashes coincidentes.
Los atacantes no tienen que hacer el esfuerzo de hacer cambios interminables con la esperanza de finalmente encontrar un documento diferente que produzca el mismo hash. En su lugar, pueden simplemente crear dos documentos diferentes, rellenarlos para que tengan la misma longitud y luego agregar una cadena de datos calculada específicamente que da como resultado los mismos valores hash para ambos documentos. Esto simplifica significativamente la producción de diferentes documentos que todavía tienen hashes coincidentes.
Ataques de preimagen
Los ataques de preimagen están relacionados con los ataques de colisión, pero implican tratar de encontrar mensajes que den como resultado hashes específicos. Profundizaremos en esto en un artículo futuro, pero por ahora solo debe tener en cuenta que:
- Un ataque de preimagen implica tomar un hash determinado y luego descubrir la entrada inicial que lo produjo.
- Un segundo ataque de preimagen implica tomar una entrada determinada y encontrar otra entrada donde ambas entradas den como resultado el mismo hash.
Colisiones en MD5
MD5 es una función hash antigua que ya no se considera segura para muchas aplicaciones. Da como resultado hashes de 128 bits, lo que, cuando se consideran ataques de cumpleaños, realmente significa que solo tiene 64 bits de seguridad.
En los años noventa, investigadores independientes descubrieron tanto una pseudo-colisión como una colisión de semi-arranque libre. Si bien estas fueron acusaciones preocupantes sobre la seguridad futura de MD5, no fueron verdaderas colisiones.
No fue hasta 2004 que un equipo de académicos publicó colisiones completas de MD5. Pudieron encontrar colisiones MD5 en menos de una hora en un IBM P690. Esto demostró que MD5 estaba realmente roto y que el mundo necesitaba alejarse rápidamente de MD5 para evitar que los ataques de colisión se generalizaran en el mundo real.
Un ataque de colisión de prefijo elegido se mostró por primera vez contra MD5 en 2007.
Los investigadores también examinaron las colisiones clásicas en MD5 y encontraron que las debilidades en la función hash les permitieron construir dos certificados X.509 con la misma firma. Esto significó importantes consecuencias en el mundo real, porque significaba que ya no podíamos confiar en la autenticidad de los certificados X.509 que usaban hash MD5.
Ha habido una variedad de otras colisiones contra MD5, tanto teóricas como prácticas. Sin embargo, dado que el algoritmo ya está bien y verdaderamente roto para muchos propósitos, no vale la pena analizarlos.
Colisiones en SHA-1
SHA-1 produce hashes de 160 bits de longitud, lo que en la práctica le otorga 80 bits de seguridad contra ataques de cumpleaños. En 2005, un equipo de académicos encontró colisiones en una versión reducida de 53 rondas de SHA-1. El SHA-1 completo en realidad tiene 80 rondas, que es básicamente la cantidad de veces que las entradas se barajan a través del algoritmo. Si bien una colisión de 53 rondas es significativa, todavía está muy lejos de una colisión completa de 80 rondas.
También ese año, otro equipo de investigadores propuso un ataque que encontró colisiones en menos de 269 operaciones, lo que supuso una mejora significativa en los ataques de fuerza bruta. Su enfoque se basó en un ataque diferencial, junto con técnicas de modificación de mensajes y colisión de bloques múltiples.
Para agosto de 2005, el ataque se había mejorado hasta el punto de que se podían encontrar colisiones en SHA-1 en 263 operaciones.
2006 vio una mejora significativa en las colisiones para la ronda reducida SHA-1, con un investigador que publicó los hallazgos de una colisión para 64 rondas. Hubo otro salto en 2010, con otro investigador llevándolo a 73 rondas. Esta fue solo otra señal de que los días de SHA-1 estaban contados.
En 2011, NIST desaprobó SHA-1 , indicando que ya no debería implementarse.
La primera colisión de inicio libre contra SHA-1 se encontró en 2015. El ataque, denominado con el nombre creativo SHAppening, solo tomó 10 días en un clúster de 64 GPU.
El SHAppening fue seguido por SHAttered, continuando la tendencia de los juegos de palabras con criptografía. SHAttered ocurrió en 2017 y fue la primera colisión clásica descubierta para SHA-1. Con una colisión total tan claramente demostrada, quedó muy claro que SHA-1 ya no podía garantizar la integridad y la autenticación de archivos o firmas digitales.
En 2020, los académicos publicaron un ataque de colisión de prefijo elegido contra SHA-1. El título del documento confirmó la tradición recién establecida, y SHA-1 es un Shambles demostró que ahora era incluso más fácil para los atacantes socavar las medidas de integridad y autenticación. Aunque SHA-1 se había considerado inseguro durante mucho tiempo, esta fue la primera colisión de prefijo elegido revelada públicamente.
Aunque SHA-1 no es seguro para su uso en cosas como firmas digitales, aún está bien que se implemente en un código de autenticación de mensajes basado en hash (HMAC).
Colisiones en SHA-2
SHA-2 se considera actualmente el estándar de oro en algoritmos criptográficos y se implementa ampliamente en nuestro mundo digital.
El hecho de que todavía se considere seguro debería darte una pista de que las colisiones no han hecho demasiada mella en su contra en esta etapa. Si se hubieran encontrado colisiones clásicas o colisiones de prefijos elegidos, todos tendríamos que estar extremadamente preocupados por nuestra seguridad en línea.
Si bien todavía se considera seguro, los criptógrafos han trabajado arduamente para intentar descifrarlo. SHA-256 es un algoritmo de 256 bits, lo que le otorga 128 bits de seguridad contra ataques de cumpleaños. SHA-512 tiene el doble de bits de longitud, lo que le otorga 256 bits de seguridad contra ataques de cumpleaños.
En 2008, el mejor ataque de ronda reducida podía encontrar colisiones en 24 de las 80 rondas de SHA-256 y 24 de las 80 rondas de SHA-512. En 2011, un ataque diferencial de orden superior fue capaz de causar pseudocolisiones en 33 de las 64 rondas del SHA-256.
Un artículo de 2013 demostró colisiones contra 31 rondas de SHA-256 y colisiones de arranque semilibre contra 38 rondas. En 2014, un documento que investigó SHA-512 usó heurística de ramificación en la búsqueda de colisión diferencial, lo que resultó en una pseudocolisión en 38 de 80 rondas.
En 2016, los investigadores analizaron SHA-256 y SHA-512 . Encontraron colisiones prácticas contra 28 de las 64 rondas de SHA-256 y colisiones contra 27 de las 80 rondas de SHA-512 . También encontraron una pseudocolisión contra 39 rondas de SHA-512.
Cada uno de estos ataques aún está lejos de representar amenazas significativas para la seguridad de SHA-2. En esta etapa, no tenemos que preocuparnos demasiado por las colisiones contra SHA-2. Sin embargo, sigue siendo crucial que los investigadores continúen investigando SHA-2 y buscando debilidades. Si no lo hacen, los estados nacionales y los delincuentes organizados seguirán haciéndolo, y no nos dirán cuándo logran encontrar colisiones factibles.
Colisiones en SHA-3
SHA-3 es el último en la línea de algoritmos hash seguros. No vemos que SHA-3 se implemente con demasiada frecuencia, porque SHA-2 todavía se considera seguro y no tiene mucho sentido gastar el esfuerzo para cambiar en esta etapa.
Aunque es más nuevo, no es necesariamente más seguro que SHA-2. Los dos cuentan con diseños internos dramáticamente diferentes, y SHA-3 no se ha estudiado tanto como SHA-2 debido a su relativa actualidad. En lugar de pensar en él como una actualización de SHA-2, es mejor pensar en él como un repuesto, porque realmente no sabemos si algoritmo resistirá la prueba del tiempo.
Sin embargo, el beneficio de tener dos algoritmos hash criptográficos completamente diferentes es que si se encuentra un ataque contra cualquiera de ellos, se supone que el otro seguirá siendo resistente. Esto significa que podríamos cambiar rápidamente al otro si fuera necesario.
En 2012, se publicó un artículo que mostraba colisiones en hasta cinco rondas del algoritmo que se convertiría en SHA-3. Los investigadores utilizaron diferenciales internos generalizados para apuntar a varias versiones del algoritmo, conocido como Keccak.
Los investigadores encontraron colisiones para versiones de tres rondas tanto de Keccak-384 como de Keccak-512. También encontraron un ataque que fue 245 veces más rápido que un ataque de cumpleaños contra Keccak-384 de 4 rondas. Contra Keccak-256, lograron encontrar colisiones durante cinco rondas . Sin embargo, estos intentos estuvieron lejos de representar una amenaza para los algoritmos, que tienen 24 rondas cada uno.
Para 2019, se finalizó el algoritmo SHA-3 y un grupo de académicos publicó otro artículo sobre los ataques en su contra. Las diferencias entre Keccak y la versión finalizada de SHA-3 son tan marginales que estos dos análisis de seguridad estaban probando esencialmente lo mismo.
Protección de tus sistemas contra ataques de colisión
El usuario medio no puede hacer mucho para protegerse contra colisiones, además de cosas básicas como actualizar a las últimas versiones para asegurarse de que no están usando software vulnerable de 2002.
Los desarrolladores deben asegurarse de que solo utilizan algoritmos hash criptográficos que sean seguros para su propósito. En el caso de cosas como las firmas digitales, deben usar algoritmos como SHA-2 o SHA-3 para garantizar que se pueda confiar en las firmas para su integridad y autenticación.
Aparte de eso, los desarrolladores deben verificar cada pocos años para mantenerse al día con el estado de seguridad de los algoritmos que utilizan. Si los ataques contra el algoritmo hash que implementan se vuelven más severos, entonces deben comenzar el proceso de cambio. Si no lo hacen, sus sistemas podrían ser vulnerables a los ataques de colisión y al fraude que los rodea.