BLAKE (función hash)
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 7 de junio de 2019; las comprobaciones requieren 2 ediciones .BLAKE es una función hash criptográfica desarrollada por Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan.
Hay dos variantes de la función hash: BLAKE-256 y BLAKE-512.
Historia
Por primera vez, BLAKE se presentó en la competencia de algoritmos criptográficos, que fue realizada por el Instituto Nacional de Estándares y Tecnología de los EE . UU . ( NIST hash function competition , Russian SHA-3 (competition) ). BLAKE se convirtió en uno de los cinco finalistas del concurso ( finalistas ingleses ).
Seguridad
La función hash de BLAKE se construye a partir de tres componentes aprendidos previamente:
- El modo de iteración de HAIFA proporciona resistencia a los ataques de segunda clase
- la estructura interna del tubo ancho local proporciona protección contra colisiones
- el algoritmo de compresión para BLAKE es una versión modificada del cifrado de flujo ChaCha altamente paralelizable cuya seguridad ha sido revisada extensamente [1]
Rendimiento e implementación
Rendimiento en dos procesadores diferentes:
| UPC | Velocidad (ciclos/byte) | |
|---|---|---|
| BLAKE-256 | BLAKE-512 | |
| Intel Core i5-2400M (Puente de arena) | 7.49 | 5.64 |
| AMD FX-8120 (excavadora) | 11.83 | 6.88 |
Posibilidad de implementación en varios microcontroladores:
| microcontrolador | BLAKE-256 | BLAKE-512 | ||
|---|---|---|---|---|
| RAM (byte) | ROM (byte) | RAM (byte) | ROM (byte) | |
| Microcontrolador basado en Cortex-M3 (procesador de 32 bits) | 280 | 1320 | 516 | 1776 |
| Microcontrolador ATmega1284P (procesador de 8 bits) | 267 | 3434 | 525 | 6350 |
Rendimiento en FPGA ( eng. FPGA ):
En el FPGA Xilinx Virtex 5 , BLAKE-256 se implementa en 56 celdas y puede lograr un rendimiento de más de 160 Mbps, y BLAKE-512 se implementa en 108 celdas y a velocidades de hasta 270 Mbps.
Rendimiento ASIC :
A 180 nm ASIC , BLAKE-256 se puede implementar a 13,5 kGE. En un ASIC de 90 nm , BLAKE-256 se implementa a 38 kGE y puede lograr un rendimiento de 10 Gb/s, mientras que BLAKE-512 se implementa a 79 kGE y 15 Gb/s [2] .
Algoritmo
Como se mencionó anteriormente, la función hash de BLAKE se construye a partir de los tres componentes aprendidos anteriormente:
- Modo de iteración HAIFA
- estructura interna de tubería ancha local
- El algoritmo de compresión para BLAKE es una versión modificada del cifrado de flujo ChaCha altamente paralelizable cuya seguridad se ha analizado exhaustivamente. [una]
Considere el algoritmo BLAKE-256 [3]
BLAKE-256 opera con palabras de 32 bits y devuelve un hash de 32 bytes.
Constantes
Hay constantes iniciales, las llamadas. VALORES INICIALES (IV):
IV0 = 6A09E667 IV1 = BB67AE85 IV2 = 3C6EF372 IV3 = A54FF53A IV4 = 510E527F IV5 = 9B05688C IV6 = 1F83D9AB IV7 = 5BE0CD1916 constantes (primeros dígitos de pi):
do 0 = 243F6A88 do 1 = 85A308D3 c 2 = 13198A2E c 3 = 03707344 c 4 = A4093822 c 5 = 299F31D0 c 6 = 082EFA98 c 7 = EC4E6C89 c 8 = 452821E6 c 9 = 38D01377 c 10 = BE5466CF c 11 = 34E90C6C c 12 = C0AC29B7 c 13 = C97C50DD c 14 = 3F84D5B5 c 15 = B5470917permutaciones {0,…,15} (utilizadas en todas las funciones de BLAKE):
σ0 = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 = 14 10 4 8 9 15 13 6 1 12 0 2 11 7 5 3 σ 2 = 11 8 12 0 5 2 15 13 10 14 3 6 7 1 9 43 = 7 9 3 1 13 12 11 14 2 6 5 10 4 0 15 84 = 9 0 5 7 2 4 10 15 14 1 11 12 6 8 3 13 σ5 = 2 12 6 10 0 11 8 3 4 13 7 5 15 14 1 96 = 12 5 1 15 14 13 4 10 0 7 6 3 9 2 8 11 7 = 13 11 7 14 12 1 3 9 5 0 15 4 8 6 2 10 σ8 = 6 15 14 9 11 3 0 8 12 2 13 7 1 4 10 5 σ9 = 10 2 8 4 7 6 1 5 15 11 9 14 3 12 13 0Funciones de compresión
La función de compresión del algoritmo BLAKE-256 toma como entrada:
- Cadena de variables h = h 0 ,…,h 7 (8 palabras);
- Bloque de mensajes m = m 0 ,…,m 15 ;
- Sal valor s = s 0 ,…,s 3 ;
- Valor de contador t = t 0 ,t 1 .
Así, recibe 30 palabras como entrada (8+16+4+2=30, 30*4 = 120 bytes = 960 bits). La función de compresión devuelve solo el nuevo valor de las variables de la cadena: h' = h' 0 ,…,h' 7 . En lo que sigue, denotaremos h'=compress(h, m, s, t).
Inicialización
16 variables, v 0 ,…,v 15 , que describen el estado actual de v , se inicializan con valores iniciales dependiendo de los datos de entrada y se presentan como una matriz de 4×4 :
←
Función redonda
Después de inicializar el estado v , se inicia una serie de 14 rondas. Una ronda es una operación de estado que realiza cálculos divididos en los siguientes bloques:
G 0 (v 0 , v 4 , v 8 , v 12 ) G 1 (v 1 , v 5 , v 9 , v 13 ) G 2 (v 2 , v 6 , v 10 , v 14 ) G 3 (v 3 , v 7 , v 11 , v 15 ) G 4 (v 0 , v 5 , v 10 , v 15 ) G 5 (v 1 , v 6 , v 11 , v 12 ) G 6 (v 2 , v 7 , v 8 , v 13 ) G 7 (v 3 , v 4 , v 9 , v 14 )
en la ronda r, el bloque de cálculo funciona de la siguiente manera:
j ← σ r%10 [2×i] k ← σ r%10 [2×i+1] un ← un + segundo + ( metro j ⊕ c k ) re ← (d ⊕ un) >>> 16 c ← c + d b ← (b ⊕ c) >>> 12 un ← un + segundo + (m k ⊕ do j ) re ← (d ⊕ un) >>> 8 c ← c + d segundo ← (segundo ⊕ c) >>> 7
Los primeros cuatro bloques G 0 ,…,G 3 se pueden calcular en paralelo, ya que cada uno cambia su propia columna específica de variables de matriz de estado. Llamemos al procedimiento de cálculo G 0 ,…,G 3 paso de columna . De manera similar, G 4 ,…,G 7 se pueden calcular en paralelo , pero ellos, a su vez, cambian cada diagonal de la matriz de estado v . Por lo tanto, llamamos al procedimiento de cálculo G 4 ,…,G 7 paso diagonal . La posibilidad de computación paralela G i se presenta gráficamente.
En rondas con números r mayores a 9, se usa la permutación σ r%10 , por ejemplo, en la ronda 13, se usa σ 3 .
Último paso
Después de todas las rondas, el nuevo valor de las variables de la cadena h' 0 ,…,h' 7 se calcula a partir de las variables de la matriz de estado, las variables de entrada y de la sal :
h' 0 ← h 0 ⊕ s 0 ⊕ v 8 h' 1 ← h 1 ⊕ s 1 ⊕ v 9 h' 2 ← h 2 ⊕ s 2 ⊕ v 10 h' 3 ← h 3 ⊕ s 3 ⊕ v 11 h' 4 ← h 4 ⊕ s 4 ⊕ v 12 h' 5 ← h 5 ⊕ s 5 ⊕ v 13 h' 6 ← h 6 ⊕ s 6 ⊕ v 14 h' 7 ← h 7 ⊕ s 7 ⊕ v 15
Hashing de mensajes
Describamos el proceso de hash de un mensaje m de longitud l<2^64 bits. Primero, el mensaje se rellena con datos por un múltiplo de 512 bits (64 bytes) mediante la función de relleno , luego, bloque por bloque, es procesado por la función de compresión .
En la función de relleno , el mensaje se rellena primero con bits para que su longitud módulo 512 sea igual a 447: primero se añade 1, luego el número requerido de ceros. Después de eso, se agrega una representación más de 1 y 64 bits de la longitud del mensaje l desde el bit más significativo hasta el menos significativo. Así, la longitud del mensaje se convierte en un múltiplo de 512 [Comm. 1] . El relleno asegura que la longitud del mensaje se convierta en un múltiplo de 512 bits.
Para calcular el hash del mensaje, el resultado de la función de relleno se divide en bloques de 16 palabras m 0 ,…,m N-1 . Sea L i el número de bits del mensaje original en bloques m 0 ,…,m i , es decir, excluyendo aquellos bits que se agregaron en el procedimiento de relleno. Por ejemplo, si el mensaje tiene una longitud de 600 bits, luego del procedimiento de relleno tendrá una longitud de 1024 bits y se dividirá en dos bloques: m 0 y m 1 . Además , L 0 = 512, L 1 = 600. En algunos casos, el último bloque no contiene un poco del mensaje original. Por ejemplo, si el mensaje original tiene 1020 bits, como resultado del procedimiento de relleno, tendrá una longitud de 1536 bits y m 0 tendrá 512 bits del mensaje original, m 1 - 508 y m 2 - 0 Fije L 0 = 512, L 1 = 1020 y L 2 = 0. Es decir, la regla es la siguiente: si no hay bits del mensaje original en el último bloque, entonces ponga el contador L N-1 a 0. Esto garantiza que si i ≠ j , entonces L i ≠ L j . El valor de sal lo define el usuario o se establece en 0 si no se va a utilizar ( s 0 =s 1 =s 2 =s 3 =0 ). El hash del mensaje se calcula de esta manera:
h 0 ← VI para i=0,...,N-1 h i+1 ← comprimir(h i ,m i ,s,l i ) volver h N .El proceso hash se presenta visualmente en el diagrama de flujo:
El algoritmo de la versión de 64 bits de la función es idéntico: los valores de cambio son 32, 25, 16 y 11 respectivamente, el número de rondas aumenta a 16.
Diferencias con el algoritmo de cuarto de ronda de ChaCha
- Adición de constantes al mensaje.
- Cambió la dirección del cambio.
Hash de BLAKE
BLAKE-512("") = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B 628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8 BLAKE-512 (" El rápido zorro marrón salta sobre el perro perezoso ") = 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD 2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451BLAKE2
BLAKE2 (sitio web de BLAKE2 ) es una versión mejorada de BLAKE, uno de los cinco finalistas del concurso de funciones hash SHA-3 (principalmente rendimiento mejorado), presentado el 21 de diciembre de 2012. Desarrolladores: Jean-Philippe Aumasson , Samuel Neves , Zooko Wilcox-O'Hearn y Christian Winnerlein . Fue creado como una alternativa a MD5 y SHA-1 , que fueron muy utilizados en el pasado, en los que se encontraron vulnerabilidades.
Diferencias con BLAKE
En BLAKE2, a diferencia de BLAKE, no hay adición de constantes en la función de ronda. También se han cambiado las constantes de desplazamiento, se ha simplificado la suma, se ha añadido un bloque de parámetros, que se suma a los vectores de inicialización. Además, el número de rondas se ha reducido de 16 a 12 para la función BLAKE2b (análogo a BLAKE-512) y de 14 a 10 para BLAKE2s (análogo a BLAKE-256). Como resultado, el número de ciclos por bit se redujo de 7,49 para BLAKE-256 y 5,64 para BLAKE-512 a 5,34 y 3,32 para Blake2s y Blake2b, respectivamente.
Hash de BLAKE2
BLAKE2b-512("") = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419 D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE BLAKE2b-512 (" El rápido zorro marrón salta sobre el perro perezoso ") = A8ADD4BDDDFD93E4877D2746E62817B116364A1FA7BC148D95090BC7333B3673 F82401CF7AA2E4CB1ECD90296E3F14CB5413F8ED77BE73045B13914CDCD6A918BLAKE2s-256("")
= 69217A3079908094E11121D042354A7C1F55B6482CA1A51E1B250DFD1ED0EEF9
BLAKE2s-256("The quick brown fox jumps over the lazy dog")
= 606BEEEC743CCBEFF6CBCDF5D5302AA855C256C29B88C8ED331EA1A6BF3C8812
BLAKE2s-128("")
= 64550D6FFE2C0A01A14ABA1EADE0200C
BLAKE2s-128("The quick brown fox jumps over the lazy dog ")
= 96FD07258925748A0D2FB1C8A1167A73
Comentarios
- ↑ Por ejemplo, un mensaje con una longitud de 447 bits agregará 1, luego 511 ceros (la longitud será 447 + 512), luego otro 1 y una representación de 64 bits del número l = 447 - 00 ... 0110111111 . Por lo tanto, la longitud será igual a 447+512+1+64 = 1024, que es un múltiplo de 512
Fuentes
- ↑ 1 2 Documentación de BLAKE en el sitio web oficial Archivado el 9 de diciembre de 2017 en Wayback Machine , p.3 Introducción.
- ↑ Sitio web oficial de BLAKE . Consultado el 21 de diciembre de 2013. Archivado desde el original el 16 de abril de 2018.
- ↑ Documentación de BLAKE en el sitio web oficial Archivado el 9 de diciembre de 2017 en Wayback Machine , p.8 Especificación.
Literatura
Eli Biham y Orr Dunkelman. Un marco para funciones hash iterativas: HAIFA . - ePrint, 2007. - 207 p.
Enlaces
- sitio web de BLAKE
- Sitio web de BLAKE2
- Código fuente VHDL desarrollado por el Grupo de Investigación de Criptografía de la Universidad George Mason
| Funciones hash | |
|---|---|
| propósito general | |
| Criptográfico | |
| Funciones de generación de claves | |
| Número de cheque ( comparación ) | |
| Hachís |
|