Secure Hash Algorithm

Los algoritmos de hash seguro (del inglés: Secure Hash Algorithm) ^[1]son una familia de funciones de hash criptográficas publicadas por el Instituto Nacional de Estándares y Tecnología (NIST) como un estándar federal de procesamiento de información (FIPS) de EE. UU; que incluyen:

SHA-0
SHA-1
SHA-2
SHA-3

Los estándares correspondientes son FIPS PUB 180 (SHA original), FIPS PUB 180-1 (SHA-1), FIPS PUB 180-2 (SHA-1, SHA-256, SHA-384 y SHA-512). NIST ha actualizado el borrador de la publicación FIPS 202, estándar SHA-3 por separado del estándar Secure Hash (SHS).^[2]

SHA-1 y SHA-2 fueron diseñados mediante un método conocido como construcción de Merkle-Damgård.

Uso de las funciones SHA

Una característica principal de las funciones SHA es la capacidad de no reflexividad, es decir, dado una cadena de bits del buffer de salida resulta prácticamente imposible intentar hallar una cadena origen que devuelva el mismo contenido, además de disponer de una gran cantidad de combinaciones posibles que evitan que se puedan dar duplicado de datos o colisiones las cuales pueden comprometer la seguridad de diferentes archivos.

Las funciones SHA permiten la creación de cadenas diferentes que facilitan seguir un registro de cambios en la seguridad de diferentes archivos conocida como huella digital, esto sirve de especial importancia en aplicaciones tales como la creación de cuentas asociadas a contraseñas que solo un usuario debe conocer, claves de desencriptado de ficheros o usos en la creación de cadenas de bloques en criptomonedas como el bitcoin.

En teoría una función SHA perfecta no debería tener ninguna colisión pero debido a que están pensadas para trabajar con cadenas de texto indeterminadas, las posibilidades de que exista una colisión imprevista no son nulas pero si son increíblemente bajas pues, tomando el ejemplo de SHA-1 de 160 bits tendríamos hasta $2^{160}$ combinaciones posibles el cual es un número tan grande que esperar a que se dé una colisión de manera fortuita resulta inviable, sin embargo no significa que sea totalmente seguro pues con métodos avanzados se ha logrado desencriptar sin necesidad de recurrir a ataques de fuerza llegando a encontrar colisiones y forzando a la creación de nuevas formas de encriptado para aumentar la seguridad.

Funciones

A lo largo de su historia, se han puesto a prueba esta familia de algoritmos:

SHA-0

Un retrónimo aplicado a la versión original de la función hash de 160 bits publicada en 1993 con el nombre "SHA". Fue retirado poco después de su publicación debido a un "defecto significativo" no revelado y reemplazado por la versión ligeramente revisada SHA-1.
En 1998 se encontró una vulnerabilidad en SHA-0, aunque esta no se podía hacer extensiva a SHA-1. En cualquier caso, la NSA aumentó en ese momento la seguridad del SHA-1.

SHA-1

Artículo principal: SHA-1

Una función hash de 160 bits que se parece algoritmo MD5 anterior. Esto fue diseñado por la Agencia de Seguridad Nacional (NSA) para ser parte de Digital Signature Algorithm. Se descubrieron debilidades criptográficas en SHA-1, y el estándar ya no fue aprobado para la mayoría de los usos criptográficos después de 2010.

SHA-1 ha sido examinado muy de cerca por la comunidad criptográfica pública y no se ha encontrado ningún ataque eficaz. No obstante, en el año 2004, se dio a conocer un número significativo de ataques contra funciones criptográficas de hash con una estructura similar a SHA-1, lo que plantea dudas sobre la seguridad a largo plazo de SHA-1.

SHA-0 y SHA-1 producen una salida resumen de 160 bits (20 bytes) de un mensaje que puede tener un tamaño máximo de 2⁶⁴ bits, y se basa en principios similares a los usados por el profesor Ronald L. Rivest del MIT en el diseño de los algoritmos de resumen de mensaje MD4 y MD5.

Ataques contra SHA-1

En 2004 se encontró una debilidad matemática en SHA-1,^[3] que MD5 (2⁶⁴).

La resistencia del algoritmo SHA-1 se ha visto comprometida a lo largo del año 2005. Después de que MD5, entre otros, quedara seriamente comprometido en el 2004 por parte de un equipo de investigadores chinos,^[4] el tiempo de vida de SHA-1 quedó sentenciado. El mismo equipo de investigadores chinos, compuesto por Xiaoyun Wang, Yiqun Lisa Yin y Hongbo Yu (principalmente de la Universidad de Shandong, en China), ha demostrado que son capaces de romper el SHA-1 en al menos 2⁶⁹ operaciones, siendo este más de 2000 veces más rápido que un ataque de fuerza bruta (que requeriría 2⁸⁰ operaciones). Los últimos ataques contra SHA-1 han logrado debilitarlo hasta 2⁶³.^[5]

Según el NIST:

«Este ataque es de particular importancia para las aplicaciones que usan firmas digitales tales como marcas de tiempo y notarías. Sin embargo, muchas aplicaciones que usan firmas digitales incluyen información sobre el contexto que hacen este ataque difícil de llevar a cabo en la práctica.»

A pesar de que 2⁶³ suponen aún un número alto de operaciones, se encuentra dentro de los límites de las capacidades actuales de cálculos, y es previsible que con el paso del tiempo romper esta función sea trivial, al aumentar las capacidades de cálculo y al ser más serios los ataques contra SHA-1.

El primer ataque de colisión a SHA-1 se trató concretamente de dos archivos PDF con contenidos distintos y que arrojaban el mismo hash SHA-1. Esto plantea un riesgo, ya que un propietario podría usar esta vulnerabilidad para redactar dos contratos con el mismo hash. Esto implica que algún propietario podría hacer firmar al inquilino un contrato con un precio de alquiler bajo y, posteriormente, alegar que se acordó un precio mayor, ya que ambos contratos tendrían el mismo hash. A este ataque se le conoce como colisión de prefijo idéntico.

Lo que implicó este ataque fue que los investigadores alertaran a los desarrolladores de GnuPG, CAcert y OpenSSL sobre este ataque para que tomaran medidas preventivas y dejaran de usar SHA-1 en sus softwares.

El 23 de febrero de 2017, un equipo formado por Google y CWI Amsterdam, han anunciado la primera colisión de SHA-1, la cual ha sido nombrada como SHAttered.

La importancia de la rotura de una función hash se debe interpretar en el siguiente sentido: Un hash permite crear una huella digital, teóricamente única, de un archivo. Una colisión entre hashes supondría la posibilidad de la existencia de dos documentos con la misma huella. La inicial similitud propuesta con la equivalencia a que hubiese personas que compartiesen las mismas huellas digitales, o peor aún, el mismo ADN no es adecuada pues, aunque fuera trivial encontrar dos ficheros con el mismo resumen criptográfico ello no implicaría que los ficheros fueran congruentes en el contexto adecuado. Siguiendo con la hipótesis de la similitud biométrica de dos personas, sería el equivalente a necesitar modificar el número de brazos en una persona para que su impresión dactilar fuera igual a la de otra.

A pesar de que el NIST contempla funciones de SHA de mayor tamaño (por ejemplo, el SHA-512, de 512 bits de longitud), expertos de la talla de Bruce Schneier abogan por, sin llamar a alarmismos, buscar una nueva función hash estandarizada que permita sustituir a SHA-1. Los nombres que se mencionan al respecto son Tiger, de los creadores de Serpent, y WHIRLPOOL, de los creadores de AES.

SHA-2

Una familia de dos funciones hash similares, con diferentes tamaños de bloque, conocidas como SHA-256 y SHA-512 . Se diferencian por el tamaño de las palabras; SHA-256 usa palabras de 32 bytes donde SHA-512 usa palabras de 64 bytes. De SHA-2, también hay versiones truncadas de cada estándar, conocidas como SHA-224 , SHA-384 , SHA-512/224 y SHA-512/256 . Estos también fueron diseñados por la NSA.

SHA-3

Una función hash anteriormente llamada Keccak , elegida en 2012 después de una competencia pública entre diseñadores que no pertenecen a la NSA. Admite las mismas longitudes de hash que SHA-2 y su estructura interna difiere significativamente del resto de la familia SHA.

Comparación de funciones SHA

En la siguiente tabla, el estado interno significa la "suma hash interna" después de cada compresión de un bloque de datos.

Comparación de funciones SHA^[6]
Algoritmo y variante		Tamaño de salida (bits)	Tamaño del estado interno (bits)	Tamaño de bloque (bits)	Rondas	Operaciones	Seguridad contra ataques de colisión (bits)	Capacidad contrataques de extensión de longitud (bits)	Rendimiento en Skylake (cpb mediano)		Publicado por primera vez
Algoritmo y variante		Tamaño de salida (bits)	Tamaño del estado interno (bits)	Tamaño de bloque (bits)	Rondas	Operaciones	Seguridad contra ataques de colisión (bits)	Capacidad contrataques de extensión de longitud (bits)	mensajes largos	8 bytes	Publicado por primera vez
MD5 (como referencia)		128	128 (4 × 32)	512	64	And, Xor, Or, Rot, Add (mod 2³²)	≤18 (colisiones encontradas)	0	4,99	55,00	1992
SHA-0		160	160 (5 × 32)	512	80	And, Xor, Or, Rot, Add (mod 2³²)	<34 (colisiones encontradas)	0	≈ SHA-1	≈ SHA-1	1993
SHA-1		160	160 (5 × 32)	512	80	And, Xor, Or, Rot, Add (mod 2³²)	<63 (colisiones encontradas)	0	3,47	52,00	1995
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	64	And, Xor, Or, Rot, Shr, Add (mod 2³² )	112 128	32 0	7,62 7,63	84,50 85,25	2004 2001
	SHA-384 SHA-512	384 512	512 (8 × 64)	1024	80	And, Xor, Or, Rot, Shr, Add (mod 2⁶⁴ )	192 256	128 (≤ 384) 0	5.12 5.06	135,75 135,50	2001
	SHA-512/224 SHA-512/256	224 256	512 (8 × 64)	1024	80	And, Xor, Or, Rot, Shr, Add (mod 2⁶⁴ )	112 128	288 256	≈ SHA-384	≈ SHA-384	2012
SHA-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	24	And, Xor, Rot, Not	112 128 192 256	448 512 768 1024	8.12 8.59 11.06 15.88	154,25 155,50 164,00 164,00	2015
SHA-3	SHAKE128 SHAKE256	d (arbitrario) d (arbitrario)	1600 (5 × 5 × 64)	1344 1088	24	And, Xor, Rot, Not	min ( d / 2, 128) min ( d / 2, 256)	256 512	7.08 8.59	155.25 155.50	2015

Véase también

Referencias

↑ «Publicación FIPS 180-2». FIPS Publication 180-2 (en inglés). 1 de agosto de 2002. Consultado el 31 de diciembre de 2020.
↑ «Estándar SHS».
↑ Schneier, Bruce (18 de febrero de 2005). «SHA-1 Broken» (html). Bruce Schneier's Blog (en inglés). Archivado desde el original el 17 de diciembre de 2018. Consultado el 17 de diciembre de 2018. «The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results: collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length. collisions in SHA-0 in 2**39 operations. collisions in 58-round SHA-1 in 2**33 operations.»
↑ Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu (17 de agosto de 2004). «Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD» (pdf). International Association for Cryptologic Research (en inglés). Archivado desde el original el 20 de diciembre de 2004. Consultado el 17 de diciembre de 2018.
↑ Schneier, Bruce (18 de febrero de 2005). «Cryptanalysis of SHA-1» (html). Bruce Schneier's Blog (en inglés). Archivado desde el original el 21 de febrero de 2005. Consultado el 17 de diciembre de 2018. «SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an infinite number of messages that hash to each possible value, there are an infinite number of possible collisions. But because the number of possible hashes is so large, the odds of finding one by chance is negligibly small (one in 280, to be exact). If you hashed 280 random messages, you'd find one pair that hashed to the same value. (...) They can find collisions in SHA-1 in 269 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology. Two comparable massive computations illustrate that point.»
↑ «Resultados-hash: amd64-skylake». Wikipedia (en inglés). 21 de diciembre de 2020. Consultado el 31 de diciembre de 2020.

^[1]

Enlaces externos

Datos: Q387688

↑ Dan Goodin (2020). «PGP keys, software security, and much more threatened by new SHA1 exploit».

[1] «Publicación FIPS 180-2». FIPS Publication 180-2 (en inglés). 1 de agosto de 2002. Consultado el 31 de diciembre de 2020.

[2] «Estándar SHS».

[3] Schneier, Bruce (18 de febrero de 2005). «SHA-1 Broken» (html). Bruce Schneier's Blog (en inglés). Archivado desde el original el 17 de diciembre de 2018. Consultado el 17 de diciembre de 2018. «The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results: collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length. collisions in SHA-0 in 2**39 operations. collisions in 58-round SHA-1 in 2**33 operations.»

[4] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu (17 de agosto de 2004). «Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD» (pdf). International Association for Cryptologic Research (en inglés). Archivado desde el original el 20 de diciembre de 2004. Consultado el 17 de diciembre de 2018.

[5] Schneier, Bruce (18 de febrero de 2005). «Cryptanalysis of SHA-1» (html). Bruce Schneier's Blog (en inglés). Archivado desde el original el 21 de febrero de 2005. Consultado el 17 de diciembre de 2018. «SHA-1 produces a 160-bit hash. That is, every message hashes down to a 160-bit number. Given that there are an infinite number of messages that hash to each possible value, there are an infinite number of possible collisions. But because the number of possible hashes is so large, the odds of finding one by chance is negligibly small (one in 280, to be exact). If you hashed 280 random messages, you'd find one pair that hashed to the same value. (...) They can find collisions in SHA-1 in 269 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology. Two comparable massive computations illustrate that point.»

[6] «Resultados-hash: amd64-skylake». Wikipedia (en inglés). 21 de diciembre de 2020. Consultado el 31 de diciembre de 2020.

[7] Dan Goodin (2020). «PGP keys, software security, and much more threatened by new SHA1 exploit».

[1]

[2]

[3]

[4]

[5]

[6]

[1]