Circuit ORAM y rendimiento práctico

Circuit ORAM, propuesta por Wang, Chan y Shi (2015), se diseñó para minimizar el sobrecoste de ancho de banda y, al mismo tiempo, ser sencilla de implementar en marcos de computación segura (garbled circuits y secret sharing). Su innovación principal consiste en reducir el tamaño de las cubetas a Z = 2 bloques (frente a Z = 5 en Path ORAM), reduciendo a la mitad el ancho de banda y manteniendo una probabilidad de fallo insignificante. El procedimiento de expulsión se rediseñó para poder expresarse como un circuito booleano pequeño.

En Path ORAM con Z = 5, la probabilidad de desbordamiento del stash se controla teniendo varios bloques por cubeta para acomodar la asignación aleatoria de bloques a las rutas. Circuit ORAM demuestra que Z = 2 es suficiente cuando se utiliza un procedimiento de expulsión determinista (deep-first eviction) en lugar de una expulsión aleatoria. Esto reduce a la mitad el almacenamiento del servidor y el sobrecoste de comunicación en comparación con Path ORAM con los mismos parámetros de seguridad.

Circuit ORAM se diseñó específicamente para contar con un procedimiento de expulsión que pueda expresarse como un circuito booleano eficiente. En los protocolos de computación segura (garbled circuits, SPDZ), el propio acceso ORAM debe evaluarse de forma oblivious: el servidor que realiza el cálculo no debe saber a qué ubicación de memoria se accede. El sencillo circuito de expulsión determinista de Circuit ORAM es mucho más eficiente de convertir en un circuito garbled que el procedimiento de expulsión de Path ORAM.

Para una base de datos de N bloques de B bytes, Circuit ORAM requiere 2 * log N * B bytes por acceso (leer y escribir una ruta con Z = 2 bloques por cubeta). Para N = 2^20 bloques de 4KB cada uno, esto supone 160KB por acceso, frente a los 400KB de Path ORAM (Z=5). Con parámetros habituales, el sobrecoste de ancho de banda frente al texto plano es de aproximadamente 40x, frente al 100x de Path ORAM.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) utiliza Circuit ORAM para construir versiones oblivious de estructuras de datos de alto nivel: listas enlazadas oblivious, mapas oblivious (tablas hash) y colas de prioridad oblivious. Estas estructuras permiten realizar computación oblivious sobre datos dinámicos sin revelar los patrones de acceso. Oblix se ejecuta dentro de enclaves Intel SGX y está orientado a la intersección privada de conjuntos y a consultas privadas a bases de datos.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) amplía Path ORAM para admitir accesos asíncronos de alto rendimiento mediante el procesamiento paralelo de múltiples solicitudes ORAM y la agrupación por lotes de las expulsiones de rutas. Al combinar los accesos a la misma ruta, TaoStore logra un rendimiento significativamente mayor (solicitudes por segundo) que las construcciones ORAM síncronas, lo que lo hace adecuado para servidores de almacenamiento en la nube con muchos clientes simultáneos.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) construye un sistema de almacenamiento transaccional completo sobre Path ORAM. Obladi admite transacciones ACID sobre un almacenamiento cifrado que oculta los patrones de acceso. Introduce la ejecución diferida: las transacciones se agrupan en épocas y se ejecutan de forma que se oculta a qué registros específicos se accedió dentro de cada época. Obladi se ejecuta como un proxy confiable entre los clientes y un backend de almacenamiento en la nube no confiable.

Para un ORAM de 1 GB (262.144 bloques de 4 KB) implementado en AWS, con un cliente que accede a los bloques a través de Internet, la latencia de Path ORAM es de aproximadamente 50-200 ms por acceso (determinada principalmente por el tiempo de ida y vuelta de los accesos a los buckets de log N = 18). Con la recuperación paralela de los buckets, este tiempo puede reducirse. En aplicaciones SGX locales con ORAM en RAM, la latencia oscila entre 1 y 10 ms por acceso, lo que resulta aceptable para muchas aplicaciones de computación segura.

La sobrecarga de ancho de banda de ORAM depende en gran medida de los patrones de acceso. En un ORAM de almacenamiento en la nube de 1 TB con bloques de 1 MB, cada acceso transfiere aproximadamente 25 MB (una sobrecarga de 25 veces para los 25 niveles de log N = 25). En el caso de bloques pequeños (4 KB), la sobrecarga por acceso es menor en bytes absolutos, pero mayor en términos relativos. Las organizaciones que implementen ORAM deben presupuestar una amplificación del ancho de banda de entre 20 y 50 veces y asegurarse de que sus enlaces de red y los costes de salida de datos de la nube lo tengan en cuenta.

Una alternativa a ORAM para proteger la privacidad de los accesos es el hardware confiable: Intel SGX o AMD SEV proporcionan un entorno de ejecución confiable en el que ni siquiera el sistema operativo anfitrión puede observar la computación o los patrones de acceso a la memoria (con las defensas adecuadas). SGX sin ORAM sigue filtrando al hardware los patrones de acceso a nivel de página, por lo que se necesita ORAM dentro de SGX para obtener una protección completa. En comparación con ORAM puro, el hardware confiable reduce la sobrecarga de ancho de banda, pero exige confiar en el fabricante del hardware y en la cadena de suministro.

ORAM resulta apropiado cuando: el adversario observa los patrones de acceso del lado del servidor (el proveedor de la nube o un coarrendatario), la sensibilidad de los datos justifica una sobrecarga del ancho de banda de entre 20 y 50 veces, y el propio patrón de acceso podría revelar información confidencial. Para la mayoría de las aplicaciones, el cifrado estándar con una gestión cuidadosa de las claves es suficiente. ORAM es una herramienta especializada para escenarios de alta seguridad, como el análisis de datos médicos, el aprendizaje automático privado, los sistemas de negociación financiera y las bases de datos de organismos encargados de hacer cumplir la ley.

Circuit ORAM reduce el tamaño del bucket a Z=2 (frente a Z=5 en Path ORAM), lo que reduce a la mitad el ancho de banda mediante una expulsión determinista en profundidad. Está diseñado para utilizarse dentro de la computación segura con circuitos garbled. La sobrecarga práctica es una amplificación del ancho de banda de 40 veces con parámetros habituales. Entre los sistemas de producción se incluyen Oblix (SGX + estructuras de datos con ocultación de patrones de acceso), TaoStore (ORAM por lotes de alto rendimiento) y Obladi (ORAM transaccional). ORAM dentro de SGX es necesario porque SGX por sí solo filtra los patrones de acceso a nivel de página.