java - generate - ¿Cuáles son los factores óptimos de scrypt work?

sha java 8 (3)

Estoy usando una biblioteca scrypt de Java para el almacenamiento de contraseñas. Requiere un valor de N , r y p cuando cifro cosas, que su documentación se refiere a los parámetros de "costo de CPU", "costo de memoria" y "costo de paralelización". El único problema es que, en realidad, no sé qué significan específicamente, o qué buenos valores serían para ellos; ¿Quizás correspondan de algún modo a los modificadores -t, -m y -M en la aplicación original de Colin Percival ?

¿Alguien tiene alguna sugerencia para esto? La biblioteca misma muestra N = 16384, r = 8 yp = 1, pero no sé si esto es fuerte o débil o qué.

Como un inicio:

cpercival menciona en sus diapositivas de 2009 algo alrededor

(N = 2 ^ 14, r = 8, p = 1) para <100ms (uso interactivo), y
(N = 2 ^ 20, r = 8, p = 1) para <5s (almacenamiento sensible).

Estos valores son lo suficientemente buenos para el uso general (password-db para algunas aplicaciones web) incluso hoy (2012-09). Por supuesto, los detalles dependen de la aplicación.

Además, esos valores (en su mayoría) significan:

N : factor de trabajo general, recuento de iteraciones.
r : tamaño de bloques en uso para hash subyacente; ajusta el costo de memoria relativo.
p : factor de paralelización; ajusta con precisión el costo relativo de la CPU.

r y p tienen como objetivo dar cabida al problema potencial de que la velocidad de la CPU y el tamaño de la memoria y el ancho de banda no aumenten como se esperaba. Si el rendimiento de la CPU aumenta más rápido, aumenta p , en su lugar, un avance en la tecnología de la memoria proporciona una mejora en el orden de magnitud, aumenta r . Y N está ahí para mantenerse al día con el doble de rendimiento general por período de tiempo .

Importante: todos los valores cambian el resultado. (Actualizado :) Esta es la razón por la cual todos los parámetros de scrypt se almacenan en la cadena de resultados.

La memoria requerida para que scrypt funcione se calcula de la siguiente manera:

128 bytes × N_cost × r_blockSizeFactor

para los parámetros que cita ( N=16384 , r=8 , p=1 )

128 × 16384 × 8 = 16,777,216 bytes = 16 MB

Debe tener esto en cuenta al elegir los parámetros.

Bcrypt es "más débil" que Scrypt (aunque sigue siendo tres órdenes de magnitud más fuerte que PBKDF2 ) porque solo requiere 4 KB de memoria. Desea dificultar la paralelización de las grietas en el hardware. Por ejemplo, si una tarjeta de video tiene 1,5 GB de memoria integrada y sintonizó scrypt para consumir 1 GB de memoria:

128 × 16384 × 512 = 1,073,741,824 bytes = 1 GB

entonces un atacante no podría paralelizarlo en su tarjeta de video. Pero luego su aplicación / teléfono / servidor necesitaría usar 1 GB de RAM cada vez que calculen una contraseña.

Me ayuda a pensar en los parámetros de scrypt como un rectángulo. Dónde:

el ancho es la cantidad de memoria requerida (128 * N * r)
la altura es la cantidad de iteraciones realizadas
y el área resultante es la dureza general

el cost ( N ) aumenta tanto el uso de la memoria como las iteraciones .
blockSizeFactor ( r ) aumenta el uso de la memoria .

La parallelization parámetros restantes ( p ) significa que debe hacer todo 2, 3 o más veces:

Si tuviera más memoria que la CPU, podría calcular las tres rutas separadas en paralelo, que requieren el triple de la memoria:

Pero en todas las implementaciones del mundo real, se calcula en serie, triplicando los cálculos necesarios:

En realidad, nadie ha elegido un factor p distinto de p=1 .

¿Cuáles son los factores ideales?

Tanta RAM como puedas
por tanto tiempo como puedas!

Gráfico de bonificación

Versión gráfica de arriba:

Notas:

el eje vertical es la escala de registro
El factor de costo (horizontal) en sí mismo es log (iteraciones = 2 ^CostFactor )
Destacado en la curva r=8

Y amplió la versión de arriba al área razonable:

No quiero dar un paso adelante en las excelentes respuestas proporcionadas anteriormente, pero nadie realmente habla sobre por qué "r" tiene el valor que tiene. La respuesta de bajo nivel proporcionada por el documento Scrypt de Colin Percival es que se relaciona con el "producto de ancho de banda de latencia de memoria". Pero, ¿qué significa eso realmente?

Si está haciendo Scrypt a la derecha, debería tener un bloque de memoria grande que se encuentra principalmente en la memoria principal. La memoria principal toma tiempo para extraer. Cuando una iteración del bucle de salto de bloques selecciona primero un elemento del bloque grande para mezclarlo en el búfer de trabajo, debe esperar del orden de 100 ns para que llegue el primer fragmento de datos. Luego tiene que solicitar otro y esperar a que llegue.

Para r = 1, estarías haciendo 4nr iteraciones Salsa20 / 8 y 2n lecturas imbuidas de latencia desde la memoria principal.

Esto no es bueno, porque significa que un atacante podría obtener una ventaja sobre usted al construir un sistema con latencia reducida en la memoria principal.

Pero si aumenta r y disminuye proporcionalmente N, puede lograr los mismos requisitos de memoria y hacer el mismo número de cálculos que antes, excepto que ha intercambiado algunos accesos aleatorios para accesos secuenciales. La ampliación del acceso secuencial permite que la CPU o la biblioteca capten previamente los siguientes bloques de datos necesarios de manera eficiente. Mientras que la latencia inicial todavía está allí, la latencia reducida o eliminada para los bloques posteriores promedia la latencia inicial a un nivel mínimo. Por lo tanto, un atacante ganaría poco al mejorar su tecnología de memoria sobre la suya.

Sin embargo, hay un punto de rendimientos decrecientes al aumentar r, y eso está relacionado con el "producto de ancho de banda de latencia de memoria" mencionado anteriormente. Lo que indica este producto es cuántos bytes de datos pueden estar en tránsito desde la memoria principal al procesador en cualquier momento dado. Es la misma idea que una carretera: si toma 10 minutos para viajar del punto A al punto B (latencia), y la carretera entrega 10 automóviles / minuto al punto B del punto A (ancho de banda), la carretera entre los puntos A y B contiene 100 autos. Entonces, la r óptima se relaciona con la cantidad de fragmentos de datos de 64 bytes que puede solicitar a la vez, para cubrir la latencia de esa solicitud inicial.

Esto mejora la velocidad del algoritmo, lo que le permite aumentar N para más memoria y cálculos o aumentar p para más cálculos, según lo desee.

Hay otros problemas con el aumento de "r" demasiado, que no he visto discutido mucho:

Aumentar r mientras se disminuye N reduce el número de saltos pseudoaleatorios en torno a la memoria. Los accesos secuenciales son más fáciles de optimizar y podrían ofrecer una ventana al atacante. Como me señaló Colin Percival en Twitter, una r mayor podría permitir que un atacante use una tecnología de almacenamiento más lenta y de menor costo, lo que reduce sus costos considerablemente ( https://twitter.com/cperciva/status/661373931870228480 ).
El tamaño del búfer en funcionamiento es de 1024 r bits, por lo que la cantidad de posibles productos finales, que eventualmente se alimentarán a PBKDF2 para producir la clave de salida Scrypt, es 2 ^ 1024r. El número de permutaciones (secuencias posibles) de saltos alrededor del bloque de memoria grande es 2 ^ NlogN. Lo que significa que hay 2 ^ NlogN posibles productos del bucle de salto de memoria. Si 1024r> NlogN, eso parece indicar que el buffer de trabajo está siendo submezclado. Aunque no lo sé con certeza, y me gustaría ver una prueba o refutación, es posible que se encuentren correlaciones entre el resultado del búfer de trabajo y la secuencia de saltos, lo que podría permitir a un atacante la oportunidad de reducir su requisitos de memoria sin un gran costo computacional. De nuevo, esta es una observación basada en los números: puede ser que todo esté tan bien mezclado en cada ronda que esto no sea un problema. r = 8 está muy por debajo de este umbral potencial para el estándar N = 2 ^ 14 - para N = 2 ^ 14, este umbral sería r = 224.

Para resumir todas las recomendaciones:

Elija r para que sea lo suficientemente grande como para promediar los efectos de latencia de memoria en su dispositivo y no más. Tenga en cuenta que el valor recomendado por Colin Percival, r = 8, parece ser bastante óptimo en términos generales para la tecnología de memoria, y aparentemente esto no ha cambiado mucho en 8 años; 16 puede ser un poco mejor.
Decida qué tan grande es la cantidad de memoria que desea usar por hilo, teniendo en cuenta que esto también afecta el tiempo de cálculo y configure N en consecuencia.
Aumente p arbitrariamente alto a lo que su uso puede tolerar (nota: en mi sistema y usando mi propia implementación, p = 250 (4 hilos) con N = 16384 y r = 8 toma ~ 5 segundos), y habilite el enhebrado si puede tratar con el costo de memoria agregado.
Al sintonizar, prefiera N grande y tamaño de bloque de memoria para aumentar el tiempo p y el tiempo de cálculo. El principal beneficio de Scrypt proviene de su gran tamaño de bloque de memoria.

Un punto de referencia de mi propia implementación de Scrypt en un Surface Pro 3 con un i5-4300 (2 núcleos, 4 hilos), utilizando una constante 128Nr = 16 MB yp = 230; eje izquierdo es segundos, eje inferior es valor r, barras de error son +/- 1 desviación estándar: