SHA-1

SHA-1 forma parte de varias aplicaciones y protocolos de seguridad ampliamente utilizados, como TLS y SSL , PGP , SSH , S/MIME e IPsec . Estas aplicaciones también pueden usar MD5 ; tanto MD5 como SHA-1 derivan de MD4 .

SHA-1 y SHA-2 son los algoritmos hash exigidos por ley para su uso en ciertas aplicaciones del gobierno estadounidense , incluyendo su uso dentro de otros algoritmos y protocolos criptográficos, para la protección de información sensible no clasificada. La publicación FIPS PUB 180-1 también fomentó la adopción y el uso de SHA-1 por parte de organizaciones privadas y comerciales. SHA-1 se está retirando de la mayoría de los usos gubernamentales; el Instituto Nacional de Estándares y Tecnología de EE. UU. declaró: "Las agencias federales deberían dejar de usar SHA-1 para... aplicaciones que requieren resistencia a colisiones tan pronto como sea posible, y deben usar la familia de funciones hash SHA-2 para estas aplicaciones después de 2010", ^{[ 24 ]} aunque esto se flexibilizó posteriormente para permitir que SHA-1 se utilizara para verificar firmas digitales antiguas y marcas de tiempo. ^{[ 24 ]}

Una de las principales motivaciones para la publicación del Algoritmo de Hash Seguro fue el Estándar de Firma Digital , en el que está incorporado.

Las funciones hash SHA se han utilizado como base para los cifrados de bloques SHACAL .

Los sistemas de control de versiones como Git , Mercurial y Monotone utilizan SHA-1, no por seguridad, sino para identificar revisiones y garantizar que los datos no hayan cambiado debido a una corrupción accidental. Linus Torvalds dijo sobre Git en 2007:

Si tienes corrupción de disco, corrupción de DRAM, o cualquier otro problema, Git lo detectará. No es cuestión de si ocurrirá , es una garantía. Puede haber personas que intenten actuar con mala intención, pero no lo conseguirán. [...] Nadie ha podido romper SHA-1, pero la cuestión es que, en lo que respecta a Git, SHA-1 ni siquiera es una función de seguridad. Es simplemente una comprobación de consistencia. La seguridad reside en otro lugar, por lo que mucha gente asume que, dado que Git usa SHA-1 y este se utiliza para la seguridad criptográfica, es una función de seguridad fundamental. No tiene nada que ver con la seguridad; es simplemente el mejor hash posible.

Te garantizo que, si guardas tus datos en Git, puedes confiar en que cinco años después, tras haberlos convertido de tu disco duro a DVD o a cualquier otra tecnología nueva y haberlos copiado, podrás verificar que los datos que recuperes son exactamente los mismos que introdujiste. [...]

Una de las razones por las que me importa es por el kernel; tuvimos una intrusión en uno de los sitios de BitKeeper donde la gente intentó corromper los repositorios del código fuente del kernel. ^{[ 25 ]}

Sin embargo, Git no requiere la resistencia a la segunda preimagen de SHA-1 como medida de seguridad, ya que siempre preferirá conservar la versión más antigua de un objeto en caso de colisión, impidiendo que un atacante sobrescriba archivos subrepticiamente. ^{[ 26 ]} Los ataques conocidos (hasta 2020) tampoco rompen la resistencia a la segunda preimagen. ^{[ 27 ]}

En CRYPTO 98, dos investigadores franceses, Florent Chabaud y Antoine Joux , presentaron un ataque a SHA-0: se pueden encontrar colisiones con una complejidad de 2 ⁶¹ , menor que los 2 ⁸⁰ para una función hash ideal del mismo tamaño. ^{[ 31 ]}

En 2004, Biham y Chen encontraron casi colisiones para SHA-0: dos mensajes que generan un valor hash casi idéntico; en este caso, 142 de los 160 bits son iguales. También encontraron colisiones completas de SHA-0 reducidas a 62 de sus 80 rondas. ^{[ 32 ]}

Posteriormente, el 12 de agosto de 2004, Joux, Carribault, Lemuet y Jalby anunciaron una colisión para el algoritmo SHA-0 completo. Esto se logró mediante una generalización del ataque de Chabaud y Joux. Encontrar la colisión tuvo una complejidad de 2⁵¹ ^y requirió aproximadamente 80 000 horas de procesador en una supercomputadora con 256 procesadores Itanium 2 (equivalente a 13 días de uso continuo de la computadora).

El 17 de agosto de 2004, en la sesión informal de CRYPTO 2004, Wang , Feng, Lai y Yu anunciaron resultados preliminares sobre un ataque a MD5 , SHA-0 y otras funciones hash. La complejidad de su ataque a SHA-0 es 2 ⁴⁰ , significativamente mejor que el ataque de Joux et al. ^{[ 33 ] [ 34 ]}

En febrero de 2005, se anunció un ataque de Xiaoyun Wang , Yiqun Lisa Yin y Hongbo Yu que podría encontrar colisiones en SHA-0 en 2 ³⁹ operaciones. ^{[ 5 ] [ 35 ]}

Otro ataque en 2008 que aplicó el ataque boomerang redujo la complejidad de encontrar colisiones a 2 ^33,6 , lo que se estimó que tomaría 1 hora en una PC promedio del año 2008. ^{[ 36 ]}

A la luz de los resultados de SHA-0, algunos expertos sugirieron que se reconsideraran los planes para el uso de SHA-1 en nuevos criptosistemas . Tras la publicación de los resultados de CRYPTO 2004, el NIST anunció que planeaba eliminar gradualmente el uso de SHA-1 para 2010 en favor de las variantes SHA-2. ^{[ 37 ]}

A principios de 2005, Vincent Rijmen y Elisabeth Oswald publicaron un ataque a una versión reducida de SHA-1 (53 de 80 rondas) que encuentra colisiones con un esfuerzo computacional de menos de 280 ^operaciones . ^{[ 38 ]}

En febrero de 2005, se anunció un ataque perpetrado por Xiaoyun Wang , Yiqun Lisa Yin y Hongbo Yu. ^{[ 5 ]} Estos ataques pueden encontrar colisiones en la versión completa de SHA-1, requiriendo menos de 2 ⁶⁹ operaciones. (Una búsqueda por fuerza bruta requeriría 2 ⁸⁰ operaciones).

Los autores escriben: «En particular, nuestro análisis se basa en el ataque diferencial original a SHA-0, el ataque de colisión cercana a SHA-0, las técnicas de colisión de bloques múltiples, así como las técnicas de modificación de mensajes utilizadas en el ataque de búsqueda de colisión a MD5. Romper SHA-1 no sería posible sin estas potentes técnicas analíticas». ^{[ 39 ]} Los autores han presentado una colisión para SHA-1 de 58 rondas, encontrada con 2 ³³ operaciones hash. El artículo con la descripción completa del ataque se publicó en agosto de 2005 en la conferencia CRYPTO.

En una entrevista, Yin afirma que, "En términos generales, explotamos las siguientes dos debilidades: una es que el paso de preprocesamiento de archivos no es lo suficientemente complejo; la otra es que ciertas operaciones matemáticas en las primeras 20 rondas tienen problemas de seguridad inesperados". ^{[ 40 ]}

El 17 de agosto de 2005, Xiaoyun Wang , Andrew Yao y Frances Yao anunciaron una mejora en el ataque SHA-1 en la sesión informal de CRYPTO 2005, reduciendo la complejidad necesaria para encontrar una colisión en SHA-1 a 2 ⁶³ . ^{[ 7 ]} El 18 de diciembre de 2007, Martin Cochran explicó y verificó los detalles de este resultado. ^{[ 41 ]}

Christophe De Cannière y Christian Rechberger mejoraron aún más el ataque a SHA-1 en "Finding SHA-1 Characteristics: General Results and Applications," ^{[ 42 ]} recibiendo el premio al mejor artículo en ASIACRYPT 2006. Se presentó una colisión de dos bloques para SHA-1 de 64 rondas, encontrada utilizando métodos no optimizados con 2 ³⁵ evaluaciones de la función de compresión. Dado que este ataque requiere el equivalente a aproximadamente 2 ³⁵ evaluaciones, se considera una ruptura teórica significativa. ^{[ 43 ]} Su ataque fue extendido aún más a 73 rondas (de 80) en 2010 por Grechnikov. ^{[ 44 ]} Sin embargo, para encontrar una colisión real en las 80 rondas completas de la función hash, se requieren enormes cantidades de tiempo de computadora. Con ese fin, una búsqueda de colisiones para SHA-1 utilizando la plataforma de computación voluntaria BOINC comenzó el 8 de agosto de 2007, organizada por la Universidad Tecnológica de Graz . El esfuerzo fue abandonado el 12 de mayo de 2009 debido a la falta de progreso. ^{[ 45 ]}

En la sesión informal de CRYPTO 2006, Christian Rechberger y Christophe De Cannière afirmaron haber descubierto un ataque de colisión en SHA-1 que permitiría a un atacante seleccionar al menos partes del mensaje. ^{[ 46 ] [ 47 ]}

En 2008, una metodología de ataque de Stéphane Manuel reportó colisiones de hash con una complejidad teórica estimada de ^2⁵¹ a ^2⁵⁷ operaciones. ^{[ 48 ]} Sin embargo, posteriormente se retractó de esa afirmación tras descubrir que las rutas de colisión locales no eran realmente independientes, y finalmente citó como el vector de colisión más eficiente un vector que ya se conocía antes de este trabajo. ^{[ 49 ]}

Cameron McDonald, Philip Hawkes y Josef Pieprzyk presentaron un ataque de colisión de hash con una complejidad declarada de 2 ⁵² en la sesión informal de Eurocrypt 2009. ^{[ 50 ]} Sin embargo, el artículo que lo acompañaba, "Differential Path for SHA-1 with complexity O (2 ⁵² )", fue retirado debido a que los autores descubrieron que su estimación era incorrecta. ^{[ 51 ]}

Un ataque contra SHA-1 fue realizado por Marc Stevens ^{[ 52 ]} con un costo estimado de $2.77M (2012) para romper un solo valor hash alquilando potencia de CPU de servidores en la nube. ^{[ 53 ]} Stevens desarrolló este ataque en un proyecto llamado HashClash, ^{[ 54 ]} implementando un ataque de ruta diferencial. El 8 de noviembre de 2010, afirmó tener un ataque de casi colisión completamente funcional contra SHA-1 completo que funcionaba con una complejidad estimada equivalente a 2 ^57.5 compresiones SHA-1. Estimó que este ataque podría extenderse a una colisión completa con una complejidad de alrededor de 2 ⁶¹ .

Las implementaciones de todas las funciones de seguridad aprobadas por FIPS pueden validarse oficialmente mediante el programa CMVP , gestionado conjuntamente por el Instituto Nacional de Estándares y Tecnología (NIST) y el Centro de Seguridad de las Comunicaciones (CSE). Para una verificación informal, se ofrece un paquete para generar un gran número de vectores de prueba, disponible para su descarga en el sitio web del NIST; sin embargo, la verificación resultante no sustituye la validación formal del CMVP, que es obligatoria por ley para determinadas aplicaciones.

A diciembre de 2013Hay más de 2000 implementaciones validadas de SHA-1, de las cuales 14 son capaces de manejar mensajes con una longitud en bits que no es múltiplo de ocho (ver Lista de validación SHS archivada el 23/08/2011 en Wayback Machine ).

Estos son ejemplos de resúmenes de mensajes SHA-1 en formato hexadecimal y en codificación de texto ASCII binario Base64 .

• SHA1("The quick brown fox jumps over the lazy dog")
  • Salida hexadecimal:2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
  • Codificación de texto ASCII a binario Base64 generada :L9ThxnotKPzthJ7hu3bnORuT6xI=

Incluso un pequeño cambio en el mensaje, con una probabilidad abrumadora, provocará que muchos bits cambien debido al efecto avalancha . Por ejemplo, cambiar doga cogproduce un hash con valores diferentes para 81 de los 160 bits:

• SHA1("The quick brown fox jumps over the lazy cog")
  • Salida hexadecimal:de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
  • Codificación de texto ASCII a binario Base64 generada :3p8sf9JeGzr60+haC9F9mxANtLM=

El hash de la cadena de longitud cero es:

• SHA1("")
  • Salida hexadecimal:da39a3ee5e6b4b0d3255bfef95601890afd80709
  • Codificación de texto ASCII a binario Base64 generada :2jmj7l5rSw0yVb/vlWAYkK/YBwk=

A continuación se muestra el pseudocódigo del algoritmo SHA-1:

Nota 1: Todas las variables son cantidades sin signo de 32 bits y se dividen en módulos de 2³² al calcular, excepto ml, la longitud del mensaje, que es una cantidad de 64 bits, y hh, el resumen del mensaje, que es una cantidad de 160 bits. Nota 2: Todas las constantes en este pseudocódigo están en formato big-endian . Dentro de cada palabra, el byte más significativo se almacena en la posición del byte más a la izquierda.Inicializar variables: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 ml = longitud del mensaje en bits (siempre un múltiplo del número de bits de un carácter). Preprocesamiento: agregue el bit '1' al mensaje, por ejemplo, agregando 0x80 si la longitud del mensaje es un múltiplo de 8 bits. agregar 0 ≤ k < 512 bits '0', de manera que la longitud del mensaje resultante en bits sea congruente con −64 ≡ 448 (mod 512)agregar ml, la longitud del mensaje original en bits, como un entero big-endian de 64 bits . Por lo tanto, la longitud total es un múltiplo de 512 bits. Procese el mensaje en bloques sucesivos de 512 bits: dividir el mensaje en fragmentos de 512 bits para cada trozo dividir el fragmento en dieciséis palabras big-endian de 32 bits w[i], 0 ≤ i ≤ 15 Programación de mensajes: extender las dieciséis palabras de 32 bits a ochenta palabras de 32 bits: para i de 16 a 79  Nota 3: SHA-0 difiere al no tener esta rotación a la izquierda. w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1 Inicialice el valor hash para este fragmento: a = h0 b = h1 c = h2 d = h3 e = h4 Bucle principal: [ 3 ] [ 56 ] para i desde 0 hasta 79  si 0 ≤ i ≤ 19 entonces f = (b y c) o (( no b) y d) k = 0x5A827999 si no, si 20 ≤ i ≤ 39 f = b xor c xor d k = 0x6ED9EBA1 si no, si 40 ≤ i ≤ 59 f = (b y c) o (b y d) o (c y d) k = 0x8F1BBCDC si no, si 60 ≤ i ≤ 79 f = b xor c xor d k = 0xCA62C1D6 temp = (a leftrotate 5) + f + e + k + w[i] e = d d = c c = b rotación izquierda 30 b = a a = temperatura Agrega el hash de este fragmento al resultado hasta el momento: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e Genera el valor hash final (big-endian) como un número de 160 bits: hh = (h0 desplazamiento a la izquierda 128) o (h1 desplazamiento a la izquierda 96) o (h2 desplazamiento a la izquierda 64) o (h3 desplazamiento a la izquierda 32) o h4

El número hhes el resumen del mensaje, que se puede escribir en hexadecimal (base 16).

Se asumió que los valores constantes elegidos utilizados en el algoritmo no eran números ocultos :

• Las cuatro constantes de ronda kson 2 ³⁰ veces las raíces cuadradas de 2, 3, 5 y 10. Sin embargo, se redondearon incorrectamente al entero más cercano en lugar de al entero impar más cercano, con proporciones equilibradas de bits cero y uno. Además, elegir la raíz cuadrada de 10 (que no es un número primo) la convirtió en un factor común para las otras dos raíces cuadradas de los primos 2 y 5, con posibles propiedades aritméticas utilizables en rondas sucesivas, lo que reduce la robustez del algoritmo frente a la detección de colisiones en algunos bits.
• Los primeros cuatro valores iniciales para h0son h3los mismos que con el algoritmo MD5, y el quinto (para h4) es similar. Sin embargo, no se verificó adecuadamente su resistencia a la inversión de las primeras rondas para inferir posibles colisiones en algunos bits, utilizables por ataques diferenciales multibloque.

En lugar de la formulación del FIPS PUB 180-1 original que se muestra, se pueden utilizar las siguientes expresiones equivalentes para realizar el cálculo fen el bucle principal anterior:

Elección bit a bit entre c y d , controlada por b . (0 ≤ i ≤ 19): f = d xor (b y (c xor d))  (alternativa 1) (0 ≤ i ≤ 19): f = (b y c) o (( no b) y d)  (alternativa 2) (0 ≤ i ≤ 19): f = (b y c) xor (( no b) y d)  (alternativa 3) (0 ≤ i ≤ 19): f = vec_sel(d, c, b)  (alternativa 4)  [premo08]  Función de mayoría bit a bit. (40 ≤ i ≤ 59): f = (b y c) o (d y (b o c))  (alternativa 1) (40 ≤ i ≤ 59): f = (b y c) o (d y (b xor c))  (alternativa 2) (40 ≤ i ≤ 59): f = (b y c) xor (d y (b xor c))  (alternativa 3) (40 ≤ i ≤ 59): f = (b y c) xor (b y d) xor (c y d)  (alternativa 4) (40 ≤ i ≤ 59): f = vec_sel(c, b, c xor d)  (alternativa 5)

También se demostró ^{[ 57 ]} que para las rondas 32-79 el cálculo de:

w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

puede ser reemplazado por:

w[i] = (w[i-6] xor w[i-16] xor w[i-28] xor w[i-32]) rotación izquierda 2

Esta transformación mantiene todos los operandos alineados a 64 bits y, al eliminar la dependencia de w[i], w[i-3]permite una implementación SIMD eficiente con una longitud de vector de 4 como las instrucciones SSE de x86 .

Tras el caso SHAttered, Marc Stevens y Dan Shumow publicaron "sha1collisiondetection" (SHA-1CD), una variante de SHA-1 que detecta ataques de colisión y modifica la salida del hash cuando se detecta uno. La tasa de falsos positivos es de 2⁻⁹⁰ ^. [ ^{63 ] GitHub} utiliza SHA-1CD desde marzo de 2017 y Git desde la versión 2.13.0 de mayo de 2017. ^{[ 64 ]}