- La propiedad crítica de tiempo constante (constant-time) en código criptográfico puede romperse solo con optimizaciones del compilador, por lo que se hizo un experimento para detectar patrones riesgosos incorporando un parche de advertencias dentro de LLVM
- La “optimización” del compilador puede acelerar partes de los benchmarks, pero las rutas críticas reales suelen depender de intrinsics y ensamblador, y el costo de los bugs generados por la optimización se acumula por separado
- En junio de 2024, Antoon Purnal confirmó que el código de referencia de Kyber, con algunas opciones de optimización en Clang 15 o superior, se transformaba en ramificaciones condicionales basadas en valores secretos, lo que podía permitir ataques de temporización
- TIMECOP 2 revisa dentro de SUPERCOP los resultados compilados declarados como de tiempo constante, pero tiene límites en las instrucciones soportadas por Valgrind y en los flujos de datos expuestos durante la ejecución real de las pruebas
- La respuesta práctica pasa por usar funciones como
crypto_{int,uint}{8,16,32,64}.h para impedir que el compilador vea un resultado de 1 bit como bool, o por migrar a ensamblador verificado, lenguajes orientados a seguridad o compiladores especializados
El vacío de responsabilidad que crea la “optimización” de compiladores
- En los historiales de cambios recientes de LLVM y GCC aparecen constantemente “optimizaciones”, pruebas de “optimización”, correcciones de pruebas y arreglos de bugs de “optimización”
- Cuando código que funcionaba bien antes de compilarse cambia después de una modificación del compilador, en muchos casos la responsabilidad recae en el programador por haber pisado “undefined behavior”
- Estos “language standards” son creados por autores de compiladores y, como resultado, la estructura hace que el código de millones de programadores cargue con más responsabilidad que los cambios de un pequeño grupo de autores de compiladores
- Como ejemplo en código criptográfico, en varios benchmarks de CPU, la implementación
avx2 de kyber768 es aproximadamente 4 veces más rápida que el código portable compilado con compiladores de “optimización”
Límites de la medición de rendimiento de las optimizaciones
- En 2000, Todd A. Proebsting formuló en Proebsting's Law que “los avances de los compiladores duplican la potencia de cómputo cada 18 años”, y concluyó que el aporte de la optimización de compiladores era marginal
- Arseny Kapoulkine resumió en un benchmark de 2022 que LLVM 11 tarda el doble que LLVM 2.7 en compilar con optimización, y que el código ejecutado es en general 10% a 20% más rápido
- Ambas discusiones omiten medir el rendimiento que perciben los usuarios reales
- En los hotspots donde se concentra el rendimiento hay muchos intrinsics y ensamblador
- FFmpeg tiene 160,000 líneas de ensamblador contando archivos
.asm y .S
- A medida que las computadoras y las redes procesan más datos, el tiempo real de CPU se concentra cada vez más en esos hotspots
- Los costos de seguridad también crecen por separado en la discusión sobre optimización
- Deloitte informó que en 2023 el presupuesto de seguridad de TI era el 0.5% de los ingresos empresariales
- Si se lo mira junto con la cifra de que los ingresos totales de las empresas del mundo superaron los 48 billones de dólares en 2022, la escala total podría estar en cientos de miles de millones de dólares
- Sin embargo, existe la salvedad de que el 0.5% de Deloitte podría ser un promedio simple por empresa y que no todas las empresas respondieron la encuesta
Fugas de temporización y el caso Kyber
- Los problemas de seguridad que crean los compiladores de “optimización” incluyen no solo bugs tradicionales, sino también fugas de temporización, donde información secreta se filtra a través del tiempo de ejecución
- El paper de EuroS&P 2018 de Laurent Simon, David Chisnall y Ross Anderson advirtió que una actualización del compilador puede abrir sin aviso un canal de temporización en código que antes era seguro
- El ejemplo destacado en el paper de 2018 era código que elegía uno de dos valores con un
bool, y el bool provocaba que el compilador generara saltos condicionales
- En implementaciones criptográficas, para evitar esto existe la práctica de eliminar
bool del código crítico y crear funciones separadas de comparación en tiempo constante
- Se cita que OpenSSL declara 37 funciones para esto
- El caso de 2015 de
curve25519-donna y MSVC 2015 se presenta en el texto como un malentendido
- En realidad, al compilar para x86 de 32 bits, las operaciones
int64 se transformaban en llamadas a llmul.asm, la biblioteca int64 de 32 bits de Microsoft
- La fuga de temporización se originaba en ramificaciones dependientes de datos dentro de
llmul.asm, y se considera que esa biblioteca también debería incluirse dentro de un concepto razonable de código fuente
- En junio de 2024, Antoon Purnal confirmó que el código de referencia de Kyber podía permitir ataques de temporización con algunas opciones de optimización en Clang 15 o superior
- La forma problemática era
(-((x>>j)&1))&y, un cálculo que produce y si el bit j de x está activado, o 0 en caso contrario
- Clang convertía ese bit en un
bool mediante una instrucción de prueba de bits y luego generaba una ramificación condicional basada en ese bool
- Dentro de LLVM,
combineShiftAnd1ToBitTest en lib/CodeGen/SelectionDAG/DAGCombiner.cpp procesa esta “optimización”
- Sanjay Patel agregó esta función en septiembre de 2019, y luego fue modificada por varias personas
- GCC también tiene casos similares de cruce de límites
- Un parche de GCC de ARM de noviembre de 2021 cambia
(-x)>>31 por -(x>0)
- En abril de 2024 apareció una advertencia al respecto
TIMECOP e inspección de tiempo constante
- TIMECOP 2 está integrado en el framework de pruebas criptográficas SUPERCOP y revisa automáticamente si en código compilado declarado como de tiempo constante hay ramificaciones condicionales derivadas de valores secretos
- Los objetivos de inspección incluyen, además de ramificaciones condicionales, índices de arreglos derivados de valores secretos
- El paper de KyberSlash también describe un parche que inspecciona divisiones derivadas de valores secretos
- TIMECOP 1 era una herramienta creada por Moritz Neikes al modificar SUPERCOP, automatizando el enfoque ctgrind de Adam Langley
- TIMECOP 2 amplía el método anterior de varias maneras
- Marca automáticamente la salida del RNG como valor secreto
- Soporta “declassification”
- Soporta especificar “public inputs”
- Se ejecuta en varios núcleos
- TIMECOP tiene límites claros
- Solo puede manejar instrucciones soportadas por Valgrind, por lo que se detiene con instrucciones como AMD XOP
- Solo inspecciona los flujos de datos visibles durante la ejecución real de las pruebas
- El trabajo en herramientas para verificar comportamiento de tiempo constante continúa, y hay una lista de herramientas relacionadas en ct-tools
- Una inspección equivalente a TIMECOP se incorporó al conjunto de pruebas de libmceliece y podría extenderse a otras bibliotecas
Métodos de reescritura en tiempo constante
- Después de encontrar fragmentos de código de tiempo variable, se necesita una forma de reescribirlos en tiempo constante sin introducir bugs
- En la presentación de julio de 2024 se introdujeron algunas funciones de tiempo constante provistas por libmceliece y SUPERCOP
- Los nombres de archivo son
crypto_{int,uint}{8,16,32,64}.h
- Estos archivos pueden copiarse y usarse en otros proyectos
- La función de ejemplo
crypto_uint32_bitmod_mask(x,j) tiene un efecto equivalente a -((x>>(j&31))&1), pero evita que el compilador vea el resultado de 1 bit
- Otro ejemplo más complejo es
crypto_uint32_max(x,y)
- El paper de 2018 trata un tweak que agrega a Clang/LLVM la función de tiempo constante
__builtin_ct_choose(bool cond, x, y)
- Ese paper sugería erróneamente que esta sola función bastaba
- Es posible que esta función entre algún día en el compilador, pero puede pasar mucho tiempo antes de que los proyectos puedan depender de ella
- Se evalúa que su forma de implementación parece más frágil que
crypto_{int,uint}{8,16,32,64}.h
Cómo evitar el problema de antemano
- Si las pruebas previas a la distribución de una biblioteca compilada detectan fugas de temporización introducidas por el compilador, se puede usar la versión anterior del compilador para distribuir mientras se reescribe el código
- Este método es una respuesta temporal para mantener seguros a los usuarios
- Una solución es distribuir la biblioteca en ensamblador
- La presentación de RWC 2024 Adoption of high-assurance and highly performant cryptographic algorithms at AWS presentó software rápido de X25519 con prueba de que calcula correctamente X25519 para todas las entradas
- La implementación está escrita en ensamblador en dos versiones para CPU Intel/AMD de 64 bits y dos versiones para CPU ARM de 64 bits
- La proposición de corrección es un teorema sobre el código máquina que los usuarios ejecutan realmente, y la prueba fue verificada con el demostrador de teoremas HOL Light
- Sin embargo, en software criptográfico que no alcanza ese nivel, sigue existiendo el problema de la dificultad de auditar ensamblador
- También se exploran formas de incorporar rápidamente “vacunas” contra fugas de temporización en código escrito en C, C++ y similares
Experimento con el parche clang-vs-clang
- Lo que tienen en común
x&1 y x>>31 es que solo hay dos resultados posibles
x&1 es 0 o 1x>>31 para uint32 es 0 o 1x>>31 para int32 es 0 o -1
- En estas formas, para los autores de “optimizaciones” del compilador es fácil meter un resultado de 1 bit en un
bool
- Existe la recomendación de compilar siempre con
-fwrapv para que GCC y Clang asuman aritmética en complemento a dos
- Aunque escanear simplemente el código fuente buscando
&1, 1&, >>31 y similares encuentra muchos ejemplos, se usó otro método: incorporar un parche directamente en el “optimizer” de LLVM
- El parche parte del commit de LLVM
68df06a0b2998765cb0a41353fcf0919bbf57ddb, busca &1 y >>31, y emite la siguiente advertencia
please take this away before clang does something bad
- Un comando de compilación de ejemplo es
clang -Rpass-analysis=clang-vs-clang -O -c x.c
- La función de prueba es la siguiente
int sra31(int x)
{
x >>= 31;
return x;
}
- No sorprende que se repita la misma advertencia
- El compilador sigue intentando aplicar “optimizaciones” hasta que ya no puede avanzar
- La salida de
clang-vs-clang distingue entre signed y unsigned en shifts
- Esta diferencia es importante para reescrituras manuales o automáticas basadas en
crypto_{int,uint}{8,16,32,64}.h
- Una forma de automatizar transformaciones de fuente es usar
clang-tidy
- El código excluido por
#ifdef o eliminado antes de esta etapa de “optimización” no genera advertencias de clang-vs-clang
Resultados al ejecutar SUPERCOP y casos encontrados
- Se ejecutó SUPERCOP 20240716 en un sistema dual EPYC 7742 con
./data-do-biglittle
- El overclocking estaba desactivado
- La lista de compiladores de SUPERCOP se ajustó para usar
clang-vs-clang agregando -Rpass-analysis=clang-vs-clang a las líneas de clang en okcompilers/{c,cpp}
- Los resultados estuvieron listos después de 3 horas
- La salida de Clang tuvo en total 675,752 líneas
- El tamaño original fue de 210,786,494 bytes
- El resultado comprimido fue
20240803-fromclang.txt.gz, de 3,595,199 bytes
- En la salida hay mucho ruido producido por ramificaciones de fuente basadas en datos públicos que generan
&1 dentro de Clang
- Un ejemplo claro que vale la pena modificar preventivamente es el siguiente
a0 += (a0>>15)&106;
- Un ejemplo que requeriría esfuerzo de parsing de C para encontrarlo con un escaneo simple del fuente es el siguiente
- La macro
ONE8 está definida como ((uint8_t)1)
*pk2^=(((* pk_cp)>>ir)&ONE8)<<jr;
- Un ejemplo más difícil de encontrar aparece en macros basadas en intrinsics AVX2
signmask_x16(x) se define como _mm256_srai_epi16((x),15)- Esto hace un shift a la derecha de 15 bits en cada fragmento signed de 16 bits dentro de un vector de 256 bits
mask = signmask_x16(sub_x16(x,const_x16((q+1)/2)));
- Este caso AVX2 no tiene prioridad alta
- Para que una operación vectorial se convierta en una ramificación condicional habría que compilar con AVX-512, y que el compilador tome la extraña decisión de convertir un
bool vectorizado en una ramificación condicional de bool serial
- TIMECOP usa Valgrind, y Valgrind no soporta AVX-512
- Por ahora no se recomienda compilar con AVX-512
int128 y una dirección más amplia de respuesta
- El hallazgo más interesante fue un caso donde un shift a la derecha de 64 bits en
int128 generó una advertencia de >>
- La implementación de
int128 puede usar internamente un shift a la derecha de 63 bits para averiguar el signo de la palabra superior de 64 bits
- Si Clang agrega, como GCC, soporte para convertir un shift a la derecha de 63 bits en
bool y luego en una ramificación condicional, mucho código int128 podría volverse de pronto de tiempo variable
- En ese caso, la situación se parecería a lo afirmado por el título del paper de 2015, pero esta vez ocurriría realmente aunque no haya
bool en el código fuente
- La forma más fácil de protección a nivel de fuente es evitar la implementación existente de
int128 del compilador y usar funciones crypto_int128
crypto_int128, a diferencia de int128 de GCC y Clang, también puede funcionar en plataformas pequeñas de 32 bits
- Agregar tipos de datos secretos a GCC y Clang parece una buena idea, pero no se ve una forma clara de hacerlo robusto dadas las estructuras de ambos compiladores
- Hay más expectativas en compiladores diseñados desde el principio para seguridad
- Entre los compiladores centrados en seguridad que exigen un nuevo lenguaje de entrada están FaCT y Jasmin, que está en desarrollo activo
- Aunque preocupa el tiempo necesario para reescribir código, viendo cómo los compiladores actuales tratan el código existente, hace falta tomar medidas de alguna forma
1 comentarios
Opiniones de Hacker News
No corresponde llamar bug del compilador a que un código con comportamiento indefinido no funcione como uno quiere.
Es parecido a ejecutar
ddcon argumentos incorrectos, borrar tus datos y luego decir queddtiene un bug.Es difícil decir que el código fuente o el compilador tengan un bug; más bien, corresponde ver que el estándar de C, según el criterio del autor, está demasiado poco especificado y genera bugs de seguridad en algunos objetivos.
Al final, los autores del estándar de C no pueden definir hasta el comportamiento del hardware, solo la semántica del lenguaje, así que el área de criptografía no tiene más remedio que sufrir por bugs atribuibles al hardware.
Una de las ventajas de Rust es que limita el comportamiento potencialmente indefinido a bloques
unsafe. Aun así, aunque Rust define muchas cosas que en C serían comportamiento indefinido, cuando uno entra en códigounsafees muy fácil pisar por accidente algún comportamiento indefinido sutil.Un tercer modelo que falla en silencio y genera código impredecible solo es útil para quienes escriben compiladores. Esconderse detrás de la especificación no beneficia a los usuarios reales.
Esa optimización rompe código que antes funcionaba bien. Los autores de compiladores podrían priorizar la compatibilidad hacia atrás, pero no lo hacen.
Además, como estas optimizaciones ni siquiera mejoran de forma significativa el rendimiento del código real, habría que refutar el argumento de que el trade-off de romper código no vale la pena.
Me gusta Bernstein, pero a veces se equivoca de rumbo y se pone exagerado; este artículo es un buen ejemplo. Al final del texto, él mismo lo admite a medias.
Gran parte del artículo trata un punto secundario: qué tan buenas son las ganancias de optimización, y eso, aun con datos, depende del caso de uso.
La queja central es que los compiladores de C no toman en cuenta semánticas que no se pueden expresar en el lenguaje, lo cual no debería sorprender.
Al final dice “usen un lenguaje que pueda expresar la semántica necesaria”, y todo el artículo podría haberse reemplazado por esa sola frase.
Para una buena parte de ellos, la justificación es dudosa, y hacen más difícil escribir programas correctos.
C y C++ no son adecuados para escribir algoritmos con garantías de tiempo constante.
El estándar casi no tiene concepto de tiempo real, y los compiladores tampoco ofrecen garantías adicionales mediante extensiones.
Pero culpar por esto a los desarrolladores de compiladores va por el camino equivocado.
En CPUs Intel, ni
clangni ningún otro puede generar código correcto en modo usuario, porque para empezar no existe tal código correcto.https://www.intel.com/content/www/us/en/developer/articles/t...
Si uno mira
DOITMen el documento, simplemente es imposible que una biblioteca criptográfica en espacio de usuario configure el bit necesario.Una vez activado, funciona bien también en espacio de usuario, así que podría ser, por ejemplo, un flag por proceso habilitado con una llamada al sistema
prctl, y el scheduler podría ajustar elMSRal cambiar de tarea.Con solo ver la frase “siempre que pueden, los autores de compiladores se niegan a hacerse responsables de los bugs que crearon”, rara vez la credibilidad técnica de un post de blog se derrumba tan rápido.
Si uno sigue el enlace, se trata apenas de un punto muy básico de C: que el comportamiento indefinido no significa que produzca “un valor arbitrario”.
A menudo, aunque haya comportamiento indefinido, el código fuente tiene un bug, pero el programa generado sigue siendo correcto. Luego, si el autor del compilador agrega una nueva optimización y, basándose en ese comportamiento indefinido, genera un programa con bugs, empieza la disputa sobre quién tiene la culpa.
Lo que no quieren admitir es que la responsabilidad frente al usuario está repartida entre todas las partes. Si una app CRUD provoca que se incendie una batería solo porque hizo una desreferenciación de
NULL, una persona razonable no culparía únicamente al autor de la app por haberse olvidado de verificarNULL.Los compiladores, sistemas operativos y fabricantes de hardware también deben hacerse responsables de productos diseñados de manera irresponsable; no alcanza con decir “comportamiento indefinido” según el estándar ISO. Todos los integrantes de la cadena de suministro comparten la responsabilidad de prever cómo puede usarse mal el producto y manejarlo de forma razonable.
El comportamiento indefinido existe para aportar valor. Se puede crear un lenguaje sin eso, pero existe deliberadamente por la portabilidad y por la flexibilidad que les da a los autores de compiladores.
El punto central del texto es si esa flexibilidad vale la pena en comparación con la dificultad de escribir programas sin comportamiento indefinido.
El autor considera que el dinero perdido por bugs parece ser mayor que el dinero ahorrado con bytecode más rápido, y que, como los autores de compiladores tienen mucha influencia sobre lo que entra en el estándar del lenguaje, hay poca voluntad de corregirlo.
Como referencia,
clangtiene el atributoclang::optnone, que desactiva todas las optimizaciones por función, y GCC tiene el excelente atributognu::optimize, que permite agregar o quitar optimizaciones por nombre, o fijar el nivel de optimización independientemente de los flags del compilador.gnu::optimize(0)es parecido a ese flag declang.clangtambién tieneclang::no_builtins, que desactiva específicamente las optimizaciones dememcpyymemset.optimizedebe usarse solo con fines de depuración y no es adecuado para código de producción”.https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
Hasta cierto punto simpatizo con los objetivos que quiere la gente de criptografía, como la evaluación en tiempo constante y ocultar valores secretos.
Pero un compilador de propósito general no piensa en eso la mayor parte del tiempo, así que parece difícil que pase de ser un hack que más o menos funciona.
Si se quiere hacer en serio, probablemente haga falta un compilador especializado propio, o seguir usando ensamblador.
Puede que algún día miremos esta época como los malos viejos tiempos y ya hayamos dejado C por lenguajes con mucho menos comportamiento indefinido.
En C es demasiado fácil escribir expresiones que compilan, pero cuya intención el compilador no puede conocer de ninguna manera.
Por ejemplo, en Python se puede escribir código como
result = [something(value) for value in set_object]. Como un objetosetno tiene orden, queda claro que no importan ni el orden en que se procesan los elementos ni el orden del resultado, y eso abre muchas optimizaciones a nivel del lenguaje sin que el compilador tenga que adivinar la intención del autor.Un código similar en otro lenguaje con datos inmutables va un paso más allá: como
something(value1)no puede afectar asomething(value2), puede ejecutarse en paralelo, ya sea con threads o procesos.Una parte importante de la optimización de los compiladores de C consiste en mirar patrones de código y encontrar formas de hacer más rápido lo que probablemente quiso hacer el autor. C tiene poca capacidad para expresar intención en comparación con los lenguajes modernos, así que existe libertad para especular, pero para obtener un rendimiento decente hay que hacer ese tipo de inferencias.
Aun así, quizá sea una bendición disfrazada, como cuando el telescopio Hubble necesitó anteojos. Para superar la limitación se crearon técnicas excelentes y, después de corregir el problema, esas técnicas dieron un rendimiento mucho mayor de lo previsto originalmente. Si las optimizaciones de compiladores de C se aplicaran a lenguajes que no sean C, tal vez funcionarían como superpoderes.
En el fondo se parece al comportamiento indefinido, pero no aparece de inmediato como un problema de seguridad, sino como resultados incorrectos. Claro que un resultado incorrecto puede terminar derivando en un problema de seguridad más adelante.
A diferencia del comportamiento indefinido, en la práctica es imposible crear un “sanitizador” que verifique que el código funcione con todos los órdenes posibles de un
set.gccyclangtienen muchas pistas de bajo nivel que suelen no existir en otros lenguajes. Están__builtin_expect/__builtin_unpredictable,__builtin_unreachable/__builtin_assume,#pragma clang loop vectorize(assume_safety)/#pragma GCC ivdep, y pragmas para desactivar el desenrollado de loops o la vectorización, o para seleccionar ciertos valores, entre otros.Creo que lo que más falta es una barrera de optimización que impida explícitamente que el compilador haga inferencias basadas en el origen de un valor.
__asm__permite hacerlo hasta cierto punto, pero tiene efectos secundarios no deseados y requiere nombres de tipos de registros específicos de la plataforma.También hay un potencial claro para optimizaciones de alto nivel basadas en la intención. Pienso, por ejemplo, en reservar espacio en una lista de arreglos antes de hacer
pushnveces en un loop, fusionar búsquedas en un hashmap del tipocontains→get→putcon la misma clave, o eliminar objetos y asignaciones infiriendo localmente el comportamiento global de asignación.C está lo suficientemente cerca del hardware real como para que el programador simplemente pueda decir qué hacer, así que el compilador no necesita adivinar la intención del programador.
Los lenguajes que implementan esas optimizaciones de memoria suelen ser de la familia de Java y, para empezar, tienen una pesimización preventiva agresiva, lo que crea el incentivo para hacer esas optimizaciones. Pero ni siquiera con esa optimización logran recuperar la pérdida.
El punto es que C tampoco es gran cosa, pero lo otro es peor.
Si no te gusta la semántica de C, no te enojes con los ingenieros de compiladores: usa otro lenguaje de programación.
qhasm. Ni siquiera Zig. Esta crítica no sorprende demasiado viniendo de él.Es un texto refrescante que presenta una perspectiva que no se escucha con frecuencia. También vale la pena ver: https://gavinhoward.com/2023/08/the-scourge-of-00ub/