Lyra2

Este artículo tiene varios problemas. Ayude a mejorarlo o discuta estos problemas en la página de discusión . ( Obtenga información sobre cómo y cuándo eliminar estos mensajes de plantilla ) Este artículo incluye contenido que está escrito como un anuncio . Ayude a mejorarlo eliminando el contenido promocional y los enlaces externos inapropiados , y agregando contenido enciclopédico escrito desde un punto de vista neutral . ( Octubre de 2017 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) Este artículo se basa demasiado en referencias a fuentes primarias . Mejore esto agregando fuentes secundarias o terciarias . ( Octubre de 2017 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla ) Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Buscar fuentes:  "Lyra2"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( octubre de 2017 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

Lyra2 es un esquema de hash de contraseña (PHS) que también puede funcionar como una función de derivación de claves (KDF). Recibió un reconocimiento especial durante el Concurso de hash de contraseñas en julio de 2015, ^[1] que ganó Argon2 . Además de ser utilizado para sus propósitos originales, también está en el núcleo de algoritmos de prueba de trabajo como Lyra2REv2, ^[2] adoptado por Vertcoin, ^[3] MonaCoin, ^[4] entre otras criptomonedas ^[5] Lyra2 fue diseñado por Marcos A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo CF dos Santos y Paulo SLM Barreto deEscola Politécnica da Universidade de São Paulo . ^[6] Es una mejora con respecto a Lyra, ^{[7] [8]} propuesto previamente por los mismos autores. Lyra2 preserva la seguridad, eficiencia y flexibilidad de su predecesor, incluyendo: (1) la capacidad de configurar la cantidad deseada de memoria, el tiempo de procesamiento y el paralelismo que utilizará el algoritmo; y (2) la capacidad de proporcionar un alto uso de memoria con un tiempo de procesamiento similar al obtenido con scrypt . Además, aporta las siguientes mejoras en comparación con su predecesor: ^[9]

• Permite un mayor nivel de seguridad contra los lugares de ataque que implican compensaciones de tiempo y memoria.
• Permite a los usuarios legítimos beneficiarse de forma más eficaz de las capacidades de paralelismo de sus propias plataformas.
• incluye ajustes para aumentar los costos involucrados en la construcción de hardware dedicado para atacar el algoritmo
• equilibra la resistencia contra las amenazas de canal lateral y los ataques que dependen de dispositivos de almacenamiento más baratos (y, por lo tanto, más lentos)
• Lyra2 es de dominio público y ofrece dos extensiones principales: ^[10]
• Lyra2-δ, le da al usuario un mejor control sobre el uso del ancho de banda del algoritmo
• Lyra2 p , aprovecha las capacidades de paralelismo en la plataforma del usuario legítimo

Este algoritmo permite la parametrización en términos de: ^[10]

• tiempo de ejecución (costo de tiempo )${\displaystyle T}$
• memoria requerida (número de filas y número de columnas )${\displaystyle R}$${\displaystyle C}$
• grado de paralelismo (número de hilos )${\displaystyle p}$
• función de permutación subyacente (puede verse como la principal primitiva criptográfica)
• número de bloques utilizados por la función de permutación subyacente ( tasa de bits )
• número de rondas realizadas para la función de permutación subyacente ( )${\displaystyle \rho }$
• número de bits que se utilizarán en rotaciones ( )${\displaystyle \omega }$
• longitud de salida ( )${\displaystyle \kappa }$

Fortalezas

Los principales puntos fuertes del algoritmo son: ^{[5] [10]}

• Alta resistencia a las compensaciones de memoria de procesamiento: los costos de procesamiento estimados de los ataques con bajo uso de memoria involucran un factor que crece exponencialmente con el costo de tiempo debido a los recálculos
• Los costos de memoria y tiempo se pueden desacoplar, lo que permite ajustar el uso de los recursos
• Rápido debido al uso de la función de esponja de redondeo reducido en el núcleo del algoritmo
• Puede proporcionar salidas de cualquier longitud deseada, comportándose como una función de derivación clave (KDF)
• El diseño combina la resistencia a los ataques de canal lateral (durante toda la fase de configuración) y a los ataques que involucran dispositivos de memoria baratos (por lo tanto, de baja velocidad) , con el objetivo de equilibrar estos requisitos conflictivos
• Considera una amplia gama de configuraciones para proteger contra plataformas atacantes mientras optimiza la ejecución en plataformas legítimas, como:
  • Soporte para paralelismo, para plataformas multi-core , sin dar mucha ventaja a los ataques basados ​​en GPU
  • Capacidad de utilizar diferentes funciones de esponja subyacentes según la plataforma de destino (por ejemplo, BLAKE2b para implementaciones de software; Keccak para implementaciones de hardware; BlaMka para resistencia adicional contra plataformas de hardware; etc.)
  • Capacidad para aumentar el uso de ancho de banda de memoria del algoritmo (nota: se espera que la especificación original maximice el ancho de banda en las máquinas actuales, pero la característica puede ser útil para hardware futuro)

Diseño

Como cualquier PHS, Lyra2 toma como entrada una sal y una contraseña , creando una salida pseudoaleatoria que luego puede usarse como material clave para algoritmos criptográficos o como una cadena de autenticación . ^{[11] [ verificación fallida ] [ cita requerida ]}

Internamente, la memoria del esquema está organizada como una matriz que se espera que permanezca en la memoria durante todo el proceso de hash de contraseña: dado que sus celdas se leen y escriben de manera iterativa, descartar una celda para guardar memoria conduce a la necesidad de volver a calcularla cada vez que se accede a ella. una vez más, hasta el punto en que se modificó por última vez. ^[5]

La construcción y visita de la matriz se realiza mediante una combinación de estado de las operaciones de absorción, compresión y duplicación de la esponja subyacente (es decir, su estado interno nunca se restablece a cero), lo que garantiza la naturaleza secuencial de todo el proceso.

Además, el usuario define el número de veces que se vuelven a visitar las celdas de la matriz después de la inicialización, lo que permite ajustar el tiempo de ejecución de Lyra2 de acuerdo con los recursos de la plataforma de destino.

Funciones / símbolos

|| Concatenar dos cadenas^ XOR bit a bit[+] Operación de adición de palabras (es decir, ignorar los acarreos entre palabras)% De móduloW Tamaño de palabra de la máquina de destino (generalmente, 32 o 64)omega Número de bits que se utilizarán en las rotaciones (recomendado: un múltiplo del tamaño de la palabra de la máquina, W)>>> Rotación a la derecharho Número de rondas para reducir las operaciones de compresión o dúplexTamaño del bloque de blen Sponge en bytes Esponja H o H_i con tamaño de bloque blen (en bytes) y permutación subyacente fH.absorb (entrada) Operación de absorción de esponja en la entradaH.squeeze (len) Operación de compresión de Sponge de len bytesH.squeeze_ {rho} (len) Operación de compresión de Sponge de len bytes usando rho rondas de fH.duplexing (input, len) La operación de duplexación de Sponge en la entrada, produciendo len bytesH.duplexing_ {rho} (input, len) La operación de duplexación de Sponge en la entrada, usando rho rondas de f, produciendo len bytespad (cadena) Rellena una cadena a un múltiplo de bytes blen (regla de relleno: 10 * 1)lsw (entrada) La palabra de entrada menos significativalen (cadena) Longitud de una cadena, en bytessyncThreads () Sincronizar subprocesos paralelosswap (input1, input2) Intercambia el valor de dos entradasC Número de columnas en la matriz de memoria (generalmente, 64, 128, 256, 512 o 1024)P Grado de paralelismo (P> = 1 y (m_cost / 2)% P = 0)

Entradas

• contraseña
• sal
• t_cost
• m_cost
• outlen

Algoritmo sin paralelismo

** Fase de arranque: inicializa las variables estatales y locales de la esponja# Representación de bytes de los parámetros de entrada (se pueden agregar otros)params = outlen || len (contraseña) || len (sal) || t_cost || m_cost || C# Inicializa el estado de la esponja (después de eso, la contraseña se puede sobrescribir)H.absorb (pad (contraseña || salt || params))# Inicializa el paso de visita, la ventana y las primeras filas que se alimentarán brecha = 1stp = 1wnd = 2sqrt = 2prev0 = 2fila1 = 1prev1 = 0** Fase de configuración: inicializa una matriz de memoria (m_cost x C), sus celdas tienen celdas blen-byte# Inicializa M [0], M [1] y M [2]para col = 0 a C-1M [0] [C-1-col] = H.squeeze_ {rho} (blen)para col = 0 a C-1M [1] [C-1-col] = H.duplexing_ {rho} (M [0] [col], blen)para col = 0 a C-1M [2] [C-1-col] = H.duplexing_ {rho} (M [1] [col], blen)# Bucle de llenado: inicializa las filas restantespara row0 = 3 a m_cost-1# Bucle de columnas: M [fila0] se inicializa y M [fila1] se actualizapara col = 0 a C-1rand = H.duplexing_ {rho} (M [fila1] [col] [+] M [prev0] [col] [+] M [prev1] [col], blen)M [fila0] [C-1-col] = M [prev0] [col] ^ randM [fila1] [col] = M [fila1] [col] ^ (rand >>> omega)# Filas que se volverán a visitar en el siguiente cicloprev0 = fila0prev1 = fila1fila1 = (fila1 + stp)% wnd# Ventana completamente revisadasi (fila1 = 0)# Duplica la ventana y ajusta el pasownd = 2 * wndstp = sqrt + espaciobrecha = -gap# Duplica sqrt cada dos iteracionessi (espacio = -1)sqrt = 2 * sqrt** Fase errante: sobrescribe iterativamente celdas pseudoaleatorias de la matriz de memoria# Bucle de visitas: (2 * m_cost * t_cost) filas revisadas de manera pseudoaleatoriapara wCount = 0 a ((m_cost * t_cost) - 1)# Selecciona filas pseudoaleatoriasrow0 = lsw (rand)% m_costfila1 = lsw (rand >>> omega)% m_cost# Bucle de columnas: actualiza tanto M [fila0] como M [fila1]para col = 0 a C-1# Selecciona columnas pseudoaleatoriascol0 = lsw ((rand >>> omega) >>> omega)% Ccol1 = lsw (((rand >>> omega) >>> omega) >>> omega)% Crand = H.duplexing_ {rho} (M [fila0] [col] [+] M [fila1] [col] [+] M [prev0] [col0] [+] M [prev1] [col1], blen)M [fila0] [col] = M [fila0] [col] ^ randM [fila1] [col] = M [fila1] [col] ^ (rand >>> omega)# La próxima iteración vuelve a visitar las filas actualizadas más recientementeprev0 = fila0prev1 = fila1** Fase de cierre: cálculo de salida# Absorbe una columna final con una esponja redondaH.absorb (M [fila0] [0])# Exprime los pedacitos con una esponja redondasalida = H.squeeze (outlen)# Proporciona una cadena de bits outlen-long como salidasalida de retorno

Algoritmo con paralelismo

para cada i en [0..P]** Fase de arranque: inicializa las variables estatales y locales de la esponja# Representación de bytes de los parámetros de entrada (se pueden agregar otros)params = outlen || len (contraseña) || len (sal) || t_cost || m_cost || C || P || I# Inicializa el estado de la esponja (después de eso, la contraseña se puede sobrescribir)H_i.absorb (pad (contraseña || salt || params))# Inicializa el paso de visita, la ventana y las primeras filas que se alimentarán brecha = 1stp = 1wnd = 2sqrt = 2sincronización = 4j = yoprev0 = 2filaP = 1prevP = 0** Fase de configuración: inicializa una matriz de memoria (m_cost x C), sus celdas tienen celdas blen-byte# Inicializa M_i [0], M_i [1] y M_i [2]para col = 0 a C-1M_i [0] [C-1-col] = H_i.squeeze_ {rho} (blen)para col = 0 a C-1M_i [1] [C-1-col] = H_i.duplexing_ {rho} (M_i [0] [col], blen)para col = 0 a C-1M_i [2] [C-1-col] = H_i.duplexing_ {rho} (M_i [1] [col], blen)# Bucle de llenado: inicializa las filas restantespara row0 = 3 a ((m_cost / P) - 1)# Bucle de columnas: M_i [fila0] se inicializa y M_j [fila1] se actualizapara col = 0 a C-1rand = H_i.duplexing_ {rho} (M_j [rowP] [col] [+] M_i [prev0] [col] [+] M_j [prevP] [col], blen)M_i [fila0] [C-1-col] = M_i [prev0] [col] ^ randM_j [rowP] [col] = M_j [rowP] [col] ^ (rand >>> omega)# Filas que se volverán a visitar en el siguiente cicloprev0 = fila0prevP = filaProwP = (rowP + stp)% wnd# Ventana completamente revisadasi (filaP = 0)# Duplica la ventana y ajusta el pasownd = 2 * wndstp = sqrt + espaciobrecha = -gap# Duplica sqrt cada dos iteracionessi (espacio = -1)sqrt = 2 * sqrt# Sincronizar puntosi (fila0 = sincronizar)sincronizar = sincronizar + (sqrt / 2)j = (j + 1)% PsyncThreads ()syncThreads ()** Fase errante: sobrescribe iterativamente celdas pseudoaleatorias de la matriz de memoriawnd = m_cost / (2 * P)sincronizar = sqrtoff0 = 0offP = wnd# Bucle de visitas: (2 * m_cost * t_cost / P) filas revisitadas de forma pseudoaleatoriapara wCount = 0 a (((m_cost * t_cost) / P) - 1)# Selecciona filas y cortes pseudoaleatorios (j)row0 = off0 + (lsw (rand)% wnd)rowP = offP + (lsw (rand >>> omega)% wnd)j = lsw ((rand >>> omega) >>> omega)% PBucle de # columnas: actualizar M_i [row0]para col = 0 a C-1# Selecciona la columna pseudoaleatoriacol0 = lsw (((rand >>> omega) >>> omega) >>> omega)% Crand = H_i.duplexing_ {rho} (M_i [fila0] [col] [+] M_i [anterior0] [col0] [+] M_j [filaP] [col], blen)M_i [fila0] [col] = M_i [fila0] [col] ^ rand# La próxima iteración vuelve a visitar las filas actualizadas más recientementeprev0 = fila0# Sincronizar puntosi (wCount = sincronizar)sincronizar = sincronizar + sqrtintercambiar (off0, offP)syncThreads ()syncThreads ()** Fase de cierre: cálculo de salida# Absorbe una columna final con una esponja redondaH_i.absorb (M_i [fila0] [0])# Exprime los pedacitos con una esponja redondaoutput_i = H_i.squeeze (outlen)# Proporciona una cadena de bits outlen-long como salidadevolver salida_0 ^ ... ^ salida_ {P-1}

Análisis de seguridad

Contra Lyra2, se espera que el costo de procesamiento de los ataques que utilizan la cantidad de memoria empleada por un usuario legítimo esté entre y , siendo este último una mejor estimación , en lugar del logrado cuando la cantidad de memoria es , donde está un usuario- parámetro definido para definir un tiempo de procesamiento.${\displaystyle 1/2^{n+2}}$${\displaystyle O(2^{2nT}R^{3})}$${\displaystyle O(2^{2nT}R^{n+2})}$${\displaystyle n\gg 1}$${\displaystyle O(R)}$${\displaystyle O(R)}$${\displaystyle T}$

Esto se compara bien con scrypt , que muestra un costo de cuándo es el uso de la memoria , ^[12] y con otras soluciones en la literatura, para las cuales los resultados suelen ser . ^{[7] [13] [14] [15]}${\displaystyle O(R^{2})}$${\displaystyle O(1)}$${\displaystyle O(R^{T+1})}$

No obstante, en la práctica, estas soluciones suelen implicar un valor de (uso de memoria) inferior a los obtenidos con Lyra2 para el mismo tiempo de procesamiento. ^{[16] [17] [18] [19] [20]}${\displaystyle R}$

Rendimiento

Rendimiento de Lyra2 habilitado para SSE, para C = 256, ρ = 1, p = 1, y diferentes configuraciones de T y R, en comparación con scrypt habilitado para SSE y finalistas de PHC con memoria dura con parámetros mínimos.

El tiempo de procesamiento obtenido con una implementación SSE de un solo núcleo de Lyra2 se ilustra en la figura que se muestra aquí. Esta cifra se extrajo de ^[9] y es muy similar a los puntos de referencia de terceros realizados durante el contexto de la APS. ^{[16] [17] [18] [19] [20]}

Los resultados representados corresponden al tiempo de ejecución promedio de Lyra2 configurados con , , bits (es decir, el estado interior tiene 256 bits), y diferentes y ajustes, da una idea general de las posibles combinaciones de parámetros y el uso correspondiente de recursos.${\displaystyle C=256}$${\displaystyle \rho =1}$${\displaystyle b=768}$${\displaystyle T}$${\displaystyle R}$

Como se muestra en esta figura, Lyra2 puede ejecutarse en: menos de 1 s mientras usa hasta 400 MB (con y ) o hasta 1 GB de memoria (con y ); o en menos de 5 s con 1,6 GB (con y ).${\displaystyle R=2^{14}}$${\displaystyle T=5}$${\displaystyle R\approx 4.2\cdot 10^{4}}$${\displaystyle T=1}$${\displaystyle R=2^{16}}$${\displaystyle T=6}$

Todas las pruebas se realizaron en un Intel Xeon E5-2430 (2,20 GHz con 12 núcleos, 64 bits) equipado con 48 GB de DRAM , con Ubuntu 14.04 LTS de 64 bits y el código fuente se compiló utilizando gcc 4.9.2. ^[9]

Referencias

1. "Concurso de hash de contraseña" . password-hashing.net . Consultado el 22 de marzo de 2016 .
2. "Lyra2REv2" . eprint.iacr.org . Consultado el 22 de marzo de 2016 .
3. "Vertcoin" . vertcoin.org . Consultado el 8 de octubre de 2019 .
4. "MonaCoin" . monacoin.org . Consultado el 8 de octubre de 2019 .
5. van Beirendonck, M .; Trudeau, L .; Giard, P .; Balatsoukas-Stimming, A. (29 de mayo de 2019). Un núcleo Lyra2 FPGA para criptomonedas basadas en Lyra2REv2 . Simposio Internacional de Circuitos y Sistemas de IEEE (ISCAS). Sapporo, Japón: IEEE. págs. 1-5. arXiv : 1807.05764 . doi : 10.1109 / ISCAS.2019.8702498 .
6. "Archivo ePrint de criptología: informe 2015/136" . eprint.iacr.org . Consultado el 22 de marzo de 2016 .
7. Almeida, Leonardo C .; Andrade, Ewerton R .; Barreto, Paulo SLM; Simplicio Jr, Marcos A. (4 de enero de 2014). "Lyra: derivación de claves basada en contraseñas con memoria optimizable y costos de procesamiento". Revista de Ingeniería Criptográfica . 4 (2): 75–89. CiteSeerX 10.1.1.642.8519 . doi : 10.1007 / s13389-013-0063-5 . ISSN 2190-8508 .  
8. "Archivo ePrint de criptología: informe 2014/030" . eprint.iacr.org . Consultado el 22 de marzo de 2016 .
9. Andrade, E .; Simplicio Jr, M .; Barreto, P .; Santos, P. (1 de enero de 2016). "Lyra2: hash eficaz de contraseñas con alta seguridad contra compensaciones de tiempo-memoria". Transacciones IEEE en computadoras . PP (99): 3096–3108. doi : 10.1109 / TC.2016.2516011 . ISSN 0018-9340 . 
10. Simplicio Jr, Marcos A .; Almeida, Leonardo C .; Andrade, Ewerton R .; Santos, Paulo C .; Barreto, Paulo SLM "La guía de referencia de Lyra2" (PDF) . PHC . La competencia de hash de contraseñas.
11. Chen, Lily (2009). "Recomendación para la derivación de claves mediante funciones pseudoaleatorias (revisada)" (PDF) . Seguridad informática . NIST. doi : 10.6028 / NIST.SP.800-108 .
12. Percival, Colin. "Derivación de claves más fuerte a través de funciones secuenciales de memoria dura" (PDF) . TARSNAP . La Conferencia Técnica BSD.
13. "Archivo ePrint de criptología: informe 2013/525" . eprint.iacr.org . Consultado el 22 de marzo de 2016 .
14. Schmidt, Sascha. "Implementación del marco de cifrado de contraseñas de Catena" (PDF) . Bauhaus-Universität Weimar . Facultad de Medios.
15. "PHC / phc-ganador-argon2" (PDF) . GitHub . Consultado el 22 de marzo de 2016 .
16. "Gmane - Pruebas mecánicas de otros candidatos de APS" . article.gmane.org . Consultado el 22 de marzo de 2016 .
17. "Gmane - Una revisión por día Lyra2" . article.gmane.org . Consultado el 22 de marzo de 2016 .
18. "Revisión inicial de Gmane - Lyra2" . article.gmane.org . Consultado el 22 de marzo de 2016 .
19. "Gmane - Rendimiento de memoria y ataques ASIC" . article.gmane.org . Consultado el 22 de marzo de 2016 .
20. "Gmane - Análisis rápido de argón" . article.gmane.org . Consultado el 22 de marzo de 2016 .

Enlaces externos

• Sitio web de Lyra2
• Repositorio de código fuente de Lyra2 en Github