LSH (función hash)

LSH es una función hash criptográfica diseñada en 2014 por Corea del Sur para garantizar la integridad en entornos de software de propósito general, como ordenadores personales y dispositivos inteligentes . ^{[ 1 ]} LSH es uno de los algoritmos criptográficos aprobados por el Programa Coreano de Validación de Módulos Criptográficos (KCMVP). Además, es el estándar nacional de Corea del Sur (KS X 3262).

Especificación

La estructura general de la función hash LSH se muestra en la siguiente figura.

La función hash LSH tiene la estructura Merkle-Damgård de tubería ancha con relleno de ceros. El proceso de hash de mensajes de LSH consta de las siguientes tres etapas.

Inicialización :
- Relleno con ceros de un mensaje de cadena de bits dado.
- Conversión de la cadena de bits rellena a bloques de mensajes de matriz de 32 palabras.
- Inicialización de una variable de encadenamiento con el vector de inicialización.
Compresión :
- Actualización de variables encadenadas mediante la iteración de una función de compresión con bloques de mensajes.
Finalización :
- Generación de un $n$ Valor hash de -bits de la variable de encadenamiento final.

Las especificaciones de la función hash LSH son las siguientes.

Inicialización

Dejar $m$ ser un mensaje de cadena de bits dado. El dado $m$ se rellena con ceros, es decir, el bit '1' se agrega al final de $m$ y los bits '0' se agregan hasta que se alcanza una longitud de bits de un mensaje relleno. $32wt$ , dónde $t=\lceil (|m|+1)/32w\rceil$ y $\lceil x\rceil$ es el entero más pequeño no menor que $x$ .

Dejar $m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}$ ser el relleno de uno-cero $32wt$ -cadena de bits de $m$ . Entonces $m_{p}$ se considera como un $4wt$ matriz de bytes $m_{a}=(m[0],\ldots ,m[4wt-1])$ , dónde $m[k]=m_{8k}\|m_{(8k+1)}\|\ldots \|m_{(8k+7)}$ a pesar de $0\leq k\leq (4wt-1)$ . El $4wt$ matriz de bytes $m_{a}$ se convierte en un $32t$ matriz de palabras ${\textsf {M}}=(M[0],\ldots ,M[32t-1])$ como sigue.

$M[s]\leftarrow m[ws/8+(w/8-1)]\|\ldots \|m[ws/8+1]\|m[ws/8]$ $(0\leq s\leq (32t-1))$

A partir de la matriz de palabras ${\textsf {M}}$ , definimos el $t$ bloques de mensajes de matriz de 32 palabras $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$ como sigue.

${\textsf {M}}^{(i)}\leftarrow (M[32i],M[32i+1],\ldots ,M[32i+31])$ $(0\leq i\leq (t-1))$

La variable de encadenamiento de matriz de 16 palabras ${\textsf {CV}}^{(0)}$ se inicializa con el vector de inicialización ${\textsf {IV}}$ .

${\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]$ $(0\leq l\leq 15)$

El vector de inicialización ${\textsf {IV}}$ es el siguiente. En las siguientes tablas, todos los valores se expresan en forma hexadecimal.

Compresión

En esta etapa, el $t$ bloques de mensajes de matriz de 32 palabras $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$ , que se generan a partir de un mensaje $m$ En la etapa de inicialización, se comprimen mediante la iteración de funciones de compresión. La función de compresión ${\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}$ tiene dos entradas; la $i$ Variable de encadenamiento de 16 palabras -th ${\textsf {CV}}^{(i)}$ y el $i$ -th bloque de mensaje de 32 palabras ${\textsf {M}}^{(i)}$ . Y devuelve el $(i+1)$ Variable de encadenamiento de 16 palabras -th ${\textsf {CV}}^{(i+1)}$ Aquí y posteriormente, ${\mathcal {W}}^{t}$ denota el conjunto de todos $t$ -matrices de palabras para $t\geq 1$ .

Las siguientes cuatro funciones se utilizan en una función de compresión:

Función de expansión de mensajes ${\textrm {MsgExp}}:{\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16(Ns+1)}$
Función de adición de mensajes ${\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$
Función mixta ${\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$
Función de permutación de palabras ${\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$

La estructura general de la función de compresión se muestra en la siguiente figura.

En una función de compresión, la función de expansión de mensajes ${\textrm {MsgExp}}$ genera $(N_{s}+1)$ Submensajes de matriz de 16 palabras $\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}$ de dado ${\textsf {M}}^{(i)}$ . Dejar ${\textsf {T}}=(T[0],\ldots ,T[15])$ ser una matriz temporal de 16 palabras establecida en el $i$ -ésima variable de encadenamiento ${\textsf {CV}}^{(i)}$ . El $j$ función de paso -ésimo ${\textrm {Step}}_{j}$ tener dos entradas ${\textsf {T}}$ y ${\textsf {M}}_{j}^{(i)}$ actualizaciones ${\textsf {T}}$ , es decir, ${\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)$ Todas las funciones escalonadas se ejecutan en orden. $j=0,\ldots ,N_{s}-1$ Luego uno más ${\textrm {MsgAdd}}$ operación por ${\textsf {M}}_{N_{s}}^{(i)}$ se procede y el $(i+1)$ -ésima variable de encadenamiento ${\textsf {CV}}^{(i+1)}$ está configurado para ${\textsf {T}}$ El proceso de una función de compresión se describe en detalle a continuación.

Aquí el $j$ función de paso -ésimo ${\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ es el siguiente.

${\textrm {Step}}_{j}:={\textrm {WordPerm}}\circ {\textrm {Mix}}_{j}\circ {\textrm {MsgAdd}}$ $(0\leq j\leq (N_{s}-1))$

La siguiente figura muestra la $j$ función de paso -ésimo ${\textrm {Step}}_{j}$ de una función de compresión.

{\displaystyle j} — El $j$ función de paso -ésimo ${\textrm {Step}}_{j}$

Función de expansión de mensajes MsgExp

Dejar ${\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])$ ser el $i$ -th bloque de mensajes de matriz de 32 palabras. La función de expansión de mensajes ${\textrm {MsgExp}}$ genera $(N_{s}+1)$ Submensajes de matriz de 16 palabras $\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}$ de un bloque de mensajes ${\textsf {M}}^{(i)}$ Los dos primeros submensajes ${\textsf {M}}_{0}^{(i)}=(M_{0}^{(i)}[0],\ldots ,M_{0}^{(i)}[15])$ y ${\textsf {M}}_{1}^{(i)}=(M_{1}^{(i)}[0],\ldots ,M_{1}^{(i)}[15])$ se definen de la siguiente manera.

${\textsf {M}}_{0}^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\ldots ,M^{(i)}[15])$
${\textsf {M}}_{1}^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\ldots ,M^{(i)}[31])$

Los siguientes submensajes $\{{\textsf {M}}_{j}^{(i)}=(M_{j}^{(i)}[0],\ldots ,M_{j}^{(i)}[15])\}_{j=2}^{N_{s}}$ se generan de la siguiente manera.

${\textsf {M}}_{j}^{(i)}[l]\leftarrow {\textsf {M}}_{j-1}^{(i)}[l]\boxplus {\textsf {M}}_{j-2}^{(i)}[\tau (l)]$ $(0\leq l\leq 15,\ 2\leq j\leq N_{s})$

Aquí $\tau$ es la permutación sobre $\mathbb {Z} _{16}$ definido de la siguiente manera.

Función de adición de mensajes MsgAdd

Para dos matrices de 16 palabras ${\textsf {X}}=(X[0],\ldots ,X[15])$ y ${\textsf {Y}}=(Y[0],\ldots ,Y[15])$ la función de adición de mensajes ${\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ se define de la siguiente manera.

${\textrm {MsgAdd}}({\textsf {X}},{\textsf {Y}}):=(X[0]\oplus Y[0],\ldots ,X[15]\oplus Y[15])$

Función de mezcla Mezcla

El $j$ -th función de mezcla ${\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ actualiza la matriz de 16 palabras ${\textsf {T}}=(T[0],\ldots ,T[15])$ mezclando cada par de palabras; $T[l]$ y $T[l+8]$ para $(0\leq l<8)$ . Para $0\leq j<N_{s}$ , la función de mezcla ${\textrm {Mix}}_{j}$ Procede de la siguiente manera.

$(T[l],T[l+8])\leftarrow {\textrm {Mix}}_{j,l}(T[l],T[l+8])$ $(0\leq l<8)$

Aquí ${\textrm {Mix}}_{j,l}$ es una función de mezcla de dos palabras. $X$ y $Y$ ser palabras. La función de mezcla de dos palabras ${\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}$ se define de la siguiente manera.

La función de mezcla de dos palabras ${\textrm {Mix}}_{j,l}$ Se muestra en la siguiente figura.

{\displaystyle {\textrm {Mezcla}}_{j,l}(X,Y)} — Función de mezcla de dos palabras ${\textrm {Mix}}_{j,l}(X,Y)$

Las cantidades de rotación de bits $\alpha _{j}$ , $\beta _{j}$ , $\gamma _{l}$ utilizado en ${\textrm {Mix}}_{j,l}$ se muestran en la siguiente tabla.

El $j$ constante de matriz de 8 palabras -th ${\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])$ utilizado en ${\textrm {Mix}}_{j,l}$ para $0\leq l<8$ se define de la siguiente manera. La constante de matriz inicial de 8 palabras ${\textsf {SC}}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])$ se define en la siguiente tabla. Para $1\leq j<N_{s}$ , el $j$ constante -ésima ${\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])$ es generado por $SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}$ para $0\leq l<8$ .

Función de permutación de palabras WordPerm

Dejar ${\textsf {X}}=(X[0],\ldots ,X[15])$ sea una matriz de 16 palabras. La función de permutación de palabras ${\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ se define de la siguiente manera.

${\textrm {WordPerm}}({\textsf {X}})=(X[\sigma (0)],\ldots ,X[\sigma (15)])$

Aquí $\sigma$ es la permutación sobre $\mathbb {Z} _{16}$ definido por la siguiente tabla.

Finalización

La función de finalización ${\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}$ devoluciones $n$ valor hash de bits $h$ de la variable de encadenamiento final ${\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])$ . Cuando ${\textsf {H}}=(H[0],\ldots ,H[7])$ es una variable de 8 palabras y ${\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])$ es un $w$ Variable de byte, la función de finalización ${\textrm {FIN}}_{n}$ realiza el siguiente procedimiento.

$H[l]\leftarrow CV^{(t)}[l]\oplus CV^{(t)}[l+8]$ $(0\leq l\leq 7)$
$h_{b}[s]\leftarrow H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\ggg (8s\mod w)}$ $(0\leq s\leq (w-1))$
$h\leftarrow (h_{b}[0]\|\ldots \|h_{b}[w-1])_{[0:n-1]}$

Aquí, $X_{[i:j]}$ denota $x_{i}\|x_{i-1}\|\ldots \|x_{j}$ , la cadena de subbits de una palabra $X$ para $i\geq j$ . Y $x_{[i:j]}$ denota $x_{i}\|x_{i+1}\|\ldots \|x_{j}$ , la cadena de subbits de un $l$ cadena de bits $x=x_{0}\|x_{1}\|\ldots \|x_{l-1}$ para $i\leq j$ .

Seguridad

LSH es seguro contra ataques conocidos a funciones hash hasta ahora. LSH es resistente a colisiones para $q<2^{n/2}$ y resistentes a la preimagen y a la segunda preimagen para $q<2^{n}$ en el modelo de cifrado ideal, donde $q$ es un número de consultas para la estructura LSH. ^{[ 1 ]} LSH-256 es seguro contra todos los ataques de función hash existentes cuando el número de pasos es 13 o más, mientras que LSH-512 es seguro si el número de pasos es 14 o más. Tenga en cuenta que los pasos que funcionan como margen de seguridad son el 50% de la función de compresión. ^{[ 1 ]}

Actuación

LSH supera a SHA-2/3 en diversas plataformas de software. La siguiente tabla muestra el rendimiento de velocidad del hash de mensajes de 1 MB con LSH en varias plataformas.

↑ Intel Core i7-4770K a 3,5 GHz (Haswell), Ubuntu 12.04 de 64 bits, GCC 4.8.1 con “-m64 -mavx2 -O3”
↑ Intel Core i7-2600K a 3,40 GHz (Sandy Bridge), Ubuntu 12.04 de 64 bits, GCC 4.8.1 con “-m64 -msse4 -O3”
↑ Intel Core 2 Quad Q9550 a 2,83 GHz (Yorkfield), Windows 7 de 32 bits, Visual Studio 2012
↑ AMD FX-8350 a 4 GHz (Piledriver), Ubuntu 12.04 de 64 bits, GCC 4.8.1 con “-m64 -mxop -O3”
↑ Samsung Exynos 5250 ARM Cortex-A15 a 1,7 GHz de doble núcleo (Huins ACHRO 5250), Android 4.1.1
↑ Qualcomm Snapdragon 800 Krait 400 a 2,26 GHz de cuatro núcleos (LG G2), Android 4.4.2
↑ Qualcomm Snapdragon 800 Krait 400 a 2,3 GHz de cuatro núcleos (Samsung Galaxy S4), Android 4.2.2
↑ Qualcomm Snapdragon 400 Krait 300 a 1,7 GHz de doble núcleo (Samsung Galaxy S4 mini), Android 4.2.2

La siguiente tabla muestra la comparación en la plataforma basada en Haswell. LSH se mide en una plataforma de cuatro núcleos Intel Core i7-4770k a 3,5 GHz, y los demás se miden en una plataforma de cuatro núcleos Intel Core i5-4570S a 2,9 GHz.

La siguiente tabla se basa en mediciones realizadas en la plataforma de doble núcleo Samsung Exynos 5250 ARM Cortex-A15 a 1,7 GHz.

Vectores de prueba

Los vectores de prueba para LSH para cada longitud de digestión son los siguientes. Todos los valores se expresan en formato hexadecimal.

LSH-256-224("abc") = F7 C5 3B A4 03 4E 70 8E 74 FB A4 2E 55 99 7C A5 12 6B B7 62 36 88 F8 53 42 F7 37 32

LSH-256-256("abc") = 5F BF 36 5D AE A5 44 6A 70 53 C5 2B 57 40 4D 77 A0 7A 5F 48 A1 F7 C1 96 3A 08 98 BA 1B 71 47 41

LSH-512-224("abc") = D1 68 32 34 51 3E C5 69 83 94 57 1E AD 12 8A 8C D5 37 3E 97 66 1B A2 0D CF 89 E4 89

LSH-512-256("abc") = CD 89 23 10 53 26 02 33 2B 61 3F 1E C1 1A 69 62 FC A6 1E A0 9E CF FC D4 BC F7 58 58 D8 02 ED EC

LSH-512-384("abc") = 5F 34 4E FA A0 E4 3C CD 2E 5E 19 4D 60 39 79 4B 4F B4 31 F1 0F B4 B6 5F D4 5E 9D A4 EC DE 0F 27 B6 6E 8D BD FA 47 25 2E 0D 0B 74 1B FD 91 F9 FE

LSH-512-512("abc") = A3 D9 3C FE 60 CC 1A CA DD 3B D4 BE F0 A6 98 53 81 A3 96 C7 D4 9D 9F D1 77 79 56 97 C3 53 52 08 B5 C5 72 24 BE F2 10 84 D4 20 83 E9 5A 4B D8 EB 33 E8 69 81 2B 65 03 1C 42 88 19 A1 E7 CE 59 6D

Implementaciones

LSH es gratuito para cualquier uso, público o privado, comercial o no comercial. El código fuente para la distribución de LSH, implementado en C, Java y Python, se puede descargar desde la página web de activación de uso de criptografía de KISA. ^{[ 2 ]}

KCMVP

LSH es uno de los algoritmos criptográficos aprobados por el Programa Coreano de Validación de Módulos Criptográficos (KCMVP). ^{[ 3 ]}

Normalización

LSH está incluido en la siguiente norma.

KS X 3262, Función hash LSH (en coreano) ^{[ 4 ]}

Referencias

1 2 3 4 5 6 Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2015). "LSH: Una nueva familia de funciones hash rápidas y seguras" . Seguridad de la información y criptología - ICISC 2014. Notas de clase en ciencias de la computación. Vol. 8949. Springer International Publishing. págs. 286–313 . doi : 10.1007/978-3-319-15943-0_18 . ISBN 978-3-319-15943-0.
^ "KISA 암호이용활성화 - 암호알고리즘 소스코드" . semilla.kisa.or.kr .
↑ «KISA 암호이용활성화 - 개요» . semilla.kisa.or.kr .
↑ "Normas y certificaciones coreanas (en coreano)" .

[2] Intel Core i7-4770K a 3,5 GHz (Haswell), Ubuntu 12.04 de 64 bits, GCC 4.8.1 con “-m64 -mavx2 -O3”

[3] Intel Core i7-2600K a 3,40 GHz (Sandy Bridge), Ubuntu 12.04 de 64 bits, GCC 4.8.1 con “-m64 -msse4 -O3”

[4] Intel Core 2 Quad Q9550 a 2,83 GHz (Yorkfield), Windows 7 de 32 bits, Visual Studio 2012

[5] AMD FX-8350 a 4 GHz (Piledriver), Ubuntu 12.04 de 64 bits, GCC 4.8.1 con “-m64 -mxop -O3”

[6] Samsung Exynos 5250 ARM Cortex-A15 a 1,7 GHz de doble núcleo (Huins ACHRO 5250), Android 4.1.1

[7] Qualcomm Snapdragon 800 Krait 400 a 2,26 GHz de cuatro núcleos (LG G2), Android 4.4.2

[8] Qualcomm Snapdragon 800 Krait 400 a 2,3 GHz de cuatro núcleos (Samsung Galaxy S4), Android 4.2.2

[9] Qualcomm Snapdragon 400 Krait 300 a 1,7 GHz de doble núcleo (Samsung Galaxy S4 mini), Android 4.2.2

[KHL+14-1] 1 2 3 4 5 6 Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2015). "LSH: Una nueva familia de funciones hash rápidas y seguras" . Seguridad de la información y criptología - ICISC 2014. Notas de clase en ciencias de la computación. Vol. 8949. Springer International Publishing. págs. 286–313 . doi : 10.1007/978-3-319-15943-0_18 . ISBN 978-3-319-15943-0.

[LSH_source-10] "KISA 암호이용활성화 - 암호알고리즘 소스코드" . semilla.kisa.or.kr .

[KCMVP-11] «KISA 암호이용활성화 - 개요» . semilla.kisa.or.kr .

[KS_X_3262-12] "Normas y certificaciones coreanas (en coreano)" .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]