En criptografía , SHA-1 ( algoritmo hash seguro 1 ) es una función hash criptográfica que toma una entrada y produce un valor hash de 160 bits (20 bytes ) conocido como resumen de mensaje , que normalmente se representa como un número hexadecimal de 40 dígitos. . Fue diseñado por la Agencia de Seguridad Nacional de los Estados Unidos y es un Estándar Federal de Procesamiento de Información de los EE. UU . [3]
Algoritmos hash seguros | |
---|---|
Conceptos | |
funciones hash · SHA · DSA | |
Estándares principales | |
SHA-0 · SHA-1 · SHA-2 · SHA-3 | |
General | |
---|---|
Diseñadores | Agencia de Seguridad Nacional |
Publicado por primera vez | 1993 (SHA-0), 1995 (SHA-1) |
Serie | ( SHA-0 ), SHA-1, SHA-2 , SHA-3 |
Certificación | FIPS PUB 180-4, CRYPTREC (supervisado) |
Detalle de cifrado | |
Tamaños de resumen | 160 bits |
Tamaños de bloque | 512 bits |
Estructura | Construcción Merkle – Damgård |
Rondas | 80 |
Mejor criptoanálisis público | |
Un ataque de 2011 de Marc Stevens puede producir colisiones hash con una complejidad entre 2 60,3 y 2 65,3 operaciones. [1] La primera colisión pública se publicó el 23 de febrero de 2017. [2] SHA-1 es propenso a ataques de extensión de longitud . |
Desde 2005, SHA-1 no se ha considerado seguro contra oponentes bien financiados; [4] a partir de 2010 muchas organizaciones han recomendado su reemplazo. [5] [6] [7] NIST desaprobó formalmente el uso de SHA-1 en 2011 y prohibió su uso para firmas digitales en 2013. A partir de 2020, los ataques de prefijo elegido contra SHA-1 son prácticos. [8] [9] Como tal, se recomienda eliminar el SHA-1 de los productos lo antes posible y, en su lugar, utilizar SHA-2 o SHA-3 . Reemplazar SHA-1 es urgente cuando se usa para firmas digitales .
Todos los principales proveedores de navegadores web dejaron de aceptar los certificados SSL SHA-1 en 2017. [10] [11] [12] En febrero de 2017, CWI Amsterdam y Google anunciaron que habían realizado un ataque de colisión contra SHA-1, publicando dos archivos PDF diferentes. que produjo el mismo hash SHA-1. [13] [2] Pero SHA-1 todavía es seguro para HMAC . [14]
Microsoft ha descontinuado el soporte de firma de código SHA-1 para Windows Update el 7 de agosto de 2020.
Desarrollo
SHA-1 produce un resumen de mensajes basado en principios similares a los utilizados por Ronald L. Rivest del MIT en el diseño de los algoritmos de resumen de mensajes MD2 , MD4 y MD5 , pero genera un valor hash mayor (160 bits frente a 128 bits).
SHA-1 se desarrolló como parte del proyecto Capstone del gobierno de EE. UU . [15] La especificación original del algoritmo fue publicada en 1993 bajo el título Secure Hash Standard , FIPS PUB 180, por la agencia de estándares del gobierno estadounidense NIST (Instituto Nacional de Estándares y Tecnología). [16] [17] Esta versión ahora se llama a menudo SHA-0 . Fue retirado por la NSA poco después de su publicación y fue reemplazado por la versión revisada, publicada en 1995 en FIPS PUB 180-1 y comúnmente designada como SHA-1 . SHA-1 se diferencia de SHA-0 solo por una única rotación bit a bit en la programación de mensajes de su función de compresión . Según la NSA, esto se hizo para corregir una falla en el algoritmo original que reducía su seguridad criptográfica, pero no brindaron más explicaciones. [18] [19] Las técnicas disponibles públicamente sí demostraron un compromiso de SHA-0, en 2004, antes de SHA-1 en 2017. Ver #Attacks
Aplicaciones
Criptografía
SHA-1 forma parte de varias aplicaciones y protocolos de seguridad ampliamente utilizados, incluidos TLS y SSL , PGP , SSH , S / MIME e IPsec . Estas aplicaciones también pueden utilizar MD5 ; tanto MD5 como SHA-1 descienden de MD4 .
SHA-1 y SHA-2 son los algoritmos hash requeridos por ley para su uso en ciertas aplicaciones del gobierno de EE. UU. , Incluido el uso dentro de otros algoritmos y protocolos criptográficos, para la protección de información confidencial no clasificada. FIPS PUB 180-1 también alentó la adopción y el uso de SHA-1 por 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. dijo: "Las agencias federales deben dejar de usar SHA-1 para ... aplicaciones que requieren resistencia a colisiones tan pronto como sea posible, y deben usar la familia SHA-2 de funciones hash para estas aplicaciones después de 2010". (énfasis en el original), [20] aunque luego se relajó para permitir que SHA-1 se usara para verificar firmas digitales antiguas y sellos de tiempo. [21]
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 para la base de los cifrados de bloques SHACAL .
Integridad de los datos
Los sistemas de control de revisiones como Git , Mercurial y Monotone usan SHA-1, no por seguridad, sino para identificar revisiones y garantizar que los datos no hayan cambiado debido a daños accidentales. Linus Torvalds dijo sobre Git:
- Si tiene daños en el disco, si tiene daños en la DRAM, si tiene algún tipo de problema, Git lo notará. No se trata de si , es una garantía. Puede haber personas que intenten ser maliciosas. No lo conseguirán. ... Nadie ha podido romper SHA-1, pero el punto es que SHA-1, en lo que respecta a Git, ni siquiera es una característica de seguridad. Es puramente una verificación de consistencia. Las partes de seguridad están en otra parte, por lo que mucha gente asume que dado que Git usa SHA-1 y SHA-1 se usa para cosas criptográficamente seguras, piensan que, está bien, es una característica de seguridad enorme. No tiene nada que ver con la seguridad, es el mejor hash que puede obtener. ...
- Te garantizo que, si pones tus datos en Git, puedes confiar en el hecho de que cinco años después, después de que se convirtió de tu disco duro a DVD a cualquier nueva tecnología y lo copiaste, cinco años después puedes verificar que el los datos que recupera son exactamente los mismos datos que ingresó. ...
- Una de las razones por las que me preocupo es por el kernel, tuvimos un robo en uno de los sitios de BitKeeper donde la gente intentó corromper los repositorios de código fuente del kernel. [22] Sin embargo, Git no requiere la segunda resistencia de preimagen de SHA-1 como característica de seguridad, ya que siempre preferirá mantener la versión más antigua de un objeto en caso de colisión, evitando que un atacante sobrescriba archivos subrepticiamente. [23]
Criptoanálisis y validación
Para una función hash para la que L es el número de bits en el resumen del mensaje, siempre se puede encontrar un mensaje que corresponda a un resumen de mensaje dado mediante una búsqueda de fuerza bruta en aproximadamente 2 L evaluaciones. Esto se denomina ataque de preimagen y puede ser práctico o no según L y el entorno informático particular. Sin embargo, una colisión , que consiste en encontrar dos mensajes diferentes que produzcan el mismo resumen de mensajes, requiere en promedio solo alrededor de 1.2 × 2 L / 2 evaluaciones usando un ataque de cumpleaños . Por lo tanto, la fuerza de una función hash generalmente se compara con un cifrado simétrico de la mitad de la longitud del resumen del mensaje. Se pensó originalmente que SHA-1, que tiene un resumen de mensajes de 160 bits, tenía una potencia de 80 bits.
En 2005, los criptógrafos Xiaoyun Wang , Yiqun Lisa Yin y Hongbo Yu produjeron pares de colisiones para SHA-0 y han encontrado algoritmos que deberían producir colisiones SHA-1 en mucho menos de las 2 80 evaluaciones originalmente esperadas . [24]
Algunas de las aplicaciones que utilizan hashes criptográficos, como el almacenamiento de contraseñas, solo se ven mínimamente afectadas por un ataque de colisión. La construcción de una contraseña que funcione para una cuenta determinada requiere un ataque de preimagen , así como el acceso al hash de la contraseña original, que puede ser o no trivial. Los ataques no permiten invertir el cifrado de contraseñas (por ejemplo, para obtener una contraseña para intentar contra la cuenta de un usuario en otro lugar). (Sin embargo, incluso un hash de contraseña seguro no puede evitar ataques de fuerza bruta en contraseñas débiles ).
En el caso de la firma de documentos, un atacante no podría simplemente falsificar una firma de un documento existente: el atacante tendría que producir un par de documentos, uno inocuo y otro dañino, y hacer que el titular de la clave privada firme el documento inocuo. Hay circunstancias prácticas en las que esto es posible; hasta finales de 2008, era posible crear certificados SSL falsificados utilizando una colisión MD5 . [25]
Debido al bloque y la estructura iterativa de los algoritmos y la ausencia de pasos finales adicionales, todas las funciones SHA (excepto SHA-3 [26] ) son vulnerables a ataques de colisión de mensajes parciales y extensión de longitud . [27] Estos ataques permiten a un atacante falsificar un mensaje firmado solo por un hash con clave - SHA ( mensaje || clave ) o SHA ( clave || mensaje ) - extendiendo el mensaje y recalculando el hash sin conocer la clave. Una mejora simple para prevenir estos ataques es hacer hash dos veces: SHA d ( mensaje ) = SHA (SHA (0 b || mensaje )) (la longitud de 0 b , bloque cero, es igual al tamaño de bloque de la función hash) .
Ataques
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 2 80 operaciones. [28]
En febrero de 2005, se anunció un ataque de Xiaoyun Wang , Yiqun Lisa Yin y Hongbo Yu. [29] Los ataques pueden encontrar colisiones en la versión completa de SHA-1, requiriendo menos de 2 69 operaciones. (Una búsqueda por fuerza bruta requeriría 2 80 operaciones).
Los autores escriben: "En particular, nuestro análisis se basa en el ataque diferencial original en SHA-0, el ataque de casi colisión en SHA-0, las técnicas de colisión multibloque, así como las técnicas de modificación de mensajes utilizadas en el ataque de búsqueda de colisión en MD5. Romper SHA-1 no sería posible sin estas poderosas técnicas analíticas ". [30] Los autores han presentado una colisión para SHA-1 de 58 rondas, encontrada con 2 33 operaciones hash. El documento con la descripción completa del ataque se publicó en agosto de 2005 en la conferencia CRYPTO.
En una entrevista, Yin afirma que, "Aproximadamente, aprovechamos las siguientes dos debilidades: una es que el paso de preprocesamiento del archivo no es lo suficientemente complicado; otra es que ciertas operaciones matemáticas en las primeras 20 rondas tienen problemas de seguridad inesperados". [31]
El 17 de agosto de 2005, se anunció una mejora en el ataque SHA-1 en nombre de Xiaoyun Wang , Andrew Yao y Frances Yao en la CRYPTO 2005 Rump Session, reduciendo la complejidad requerida para encontrar una colisión en SHA-1 a 2 63 . [32] El 18 de diciembre de 2007, Martin Cochran explicó y verificó los detalles de este resultado. [33]
Christophe De Cannière y Christian Rechberger mejoraron aún más el ataque a SHA-1 en "Encontrar características de SHA-1: resultados generales y aplicaciones", [34] recibiendo el premio al mejor artículo en ASIACRYPT 2006. Una colisión de dos bloques para SHA de 64 rondas Se presentó -1, encontrado usando métodos no optimizados con 2 35 evaluaciones de función de compresión. Dado que este ataque requiere el equivalente a unas 2 35 evaluaciones, se considera una ruptura teórica significativa. [35] Su ataque se extendió aún más a 73 rondas (de 80) en 2010 por Grechnikov. [36] 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 colisión para SHA-1 utilizando la plataforma de computación distribuida 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 avances. [37]
En la Rump Session 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. [38] [39]
En 2008, una metodología de ataque de Stéphane Manuel informó colisiones de hash con una complejidad teórica estimada de 2 51 a 2 57 operaciones. [40] Sin embargo, más tarde se retractó de esa afirmación después de descubrir que las rutas de colisión locales no eran realmente independientes, y finalmente citó el vector de colisión más eficiente que ya se conocía antes de este trabajo. [41]
Cameron McDonald, Philip Hawkes y Josef Pieprzyk presentaron un ataque de colisión hash con una supuesta complejidad 2 52 en la Rump Session de Eurocrypt 2009. [42] Sin embargo, el documento adjunto, "Differential Path for SHA-1 con complejidad O (2 52 )" ha sido retirado debido al descubrimiento de los autores de que su estimación era incorrecta. [43]
Un ataque contra SHA-1 fue Marc Stevens [44] con un costo estimado de $ 2.77M (2012) para romper un solo valor hash alquilando la potencia de la CPU de los servidores en la nube. [45] Stevens desarrolló este ataque en un proyecto llamado HashClash, [46] implementando un ataque de ruta diferencial. El 8 de noviembre de 2010, afirmó que tenía un ataque de casi colisión en pleno funcionamiento contra SHA-1 completo en funcionamiento 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 61 .
El SHAppening
El 8 de octubre de 2015, Marc Stevens, Pierre Karpman y Thomas Peyrin publicaron un ataque de colisión de inicio libre en la función de compresión de SHA-1 que requiere solo 2 57 evaluaciones de SHA-1. Esto no se traduce directamente en una colisión en la función hash SHA-1 completa (donde un atacante no puede elegir libremente el estado interno inicial), pero socava las afirmaciones de seguridad para SHA-1. En particular, fue la primera vez que se demostró un ataque contra SHA-1 completo ; todos los ataques anteriores fueron demasiado costosos para que sus autores los llevaran a cabo. Los autores nombraron este avance significativo en el criptoanálisis de SHA-1 The SHAppening . [6]
El método se basó en su trabajo anterior, así como en la técnica de aceleración de rutas auxiliares (o bumeranes) de Joux y Peyrin, y en el uso de tarjetas GPU rentables y de alto rendimiento de NVIDIA . La colisión se encontró en un clúster de 16 nodos con un total de 64 tarjetas gráficas. Los autores estimaron que se podría encontrar una colisión similar comprando US $ 2,000 de tiempo de GPU en EC2 . [6]
Los autores estimaron que el costo de alquilar suficiente tiempo de CPU / GPU EC2 para generar una colisión completa para SHA-1 en el momento de la publicación estaba entre US $ 75K y 120K, y señalaron que estaba dentro del presupuesto de las organizaciones criminales, no para mencionar las agencias nacionales de inteligencia . Como tal, los autores recomendaron que SHA-1 se desaproveche lo antes posible. [6]
SHAtter: primera colisión pública
El 23 de febrero de 2017, el CWI (Centrum Wiskunde & Informatica) y Google anunciaron el ataque SHAtter , en el que generaron dos archivos PDF diferentes con el mismo hash SHA-1 en aproximadamente 2 63.1 evaluaciones SHA-1. Este ataque es aproximadamente 100.000 veces más rápido que la fuerza bruta de una colisión SHA-1 con un ataque de cumpleaños , que se estimó en 2 80 evaluaciones SHA-1. El ataque requirió "la potencia de procesamiento equivalente a 6.500 años de cálculos con una sola CPU y 110 años de cálculos con una sola GPU". [2]
Ataque de cumpleaños cercano a la colisión: primer ataque práctico de prefijo elegido
El 24 de abril de 2019, un artículo de Gaëtan Leurent y Thomas Peyrin presentado en Eurocrypt 2019 describió una mejora del ataque de prefijo elegido anteriormente en funciones de digestión similares a Merkle-Damgård basadas en cifrados de bloque de Davies-Meyer . Con estas mejoras, este método es capaz de encontrar colisiones de prefijo elegido en aproximadamente 2 68 evaluaciones SHA-1. Esto es aproximadamente mil millones de veces más rápido (y ahora se puede usar para muchos ataques dirigidos, gracias a la posibilidad de elegir un prefijo, por ejemplo, código malicioso o identidades falsas en certificados firmados) que las evaluaciones 2 77.1 del ataque anterior (pero sin el prefijo elegido, que no era práctico para la mayoría de los ataques dirigidos porque las colisiones encontradas eran casi aleatorias) [47] y es lo suficientemente rápido como para ser práctico para atacantes ingeniosos, requiriendo aproximadamente $ 100,000 de procesamiento en la nube. Este método también es capaz de encontrar colisiones de prefijo elegido en la función MD5 , pero a una complejidad de 2 46,3 no supera el mejor método disponible anterior a nivel teórico (2 39 ), aunque potencialmente a nivel práctico (≤2 49 ). [48] [49] Este ataque tiene un requisito de memoria de más de 500 GB.
El 5 de enero de 2020, los autores publicaron un ataque mejorado. [9] En este artículo demuestran un ataque de colisión de prefijo elegido con una complejidad de 2 63,4 , que en el momento de la publicación costaría 45k USD por colisión generada.
SHA-0
En CRYPTO 98, dos investigadores franceses, Florent Chabaud y Antoine Joux , presentaron un ataque a SHA-0: se pueden encontrar colisiones con complejidad 2 61 , menos de 2 80 para una función hash ideal del mismo tamaño. [50]
En 2004, Biham y Chen encontraron casi colisiones para SHA-0, dos mensajes que tienen casi el mismo valor; 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. [51]
Posteriormente, el 12 de agosto de 2004, Joux, Carribault, Lemuet y Jalby anunciaron una colisión para el algoritmo SHA-0 completo. Esto se hizo utilizando una generalización del ataque de Chabaud y Joux. Encontrar la colisión tuvo una complejidad 2 51 y tomó alrededor de 80.000 horas de procesador en una supercomputadora con 256 procesadores Itanium 2 (equivalente a 13 días de uso a tiempo completo de la computadora).
El 17 de agosto de 2004, en la Sesión Rump de CRYPTO 2004, Wang , Feng, Lai y Yu anunciaron los resultados preliminares sobre un ataque a MD5 , SHA-0 y otras funciones hash. La complejidad de su ataque a SHA-0 es 2 40 , significativamente mejor que el ataque de Joux et al. [52] [53]
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 39 operaciones. [29] [54]
Otro ataque en 2008 que aplicó el ataque boomerang redujo la complejidad de encontrar colisiones a 2 33,6 , lo que se estimó en 1 hora en una PC promedio a partir del año 2008. [55]
A la luz de los resultados de SHA-0, algunos expertos [ ¿quién? ] sugirió que se deberían reconsiderar los planes para el uso de SHA-1 en nuevos criptosistemas . Después de que se publicaron los resultados de CRYPTO 2004, NIST anunció que planeaba eliminar el uso de SHA-1 para 2010 a favor de las variantes de SHA-2. [56]
Validación oficial
Las implementaciones de todas las funciones de seguridad aprobadas por FIPS pueden validarse oficialmente a través del programa CMVP , administrado conjuntamente por el Instituto Nacional de Estándares y Tecnología (NIST) y el Establecimiento de Seguridad de las Comunicaciones (CSE). Para la verificación informal, un paquete para generar una gran cantidad de vectores de prueba está disponible para su descarga en el sitio del NIST; la verificación resultante, sin embargo, no reemplaza la validación formal CMVP, que es requerida por ley para ciertas aplicaciones.
A diciembre de 2013[actualizar], hay más de 2000 implementaciones validadas de SHA-1, con 14 de ellas capaces de manejar mensajes con una longitud en bits que no es múltiplo de ocho (ver Lista de validación de SHS ).
Ejemplos y pseudocódigo
Hashes de ejemplo
Estos son ejemplos de resúmenes de mensajes SHA-1 en codificación de texto hexadecimal y binario Base64 a ASCII .
SHA1("The quick brown fox jumps over the lazy dog")
- Salida hexadecimal:
2fd4e1c67a2d28fced849ee1bb76e7391b93eb12
- Codificación de texto binario de Base64 a ASCII :
L9ThxnotKPzthJ7hu3bnORuT6xI=
- Salida hexadecimal:
Incluso un pequeño cambio en el mensaje, con una probabilidad abrumadora, dará como resultado que muchos bits cambien debido al efecto de avalancha . Por ejemplo, cambiar dog
a cog
produce un hash con diferentes valores para 81 de los 160 bits:
SHA1("The quick brown fox jumps over the lazy cog")
- Salida hexadecimal:
de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3
- Codificación de texto binario de Base64 a ASCII :
3p8sf9JeGzr60+haC9F9mxANtLM=
- Salida hexadecimal:
El hash de la cadena de longitud cero es:
SHA1("")
- Salida hexadecimal:
da39a3ee5e6b4b0d3255bfef95601890afd80709
- Codificación de texto binario de Base64 a ASCII :
2jmj7l5rSw0yVb/vlWAYkK/YBwk=
- Salida hexadecimal:
Pseudocódigo SHA-1
A continuación, se muestra el pseudocódigo para el algoritmo SHA-1:
Nota 1: Todas las variables son cantidades de 32 bits sin firmar y se ajustan al módulo 2 32 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 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 = 0x67452301h1 = 0xEFCDAB89h2 = 0x98BADCFEh3 = 0x10325476h4 = 0xC3D2E1F0ml = 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.añadir 0 ≤ k <512 bits '0', de modo que la longitud del mensaje resultante en bits sea congruente con −64 ≡ 448 (mod 512)agregue ml, la longitud original del mensaje en bits, como un entero big-endian de 64 bits . Por tanto, la longitud total es un múltiplo de 512 bits.Procese el mensaje en sucesivos fragmentos de 512 bits:dividir el mensaje en trozos de 512 bitspor cada trozo dividir el fragmento en dieciséis palabras big-endian de 32 bits w [i], 0 ≤ i ≤ 15 Programación de mensajes: amplíe las dieciséis palabras de 32 bits en ochenta palabras de 32 bits: para i de 16 a 79 Nota 3: SHA-0 se diferencia por no tener este giro a la izquierda. w [i] = (w [i-3] xor w [i-8] xor w [i-14] xor w [i-16]) girar a la izquierda 1 Inicialice el valor hash para este fragmento: a = h0 b = h1 c = h2 d = h3 e = h4 Bucle principal: [3] [57] para i a partir de 0 a 79 si 0 ≤ i ≤ 19 entonces f = (b y c) o (( no b) y d) k = 0x5A827999 de lo contrario, si 20 ≤ i ≤ 39 f = b xor c xor d k = 0x6ED9EBA1 de lo contrario, si 40 ≤ i ≤ 59 f = (b y c) o (b y d) o (c y d) k = 0x8F1BBCDC de lo contrario si 60 ≤ i ≤ 79 f = b xor c xor d k = 0xCA62C1D6 temp = (a izquierda rotar 5) + f + e + k + w [i] e = d d = c c = b girar a la izquierda 30 b = a a = temp Agregue el hash de este fragmento al resultado hasta ahora: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + eProducir el valor hash final (big-endian) como un número de 160 bits: hh = (h0 izquierda desplazamiento 128) o (h1 izquierda desplazamiento 96) o (h2 izquierda desplazamiento 64) o (h3 izquierda desplazamiento 32) o h4
El número hh
es 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 nada en mis números de la manga :
- Las cuatro constantes redondas
k
son 2 30 veces las raíces cuadradas de 2, 3, 5 y 10. Sin embargo, se redondearon incorrectamente al número entero más cercano en lugar de redondearse al número entero impar más cercano, con proporciones equilibradas de cero y uno bits. 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 elegidas de los números primos 2 y 5, con propiedades aritméticas posiblemente utilizables en rondas sucesivas, lo que reduce la fuerza del algoritmo contra encontrando colisiones en algunos bits. - Los primeros cuatro valores iniciales para a
h0
travésh3
son los mismos con el algoritmo MD5, y el quinto (parah4
) es similar. Sin embargo, no se verificó adecuadamente que fueran resistentes 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 usar las siguientes expresiones equivalentes para calcular f
en el ciclo principal anterior:
Elección Bitwise entre c y d , controlado por b . (0 ≤ i ≤ 19): f = d xor (b y (c xor d)) (alternativa 1) (0 ≤ i ≤ 19): f = (b y c) xor (( 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) 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 (d y (b xor c)) (alternativa 4) (40 ≤ i ≤ 59): f = (b y c) xor (b y d) xor (c y d) (alternativa 5) (40 ≤ i ≤ 59): f = vec_sel (c, b, c xor d) (alternativa 6)
También se demostró [58] 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]) girar a la izquierda 1
se puede reemplazar con:
w [i] = (w [i-6] xor w [i-16] xor w [i-28] xor w [i-32]) rotar a la izquierda 2
Esta transformación mantiene alineados todos los operandos de 64 bits y, al eliminar la dependencia de w[i]
on w[i-3]
, permite una implementación SIMD eficiente con una longitud de vector de 4 como instrucciones SSE x86 .
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.
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) | Seguridad contra ataques de extensión de longitud (bits) | Rendimiento en Skylake ( cpb mediano ) [59] | Publicado por primera vez | ||
---|---|---|---|---|---|---|---|---|---|---|---|
Mensajes largos | 8 bytes | ||||||||||
MD5 (como referencia) | 128 | 128 (4 × 32) | 512 | 64 | Y, Xor, Rot, Add (mod 2 32 ), O | ≤ 18 (colisiones encontradas) [60] | 0 | 4,99 | 55,00 | 1992 | |
SHA-0 | 160 | 160 (5 × 32) | 512 | 80 | Y, Xor, Rot, Add (mod 2 32 ), O | <34 (colisiones encontradas) | 0 | ≈ SHA-1 | ≈ SHA-1 | 1993 | |
SHA-1 | <63 (colisiones encontradas) [61] | 3,47 | 52,00 | 1995 | |||||||
SHA-2 | SHA-224 SHA-256 | 224 256 | 256 (8 × 32) | 512 | 64 | Y, Xor, Rot, Add (mod 2 32 ), Or, Shr | 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 | Y, Xor, Rot, Add (mod 2 64 ), Or, Shr | 192 256 | 128 (≤ 384) 0 [62] | 5.12 5.06 | 135,75 135,50 | 2001 | |
SHA-512/224 SHA-512/256 | 224 256 | 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 [63] | Y, Xor, Rot, No | 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 |
SHAKE128 SHAKE256 | d (arbitrario) d (arbitrario) | 1344 1088 | min ( d / 2, 128) min ( d / 2, 256) | 256 512 | 7.08 8.59 | 155.25 155.50 |
Implementaciones
A continuación se muestra una lista de bibliotecas de criptografía que admiten SHA-1:
- Botan
- Castillo inflable
- cryptlib
- Cripto ++
- Libgcrypt
- TLS de Mbed
- Ortiga
- LibreSSL
- OpenSSL
- GnuTLS
- loboSSL
La aceleración de hardware la proporcionan las siguientes extensiones de procesador:
- Extensiones Intel SHA : disponibles en algunos procesadores Intel y AMD x86.
- VIA Candado
- Extensiones de criptografía ARMv8 [64]
Ver también
- Comparación de funciones hash criptográficas
- Resumen de seguridad de la función hash
- Asociación Internacional para la Investigación Criptológica
- Estándar de hash seguro
Notas
- ^ Stevens, Marc (19 de junio de 2012). Ataques a funciones y aplicaciones hash (PDF) (Tesis). Universidad de Leiden . hdl : 1887/19093 . ISBN 9789461913173. OCLC 795702954 .
- ^ a b c Stevens, Marc ; Bursztein, Elie ; Karpman, Pierre; Albertini, Ange; Markov, Yarik (2017). Katz, Jonathan ; Shajam, Hovav (eds.). La primera colisión para SHA-1 completo (PDF) . Avances en Criptología - CRYPTO 2017. Apuntes en Informática . 10401 . Springer . págs. 570–596. doi : 10.1007 / 978-3-319-63688-7_19 . ISBN 9783319636870. Archivado desde el original (PDF) el 15 de mayo de 2018 . Consultado el 23 de febrero de 2017 . Resumen de Lay - Blog de seguridad de Google (23 de febrero de 2017).
- ^ a b https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
- ^ Schneier, Bruce (18 de febrero de 2005). "Schneier sobre seguridad: criptoanálisis de SHA-1" .
- ^ "NIST.gov - División de seguridad informática - Centro de recursos de seguridad informática" . Archivado desde el original el 25 de junio de 2011 . Consultado el 5 de enero de 2019 .
- ^ a b c d Stevens1, Marc; Karpman, Pierre; Peyrin, Thomas. "El SHAppening: colisiones de inicio libre para SHA-1" . Consultado el 9 de octubre de 2015 .
- ^ Schneier, Bruce (8 de octubre de 2015). "SHA-1 Freestart Collision" . Schneier sobre seguridad .
- ^ "Fallo crítico demostrado en algoritmo de seguridad digital común" . media.ntu.edu.sg .
- ^ a b Gaëtan Leurent; Thomas Peyrin (5 de enero de 2020). "SHA-1 es una primera colisión de prefijo elegido de Shambles en SHA-1 y una aplicación a PGP Web of Trust" (PDF) . Archivo de Cryptology ePrint, Informe 2020/014 .
- ^ Goodin, Dan (4 de mayo de 2016). "Microsoft retirará el soporte para certificados SHA1 en los próximos 4 meses" . Ars Technica . Consultado el 29 de mayo de 2019 .
- ^ "Google eliminará el cifrado SHA-1 de Chrome antes del 1 de enero de 2017" . VentureBeat . 2015-12-18 . Consultado el 29 de mayo de 2019 .
- ^ "El fin de SHA-1 en la Web Pública" . Blog de seguridad de Mozilla . Consultado el 29 de mayo de 2019 .
- ^ "CWI, Google anuncia la primera colisión para el estándar de seguridad industrial SHA-1" . Consultado el 23 de febrero de 2017 .
- ^ Barker, Elaine (mayo de 2020). "Recomendación para la gestión de claves: Parte 1 - General, Tabla 3" . NIST, Informe técnico : 56. doi : 10.6028 / NIST.SP.800-57pt1r5 .
- ^ Preguntas frecuentes de RSA sobre Capstone
- ^ Selvarani, R .; Aswatha, Kumar; TV Suresh, Kumar (2012). Actas de la Conferencia Internacional sobre Avances en Computación . Springer Science & Business Media. pag. 551. ISBN 978-81-322-0740-5.
- ^ Secure Hash Standard, publicación de estándares federales de procesamiento de información FIPS PUB 180 , Instituto Nacional de Estándares y Tecnología, 11 de mayo de 1993
- ^ Kramer, Samuel (11 de julio de 1994). "Revisión propuesta del estándar federal de procesamiento de información (FIPS) 180, estándar de hash seguro" . Registro Federal .
- ^ fgrieu. "¿Dónde puedo encontrar una descripción del algoritmo hash SHA-0?" . Intercambio de pila de criptografía .
- ^ Centro de recursos de seguridad informática del Instituto Nacional de Estándares y Tecnología, Política de marzo de 2006 del NIST sobre funciones hash Archivado 2014-01-02 en Wayback Machine , consultado el 28 de septiembre de 2012.
- ^ Centro de recursos de seguridad informática del Instituto Nacional de Estándares y Tecnología, Política de NIST sobre funciones Hash Archivado 2011-06-09 en Wayback Machine , consultado el 28 de septiembre de 2012.
- ^ "Charla técnica: Linus Torvalds en git" . Consultado el 13 de noviembre de 2013 .
- ^ Torvalds, Linus. "Re: ¿Empezando a pensar en sha-256?" . marc.info . Consultado el 30 de mayo de 2016 .
- ^ Wang, Xiaoyun; Yin, Yiqun Lisa; Yu, Hongbo (14 de agosto de 2005). Encontrar colisiones en el SHA-1 completo (PDF) . Avances en criptología - CRYPTO 2005 . Apuntes de conferencias en Ciencias de la Computación. 3621 . Springer, Berlín, Heidelberg. págs. 17–36. doi : 10.1007 / 11535218_2 . ISBN 978-3-540-28114-6.
- ^ Sotirov, Alexander; Stevens, Marc; Appelbaum, Jacob; Lenstra, Arjen; Molnar, David; Osvik, Dag Arne; de Weger, Benne (30 de diciembre de 2008). "MD5 considerado dañino hoy: Creación de un certificado de CA falso" . Consultado el 29 de marzo de 2009 .
- ^ "Fortalezas de Keccak - Diseño y seguridad" . La familia de funciones de esponja Keccak . Equipo de Keccak . Consultado el 20 de septiembre de 2015 .
A diferencia de SHA-1 y SHA-2, Keccak no tiene la debilidad de extensión de longitud, por lo que no necesita la construcción anidada HMAC. En cambio, el cálculo de MAC se puede realizar simplemente anteponiendo la clave al mensaje.
- ^ Niels Ferguson, Bruce Schneier y Tadayoshi Kohno, Ingeniería de criptografía , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
- ^ "Archivo de Cryptology ePrint: Informe 2005/010" .
- ^ a b "SHA-1 roto - Schneier sobre seguridad" .
- ^ Ataques de búsqueda de colisión en SHA1 Archivado el 19 de febrero de 2005 en la Wayback Machine , Instituto de Tecnología de Massachusetts
- ^ Lemos, Robert. "Arreglando un agujero en la seguridad" . ZDNet .
- ^ "Nuevos resultados criptoanalíticos contra SHA-1 - Schneier sobre seguridad" .
- ^ Notas sobre Wang et al. 2 63 Ruta diferencial SHA-1
- ^ De Cannière, Christophe; Rechberger, Christian (15 de noviembre de 2006). "Encontrar características de SHA-1: resultados generales y aplicaciones". Avances en Criptología - ASIACRYPT 2006 . Apuntes de conferencias en Ciencias de la Computación. 4284 . págs. 1–20. doi : 10.1007 / 11935230_1 . ISBN 978-3-540-49475-1.
- ^ "IAIK Krypto Group - Descripción del proyecto de búsqueda de colisiones SHA-1" . Archivado desde el original el 15 de enero de 2013 . Consultado el 30 de junio de 2009 .
- ^ "Colisiones para SHA-1 de 72 y 73 pasos: Mejoras en el método de características" . Consultado el 24 de julio de 2010 .
- ^ "Búsqueda de colisión SHA-1 Graz" . Archivado desde el original el 25 de febrero de 2009 . Consultado el 30 de junio de 2009 .
- ^ "heise online - IT-News, Nachrichten und Hintergründe" . heise en línea .
- ^ "Programa de grupa de Crypto 2006" .
- ^ Manuel, Stéphane. "Clasificación y generación de vectores de perturbación para ataques de colisión contra SHA-1" (PDF) . Consultado el 19 de mayo de 2011 . Cite journal requiere
|journal=
( ayuda ) - ^ Manuel, Stéphane (2011). "Clasificación y generación de vectores de perturbación para ataques de colisión contra SHA-1". Diseños, Códigos y Criptografía . 59 (1-3): 247-263. doi : 10.1007 / s10623-010-9458-9 . S2CID 47179704 . el vector de perturbación más eficiente es Codeword2 reportado por primera vez por Jutla y Patthak
- ^ Colisiones SHA-1 ahora 2 ^ 52
- ^ "Archivo de Cryptology ePrint: Informe 2009/259" .
- ^ Criptoanálisis de MD5 y SHA-1
- ^ "¿Cuándo veremos colisiones para SHA-1? - Schneier sobre seguridad" .
- ^ "Alojamiento de proyectos de Google" .
- ^ Marc Stevens (19 de junio de 2012). "Ataques a funciones y aplicaciones hash" (PDF) . Tesis de Doctorado .
- ^ Leurent, Gaëtan; Peyrin, Thomas (2019). "De las colisiones a la aplicación de colisiones de prefijo elegido a SHA-1 completo" (PDF) . Avances en Criptología - EUROCRYPT 2019 . Apuntes de conferencias en Ciencias de la Computación. 11478 . págs. 527–555. doi : 10.1007 / 978-3-030-17659-4_18 . ISBN 978-3-030-17658-7.
- ^ Gaëtan Leurent; Thomas Peyrin (24 de abril de 2019). "De las colisiones a las colisiones de prefijo elegido: aplicación a SHA-1 completo" (PDF) . Eurocrypt 2019 .
- ^ Chabaud, Florent; Joux, Antoine (1998). Krawczyk, Hugo (ed.). Colisiones diferenciales en SHA-0 (PDF) . Avances en Criptología - CRYPTO 1998. Apuntes en Ciencias de la Computación . 1462 . Springer . págs. 56–71. CiteSeerX 10.1.1.138.5141 . doi : 10.1007 / bfb0055720 . ISBN 9783540648925.
- ^ Biham, Eli; Chen, Rafi. "Casi colisiones de SHA-0" (PDF) .
- ^ "Informe de Crypto 2004" . Archivado desde el original el 21 de agosto de 2004 . Consultado el 23 de agosto de 2004 .
- ^ Grieu, Francois (18 de agosto de 2004). "Re: ¿Alguna noticia anticipada de la sesión de criptografía?". Grupo de noticias : sci.crypt . El evento ocurre a las 05:06:02 +0200. Usenet: [email protected] .
- ^ Ataques de búsqueda de colisión eficiente en SHA-0 Archivado el 10 de septiembre de 2005 en la Wayback Machine , Universidad de Shandong
- ^ Manuel, Stéphane; Peyrin, Thomas (11 de febrero de 2008). Colisiones en SHA-0 en una hora (PDF) . Cifrado rápido de software 2008. Apuntes de clase en Ciencias de la Computación. 5086 . págs. 16–35. doi : 10.1007 / 978-3-540-71039-4_2 . ISBN 978-3-540-71038-7.
- ^ "Comentarios breves del NIST sobre los recientes ataques criptoanalíticos sobre las funciones de hash seguro y la seguridad continua que proporciona SHA-1" (PDF) . Archivado desde el original (PDF) el 4 de junio de 2011 . Consultado el 5 de mayo de 2010 .
- ^ "RFC 3174 - Algoritmo de hash seguro 1 de EE. UU. (SHA1)" .
- ^ Locktyukhin, Max; Farrel, Kathy (2010-03-31), "Improving the Performance of the Secure Hash Algorithm (SHA-1)" , Intel Software Knowledge Base , consultado el 2010-04-02
- ^ "Tabla de medidas" . bench.cr.yp.to .
- ^ Tao, Xie; Liu, Fanbao; Feng, Dengguo (2013). Ataque de colisión rápido en MD5 (PDF) . Cryptology ePrint Archive (informe técnico). IACR .
- ^ Stevens, Marc ; Bursztein, Elie ; Karpman, Pierre; Albertini, Ange; Markov, Yarik. La primera colisión para SHA-1 completo (PDF) (Informe técnico). Investigación de Google . Resumen de Lay - Blog de seguridad de Google (23 de febrero de 2017).
- ^ Sin truncamiento, se conoce el estado interno completo de la función hash, independientemente de la resistencia a la colisión. Si se trunca la salida, se debe buscar y encontrar la parte eliminada del estado antes de que se pueda reanudar la función hash, lo que permite que el ataque continúe.
- ^ "La familia de funciones de esponja Keccak" . Consultado el 27 de enero de 2016 .
- ^ "Extensión de criptografía manual de referencia técnica del procesador ARM Cortex-A53 MPCore" .
Referencias
- Eli Biham , Rafi Chen, Near-Collisions of SHA-0, Cryptology ePrint Archive, Report 2004/146, 2004 (apareció en CRYPTO 2004), IACR.org
- Xiaoyun Wang , Hongbo Yu y Yiqun Lisa Yin, Ataques de búsqueda de colisiones eficientes en SHA-0 , Crypto 2005
- Xiaoyun Wang , Yiqun Lisa Yin y Hongbo Yu, Encontrando colisiones en el SHA-1 completo , Crypto 2005
- Henri Gilbert , Helena Handschuh : Análisis de seguridad de SHA-256 y Sisters . Áreas seleccionadas en criptografía 2003: pp175–193
- Una guía ilustrada de hashes criptográficos
- "Revisión propuesta del estándar federal de procesamiento de información (FIPS) 180, estándar de hash seguro" . Registro Federal . 59 (131): 35317–35318. 1994-07-11 . Consultado el 26 de abril de 2007 .[ enlace muerto permanente ]
- A. Cilardo, L. Esposito, A. Veniero, A. Mazzeo, V. Beltran, E. Ayugadé, A CellBE-based HPC application for the analysis of vulnerabilities in cryptographic hash functions , High Performance Computing and Communication international conference, agosto de 2010
enlaces externos
- Kit de herramientas criptográficas de CSRC : sitio oficial del NIST para el estándar Secure Hash
- FIPS 180-4: Estándar de hash seguro (SHS)
- RFC 3174 (con implementación de ejemplo C)
- Entrevista a Yiqun Lisa Yin sobre el ataque a SHA-1
- Explicación de los ataques exitosos a SHA-1 (3 páginas, 2006)
- Investigación en criptografía - Preguntas y respuestas sobre colisión de hash
- SHA-1 en Curlie
- Conferencia sobre SHA-1 (1h 18m) en YouTube a cargo de Christof Paar