¿La especulación de dependencia de la memoria impide que BN_consttime_swap sea de tiempo constante?

assembly openssl (3)

Contexto

La function BN_consttime_swap en OpenSSL es una cosa de belleza. En este fragmento, la condition se ha calculado como 0 o (BN_ULONG)-1 :

#define BN_CONSTTIME_SWAP(ind) / do { / t = (a->d[ind] ^ b->d[ind]) & condition; / a->d[ind] ^= t; / b->d[ind] ^= t; / } while (0) … BN_CONSTTIME_SWAP(9); … BN_CONSTTIME_SWAP(8); … BN_CONSTTIME_SWAP(7);

La intención es que a fin de garantizar que las operaciones bignum de nivel superior tomen tiempo constante, esta función intercambie dos bignums o los deje en su lugar en tiempo constante. Cuando los deja en su lugar, en realidad lee cada palabra de cada bignum, calcula una nueva palabra que es idéntica a la palabra antigua y escribe el resultado en la ubicación original.

La intención es que esto lleve el mismo tiempo que si se hubieran intercambiado los grandes.

En esta pregunta, asumo una arquitectura moderna y generalizada como las descritas por Agner Fog en sus manuales de optimización . También se asume la traducción directa del código C al ensamblaje (sin que el compilador C deshaga los esfuerzos del programador).

Pregunta

Estoy tratando de entender si la construcción anterior se caracteriza como un tipo de ejecución constante de "mejor esfuerzo", o como ejecución perfecta de tiempo constante.

En particular, me preocupa el escenario donde bignum a ya está en el caché de datos L1 cuando se llama a la función BN_consttime_swap , y el código justo después de que la función retorna comienza a trabajar en el bignum a inmediato. En un procesador moderno, puede haber suficientes instrucciones en vuelo al mismo tiempo para que la copia no se termine técnicamente cuando se usa el bignum a . El mecanismo que permite que las instrucciones después de la llamada a BN_consttime_swap para trabajar en a BN_consttime_swap de dependencia de memoria es. Asumamos especulaciones de dependencia de memoria ingenua por el bien del argumento.

Lo que la pregunta parece reducirse a esto es:

Cuando el procesador finalmente detecta que el código después de BN_consttime_swap lee de la memoria que, contrariamente a la especulación, se escribió dentro de la función, ¿cancela la ejecución especulativa tan pronto como detecta que la dirección se ha escrito o permite ¿Se mantiene a sí mismo cuando detecta que el valor que se ha escrito es el mismo que el que ya existía?

En el primer caso, parece que BN_consttime_swap implementa el tiempo constante perfecto. En el segundo caso, solo es el tiempo constante de mejor esfuerzo: si no se intercambiaron los bignums, la ejecución del código que viene después de la llamada a BN_consttime_swap será considerablemente más rápida que si hubiera sido intercambiada.

Incluso en el segundo caso, esto es algo que parece que podría solucionarse en el futuro inmediato (siempre que los procesadores permanezcan lo suficientemente ingenuos) por cada palabra de cada uno de los dos grandes nombres, escribiendo un valor diferente de los dos posibles finales valores antes de volver a escribir el valor antiguo o el nuevo valor. Es posible que el calificador de tipo volatile deba involucrarse en algún momento para evitar que un compilador ordinario optimice en exceso la secuencia, pero aún así suena posible.

NOTA: Sé sobre el reenvío de tiendas , pero el reenvío de tiendas es solo un acceso directo. No impide que se ejecute una lectura antes de la escritura que se supone que debe seguir. Y en algunas circunstancias falla, aunque uno no lo esperaría en este caso.

También se asume la traducción directa del código C al ensamblaje (sin que el compilador C deshaga los esfuerzos del programador).

Sé que no es la idea central de tu pregunta, y sé que sabes esto, pero necesito una perorata por un minuto. Esto ni siquiera califica como un intento de "mejor esfuerzo" para proporcionar ejecución constante. Un compilador tiene licencia para verificar el valor de la condition y omitir todo si la condition es cero. El ofuscar la configuración de la condition hace que esto sea menos probable, pero no es garantía.

El código supuestamente de "tiempo constante" no debe escribirse en C, punto final. Incluso si es tiempo constante hoy, en los compiladores que pruebes, un compilador más inteligente aparecerá y te derrotará. Uno de sus usuarios usará este compilador antes que usted, y no será consciente del riesgo al que los ha expuesto. Estoy al tanto de exactamente tres formas de lograr un tiempo constante: hardware dedicado, ensamblaje o un DSL que genera código de máquina más una prueba de ejecución de tiempo constante.

Dejando a un lado, en la pregunta de arquitectura actual: asumiendo un compilador estúpidamente ingenuo, este código es un tiempo constante en los µarches con los que estoy lo suficientemente familiar como para evaluar la pregunta, y espero que sea cierto en general por una sencilla razón: poder. Espero que comprobar en la cola de la tienda o en la memoria caché si un valor que se está almacenando coincide con el valor ya existente y con un cortocircuito condicional de la tienda o evitando ensuciar la línea de la memoria caché en cada tienda consume más energía de la que se ahorraría en las raras ocasiones en las que obtiene para evitar algún trabajo. Sin embargo, no soy un diseñador de CPU, y no pretendo hablar en su nombre, así que tome esto con varias cucharadas de sal, y consulte uno antes de asumir que esto es cierto.

Esta publicación de blog , y los comments hechos por el autor, Henry, sobre el tema de esta pregunta deben considerarse como autoritativos como cualquier persona debería esperar. Reproduciré este último aquí para archivar:

No pensé que el caso de sobrescribir una ubicación de memoria con el mismo valor tuviera un uso práctico. Creo que la respuesta es que en los procesadores actuales, el valor de la tienda es irrelevante, solo la dirección es importante.
Aquí en el mundo académico, he oído hablar de dos enfoques para hacer la desambiguación de la memoria: basada en la dirección o basada en el valor. Que yo sepa, todos los procesadores actuales hacen desambiguación basada en direcciones.
Creo que la marca microbiológica actual tiene alguna evidencia de que el valor no es relevante. Muchos de los casos involucran el almacenamiento repetido del mismo valor en la misma ubicación (particularmente aquellos con desplazamiento = 0). Estos no fueron anormalmente rápidos.
Los esquemas basados en direcciones utilizan una cola de almacenamiento y una cola de carga para rastrear las operaciones de memoria pendientes. Las cargas comprueban la cola de la tienda para una coincidencia de direcciones (¿Debería esta carga hacer el reenvío de la tienda a la carga en lugar de leer desde la memoria caché?), Mientras que las tiendas comprueban la cola de la carga (¿Acaso esta tienda marcó la ubicación de una carga posterior que permití ejecutar? ¿temprano?). Estas verificaciones se basan completamente en direcciones (donde un almacén y una carga colisionaron). Una de las ventajas de este esquema es que es una extensión bastante sencilla en la parte superior del reenvío de almacenamiento a carga, ya que la búsqueda de la cola de almacenamiento también se usa allí.
Los esquemas basados en valores eliminan la búsqueda asociativa (es decir, más rápido, menor potencia, etc.), pero requieren un mejor predictor para realizar el reenvío de almacenamiento a carga (ahora tiene que adivinar si y dónde reenviar, en lugar de buscar) la SQ). Estos esquemas verifican las infracciones del pedido (y el reenvío incorrecto) al volver a ejecutar las cargas en el momento del compromiso y verificar si sus valores son correctos. En estos esquemas, si tiene una tienda conflictiva (o cometió algún otro error) que aún resultó en el valor de resultado correcto, no se detectaría como una violación de orden.
¿Podrían los futuros procesadores pasar a esquemas basados en valores? Sospecho que podrían. Se propusieron a mediados de la década de 2000 (?) Para reducir la complejidad del hardware de ejecución de memoria.

La idea detrás de la implementación de tiempo constante no es realizar todo en tiempo constante. Eso nunca sucederá en una arquitectura fuera de orden. El requisito es que no se pueda revelar información secreta mediante el análisis de tiempo. Para evitar esto hay básicamente dos requisitos:

a) No use nada secreto como una condición de parada para un bucle, o como un predicado a una rama. Si no lo hace, lo abrirá a un ataque de predicción de rama https://eprint.iacr.org/2006/351.pdf

b) No utilice nada secreto como un índice para acceder a la memoria. Esto conduce a ataques de tiempo de caché http://www.daemonology.net/papers/htt.pdf

En cuanto a su código: asumiendo que su secreto es "condición" y posiblemente el contenido de a y b, el código es perfectamente constante en el sentido de que su ejecución no depende del contenido real de a, b y la condición. Por supuesto, la localidad de ayb en la memoria afectará el tiempo de ejecución del bucle, pero no los CONTENIDOS que son secretos. Eso es asumiendo que la condición del curso fue computada en una forma de tiempo constante. En cuanto a las optimizaciones de C: el compilador solo puede optimizar el código basado en la información que conoce. Si la "condición" es verdaderamente secreta, el compilador no debería poder discernir su contenido y optimizarlo. Si se puede deducir de su código, entonces el compilador probablemente realizará la optimización para el caso 0.