Función hash criptográfica

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 11 de mayo de 2019; las comprobaciones requieren 58 ediciones .

Las funciones hash criptográficas son una clase distinta de funciones hash que tienen ciertas propiedades que las hacen adecuadas para su uso en criptografía .

Principios de construcción

Circuito Secuencial Iterativo

En el caso general, la construcción de una función hash se basa en un esquema secuencial iterativo. El núcleo del algoritmo es una función de compresión : convertir k entrada en n bits de salida, donde n es la longitud de la función hash y k es un número arbitrario mayor que n . En este caso, la función de compresión debe cumplir todas las condiciones de fuerza criptográfica .

El flujo de entrada se divide en bloques de ( k − n ) bits. El algoritmo utiliza una variable temporal de tamaño n bits, cuyo valor inicial es un número conocido. Cada siguiente bloque de datos se combina con el valor de salida de la función de reducción en la iteración anterior. El valor de la función hash es la salida n bits de la última iteración. Cada bit del valor de salida de una función hash depende de todo el flujo de datos de entrada y del valor inicial. Así, se consigue un efecto de avalancha .

Cuando se diseñan funciones hash basadas en un esquema iterativo, existe un problema con el tamaño del flujo de datos de entrada. El tamaño del flujo de datos de entrada debe ser un múltiplo de ( k − n ) . Como regla general, antes del inicio del algoritmo, los datos se expanden de alguna manera conocida de antemano.

Además de los algoritmos de paso único, existen algoritmos de paso múltiple en los que se mejora aún más el efecto de avalancha. En este caso, los datos primero se repiten y luego se expanden al tamaño requerido.

Función de contracción basada en el algoritmo de bloques simétricos

El algoritmo de cifrado de bloque simétrico se puede utilizar como una función de compresión . Para garantizar una mayor seguridad, puede utilizar el bloque de datos destinado al hash en esta iteración como clave y el resultado de la función de compresión anterior como entrada. Luego, el resultado de la última iteración será la salida del algoritmo. En tal caso, la seguridad de la función hash se basa en la seguridad del algoritmo utilizado.

Por lo general, cuando se construye una función hash, se usa un sistema más complejo. El esquema generalizado del algoritmo de cifrado de bloques simétricos se muestra en la Fig. 2.

Por lo tanto, tenemos 64 opciones para construir una función de contracción. La mayoría de ellos son triviales o inseguros. A continuación se muestran los cuatro esquemas más seguros para todo tipo de ataques.

La principal desventaja de las funciones hash diseñadas sobre la base de algoritmos de bloque es su baja velocidad. La fuerza criptográfica necesaria también se puede lograr en un número menor de operaciones en los datos de entrada. Existen algoritmos hash más rápidos diseñados por usted mismo, desde cero, basados en los requisitos de fortaleza criptográfica. Los más comunes son MD5 , SHA-1 , SHA-2 .

Requisitos

Los requisitos para las funciones hash criptográficas son:

1. Primera resistencia a la búsqueda de preimagen : Dado un hash , debería ser difícil encontrar cualquier mensaje tal que Esta propiedad está relacionada con la noción de una función unidireccional . Las funciones que carecen de esta propiedad son vulnerables a los primeros ataques de preimagen . $h$ $metro$ $h=hash(m)$

2. Resistencia a la búsqueda de la segunda preimagen : dado un mensaje , debería ser difícil encontrar otro mensaje (que no sea igual a ) tal que . Esta propiedad a veces se denomina resistencia a la colisión débil. Las funciones que carecen de esta propiedad son vulnerables a los segundos ataques de búsqueda de preimagen. $m_1$ $m_2$ $m_1$ $hash(m_{1})=hash(m_{2})$

3. Resistencia a colisiones

Una colisión de función hash es un par de valores y ′, ′ para los cuales . Dado que la cantidad de posibles textos sin formato es mayor que la cantidad de posibles valores de la convolución, entonces para alguna convolución hay muchas preimágenes y, por lo tanto, necesariamente existen colisiones para las funciones hash. Por ejemplo, deje que la longitud de la preimagen hash sea de 6 bits, la longitud de la convolución sea de 4 bits. Entonces el número de pliegues diferentes es , y el número de preimágenes hash es , es decir, 4 veces más, lo que significa que al menos uno de todos los pliegues corresponde a 4 preimágenes. $metro$ $metro$ ${\ estilo de visualización m \ neq m}$ $H(m)=H(m')$ ${\ estilo de visualización 2 ^ {4} = 16}$ $2^6=64$

La resistencia de una función hash a las colisiones significa que no existe un algoritmo polinomial eficiente para encontrar colisiones.

Estas propiedades no son independientes:

Una función invertible es inestable a la restauración de la segunda preimagen y las colisiones.
Una función que no es resistente a la restauración de la segunda preimagen no es resistente a las colisiones; Lo opuesto no es verdad.
La función es resistente a la colisión, resistente a la segunda preimagen.
Una función hash resistente a colisiones no es necesariamente unidireccional.

Es importante para la criptografía que los valores hash cambien mucho con el más mínimo cambio en el argumento ( efecto avalancha ). El valor hash no debe filtrar información ni siquiera sobre bits individuales del argumento.

Al desarrollar el estándar ruso moderno GOST R 34.11-2012 (Stribog) , se formularon los siguientes requisitos para las funciones hash criptográficas:

Dificultad para calcular la preimagen: si se conoce el valor de la función, entonces debería ser difícil encontrar dicho mensaje, cuya función hash es igual a la conocida;
Seguridad del cálculo de la segunda preimagen: que haya un valor, y se conoce el código hash de este valor. Entonces debería ser difícil para un atacante encontrar otro valor similar para que su función hash coincida con la función hash del primer valor;
Dificultad para encontrar colisiones: debería ser difícil encontrar dos mensajes de este tipo que no sean iguales, pero que tengan los mismos códigos hash;
Resistencia al alargamiento de preimagen: si un atacante no conoce el mensaje, pero conoce su longitud y el código hash de él, entonces debería ser difícil para él captar un mensaje que, cuando se agrega al original, dará alguna función hash conocida. . En otras palabras, no debería ser posible que un atacante cambie algo agregando algo al mensaje mientras da a conocer el resultado. Esto se puede decir de otra manera: la función hash no necesita estar bien "rellenada".

4. Pseudoaleatoriedad : debería ser difícil distinguir un generador de números pseudoaleatorios basado en hash de un generador de números aleatorios, por ejemplo, pasa las pruebas habituales de aleatoriedad .

Funciones hash demostrablemente seguras

La seguridad de una función hash puede garantizarse por la complejidad de algún problema matemático, siempre que exista evidencia de que los ataques dirigidos a violar los requisitos para ello son tan difíciles como la solución de este problema. [una]

Se puede demostrar que una función hash criptográfica es a prueba de colisiones si el problema de encontrar colisiones puede mediarse en tiempo polinomial a partir de un problema que se considera irresoluble en tiempo polinomial . En otras palabras, si el algoritmo permitiría resolver el problema de encontrar colisiones en tiempo polinomial si existe un algoritmo reductor que también trabaja en tiempo polinomial, entonces este último permitiría al algoritmo resolver el problema en tiempo polinomial, lo que contradice su complejidad. , lo que significa que el problema de encontrar colisiones no es más fácil que la tarea . $PAGS$ $A$ $R$ $A$ $PAGS$ $PAGS$

La seguridad demostrable frente a la búsqueda de la primera y la segunda preimágenes se define de manera similar.

La resistencia a la búsqueda de la segunda preimagen se deriva de la resistencia probada a las colisiones, por lo tanto, en la práctica, a veces, solo se prueban teóricamente la resistencia a encontrar la primera preimagen y la resistencia a las colisiones. [2]

Algunos problemas que se supone que no tienen solución en tiempo polinomial, que se pueden usar para construir tales funciones:

Desventajas del enfoque basado en la evidencia

En presencia de garantías teóricas de complejidad, el enfoque basado en la evidencia también tiene importantes inconvenientes:

Los actuales algoritmos hash demostrablemente seguros son demasiado complejos desde el punto de vista computacional para ser utilizados en la práctica. En comparación con las funciones hash normales, son bastante lentas.
La creación de funciones hash demostrablemente seguras requiere mucho más tiempo que los enfoques clásicos.
La prueba de seguridad en sí misma a menudo se basa en un problema que tiene la complejidad requerida promedio o en el peor de los casos. La complejidad del peor de los casos suele describir situaciones patológicas en lugar de las típicas de la tarea. Incluso la reducción a un problema con complejidad en promedio proporciona una seguridad limitada, ya que se puede encontrar un algoritmo que resuelva fácilmente el problema para un cierto subconjunto de datos del problema. Así, por ejemplo, se demostró que para dos de los tres parámetros propuestos en el artículo original para la función hash Fast Syndrome-Based , existen más ataques óptimos que los propuestos por los creadores para probar la seguridad. [3]

SWIFFT es un ejemplo de una función hash que elude un poco el problema de seguridad descrito. Se puede demostrar que para cualquier algoritmo que rompa SWIFFT con probabilidad en el tiempo, existe un algoritmo que resuelve cierto problema matemático en el peor de los casos en el tiempo dependiendo de y . [cuatro] $PAGS$ $T$ $T'$ $PAGS$ $T$

Ejemplos de funciones hash comprobablemente seguras

VSH (función Very Smooth Hash ) es una función resistente a colisiones demostrablemente segura que se basa en la dificultad de encontrar raíces cuadradas no triviales módulo un número compuesto n (que es tan difícil como factorizar n ).
MuHASH
ECOH - Elliptic curve only hash - función hash basada en la idea de curvas elípticas , problema de suma de subconjuntos y suma de polinomios. La prueba de seguridad se basó en la suposición de la integridad NP del problema matemático subyacente, pero se encontró una vulnerabilidad para el ataque generalizado de "cumpleaños" de Wagner relacionado con la búsqueda de la segunda preimagen. [5]
FSB - Función hash rápida basada en el síndrome : se puede demostrar que romper el FSB es al menos tan difícil como resolver el problema NP-completo conocido como decodificación del síndrome regular. [6]
SWIFFT : SWIFFT se basa en FFT y es probablemente seguro bajo una suposición bastante débil sobre la dificultad en el peor de los casos de encontrar vectores cortos en una red cíclica/ideal. [7]
Chaum, van Heijst, función hash de Pfitzmann : una función en la que encontrar colisiones es tan laborioso como encontrar un logaritmo discreto en un grupo finito . $F_{2p+1}$
Las funciones hash basadas en mochila son una familia de funciones hash basadas en el problema de la mochila .
Existe un enfoque general para construir algoritmos de hashing comprobablemente seguros basados en cualquier protocolo sigma adecuado . De esta forma se puede obtener una versión más rápida de VSH (llamada VSH*).

La función hash criptográfica ideal

Una función hash criptográfica ideal es una función hash criptográfica que tiene cinco propiedades básicas:

determinismo . Con los mismos datos de entrada, el resultado de la función hash será el mismo (el mismo mensaje siempre conduce al mismo hash);
Cálculo de alta velocidad del valor hash para cualquier mensaje dado;
La incapacidad de generar un mensaje a partir de su valor hash, con la excepción de intentar crear todos los mensajes posibles;
Efecto avalancha. Un pequeño cambio en los mensajes debería cambiar los valores de hash tan ampliamente que los nuevos valores de hash no coincidan con los valores de hash anteriores;
La incapacidad de encontrar dos mensajes diferentes con el mismo valor hash.

Por lo tanto, una función hash criptográfica ideal, que tiene una longitud n (es decir, la salida es de n bits), debe requerir al menos operaciones para calcular la preimagen. $2^{n}$

Un atacante buscará una preimagen para una función hash ideal de la siguiente manera: tiene un número h y necesita encontrar m tal que H(m) = h. Si esta es una función hash ideal, entonces el atacante solo puede pasar por todos los M posibles y verificar a qué equivale la función hash de este mensaje. El resultado del cálculo, si m se itera completamente, es de hecho un número aleatorio. Si el número h se encuentra en el rango de 0 a , entonces, en promedio, el atacante pasará iteraciones buscando el h deseado. Por lo tanto, el cálculo de la preimagen requerirá la mitad de iteraciones que en el caso ideal. $2^{n}$ $2^{{n-1}}$

Queda el cálculo de la segunda preimagen . En la búsqueda de colisiones, la puntuación dará , y este no es un resultado del todo exacto. Esta evaluación proviene de una evaluación de la llamada " Paradoja del cumpleaños ". $2^{n}$ $2^{n}$

Si un atacante quiere escribir un programa para encontrar colisiones, sería óptimo para él obtener primero un diccionario de colisiones. En consecuencia, luego calcula la función hash del siguiente mensaje y verifica si esta función hash pertenece al siguiente mensaje o no. Si es así, entonces se encuentra la colisión y luego el mensaje original con el código hash dado se puede encontrar en el diccionario. Si no, entonces repone el diccionario. En la práctica, este método no está implementado porque no habría suficiente memoria para dicho diccionario.

Ataque de cumpleaños

El ataque de cumpleaños es el nombre utilizado en el criptoanálisis para un método de detección de colisiones de funciones hash basado en la paradoja del cumpleaños. La esencia de la paradoja es que en un grupo de 23 o más personas, la probabilidad de coincidencia de cumpleaños (día y mes) de al menos dos personas supera el 50%. Por ejemplo, si hay 23 o más estudiantes en una clase, entonces es más probable que el cumpleaños de uno de los compañeros de clase caiga el mismo día que que todos tengan su propio cumpleaños único.

Efecto Avalancha

Consideremos este efecto y su papel en el ejemplo del proceso de hashing de blockchain. Esta propiedad significa que si hacemos pequeños cambios en la cadena de entrada, los hash (es decir, la salida de la función criptográfica) serán drásticamente diferentes entre sí. Verifiquemos esta propiedad en un ejemplo simple. Considere, por ejemplo, el resultado de una función hash de la familia MD - MD5. En la entrada, proporcionaremos valores que diferirán solo en el caso de los primeros caracteres: las cadenas son casi idénticas. Sin embargo, sus hashes (el resultado de la función hash) son diferentes.

Un ejemplo de cómo funciona el algoritmo de encriptación MD5
Aporte	Producción
bitcoin	0xCD5B1E4947E304476C788CD474FB579A
bitcoin	0xD023EC040F79F1A9B2AC960B43785089

"Alta entropía"

Las buenas funciones hash tienen la propiedad "Alta entropía ". Esto significa que los hash de las matrices de datos deben distribuirse al máximo en el sistema durante el proceso de hash, es decir, deben tener una alta entropía en el sentido de información. Como saben, la entropía en el sentido de información es una medida de la incertidumbre de un determinado sistema, en particular, la imprevisibilidad de la aparición de un símbolo.

Entonces, por ejemplo, considere la ecuación , donde es la concatenación de una cadena y una cadena , y es una función hash criptográfica. Si el valor tiene un índice de entropía alto, será casi imposible encontrar un valor que satisfaga la ecuación. $SALIDA=H(K|ENTRADA)$ $K|ENTRADA$ $k$ $ENTRADA$ $H$ $k$ $ENTRADA$

El término "Alta entropía" en el contexto de las funciones hash significa un estado en el que se elige un valor de una gama tan amplia de opciones posibles que los intentos de adivinar por selección aleatoria no tienen posibilidad de éxito. Por ejemplo, un número que está entre 1 y 10 tiene una entropía baja, mientras que un número que está entre 1 y , por el contrario, tiene una entropía alta. $2^{256}$

Familia de funciones hash MD y SHA

Hasta la fecha, la gran mayoría de las aplicaciones de funciones hash están "tomadas" por los algoritmos MD5 , SHA-1 , SHA-256 , y en Rusia , también GOST R 34.11-2012 (Stribog) . Por supuesto, hay muchos otros algoritmos que son menos conocidos o comunes solo en comunidades estrechas (por ejemplo, RIPEMD , TIGER , Panamá , etc.), sin embargo, estos algoritmos no son tan comunes. A continuación se muestra un análisis de las funciones hash MD4 , que fue el antecesor de MD5, así como de la función hash SHA.

Tipo de	Descripción
MD4	La más rápida, optimizada para máquinas de 32 bits entre la familia de funciones MD. Una función hash desarrollada por el profesor de la Universidad de Massachusetts Ronald Rivest en 1990 y descrita por primera vez en RFC 1186. Contiene tres bucles de 16 pasos cada uno. En 1993, se describió el algoritmo de craqueo MD4, por lo que hoy en día no se recomienda el uso de esta función con aplicaciones reales.
MD5	La más común de la familia de funciones MD. Similar a MD4, pero las mejoras de seguridad lo hacen un 33 % más lento que MD4. Contiene cuatro ciclos de 16 pasos cada uno. Proporciona control de integridad de datos. Los primeros intentos exitosos de descifrar esta función hash se remontan a 1993: los investigadores Bert den Boer y Anton Bossilaris demostraron que las pseudocolisiones son posibles en el algoritmo. En 1996, Hans Dobbertin mostró la posibilidad de colisiones y describió teóricamente el algoritmo de piratería. El 24 de agosto de 2004, cuatro investigadores independientes, Wang Xiaoyun, Feng Dengguo, Lai Xuejia y Yu Hongbo, descubrieron una vulnerabilidad de algoritmo que permite encontrar colisiones mediante un método analítico en un tiempo más o menos aceptable. En 2005, Vlastimil Klima publicó un algoritmo para detectar colisiones en pocas horas. El 18 de marzo de 2006, un investigador publicó un algoritmo que encuentra colisiones en un minuto, que luego se denominó "túnel". A partir de hoy, no se recomienda el uso de MD5 en aplicaciones del mundo real.
SHA-1 (Seguro Picadillo Algoritmo 1)	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. SHA-1 crea un valor de 160 bits, también llamado resumen de mensaje. Contiene cuatro etapas. Tanto MD5 como SHA-1 son esencialmente extensiones mejoradas de MD4. Diferencias: En SHA-1, la cuarta etapa utiliza la misma función que 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. MD5 tiene cuatro funciones booleanas elementales diferentes, mientras que SHA-1 tiene 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.
SHA-2	Una familia de algoritmos criptográficos: funciones hash, incluidos los algoritmos SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 y SHA-512/224. En 2003, Gilbert y Handschuh realizaron un estudio sobre SHA-2 , pero no encontraron ninguna vulnerabilidad. Sin embargo, en marzo de 2008, los investigadores indios Somitra Kumar Sanadiya y Palash Sarkar publicaron las colisiones que encontraron para 22 iteraciones de SHA-256 y SHA-512. En septiembre del mismo año, presentaron un método para construir colisiones para versiones truncadas de SHA-2 (21 iteraciones). Los estudios han demostrado [8] que los algoritmos SHA-2 funcionan de 2 a 3 veces más lento que los algoritmos hash MD5 , SHA-1 .
SHA-256	Por separado, destaca el algoritmo SHA-256, que se utiliza en algoritmos de hash para bitcoin y otras criptomonedas. Como implica el nombre de la función hash criptográfica, el hash de salida tiene una longitud de 256 bits, la entropía correspondiente se puede definir como un conjunto de valores de 1 a 2 elevado a 256: una gran cantidad de valores, lo que hace que el cracking y el descifrado es un proceso extremadamente laborioso basado en la enumeración secuencial.
SHA-3 ( Keccak )	La función hash SHA-3 (también llamada Keccak) es una función de bit variable desarrollada por un grupo de autores liderado por Joan Dymen . El 2 de octubre de 2012, Keccak se convirtió en el ganador de la competencia de algoritmos criptográficos realizada por el Instituto Nacional de Estándares y Tecnología de EE. UU . [9] . El 5 de agosto de 2015, el algoritmo de función fue aprobado y publicado como estándar FIPS 202 [10] [11] . El algoritmo de la función SHA-3 se basa en el principio de una esponja criptográfica .

Aplicaciones

Firma electrónica

Para asegurarse de que el mensaje fue enviado por un remitente específico, junto con el mensaje se transmite una llamada firma electrónica. El destinatario verifica si la firma electrónica realmente pertenece al mensaje dado.

Debido a que el uso de la criptografía con claves públicas (firma, verificación de firmas, etc.) es un proceso muy lento, además, si firma el mensaje completo, el tamaño de esta firma será comparable al tamaño del mensaje, no firme el mensaje y una función hash del mensaje. Y luego el destinatario, al descifrar la firma, recibe una función hash. A continuación, compara la función hash del mensaje que recibió y la función hash que se obtuvo como resultado del descifrado. Debido al hecho de que la función hash tiene una longitud fija, es más pequeña que el mensaje en sí. Esto le permite calcular rápidamente la firma digital. El tamaño de esta firma será pequeño en comparación con el tamaño del mensaje.

Verificación de frase de contraseña

En la mayoría de los casos, las frases de contraseña no se almacenan en los destinos, solo se almacenan sus valores hash. No es recomendable almacenar frases de contraseña, porque en caso de acceso no autorizado a un archivo con frases, un atacante conocerá todas las frases de contraseña y podrá usarlas de inmediato, y al almacenar valores hash, aprenderá solo valores hash. que no son reversibles a los datos originales, en este caso, en una frase de contraseña. Durante el procedimiento de autenticación, el valor hash de la frase de contraseña ingresada se calcula y se compara con la almacenada.

Ejemplos en este caso son GNU/Linux y Microsoft Windows XP . Almacenan solo valores hash de frases de contraseña de cuentas de usuario .

Este sistema implica la transmisión de un mensaje por un canal seguro, es decir, un canal desde el cual es imposible que un criptoanalista intercepte mensajes o envíe los suyos propios. De lo contrario, puede interceptar la frase de contraseña y usarla para una autenticación ilegal adicional. Puede protegerse de tales ataques utilizando el método de desafío-respuesta .

Permita que un cliente con nombre se autentique con una frase de contraseña, pase , a un servidor. El servidor almacena el valor hash H ( pass , R 2 ) , donde R 2 es un número preseleccionado pseudoaleatorio. El cliente envía una solicitud ( nombre , R 1 ), donde R 1 es un pseudoaleatorio, cada vez un nuevo número. En respuesta, el servidor envía el valor R 2 . El cliente calcula el valor hash H ( R 1 , H ( pass , R 2 )) y lo envía al servidor. El servidor también calcula el valor H ( R 1 , H ( pass , R 2 )) y lo compara con el recibido. Si los valores coinciden, la autenticación es correcta.

En tal situación, la contraseña no se almacena abiertamente en el servidor, e incluso después de interceptar todos los mensajes entre el cliente y el servidor, el criptoanalista no puede recuperar la contraseña y el valor hash transmitido es diferente cada vez.

Hash de Bitcoin

Las transacciones del sistema de pago de Bitcoin , que se presentan como una determinada matriz de datos, se combinan en bloques (en adelante, la totalidad de todos los bloques se denominará cadena de bloques ) y pasan por un algoritmo hash, es decir, sus datos de campo se alimentan a la entrada de una función hash criptográfica. Cada transacción indica de dónde se cargan los fondos y adónde van. Para especificar el destinatario, se utiliza su clave pública (un identificador único en la red bitcoin). Para que el destinatario utilice el dinero recibido dentro del protocolo bitcoin (excluimos la venta de su propia billetera - Wallet), debe crear una nueva transacción que tomará la moneda de la anterior y la redirigirá a otra dirección utilizando el Llave pública. En consecuencia, la nueva transacción, junto con las transacciones de otros usuarios de la red bitcoin, caerá en un nuevo bloque. Por lo tanto, crece la cantidad de bloques en la cadena de bloques. Sin embargo, cada transacción debe ser aprobada; el sistema debe llegar a un consenso. Hay varias formas de hacer esto, pero Bitcoin usa el principio de Prueba de trabajo (PoW). Una vez que se acepta la transacción, se considera real y la criptomoneda se mueve de una billetera a otra.

El sistema Bitcoin es un sistema descentralizado sin centros de generación de bloques dedicados. Cada participante puede tomar un conjunto de transacciones que esperan ser registradas y formar un nuevo bloque. Además, en sistemas como BitCoin, dicho participante (minero) también recibirá una bonificación en forma de una cierta cantidad o comisión de las transacciones aceptadas en el bloque.

Pero no puede simplemente tomar y formar un bloque en sistemas descentralizados. El sistema debe llegar a un consenso, es decir, obtener la aprobación. Hay varias formas de hacer esto, pero Bitcoin usa el principio de Prueba de trabajo (PoW). La confiabilidad de tales sistemas se basa precisamente en el hecho de que un nuevo bloque no se puede formar más rápido (en promedio) que en un tiempo determinado. Por ejemplo, en 10 minutos (BitCoin).

La estructura de bloques de la cadena de bloques de BitCoin

campo	Descripción	Talla
Magia sin	valor siempre 0xD9B4BEF9	4 bytes
tamaño de bloque	número de bytes que siguen hasta el final del bloque	4 bytes
cabeza de bloque	compuesto por 6 elementos	80 bytes
contador de transacciones	entero positivo	1-4 bytes
actas	la lista <no vacía> de transacciones	<Contador de transacciones> - muchas transacciones

La estructura Blockheader en el bloque Blockchain de BitCoin

campo	Objetivo	Actualizar cuando...	Talla
versión	número de versión del bloque	Actualiza el software y especifica una nueva versión	cuatro
hashAnteriorBloquear	Hash de 256 bits del encabezado del bloque anterior	Entra un nuevo bloque	32
hashMerkelRaíz	Hash de 256 bits basado en todas las transacciones en el bloque	Se acepta una transacción	32
Tiempo	marca de tiempo actual en segundos desde 1970-01-01 T00:00 UTC	Cada pocos segundos	cuatro
pedacitos	objetivo actual en formato compacto	La dificultad se ajusta	cuatro
mientras tanto	Número de 32 bits (comienza en 0)	Un hash está cansado (incrementos)	cuatro

La dificultad es el número de ceros que habrá al comienzo del número de destino .

target es el número que el hash del bloque debe ser menor que para que el bloque se considere válido. El objetivo o, más precisamente, la dificultad depende de la potencia actual de la red y debe cambiar la dificultad cada n (en la red BitCoin - 2016) bloques, de modo que se genere un bloque cada 10 minutos. Supongamos que se generan 2016 bloques en la red, y cada cliente verifica cuánto tiempo se creó cada bloque. Si este tiempo es mayor al calculado, es decir, más de 10 minutos, entonces la complejidad disminuye.

nonce es un número aleatorio que los mineros deben recoger para hacer un bloque.

La estructura de la estructura de datos de bitcoin

Como se mencionó anteriormente, un conjunto de transacciones de Bitcoin se representan como bloques de datos conectados: blockchain . La estructura del dispositivo de la propia cadena de bloques se presenta como una lista enlazada con punteros.

Cada bloque tiene un puntero que contiene un enlace al bloque de datos anterior. Así, para ir a n + 1 bloques, es necesario seguir los punteros de los n bloques anteriores. En consecuencia, los punteros agregan la dirección de un nuevo bloque solo después de que el bloque de datos original haya pasado por el algoritmo hash de bitcoin; esto le permite hacer que la conexión sea confiable y segura.

Es menos probable que un sistema de este tipo sea atacado por intrusos que intenten cambiar los datos en la cadena de bloques, por ejemplo, para realizar su propia transacción en la dirección elegida. Como ya se mencionó, el hash de cada bloque en la cadena de bloques no solo depende de su propio contenido, sino también del contenido del bloque anterior. Por lo tanto, cualquier cambio en los datos del bloque original implica un cambio en los datos de otros bloques. Esto garantiza la inmutabilidad de la cadena de bloques y la seguridad del sistema, ya que es extremadamente difícil “falsificar” la cadena de bloques. Sin embargo, debe tenerse en cuenta que el hash de cada bloque debe ser único, de lo contrario, será imposible rastrear los intentos de ataque.

árbol Merkle

Todas las transacciones se representan como cadenas en formato hexadecimal, que se codifican para obtener ID de transacciones. En base a ellos, se construye un hash de bloque, que es tenido en cuenta por el bloque posterior, asegurando inmutabilidad y coherencia. Se recopila un valor hash de un solo bloque mediante un árbol de Merkle .

Un árbol de Merkle es un árbol binario completo , cuyos vértices de hojas contienen hashes de transacciones, y los vértices internos contienen hashes de agregar valores en vértices secundarios, y el nodo raíz del árbol (Top Hash) contiene un hash del conjunto completo de datos.

La construcción del árbol de Merkle para la cadena de bloques de bitcoin es la siguiente:

$H(L_{i})$ - el resultado de la función hash de la transacción $L_{yo}$

Se calculan los hash de las transacciones colocadas en bloques: H(L1), H(L2), H(L3) y así sucesivamente.
Los hashes se calculan a partir de la suma de los hashes de las transacciones, por ejemplo, H(H(L1) + H(L2)). Dado que el árbol de Merkle es binario, el número de elementos en cada iteración debe ser par. Por lo tanto, si un bloque contiene un número impar de transacciones, este último se duplica y se suma a sí mismo: hash (H(L3) + H(L3)).
Además, los valores hash se calculan nuevamente a partir de la suma de los valores hash. El proceso se repite hasta que se obtiene un solo hash: la raíz del árbol Merkle. Es una prueba criptográfica de la integridad del bloque (es decir, que todas las transacciones están en el orden establecido). El valor de la raíz se fija en el encabezado del bloque.

Al mismo tiempo, cuando se gasta la transacción L1, por ejemplo, los datos sobre ella se pueden eliminar del bloque y solo se puede dejar su hash para la verificación del bloque. Cuando se gastan las transacciones L1 y L2, podemos eliminar sus hashes (Hash 0-0 y Hash 0-1), dejando solo Hash 0, nuevamente para fines de verificación de bloques. En el momento en que se utilizan todas las transacciones, se pueden eliminar todos los hashes, excepto el Top Hash, porque ya no se necesitará información sobre estas transacciones.

Por lo tanto, para obtener un hash para un nuevo bloque de cadena, es necesario tener en cuenta todos los hash de transacciones anteriores. Cambiar el hash de al menos uno de los bloques anteriores conducirá a un cambio en el hash del siguiente bloque, respectivamente, dicha transacción puede identificarse inmediatamente como no válida.

Minería de Bitcoin

La minería es el proceso de encontrar consenso sobre el principio de Prueba de trabajo: obtener la aprobación para crear un nuevo bloque. De hecho, en la red BitCoin, esto se reduce a contar el hash del bloque y compararlo con el número objetivo : si el hash es menor que el objetivo, se genera un nuevo bloque; de lo contrario, no lo es.

Los mineros aseguran el crecimiento continuo de la cadena de bloques. Para esto, se utiliza una gran potencia informática: cada minero contribuye a aumentar el hashrate total de bitcoin (potencia informática). La participación de la operación de hashing de bitcoin por parte de cada minero depende del indicador de hashrate total: cuanto mayor sea el hashrate total de la red, más trabajo computacional en menos tiempo debe realizar el minero para mantener el tamaño promedio de su recompensa minera.

El proceso de sustituir un nonce en una cadena continúa hasta que se encuentra la solución correcta. A veces, el número de intentos puede llegar a millones de veces. El minero que primero encuentra la solución correcta agrega el bloque a la cadena de bloques y recibe una recompensa por esto.

El proceso de selección de nonce se basa en el método de fuerza bruta . Por lo tanto, el equipo de minería genera continuamente cadenas aleatorias hasta que se encuentra el valor de nonce requerido .

Ejemplos de criptomonedas que utilizan la función hash SHA-256 para el cifrado

SHA-256 es un algoritmo clásico para criptomonedas: la criptomoneda principal, Bitcoin, se basa en él. En consecuencia, este algoritmo también se usa en bifurcaciones de Bitcoin: en Bitcoin Cash, Bitcoin SV. Al mismo tiempo, en Bitcoin Gold, los mineros usan una función criptográfica - Equihash

Además de ellos, SHA-256 también se utiliza en:

Steemit;
peercoin ;
NombreMoneda ;
Ocoin;
Zetacoin;
emercoin _

Además, el algoritmo SHA-256 se usa como subrutina en la criptomoneda Litecoin, y el algoritmo principal para minarlo es Scrypt.

Véase también

Notas

↑ Daniel Augot, Matthieu Finiasz, Nicolás Sendrier. Una función hash criptográfica rápida y demostrablemente segura . - 2003. - Nº 230 . - Pág. 3-4 . Archivado desde el original el 8 de diciembre de 2019.
↑ Daniel Augot, Matthieu Finiasz, Nicolás Sendrier. Una función hash criptográfica rápida y demostrablemente segura . - 2003. - Nº 230 . - S. 3 . Archivado desde el original el 8 de diciembre de 2019.
↑ Jean-Sebastien Coron, Antoine Joux. Criptoanálisis de una función hash criptográfica demostrablemente segura . - 2004. - Nº 013 . - S. 1.3 . Archivado desde el original el 7 de diciembre de 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Una propuesta modesta para Hashing FFT // Cifrado rápido de software. — Springer, Berlín, Heidelberg, 2008-02-10. — Pág. 65 . — ISBN 9783540710387 , 9783540710394 . -doi : 10.1007 / 978-3-540-71039-4_4 . Archivado desde el original el 8 de abril de 2019.
↑ Michael A. Halcrow, Niels Ferguson. Un segundo ataque previo a la imagen contra el hash de curva elíptica únicamente (ECOH) . - 2009. - Nº 168 . Archivado desde el original el 24 de diciembre de 2018.
↑ Daniel Augot, Matthieu Finiasz, Nicolás Sendrier. Una función hash criptográfica rápida y demostrablemente segura . - 2003. - Nº 230 . Archivado desde el original el 8 de diciembre de 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Una propuesta modesta para Hashing FFT // Cifrado rápido de software. — Springer, Berlín, Heidelberg, 2008-02-10. - Pág. 54-72 . — ISBN 9783540710387 , 9783540710394 . -doi : 10.1007 / 978-3-540-71039-4_4 . Archivado desde el original el 8 de abril de 2019.
↑ Comparación de velocidad de algoritmos criptográficos populares . www.cryptopp.com. Consultado el 22 de diciembre de 2017. Archivado desde el original el 2 de julio de 2017.
↑ Swenson, Gayle . NIST selecciona al ganador de la competencia Secure Hash Algorithm (SHA-3) (ing.) , NIST (2 de octubre de 2012). Archivado desde el original el 5 de octubre de 2012. Consultado el 23 de diciembre de 2017.
↑ Hernández, Pablo . NIST lanza SHA-3 Cryptographic Hash Standard , NIST ( 5 de agosto de 2015). Archivado desde el original el 24 de enero de 2018. Consultado el 23 de diciembre de 2017.
↑ Morris J. Dworkin. Estándar SHA-3: hash basado en permutación y funciones de salida extensible // Federal Inf. proceso. Estándares (NIST FIPS) - 202. - 2015-08-04. Archivado desde el original el 17 de septiembre de 2017.

Literatura

Bruce Schneier. Criptografía aplicada. Protocolos, algoritmos, textos fuente en lenguaje C. - M. : Triunfo, 2002. - ISBN 5-89392-055-4 .
Laponina O.R. Fundamentos criptográficos de seguridad . - M. : Universidad de Internet de Tecnologías de la Información - INTUIT.ru, 2004. - P. 320. - ISBN 5-9556-00020 -5.

Enlaces

Información sobre firma digital electrónica . (indefinido)
The Keccak Hash Function and the Sponge Construction as a Universal Crypto Primitive, pgpru.com, 2010-2013 (traducido de noekon.org)
El texto del estándar oficial GOST R 34.11-2012 en Wikisource

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