Hace tiempo que conozco el sitio Have I Been Pwned (HIBP) . Es cierto, hasta hace poco, nunca había estado allí. Siempre tuve dos contraseñas. Uno de ellos fue usado repetidamente para correo basura y un par de cuentas en sitios extraños. Pero tuve que rechazarlo, porque el correo fue pirateado. Y para ser honesto, estoy agradecido con el hacker porque este evento me hizo revisar mis contraseñas, la forma en que las uso y las guardo.

Por supuesto, cambié las contraseñas en todas las cuentas donde había una contraseña comprometida. Luego me pregunté si la contraseña filtrada estaba en la base de datos HIBP. No quería ingresar la contraseña en el sitio, así que descargué la base de datos (pwned-passwords-sha1-ordered-by-count-v5) La base es muy impresionante. Este es un archivo de texto de 22.8 GB con un conjunto de hashes SHA-1, uno en cada línea con un contador, cuántas veces se produjo la contraseña con este hash en fugas. Descubrí el SHA-1 de mi contraseña descifrada e intenté encontrarla.

Contenido

[G] rep

Tenemos un archivo de texto con un hash en cada línea. Probablemente el mejor lugar para ir es grep.

grep -m 1 '^XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX' pwned-passwords-sha1-ordered-by-count-v5.txt

Mi contraseña estaba en la parte superior de la lista con una frecuencia de más de 1,500 veces, por lo que realmente apesta. En consecuencia, los resultados de búsqueda regresaron casi al instante.

Pero no todos tienen contraseñas débiles. Quería comprobar cuánto tiempo llevaría encontrar el peor de los casos: el último hash del archivo:

time grep -m 1 '^4541A1E4605EEBF3F4C166329C18502DF75D348A' pwned-passwords-sha1-ordered-by-count-v5.txt

Resultado: 33,35s user 23,39s system 41% cpu 2:15,35 total

Esto es triste. Después de todo, dado que mi correo fue pirateado, quería verificar la presencia de todas mis contraseñas antiguas y nuevas en la base de datos. Pero un grep de dos minutos simplemente no te permite hacer esto cómodamente. Por supuesto, podría escribir un script, ejecutarlo e ir a caminar, pero esta no es una opción. Quería encontrar una mejor solución y aprender algo.

Estructura Trie

La primera idea fue utilizar una estructura de datos trie. La estructura parece ideal para almacenar hash SHA-1. El alfabeto es pequeño, por lo que los nodos también serán pequeños, al igual que el archivo resultante. ¿Quizás incluso cabe en la RAM? La búsqueda clave debe ser muy rápida.

Entonces implementé esta estructura. Luego tomó los primeros 1,000,000 hashes de la base de datos de origen para construir el archivo resultante y verificar si todo está en el archivo creado.

Sí, pude encontrar todo en el archivo, por lo que la estructura funcionó bien. El problema fue diferente.

El archivo resultante se lanzó en tamaño 2283686592B (2,2 GB). Esto no está bien. Vamos a contar y ver qué pasa. Un nodo es una estructura simple de dieciséis valores de 32 bits. Los valores son "punteros" a los siguientes nodos con el símbolo hash SHA-1 especificado. Entonces, un nodo toma 16 * 4 bytes = 64 bytes. Parece ser un poco? Pero si lo piensa, un nodo representa un carácter en un hash. Por lo tanto, en el peor de los casos, el hash SHA-1 tomará 40 * 64 bytes = 2560 bytes. Esto es mucho peor que, por ejemplo, una representación textual de un hash que ocupa solo 40 bytes.

La estructura trie tiene la ventaja de reutilizar nodos. Si tiene dos palabras aaay abb, entonces el nodo para los primeros caracteres se reutiliza, porque los caracteres son iguales - a.

Volvamos a nuestro problema. Calculemos cuántos nodos se almacenan en el archivo resultante: file_size / node_size = 2283686592 / 64 = 35682603

ahora veamos cuántos nodos se crearán en el peor de los casos a partir de un millón de hashes: por lo 1000000 * 40 = 40000000

tanto, la estructura trie reutiliza solo 40000000 - 35682603 = 4317397nodos, que es el 10.8% del peor de los casos.

Con tales indicadores, el archivo resultante para toda la base de datos HIBP tomaría 1421513361920 bytes (1.02 TB). Ni siquiera tengo suficiente disco duro para verificar la velocidad de búsqueda clave.

Ese día, descubrí que la estructura del trie no es adecuada para datos relativamente aleatorios.

Busquemos otra solución.

Búsqueda binaria

Los hash SHA-1 tienen dos características agradables: son comparables entre sí y son todos del mismo tamaño.

Gracias a esto, podemos procesar la base de datos HIBP original y crear un archivo a partir de los valores SHA-1 ordenados.

Pero, ¿cómo ordenar un archivo de 22 GB?

Pregunta. ¿Por qué ordenar el archivo fuente? HIBP devuelve un archivo con cadenas ya ordenadas por hashes.

Responder. Simplemente no lo pensé. En ese momento no sabía sobre el archivo ordenado.

Clasificación

Ordenar todos los hashes en RAM no es una opción; no tengo mucha RAM. La solución fue esta:

Divide un archivo grande en archivos más pequeños que quepan en la RAM.
Descargue datos de archivos pequeños, ordene en RAM y vuelva a escribir en los archivos.
Combina todos los archivos pequeños y ordenados en uno grande.

Con un archivo ordenado grande, puede buscar nuestro hash utilizando una búsqueda binaria. El acceso al disco duro es importante. Calculemos cuántos resultados se requieren en una búsqueda binaria: log2(555278657) = 29.0486367039es decir, 30 resultados. No es tan malo.

En la primera etapa, se puede realizar la optimización. Convierte hashes de texto en datos binarios. Esto reducirá el tamaño de los datos resultantes a la mitad: de 22 a 11 GB. Multa.

¿Por qué fusionarse de nuevo?

En ese momento, me di cuenta de que puedes hacerlo de manera más inteligente. ¿Qué sucede si no combina archivos pequeños en uno grande, sino que realiza una búsqueda binaria en archivos pequeños ordenados en RAM? El problema es cómo encontrar el archivo deseado en el que buscar la clave. La solución es muy simple. Nuevo enfoque:

Cree 256 archivos con los nombres "00" ... "FF".
Cuando lea hashes de un archivo grande, escriba hash que comiencen con “00 ..” en un archivo llamado “00”, hash que comiencen con “01 ..” - en un archivo “01” y así sucesivamente.
Descargue datos de archivos pequeños, ordene en RAM y vuelva a escribir en los archivos.

Todo es muy simple. Además, aparece otra opción de optimización. Si el hash está almacenado en el archivo "00", entonces sabemos que comienza con "00". Si el hash se almacena en el archivo "F2", comienza con "F2". Por lo tanto, al escribir hash en archivos pequeños, ¡podemos omitir el primer byte de cada hash! Este es el 5% de todos los datos. 555 MB se guardan en total.

Paralelismo

La separación en archivos más pequeños ofrece otra oportunidad para la optimización. Los archivos son independientes entre sí, por lo que podemos ordenarlos en paralelo. Recordamos que a todos sus procesadores les gusta sudar al mismo tiempo;)

No seas un bastardo egoísta

Cuando implementé la solución anterior, me di cuenta de que otras personas probablemente tenían un problema similar. Probablemente muchos otros también descarguen y busquen en la base de datos HIBP. Entonces decidí compartir mi trabajo.

Antes de eso, una vez más revisé mi enfoque y encontré un par de problemas que me gustaría solucionar antes de publicar el código y las herramientas en Github.

En primer lugar, como usuario final, no quisiera utilizar una herramienta que crea muchos archivos extraños con nombres extraños, en los que no está claro qué está almacenado, etc.

Bueno, esto se puede resolver combinando los archivos "00" .. "FF" en Un gran archivo.

Desafortunadamente, tener un archivo grande para ordenar plantea un nuevo problema. ¿Qué sucede si quiero insertar un hash en este archivo? Solo un hash. Esto es solo 20 bytes. Oh, el hash comienza con "000000000 ..". Bueno. Liberemos espacio para él moviendo 11 GB de otros hashes ...

Entiende cuál es el problema. Insertar datos en el medio de un archivo no es la operación más rápida.

Otro inconveniente de este enfoque es que necesita almacenar los primeros bytes nuevamente: son 555 MB de datos.

Y por último, pero no menos importante, una búsqueda binaria en los datos almacenados en un disco duro es mucho más lenta que acceder a la RAM. Quiero decir, esto es 30 lecturas de disco versus 0 lecturas de disco.

B3

De nuevo. Lo que tenemos y lo que queremos lograr.

Tenemos 11 GB de valores binarios. Todos los valores son comparables y tienen el mismo tamaño. Queremos averiguar si una clave particular está presente en los datos almacenados, y también queremos cambiar la base de datos. Y para que todo funcione rápidamente.

B-árbol? Derecha

El árbol B le permite minimizar el acceso al disco cuando busca, modifica, etc. Tiene muchas más funciones, pero necesitamos estas dos.

Tipo de inserción

El primer paso es convertir los datos del archivo fuente HIBP al árbol B. Esto significa que debe extraer todos los hashes a su vez e insertarlos en la estructura. El algoritmo de inserción habitual es adecuado para esto. Pero en nuestro caso, puedes hacerlo mejor.

Insertar una gran cantidad de datos en bruto en un árbol B es un escenario bien conocido. Las personas sabias han inventado un mejor enfoque para esto que el inserto habitual. En primer lugar, debe ordenar los datos. Esto se puede hacer como se describió anteriormente (dividir el archivo en archivos más pequeños y ordenarlos en RAM). Luego inserte los datos en el árbol.

En el algoritmo habitual, si encuentra el nodo hoja donde desea insertar el valor y se llena, entonces crea un nuevo nodo (a la derecha) y distribuye uniformemente los valores entre los dos nodos, izquierdo y derecho (más un valor va al nodo principal pero no es importante aquí). En resumen, los valores en el nodo izquierdo son siempre menores que los valores en el derecho. El hecho es que cuando inserta los datos ordenados, sabe que los valores más pequeños ya no se insertarán en el árbol, por lo tanto, no más valores irán al nodo izquierdo. El nodo izquierdo permanece medio vacío todo el tiempo. Además, si inserta suficientes valores, puede encontrar que el nodo derecho está lleno, por lo que debe mover la mitad de los valores al nuevo nodo derecho. El nodo dividido permanece medio vacío, como en el caso anterior. Etc ...

Como resultado, después de todas las inserciones, obtienes un árbol en el que casi todos los nodos están medio vacíos. Este no es un uso muy eficiente del espacio. Podemos hacerlo mejor.

¿Separado o no?

En el caso de insertar datos ordenados, puede realizar una pequeña modificación en el algoritmo de inserción. Si el nodo en el que desea pegar el valor está lleno, no lo rompa. Simplemente cree un nuevo nodo vacío y pegue el valor en el nodo principal. Luego, cuando inserta los siguientes valores (que son más grandes que los anteriores), los inserta en un nodo nuevo y vacío.

Para preservar las propiedades del árbol B, después de todas las inserciones, es necesario ordenar los nodos más a la derecha en cada capa del árbol (excepto la raíz) y dividir equitativamente los valores de este nodo extremo y su vecino izquierdo. Entonces obtienes el árbol más pequeño posible.

Propiedades del árbol HIBP

Al diseñar un árbol B, debe elegir su orden. Muestra cuántos valores se pueden almacenar en un nodo, así como cuántos hijos puede tener el nodo. Al manipular este parámetro, podemos manipular la altura del árbol, el tamaño binario del nodo, etc.

En HIBP, tenemos 555278657hashes. Supongamos que queremos un árbol de tres en altura (por lo que no necesitamos más de tres operaciones de lectura para verificar la presencia de un hash). Necesitamos encontrar un valor de M tal que logM(555278657) < 3. Elegí 1024. Este no es el valor más pequeño posible, pero permite insertar más hashes y preservar la altura del árbol.

Archivo de salida

El archivo fuente HIBP tiene un tamaño de 22.8 GB. El archivo de salida con el árbol B es de 12,4 GB. Se tarda unos 11 minutos en crearlo en mi máquina (Intel Core i7-6700, 3,4 GHz, 16 GB de RAM), disco duro (no SSD).

Puntos de referencia

La opción B-tree muestra un resultado bastante bueno:

El | El | tiempo [μs] | % |
| -----------------: | ------------: | ------------: |
El | okon | 49 100
El | grep '^ hash' | 135'350'000 | 276'224'489 |
El | grep | 135'480'000 | 276'489'795 |
El | C ++ línea por línea | 135'720'201 | 276'980'002 |

okon - biblioteca y CLI

Como dije, quería compartir mi trabajo con el mundo. Implementé una biblioteca y una interfaz de línea de comandos para procesar la base de datos HIBP y buscar rápidamente hashes. La búsqueda es tan rápida que puede, por ejemplo, integrarse en un administrador de contraseñas y dar retroalimentación al usuario cada vez que se presiona una tecla. Hay muchos usos posibles.

La biblioteca tiene una interfaz C, por lo que se puede usar en casi todas partes. CLI es un CLI. Simplemente puede compilar y ejecutar (:

El código está en mi repositorio .

Descargo de responsabilidad: okon aún no proporciona una interfaz para insertar valores en el árbol B creado. Solo puede procesar el archivo HIBP, crear un árbol B y buscar en él. Estas funciones funcionan bastante bien, así que decidí compartir el código y continuar trabajando en la inserción y otras funciones posibles.

Acelere su búsqueda en ¿Me han llevado a 49 microsegundos (C ++)