scrypt

En criptografía , scrypt (pronunciado "ess crypt" ^{[ 1 ]} ) es una función de derivación de clave basada en contraseña creada por Colin Percival en marzo de 2009, originalmente para el servicio de copia de seguridad en línea Tarsnap . ^{[ 2 ] [ 3 ]} El algoritmo fue diseñado específicamente para dificultar la realización de ataques de hardware personalizados a gran escala , al requerir grandes cantidades de memoria. En 2016, el algoritmo scrypt fue publicado por la IETF como RFC 7914. ^{[ 4 ]} Una versión simplificada de scrypt se utiliza como esquema de prueba de trabajo por varias criptomonedas , implementada por primera vez por un programador anónimo llamado ArtForz en Tenebrix y seguida poco después por Fairbrix y Litecoin . ^{[ 5 ]}

Una función de derivación de clave basada en contraseña (KDF basada en contraseña) suele diseñarse para ser computacionalmente intensiva, por lo que su cálculo requiere un tiempo relativamente largo (del orden de varios cientos de milisegundos). Los usuarios legítimos solo necesitan ejecutar la función una vez por operación (por ejemplo, autenticación), por lo que el tiempo requerido es insignificante. Sin embargo, un ataque de fuerza bruta probablemente necesitaría realizar la operación miles de millones de veces, momento en el que los requisitos de tiempo se vuelven significativos e, idealmente, prohibitivos.

Las funciones de derivación de claves ( KDF) basadas en contraseñas anteriores (como la popular PBKDF2 de RSA Laboratories ) requieren relativamente pocos recursos, lo que significa que no necesitan hardware complejo ni mucha memoria para funcionar. Por lo tanto, se implementan de forma sencilla y económica en hardware (por ejemplo, en un ASIC o incluso en una FPGA ). Esto permite a un atacante con recursos suficientes lanzar un ataque paralelo a gran escala mediante la creación de cientos o incluso miles de implementaciones del algoritmo en hardware, haciendo que cada una busque en un subconjunto diferente del espacio de claves. Esto divide el tiempo necesario para completar un ataque de fuerza bruta entre el número de implementaciones disponibles, lo que posiblemente lo reduzca a un plazo razonable.

La función scrypt está diseñada para dificultar tales intentos aumentando los requisitos de recursos del algoritmo. Específicamente, el algoritmo está diseñado para usar una gran cantidad de memoria en comparación con otras KDF basadas en contraseñas, ^{[ 6 ]} lo que hace que el tamaño y el costo de una implementación de hardware sean mucho más costosos y, por lo tanto, limita la cantidad de paralelismo que un atacante puede usar, para una cantidad determinada de recursos financieros.

Los elevados requisitos de memoria de Scrypt se deben a un gran vector de cadenas de bits pseudoaleatorias que se generan como parte del algoritmo. Una vez generado el vector, se accede a sus elementos en un orden pseudoaleatorio y se combinan para producir la clave derivada. Una implementación sencilla requeriría mantener todo el vector en la memoria RAM para poder acceder a él según sea necesario.

Dado que los elementos del vector se generan algorítmicamente, cada elemento podría generarse sobre la marcha según sea necesario, almacenando solo un elemento en memoria a la vez y, por lo tanto, reduciendo significativamente los requisitos de memoria. Sin embargo, la generación de cada elemento está diseñada para ser computacionalmente costosa, y se espera que los elementos se accedan muchas veces durante la ejecución de la función. Por lo tanto, existe una importante compensación entre velocidad y reducción de los elevados requisitos de memoria.

Este tipo de compensación entre tiempo y memoria suele darse en los algoritmos informáticos: se puede aumentar la velocidad a costa de usar más memoria, o disminuir los requisitos de memoria a costa de realizar más operaciones y tardar más. La idea detrás de scrypt es hacer que esta compensación sea costosa en ambos sentidos. Así, un atacante podría usar una implementación que no requiera muchos recursos (y que, por lo tanto, pueda paralelizarse masivamente con un coste limitado) pero que se ejecute muy lentamente, o usar una implementación que se ejecute más rápido pero que tenga requisitos de memoria muy grandes y, por lo tanto, sea más costosa de paralelizar.

Función scrypt  Entradas: Este algoritmo incluye los siguientes parámetros: Contraseña:  Cadena de bytes de caracteres a cifrar Salt :  Cadena de bytes de caracteres aleatorios que modifica el hash para proteger contra ataques de tabla arcoíris CostFactor (N): Parámetro entero  de costo de CPU/memoria – Debe ser una potencia de 2 (por ejemplo, 1024) BlockSizeFactor (r):  Parámetro entero de tamaño de bloque, que ajusta el tamaño y el rendimiento de la lectura secuencial de memoria. (Se suele usar 8) ParallelizationFactor (p): Parámetro entero  de paralelización . (1 .. 2 32 -1 * hLen/MFlen) DesiredKeyLen (dkLen):  Longitud de clave deseada en bytes (Longitud de salida prevista en octetos de la clave derivada; un entero positivo que satisface dkLen ≤ (2 32 − 1) * hLen.) hLen: Entero La longitud en octetos de la función hash (32 para SHA256). MFlen: Entero La longitud en octetos de la salida de la función de mezcla ( SMix a continuación). Definido como r * 128 en RFC7914. Salida: DerivedKey: Bytes matriz de bytes, DesiredKeyLen longPaso 1. Generar un bloque de sal costoso. Tamaño del bloque ← 128 * Factor de tamaño del bloque  // Longitud (en bytes) de la salida de la función de mezcla SMix (por ejemplo, 128 * 8 = 1024 bytes)Utilice PBKDF2 para generar 128*BlockSizeFactor*p bytes de datos iniciales (por ejemplo, 128*8*3 = 3072 bytes). Trate el resultado como una matriz de p elementos, donde cada entrada es de tamaño de bloque en bytes (por ejemplo, 3 elementos, cada uno de 1024 bytes). [B 0 ...B p−1 ] ← PBKDF2 HMAC-SHA256 ( Contraseña , Sal , 1, tamaño de bloque*Factor de paralelización) Mezcla cada bloque en B veces CostFactor usando la función ROMix (cada bloque se puede mezclar en paralelo) para i ← 0 a p-1 hacer B i ← ROMix(B i , CostFactor) Todos los elementos de B son nuestra nueva sal "cara" expensiveSalt ← B 0 ∥B 1 ∥B 2 ∥ ... ∥B p-1 // donde ∥ es concatenaciónPaso 2. Use PBKDF2 para generar el número deseado de bytes, pero usando la costosa sal que acabamos de generar return PBKDF2 HMAC-SHA256 (Passphrase, expensiveSalt, 1, DesiredKeyLen);

Donde PBKDF2(P, S, c, dkLen)la notación se define en RFC 2898, donde c es un contador de iteraciones.

Esta notación es utilizada por RFC 7914 para especificar un uso de PBKDF2 con c = 1.

Función ROMix(Bloque, Iteraciones) Crear copias iterativas de X X ← Bloque para i ← 0 hasta Iteraciones−1 hacer V i ← X X ← BlockMix(X) para i ← 0 hasta Iteraciones−1 hacer j ← Integerify(X) mod Iteraciones X ← BlockMix(X xor V j ) devolver X

Donde RFC 7914 define Integerify(X)como el resultado de interpretar los últimos 64 bytes de X como un entero little-endian A ₁ .

Dado que Iteraciones es igual a 2 elevado a la potencia de N, solo se necesitan los primerosCeiling(N / 8) bytes entre los últimos 64 bytes de X, interpretados como un entero little-endian A ₂ , para realizar el cálculo .Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations

Función BlockMix(B): El bloque B consta de r fragmentos de 128 bytes (lo que equivale a 2r fragmentos de 64 bytes). r ← Longitud(B) / 128; Trate B como una matriz de 2r bloques de 64 bytes [B 0 ...B 2r-1 ] ← B X ← B 2r−1 para i ← 0 a 2r−1 hacer X ← Salsa20/8(X xor B i ) // Salsa20/8 convierte hashes de 64 bytes a 64 bytes Y i ← X retorno ← Y 0 ∥Y 2 ∥...∥Y 2r−2 ∥ Y 1 ∥Y 3 ∥...∥Y 2r−1

Donde Salsa20/8 es la versión de 8 rondas de Salsa20 .

Scrypt se utiliza en muchas criptomonedas como algoritmo de prueba de trabajo (más precisamente, como la función hash en el algoritmo de prueba de trabajo Hashcash ). Se implementó por primera vez para Tenebrix (lanzado en septiembre de 2011) y sirvió de base para Litecoin y Dogecoin , que también adoptaron su algoritmo scrypt. ^{[ 7 ] [ 8 ]} La minería de criptomonedas que utilizan scrypt se realiza a menudo en unidades de procesamiento gráfico ( GPU ) ya que las GPU tienden a tener una potencia de procesamiento significativamente mayor (para algunos algoritmos) en comparación con la CPU. ^{[ 9 ]} Esto provocó escasez de GPU de gama alta debido al aumento del precio de estas monedas en los meses de noviembre y diciembre de 2013. ^{[ 10 ]}

La utilidad scrypt fue escrita en mayo de 2009 por Colin Percival como una demostración de la función de derivación de clave scrypt. ^{[ 2 ] [ 3 ]} Está disponible en la mayoría de las distribuciones de Linux y BSD .

• Argon2 – ganador del concurso de hash de contraseñas de 2015
• bcrypt : función de hash de contraseñas basada en blowfish
• bcrypt : utilidad de cifrado de archivos multiplataforma basada en blowfish desarrollada en 2002 ^{[ 12 ] [ 13 ] [ 14 ] [ 15 ]}
• crypt – función de la biblioteca C de Unix
• crypt – utilidad de Unix
• ccrypt – utilidad
• Función de derivación de clave
• Estiramientos clave
• mcrypt – utilidad
• PBKDF2 : una función de derivación de clave basada en contraseña ampliamente utilizada (Password-Based Key Derivation Function 2)
• PufferFish : una función de hash de contraseñas resistente a la caché basada en un diseño bcrypt mejorado.
• compensación espacio-tiempo
• yescrypt – sucesor de scrypt

• La página scrypt en el sitio web de Tarsnap.
• El documento original de Scrypt.
• scrypt en GitHub