En criptografía , scrypt (pronunciado "ess crypt" [1] ) es una función de derivación de claves basada en contraseña creada por Colin Percival, originalmente para el servicio de respaldo en línea de Tarsnap . [2] El algoritmo fue diseñado específicamente para que resulte costoso realizar ataques de hardware personalizados a gran escala al requerir grandes cantidades de memoria. En 2016, el algoritmo scrypt fue publicado por el IETF como RFC 7914. Una versión simplificada de scrypt se utiliza como una prueba de trabajo esquema por una serie de cryptocurrencies , implementado por primera vez por un programador anónimo llamado ArtForz en Tenebrix y seguido por Fairbrix yLitecoin poco después. [3]
General | |
---|---|
Diseñadores | Colin Percival |
Publicado por primera vez | 2009 |
Detalle de cifrado | |
Tamaños de resumen | variable |
Tamaños de bloque | variable |
Rondas | variable |
Introducción
Una función de derivación de clave basada en contraseña (KDF basada en contraseña) generalmente está diseñada para ser computacionalmente intensiva, por lo que lleva un tiempo relativamente largo para calcular (digamos del orden de varios cientos de milisegundos). Los usuarios legítimos solo necesitan realizar 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.
Los KDF basados en contraseñas anteriores (como el popular PBKDF2 de RSA Laboratories ) tienen demandas de recursos relativamente bajas, lo que significa que no requieren hardware elaborado ni mucha memoria para funcionar. Por lo tanto, se implementan de manera fácil y económica en hardware (por ejemplo, en un ASIC o incluso en un FPGA ). Esto permite que un atacante con recursos suficientes lance un ataque paralelo a gran escala construyendo cientos o incluso miles de implementaciones del algoritmo en hardware y haciendo que cada una busque un subconjunto diferente del espacio clave. Esto divide la cantidad de tiempo necesaria para completar un ataque de fuerza bruta por la cantidad de implementaciones disponibles, muy posiblemente reduciéndolo a un período de tiempo razonable.
La función scrypt está diseñada para obstaculizar tales intentos aumentando las demandas de recursos del algoritmo. Específicamente, el algoritmo está diseñado para usar una gran cantidad de memoria en comparación con otros KDF basados en contraseñas, [4] haciendo que el tamaño y el costo de una implementación de hardware sean mucho más costosos y, por lo tanto, limitando la cantidad de paralelismo que puede usar un atacante. por una determinada cantidad de recursos financieros.
Descripción general
Los grandes requisitos de memoria de scrypt provienen de un gran vector de cadenas de bits pseudoaleatorias que se generan como parte del algoritmo. Una vez que se genera el vector, se accede a sus elementos en un orden pseudoaleatorio y se combinan para producir la clave derivada. Una implementación sencilla necesitaría mantener todo el vector en la RAM para que se pueda acceder a él según sea necesario.
Debido a 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 la memoria a la vez y, por lo tanto, reduciendo significativamente los requisitos de memoria. Sin embargo, se pretende que la generación de cada elemento sea computacionalmente costosa y se espera que se acceda a los elementos muchas veces durante la ejecución de la función. Por lo tanto, existe una compensación significativa en la velocidad para deshacerse de los grandes requisitos de memoria.
Este tipo de compensación entre tiempo y memoria a menudo existe en los algoritmos informáticos: la velocidad puede aumentarse a costa de usar más memoria o los requisitos de memoria disminuyen a costa de realizar más operaciones y tomar más tiempo. La idea detrás de scrypt es hacer deliberadamente costosa esta compensación en cualquier dirección. Por lo tanto, un atacante podría usar una implementación que no requiera muchos recursos (y, por lo tanto, se puede paralelizar masivamente con un gasto limitado) pero que se ejecuta muy lentamente, o usar una implementación que se ejecuta más rápidamente pero tiene requisitos de memoria muy grandes y, por lo tanto, es más cara paralelizar.
Algoritmo
Función scrypt Entradas: Este algoritmo incluye los siguientes parámetros: Frase de contraseña: Cadena de bytes de caracteres a ser hash Salt : Cadena de bytes de caracteres aleatorios que modifica el hash para proteger contra ataques de tablas Rainbow CostFactor (N): Parámetro de costo de memoria / CPU entero - Debe ser una potencia de 2 (por ejemplo, 1024) BlockSizeFactor (r): parámetro de tamaño de bloque entero , que ajusta el tamaño y el rendimiento de lectura de memoria secuencial. (8 se usa comúnmente) ParallelizationFactor (p): Parámetro de paralelización de enteros . (1 .. 2 32 -1 * hLen / MFlen) DesiredKeyLen (dkLen): Entero Longitud de clave deseada en bytes (Longitud de salida deseada en octetos de la clave derivada; un entero positivo que satisface dkLen ≤ (2 32 - 1) * hLen. ) hLen: Integer 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: matriz de bytes de bytes, DesiredKeyLen largo Paso 1. Genere un costoso salt blockSize ← 128 * BlockSizeFactor // 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 (p. Ej., 128 * 8 * 3 = 3072 bytes) Trate el resultado como una matriz de p elementos, siendo cada entrada bytes de tamaño de bloque (p. Ej., 3 elementos, cada 1024 bytes) [B 0 ... B p − 1 ] ← PBKDF2 HMAC-SHA256 ( Passphrase , Salt , 1, blockSize * ParallelizationFactor) Mezclar cada bloque en B veces Costfactor utilizando RoMix función (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 es nuestra nueva sal "cara" cara ← B 0 ∥B 1 ∥B 2 ∥ ... ∥B p-1 // donde ∥ es la concatenación Paso 2. Use PBKDF2 para generar la cantidad deseada de bytes, pero usando la sal costosa que acabamos de generar, devuelva PBKDF2 HMAC-SHA256 (Passphrase, costosaSalt, 1, DesiredKeyLen);
Donde la notación PBKDF2 (P, S, c, dkLen) se define en RFC 2898, donde c es un recuento de iteraciones.
RFC 7914 utiliza esta notación para especificar un uso de PBKDF2 con c = 1.
Función ROMix (bloque, iteraciones) Crear copias de iteraciones de X X ← Bloque para i ← 0 a iteraciones − 1 hacer V i ← X X ← BlockMix (X) para i ← 0 a iteraciones − 1 hacer j ← Integerify (X) mod Iteraciones X ← BlockMix (X xor V j ) volver X
Donde RFC 7914 define Integerify(X)
como el resultado de interpretar los últimos 64 bytes de X como un entero little-endian A 1 .
Dado que las iteraciones equivalen a 2 elevado a la potencia de N, solo los primeros bytes de techo (N / 8) entre los últimos 64 bytes de X, interpretados como un entero little-endian A 2 , son realmente necesarios para calcular .Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations
Función BlockMix (B): El bloque B es r trozos de 128 bytes (que es equivalente a 2r trozos de 64 bytes) r ← Longitud (B) / 128; Trate B como una matriz de 2r fragmentos de 64 bytes [B 0 ... B 2r-1 ] ← B X ← B 2r − 1 para i ← 0 a 2r − 1 do X ← Salsa20 / 8 (X xor B i ) // Salsa20 / 8 hashes de 64 bytes a 64 bytes Y i ← X volver ← 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 .
Usos de criptomonedas
Scrypt se utiliza en muchas criptomonedas como algoritmo de prueba de trabajo . Se implementó por primera vez para Tenebrix (lanzado en septiembre de 2011) y sirvió como base para Litecoin y Dogecoin , que también adoptaron su algoritmo scrypt. [5] [6] La extracción de criptomonedas que usan scrypt se realiza a menudo en unidades de procesamiento de gráficos ( GPU ), ya que las GPU tienden a tener una potencia de procesamiento significativamente mayor (para algunos algoritmos) en comparación con la CPU. [7] Esto provocó una escasez de GPU de gama alta debido al aumento del precio de estas monedas en los meses de noviembre y diciembre de 2013. [8]
A partir de mayo de 2014, el hardware de minería ASIC especializado está disponible para criptomonedas basadas en scrypt. [ cita requerida ]
Ver también
- Función de derivación clave
- Argon2 , ganador del concurso de hash de contraseñas
- cripta , almacenamiento de contraseñas y esquema de verificación
- PBKDF2 , una función de derivación de clave basada en contraseña estándar ampliamente utilizada
- bcrypt , función de hash de contraseña usando Blowfish
- Compensación espacio-tiempo
Referencias
- ^ "Colin Percival en Twitter" .
- ^ "página de scrypt en el sitio web de Tarsnap" . Consultado el 21 de enero de 2014 .
- ^ Alec Liu. "Más allá de Bitcoin: una guía de las criptomonedas más prometedoras" .
- ^ Derivación de claves más fuerte a través de funciones secuenciales de memoria dura , Colin Percival
- ^ Andreas M. Antonopoulos (3 de diciembre de 2014). Dominar Bitcoin: desbloquear criptomonedas digitales . O'Reilly Media. págs. 221, 223. ISBN 9781491902646.
- ^ "Historia de la criptomoneda" . Archivado desde el original el 11 de junio de 2016 . Consultado el 27 de junio de 2014 .
- ^ Roman Guelfi-Gibbs. Configuraciones de minería de Litecoin Scrypt para Radeon 7950 . Servicios digitales de Amazon.
- ^ Joel Hruska (10 de diciembre de 2013). "El aumento masivo de la minería de Litecoin conduce a la escasez de tarjetas gráficas" . ExtremeTech.
enlaces externos
- La página de scrypt en el sitio web de Tarsnap.
- El papel scrypt original.
- scrypt en GitHub