SHA-1

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 29 de octubre de 2020; las comprobaciones requieren 12 ediciones .

SHA-1
Desarrolladores	NSA con NIST
Creado	1995
publicado	1995
Predecesor	SHA-0
Sucesor	SHA-2
tamaño de hash	160 bits
Número de rondas	80
Tipo de	función hash

Secure Hash Algorithm 1 es un algoritmo hash criptográfico . Descrito en RFC 3174 . Para un mensaje de entrada de longitud arbitraria ( bits máximo, que es aproximadamente igual a 2 exabytes ), el algoritmo genera un valor hash de 160 bits (20 bytes), también llamado resumen del mensaje , que generalmente se muestra como un hexadecimal de 40 dígitos. número. Se utiliza en muchas aplicaciones y protocolos criptográficos. También recomendado como primario para agencias gubernamentales en los EE.UU. Los principios detrás de SHA-1 son similares a los utilizados por Ronald Rivest al diseñar MD4 . $2^{64}-1$

Historia

En 1993, la NSA trabajó con el NIST para desarrollar el algoritmo hash seguro (ahora conocido como SHA-0) (publicado en FIPS PUB 180) para un estándar hash seguro. Sin embargo, la NSA pronto retiró esta versión, citando un error que descubrieron que nunca se reveló. Y lo reemplazó con una versión revisada publicada en 1995 en FIPS PUB 180-1. Esta versión se considera lo que se denomina SHA-1. Más tarde, en la conferencia CRYPTO de 1998 , dos investigadores franceses presentaron un ataque al algoritmo SHA-0 que no funcionó con el algoritmo SHA-1. Esto puede haber sido un error descubierto por la NSA .

Descripción del algoritmo

SHA-1 implementa una función hash , basada en la idea de una función de compresión. Las entradas a la función de compresión son un bloque de mensajes de 512 bits y la salida del bloque de mensajes anterior. La salida es el valor de todos los bloques hash hasta ese punto. En otras palabras, el bloque hash es . El valor hash de todo el mensaje es la salida del último bloque. $Mi}$ $h_i = f(M_i, h_{i-1})$

Inicialización

El mensaje original se divide en bloques de 512 bits cada uno. El último bloque se rellena con una longitud múltiplo de 512 bits. Primero, se agregan 1 (bits) y luego se agregan ceros para que la longitud del bloque sea 512 - 64 = 448 bits. Los 64 bits restantes contienen la longitud del mensaje original en bits (en formato big-endian ). Si el último bloque tiene una longitud de más de 447 pero menos de 512 bits, entonces el relleno se realiza de la siguiente manera: primero, se agrega 1 (bit), luego se agregan ceros hasta el final del bloque de 512 bits; después de eso, se crea otro bloque de 512 bits, que se llena hasta 448 bits con ceros, después de lo cual la longitud del mensaje original en bits (en formato big-endian) se escribe en los 64 bits restantes. El último bloque siempre se rellena, incluso si el mensaje ya tiene la longitud deseada.

Se inicializan cinco variables de 32 bits.

A=0x67452301 B=0xEFCDAB89 C=0x98BADCFE D=0x10325476 E=0xC3D2E1F0

Se definen cuatro operaciones no lineales y cuatro constantes.

$F_t(m, l, k) = (m \cuña l) \vee (\neg{m} \cuña k)$	$k_t$ = 0x5A827999	0≤t≤19
$F_t(m, l, k) = m \oplus l \oplus k$	$k_t$ = 0x6ED9EBA1	20≤t≤39
$F_t(m, l, k) = (m \cuña l) \vee (m \cuña k) \vee (l \cuña k)$	$k_t$ = 0x8F1BBCDC	40≤t≤59
$F_t(m, l, k) = m \oplus l \oplus k$	$k_t$ = 0xCA62C1D6	60≤t≤79

Bucle principal

El ciclo principal procesa iterativamente cada bloque de 512 bits. Al inicio de cada ciclo se introducen las variables a, b, c, d, e, las cuales se inicializan con los valores A, B, C, D, E, respectivamente. El bloque de mensajes se convierte de 16 palabras de 32 bits a 80 palabras de 32 bits de acuerdo con la siguiente regla: $Mi}$ $W_j$

W_t = M_t

para 0≤t≤15 = ( -3 -8 -14 -16 ) << 1 para 16≤t≤79

W_{t}

W_{t}

\oplus

W_{t}

\oplus

W_{t}

\oplus

W_{t}

, donde "<<" es un desplazamiento circular a la izquierda.

para 0 a 79 temp = (a<<5) + ( b,c,d) + e + e = d d = c c = b<<30 b = a

t

Pie

W_t + K_t

a = temperatura

, donde "+" es la suma de enteros de 32 bits sin signo con el exceso (bit 33) descartado.

Después de eso, los valores a, b, c, d, e se suman a A, B, C, D, E, respectivamente. Comienza la siguiente iteración.

El valor final será la concatenación de cinco palabras de 32 bits (A, B, C, D, E) en un valor hash de 160 bits.

Pseudocódigo SHA-1

El pseudocódigo para el algoritmo SHA-1 es el siguiente:

Nota: Todas las variables utilizadas son de 32 bits. Inicialización de variables: h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 Procesamiento preliminar: Adjunte el bit '1' al mensaje Agregue k bits '0', donde k es el número más pequeño ≥ 0 tal que la longitud del mensaje resultante (en bits) módulo 512 es comparable a 448 (longitud mod 512 == 448) Agregue la longitud del mensaje original (antes del preprocesamiento) como un número entero de 64 bits Número big-endian , en bits . En el proceso, el mensaje se divide secuencialmente en 512 bits: para iterar sobre todas esas partes dividimos esta pieza en 16 partes, palabras de 32 bits (big-endian) w[i], 0 <= i <= 15 16 palabras de 32 bits se rellenan a 80 palabras de 32 bits: para i de 16 a 79 w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) girar a la izquierda 1 Inicializando los valores hash de esta parte: a = h0 b = h1 c = h2 re = h3 e=h4 Bucle principal: para i 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 entonces f = b xor c xor d k = 0x6ED9EBA1 de lo contrario, si 40 ≤ i ≤ 59 entonces f = (b y c) o (b y d) o (c y d) k = 0x8F1BBCDC de lo contrario, si 60 ≤ i ≤ 79 entonces f = b xor c xor d k = 0xCA62C1D6 temp = (un giro a la izquierda 5) + f + e + k + w[i] e = d re=c c = b girar a la izquierda 30 b = un a = temperatura Agregue el valor hash de esta parte al resultado: h0 = h0 + un h1 = h1 + segundo h2 = h2 + c h3 = h3 + d h4 = h4 + e Valor hash final (h0, h1, h2, h3, h4 debe convertirse a big-endian): resumen = hash = h0 agregar h1 agregar h2 agregar h3 agregar h4

En lugar de la redacción original de FIPS PUB 180-1, se dan las siguientes expresiones equivalentes y se pueden usar en una computadora fen el bucle principal:

(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) + (( no b) y d) (alternativa 3) (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) + (d y (b xor c)) (alternativa 3) (40 ≤ i ≤ 59): f = (b y c) xor (b y d) xor (c y d) (alternativa 4)

Ejemplos

Los siguientes son ejemplos de hash SHA-1. Se supone que todos los mensajes utilizan la codificación UTF-8 .

Pangrama hash en ruso:

SHA-1("¿Habría cítricos en los matorrales del sur? ¡Sí, pero uno falso!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b

Pangrama hash en inglés:

SHA-1 (" El rápido zorro marrón salta sobre el perro perezoso ") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 SHA-1("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926

Un pequeño cambio en el texto de origen (una letra en mayúscula) genera un gran cambio en el propio hash. Esto se debe al efecto de avalancha .

SHA-1("sha") = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640

Incluso para una cadena vacía, se calcula un valor hash no trivial.

SHA-1("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Criptoanálisis

El criptoanálisis de funciones hash tiene como objetivo estudiar la vulnerabilidad a varios tipos de ataques. Los principales son:

detección de colisión: una situación en la que dos mensajes de origen diferentes corresponden al mismo valor hash.
encontrar el prototipo, el mensaje original, por su hash.

Al resolver por el método de "fuerza bruta" :

la primera tarea requiere un promedio de 2160/2 = 280 operaciones usando el ataque de cumpleaños .
el segundo requiere 2.160 operaciones.

La seguridad de la firma digital electrónica que utiliza este algoritmo hash depende de la estabilidad de la función hash para encontrar colisiones . La resistencia a la preimagen depende de la seguridad del almacenamiento de hash de contraseñas con fines de autenticación .

En enero de 2005, Vincent Rayman y Elisabeth Oswald publicaron un ataque a una versión truncada de SHA-1 (53 rondas en lugar de 80 ), que permite encontrar colisiones en menos de 280 operaciones.

En febrero de 2005, Xiaoyun Wang , Yiqun Lisa Yin y Hongbo Yu presentaron un ataque a SHA-1 completo que requiere menos de 269 operaciones.

Sobre el método, los autores escriben:

Presentamos un conjunto de estrategias y técnicas relacionadas que se pueden utilizar para superar algunos obstáculos importantes en la búsqueda de colisiones en SHA-1. Primero buscamos caminos diferenciales cercanos a la colisión que tengan un pequeño "peso de Hamming" en el "vector de ruido" donde cada bit representa una colisión local de 6 pasos. Luego ajustamos la ruta diferencial desde la primera etapa a otra ruta diferencial aceptable en consecuencia para evitar colisiones en serie y truncadas inaceptables. Finalmente, convertimos dos caminos diferenciales de casi colisión de un bloque en un camino de colisión de dos bloques con el doble de complejidad computacional. [una]

Texto original (inglés)[ mostrarocultar]

Presentamos un conjunto de estrategias y técnicas correspondientes que se pueden usar para eliminar algunos obstáculos importantes en la búsqueda de colisiones para SHA-1. En primer lugar, buscamos una ruta diferencial cercana a la colisión que tenga un peso de Hamming bajo en el "vector de perturbación", donde cada bit representa una colisión local de 6 pasos. En segundo lugar, ajustamos adecuadamente la trayectoria diferencial en la primera ronda a otra trayectoria diferencial posible para evitar colisiones locales consecutivas imposibles y colisiones locales truncadas. En tercer lugar, transformamos dos caminos diferenciales de casi colisión de un bloque en un camino diferencial de colisión de dos bloques con el doble de complejidad de búsqueda.

También afirman:

En particular, nuestro análisis se basa en el ataque diferencial original en SHA-0, el ataque de "casi colisión" en SHA-0, la técnica de bloques múltiples y la técnica de modificación de mensaje original utilizada en los ataques de búsqueda de colisión en HAVAL : 128, MD4 , RIPEMD y MD5 .

Texto original (inglés)[ mostrarocultar]

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 de bloques múltiples, así como las técnicas de modificación de mensajes utilizadas en los ataques de búsqueda de colisión en HAVAL-128. , MD4, RIPEMD y MD5.

Un artículo que describe el algoritmo fue publicado en agosto de 2005 en la conferencia CRYPTO .

En el mismo artículo, los autores publicaron un ataque a SHA-1 truncado (58 rondas), que permite encontrar colisiones en 233 operaciones.

En agosto de 2005, en CRYPTO 2005, los mismos expertos presentaron una versión mejorada del ataque al SHA-1 completo, con una complejidad computacional de 263 operaciones. En diciembre de 2007, Martin Cochran revisó los detalles de esta mejora.

Christophe de Kanier y Christian Rechberg presentaron más tarde un ataque mejorado contra SHA-1, por el que recibieron el premio al mejor artículo en la conferencia ASIACRYPT de 2006 . Presentaron una colisión de dos bloques en un algoritmo de 64 rondas con una complejidad computacional de alrededor de 2 35 operaciones. [2]

Existe un proyecto de investigación a gran escala que se inició en la Universidad Tecnológica de la ciudad austriaca de Graz , que: “... utiliza computadoras conectadas a través de Internet para realizar investigaciones en el campo del criptoanálisis. Puedes participar en el proyecto descargando y ejecutando el programa gratuito en tu computadora". [3]

Burt Kalinske , jefe de investigación del " laboratorio RSA ", predice que el primer ataque de preimagen tendrá éxito en los próximos 5 a 10 años.

Dado que los ataques teóricos a SHA-1 han tenido éxito, el NIST planea eliminar por completo el uso de SHA-1 en las firmas digitales. [cuatro]

Debido a la estructura iterativa y de bloques de los algoritmos, así como a la falta de un procesamiento especial al final del hash, todas las funciones hash de la familia SHA son vulnerables a ataques de alargamiento de mensajes y colisiones cuando se codifica parcialmente un mensaje. [5] Estos ataques permiten falsificar mensajes firmados solo con hash, o bien , alargando el mensaje y recalculando el hash sin conocer el valor de la clave. La solución más simple para protegerse contra estos ataques es duplicar hash - ( es un bloque de ceros de la misma longitud que el bloque de función hash). $SHA(mensaje || clave)$ $SHA(clave || mensaje )$ $SHA_d(mensaje) = SHA(SHA(0^b || mensaje))$ $0^b$

El 2 de noviembre de 2007, NIST anunció un concurso para desarrollar un nuevo algoritmo SHA-3 que estuvo vigente hasta 2012 . [6]

Aceleración

El 8 de octubre de 2015, Marc Stevens, Pierre Karpman y Thomas Peyrin publicaron un ataque a la función de compresión del algoritmo SHA-1 que requiere solo 257 cálculos .

Hack real: SHAttered (detección de colisión)

El 23 de febrero de 2017, especialistas de Google y CWI anunciaron un truco práctico del algoritmo al publicar 2 archivos PDF con la misma suma de verificación SHA-1 . Esto requirió una búsqueda de opciones, lo que llevaría 110 años para 1 GPU [7] . ${\ estilo de visualización 9 \ veces 10 ^ {18}}$

Comparación de SHA-1 con otros algoritmos

Comparación con MD5

Tanto MD5 como SHA-1 son esencialmente extensiones mejoradas de MD4 .

similitudes:

Cuatro etapas.
Cada acción se suma al resultado obtenido anteriormente.
El tamaño del bloque de procesamiento es de 512 bits.
Ambos algoritmos realizan sumas módulo 2 32 y están diseñados para arquitectura de 32 bits.

Diferencias:

En SHA-1, se utiliza la misma función f en la cuarta etapa que en la segunda etapa.
En MD5 , cada acción utiliza una constante incremental única. En SHA-1, las constantes se reutilizan para cada uno de los cuatro grupos.
Se ha agregado una quinta variable a SHA-1.
SHA-1 utiliza un código de corrección de errores cíclico .
En MD5 , los cuatro desplazamientos utilizados en cada paso son diferentes de los valores utilizados en los pasos anteriores. En SHA , se utiliza un valor de cambio constante en cada etapa.
En MD5 hay cuatro funciones lógicas elementales diferentes, en SHA-1 hay tres.
En MD5 , la longitud del resumen es de 128 bits, en SHA-1 es de 160 bits.
SHA-1 contiene más rondas (80 en lugar de 64) y se ejecuta en un búfer de 160 bits en comparación con el búfer de 128 bits de MD5 . Por lo tanto, SHA-1 debería funcionar aproximadamente un 25 % más lento que MD5 en el mismo hardware.

Bruce Schneier concluye: “SHA-1 es MD4 con la adición de un elenco más amplio, un paso adicional y una avalancha mejorada. MD5 es MD4 con hash de bits mejorado, un paso adicional y avalancha mejorada".

Comparación con GOST R 34.11-94

Una serie de características distintivas de GOST R 34.11-94 :

Al procesar bloques, las transformaciones se utilizan de acuerdo con el algoritmo GOST 28147-89 ;
Se procesa un bloque de 256 bits y el valor de salida también tiene una longitud de 256 bits.
Se aplican medidas de búsqueda anticolisión basadas en la incompletitud del último bloque.
Los bloques se procesan de acuerdo con el algoritmo de cifrado GOST 28147-89 , que contiene transformaciones en S-boxes , lo que complica significativamente la aplicación del método de criptoanálisis diferencial para la búsqueda de colisiones del algoritmo GOST R 34.11-94 . Esta es una ventaja significativa en comparación con SHA-1.
La seguridad teórica de GOST R 34.11-94 es 2128 , que es muchas veces mayor que 280 para SHA-1.

Comparación con otros SHA

En la tabla, "tamaño de hash intermedio" significa "tamaño de suma de hash interno" después de cada iteración.

Variaciones de algoritmos		Tamaño de hash de salida (bits)	Tamaño de hash intermedio (bits)	Tamaño de bloque (bits)	Longitud máxima del mensaje de entrada (bits)	Tamaño de palabra (bits)	Número de rondas	Operaciones utilizadas	Colisiones encontradas
SHA-0		160	160	512	2 64 - 1	32	80	+, y, o, xor, rotl	Hay
SHA-1		160	160	512	2 64 - 1	32	80	+, y, o, xor, rotl	2 52 operaciones
SHA-2	SHA-256/224	256/224	256	512	2 64 - 1	32	64	+, y, o, xor, shr, rotr	No
SHA-2	SHA-512/384	512/384	512	1024	2 128 - 1	64	80	+, y, o, xor, shr, rotr	No

Uso

Las funciones hash se utilizan en sistemas de control de versiones, sistemas de firma electrónica y para crear códigos de autenticación .

SHA-1 es el más común de toda la SHA y se utiliza en una variedad de aplicaciones y algoritmos criptográficos ampliamente utilizados.

SHA-1 se utiliza en las siguientes aplicaciones:

S/MIME : resúmenes de mensajes.
SSL : resúmenes de mensajes.
IPSec : para el algoritmo de verificación de integridad en una conexión punto a punto.
SSH : para verificar la integridad de los datos transferidos.
PGP : para crear una firma digital electrónica.
Git : para identificar cada objeto mediante el hash SHA-1 a partir de la información almacenada en el objeto.
Mercurial - para identificar revisiones
BitTorrent : para verificar la integridad de los datos descargados.

SHA-1 es la base del cifrado de bloque SHACAL .

Descargo de responsabilidad

Google ha expresado durante mucho tiempo su desconfianza en SHA-1, especialmente por usar esta función para firmar certificados TLS . En 2014, poco después de la publicación del trabajo de Mark Stevens, el equipo de desarrollo de Chrome anunció que eliminarían SHA-1.

Desde el 25 de abril de 2016 Yandex . Mail ha dejado de admitir programas de correo más antiguos que usan SHA-1 [8] .

Notas

↑ Encontrar colisiones en el SHA-1 completo (inglés) (enlace descendente) . — Un artículo de investigadores chinos sobre el hack SHA-1. Archivado desde el original el 23 de agosto de 2011.
↑ Búsqueda de características de SHA-1 : resultados generales y aplicaciones . Consultado el 4 de octubre de 2017. Archivado desde el original el 26 de julio de 2008.
↑ SHA-1 Collision Search Graz (inglés) (enlace no disponible) . — Proyecto de investigación de la Universidad Tecnológica de Graz. Archivado desde el original el 7 de noviembre de 2008.
↑ Comentarios del NIST sobre ataques criptoanalíticos en SHA-1 ( enlace inaccesible) . — Comentario oficial del NIST sobre los ataques SHA-1. Archivado desde el original el 13 de octubre de 2012.
↑ Niels Ferguson, Bruce Schneier y Tadayoshi Kohno, Cryptography Engineering (inglés) (enlace no disponible) . Archivado desde el original el 13 de octubre de 2012. , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
↑ NIST Hash Competition (inglés) (enlace no disponible) . — Concurso para el desarrollo de SHA-3. Archivado desde el original el 13 de octubre de 2012.
↑ La primera forma de generar colisiones para SHA-1 . Consultado el 9 de marzo de 2017. Archivado desde el original el 10 de marzo de 2017. (indefinido)
↑ Actualización de programas de correo electrónico - Mail - Yandex.Help . yandex.ru. Consultado el 7 de abril de 2016. Archivado desde el original el 20 de abril de 2016. (indefinido)

Literatura

Schneier B. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 .
Nils Ferguson , Bruce Schneier . Criptografía Práctica = Criptografía Práctica: Diseño e Implementación de Sistemas Criptográficos Seguros. - M. : Dialéctica, 2004. - 432 p. - 3000 copias. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .

Enlaces

RFC 3174
Descripción general de SHA-1 del World Wide Web Consortium Archivado el 4 de marzo de 2005 en Wayback Machine .
SHA-1 Hack Archivado el 5 de mayo de 2017 en Wayback Machine .
Informe de hackeo SHA1
Bruce Schneier en SHA Hack Archivado desde el original el 1 de diciembre de 2012. (Inglés)
Consecuencias de los ataques SHA-1 exitosos Archivado el 26 de diciembre de 2008 en Wayback Machine .

Funciones hash
propósito general	Adler-32 CDN Suma de comprobación de Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Árbol de hachís picadillo de jenkins suma de hash
Criptográfico	Stribog GOST R 34.11-94 Cinturón BLAKE BMW CubeHash ECO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna Hachís de LM luffa MD2 MD4 MD5 MD6 N-hachís RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD RÁPIDO Piel Snefru Tigre Torbellino
Funciones de generación de claves	cripta PBKDF2 cripta Argón2 Lyra2
Número de cheque ( comparación )	Suma de verificación Algoritmo de Verhouff Algoritmo lunar Maldito algoritmo Código de barras cuentas bancarias tarjetas bancarias ES EN SNILES OKPO ESTAÑO OKATO ISBN OGRN y OGRNIP VIN
Hachís	Comparación de números de cheque Protocolos de autenticación Comparación de códigos de barras Criptografía Enlace magnético firma Merkle ed2k URNA