Indexación de datos encriptados para una búsqueda eficiente

Question

Indexación de datos encriptados para una búsqueda eficiente

#1 de Tom Leek (2 votos)

0

He implementado el cifrado para ciertas columnas en una base de datos. En algunos casos, puede ser necesario buscar por estas columnas, ya sea para coincidencias exactas o para subcadenas. En este momento, hay menos de 10000 filas para buscar (como máximo). Sin embargo, esto probablemente cambiará en el futuro, por lo que estoy anticipando problemas de eficiencia.

Los datos permanecerán cifrados en la base de datos, pero cuando los recupere la aplicación, se podrán descifrar. Esto significa que la recuperación no tiene que ser 100% precisa, puede recuperar más registros que realmente coinciden con la consulta, y la aplicación en sí puede descartar los registros no coincidentes.

Con esto en mente, se me ocurrieron las siguientes soluciones:

Para una coincidencia exacta del texto, haga un hash de los datos cifrados y modúelo esto con un número relativamente bajo (2 ^ 16 quizás), y almacene ese valor en una columna adicional. Al consultar la base de datos, solo es necesario realizar la misma operación en la cadena de entrada y recuperar todos los registros con el valor hash correspondiente.
Para buscar subcadenas, haga clic en cada letra y modifique el resultado. A continuación, establezca el bit correspondiente en un número entero. Realice la misma operación en la cadena de consulta. Por lo tanto, solo es necesario recuperar registros en los que el resultado de un AND binario en la consulta con el valor almacenado sea mayor que 0. Esto también podría hacerse usando cada par de letras, quizás con un entero de 64 bits o más para permitir más registros para ser descartados.

Mi pregunta es, ¿alguna de estas técnicas tendría un impacto real en la seguridad de los datos en las columnas cifradas? El esquema de encriptación es AES-256.

encryption databases

pregunta Slicedpan 06.11.2014 - 16:11

fuente

1 respuesta

Lea otras preguntas en las etiquetas encryption databases

¿Por qué la dirección IP debe aparecer como un nombre de DNS en los certificados SAN / UCC? Página infectada de Drupal 6 con un shell php

score 2 · Answer 1

La capacidad de reducir las búsquedas tiende a estar en oposición directa con la confidencialidad que busca a través del cifrado. Por ejemplo, si almacena su "hash de 16 bits" en una columna adicional, el hash revela 16 bits de los datos: 16 bits indirectos, pero de todos modos, 16 bits. Un atacante que ve la base de datos puede intentar adivinar (fuerza bruta) el contenido del registro, y los 16 bits le permitirán detectar 65535 / 65536o de malas conjeturas: esta es una ventaja sustancial.

La capacidad para realizar búsquedas de subcadenas es aún peor, ya que necesariamente revela información que permite que el ataque de fuerza bruta se realice en pasos graduales (este es, de hecho, el mismo problema que autenticación parcial de contraseña ).

En el mejor de los casos, lo que podría hacer es implementar el cifrado determinista , de manera que el cifrado de un valor de registro dado siempre produzca el mismo resultado cifrado. Esto filtra un mínimo de información (si dos registros tienen el mismo contenido, esto se mostrará, a pesar de la capa de cifrado); por otro lado, permite búsquedas exactas: usted cifra el valor para buscar y usa el índice en los valores cifrados. Sin embargo, las búsquedas de subcadenas deben evitarse a toda costa.

Creo que un método mejor sería revisar sus suposiciones:

Sin embargo, esto probablemente cambiará en el futuro, por lo que estoy anticipando problemas de eficiencia.

Por lo general, los problemas de rendimiento no existen hasta que se han encontrado realmente (al menos en una plataforma de prueba, si no están en producción) y se miden debidamente. Como escribió Donald Knuth : la optimización prematura es la raíz de todos los males .

Incluso si el problema de rendimiento previsto es real y sabes cuánto costará, podrían aplicarse algunos métodos alternativos. Por ejemplo, puede leer todos los registros en la memoria RAM de la aplicación, descifrarlos todos y mantenerlos en la memoria RAM. Esto permitiría búsquedas muy rápidas sin siquiera ir al nivel SQL. Los servidores modernos tienen mucha memoria RAM. Como ejemplo, se considera que los servidores que mantienen los sitios StackExchange (todos ellos) han sido lo suficientemente mejorados en la RAM (unos pocos cientos de gigabytes) para que todos los datos puedan almacenarse en caché, y los servidores puede realizar todos los accesos de lectura a la velocidad de la RAM.

Si sus registros tienen, digamos, no más de 100 bytes (por ejemplo, son los nombres de algunas personas), entonces puede almacenar 10 millones de valor en un simple gigabyte de RAM. ¿Qué es un gigabyte? Incluso tu teléfono tiene más memoria RAM que esa.