Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Timing Attacks

andresriancho
September 16, 2016

Timing Attacks

Incomplete research presented at Security JAM Sessions @ Buenos Aires / Ekoparty Hackerspace.

Co-Authored with Sebastian Muñiz (@_topo)

andresriancho

September 16, 2016
Tweet

More Decks by andresriancho

Other Decks in Technology

Transcript

  1. Timing Side Channels • Enviamos el mensaje M1 a un

    proceso y devuelve la respuesta R en 3ms • Enviamos el mensaje M2 al mismo proceso, devuelve nuevamente R pero esta vez tarda 6ms • Los resultados son consistentes para sucesivas mediciones del tiempo de procesamiento para M1 y M2. • Encontramos un side channel!
  2. Timing Side Channels • Si prestaron atención mientras estaban haciendo

    un análisis de seguridad de una web application seguramente notaron un timing side channel en: ◦ Login: El hash (bcrypt, pbkdf2) se calcula unicamente cuando el usuario es valido. ◦ Múltiples queries SQL (secuenciales) son ejecutadas cuando envio M1, pero no cuando envio M2. • Side channels de unos pocos milisegundos o menos son muy comunes, no siempre explotables, e imposibles de detectar “a ojo”.
  3. Tipos de Timing Attacks • String compare ◦ La diferencia

    de tiempo se genera al momento de comparar dos strings y depende de la cantidad de bytes en común desde el inicio • Application logic ◦ La diferencia en el tiempo de respuesta está dada por la lógica de la aplicación. def login(username, password): if not self.user_exists(username): return False return self.get_user_hash(username).check(password) if user_input.get('API_KEY') == MASTER_API_KEY: allow()
  4. Simple (unreal?!) test-case. Password input from serial compared with hardcoded

    value. • Microcontroller Atmega328P • Board Arduino UNO • Compiler AVR-GCC • AVR LibC * * http://download.savannah.gnu.org/releases/avr-libc/avr-libc-2.0.0.tar.bz2 Timing Attack on Embedded - Test Atmega328P
  5. Timing Attack Embedded - Test Atmega328P Optimization : None Clock

    : 16 MHz Invalid Character index • None • 5th • 2nd • 1st
  6. Timing Attack on Embedded - Test Atmega328P Optimization : Speed

    Clock : 16 MHz Invalid Character index • None • 5th • 2nd • 1st
  7. Timing Attack on Embedded - Other Systems • Clock Drift

    (affects Hardware Random Number Generator) ◦ Temperature ◦ Clock Glitching (Using CPLD & FPGA) • Side-Channel Attacks (off-topic) ◦ Power Analysis (Simple, Differential, etc.) ◦ Voltage Glitching ◦ Electromagnetic Radiation ◦ Others
  8. String Compare Timing Attacks Funcion de comparacion de strings con

    timing side channel: • timeit(compare_strings('bbb', 'aaa')) > timeit(compare_strings('b', 'aaa')) • timeit(compare_strings('aaa', 'aaa')) > timeit(compare_strings('abb', 'aaa')) def compare_strings(str_a, str_b): if len(str_a) != len(str_b): return False for i, char_a in enumerate(str_a): if str_b[i] != char_a: return False return True
  9. String Compare Timing Attacks Entonces, en un caso ideal, es

    posible explotar este side channel y realizar un ataque de fuerza bruta byte-per-byte sobre el secreto. Se envían peticiones HTTP a la aplicación con API KEYs con tamaño incremental hasta que se nota un “salto” en el tiempo que toma comparar la key enviada con MASTER_API_KEY. if compare_strings(user_input.get('API_KEY'), MASTER_API_KEY): allow()
  10. String Compare Timing Attacks Luego se realiza una fuerza bruta

    byte-per-byte: • AXXXXXXXXX • BXXXXXXXXX • CXXXXXXXXX Donde el primer byte es el que quiero descubrir y el resto es padding. Continuo probando hasta que encuentro un resultado para el cual la aplicación tarda más tiempo (compara un byte más). if compare_strings(user_input.get('API_KEY'), MASTER_API_KEY): allow()
  11. Local Jitter Hay muchas fuentes de ruido que no permiten

    medir el tiempo de ejecución con la precisión necesaria para explotar todos los timing side channels. Fuentes de ruido en la computadora desde donde se realiza la medición: 1. Context switching 2. CPU load 3. Power save 4. WiFi (no!) 5. Conexión a Internet local (switches, routers, picos de tráfico, ISP QoS) 6. Cable => Network card Ring Buffer => IRQ => Kernel => Timestamp con precisión de milisegundos
  12. Remote Jitter • “Internet” agrega mucho ruido a las mediciones

    • Fuentes de ruido en el servidor vulnerable: 1. Context switching 2. CPU load 3. Virtualización 4. SDN
  13. jitter, die! Para reducir el ruido en nuestra computadora: •

    Context switching y CPU load se soluciona utilizando isolcpus • Se deshabilita power save • Conectarse con un cable de red a Internet. Reducir lo más posible la cantidad de equipos de red entre el host e Internet. • pkill -f torrent • Compramos una placa de red que estampe tiempos en cada paquete con precisión de nanosegundos (Intel i350)
  14. CPU load remoto Un problema común es que durante unos

    segundos el equipo remoto se encuentre con mucha carga. Si medimos un evento durante ese periodo, el resultado se verá afectado. Para reducir el efecto que tiene el CPU load remoto en nuestras mediciones lo que se hace es medir de manera entrelazada y tomar como valor de la medición la diferencia entre dos mediciones consecutivas. for _ in xrange(SAMPLES): data_point = timeit('AXXXX') - timeit('BXXXX') save(data_point)
  15. Kill jitter using Si la aplicación objetivo se encuentra en

    un cloud público (AWS, DigitalOcean) es posible reducir el jitter agregado por Internet utilizando como host para realizar las mediciones un servidor en el mismo data-center que el objetivo. En algunos casos podría hasta ser posible obtener una instancia en el mismo hardware donde se ejecuta el target: “Hey, You, Get Off of My Cloud”.
  16. Tiempos muy pequeños Aun con funciones muy naive (más sobre

    esto luego) de comparación de strings como: Los tiempos a medir son muy pequeños y la precisión con la cual es posible medirlos es reducida. def compare_strings(str_a, str_b): if len(str_a) != len(str_b): return False for i, char_a in enumerate(str_a): if str_b[i] != char_a: return False return True
  17. Incrementar el tiempo a medir Como los tiempos a medir

    suelen ser muy pequeños, se puede aplicar una técnica conocida como “mathematical amplification” (bleh!) para incrementar el tiempo a medir. No es perfecto porque incrementa la cantidad de peticiones HTTP a realizar , pero incrementa sustancialmente el intervalo de tiempo a medir. En este caso el brute-force se hace de a tres bytes: timeit('AAAXX') vs timeit('AABXXXX') ... vs timeit('ZZZXXXX')
  18. Histograma Una solución para los problemas de jitter es realizar

    cientos de miles de mediciones, entonces se obtiene una distribución:
  19. Cientos de miles de mediciones La comparación de estas distribuciones

    no es trivial, en general hay que tener en cuenta los siguientes componentes: • Filtros para eliminar outliers de una distribución, se suele utilizar únicamente el rango de datos menor al N% con N: {5, 10, 15, 20} • Métodos de comparación de distribuciones: ◦ Box test ◦ Midsummary ◦ Expectation-Maximization • Certeza del resultado
  20. Comparación de Strings en Ruby, CPython y PHP Todos los

    lenguajes de programación desarrollados en C terminan utilizando memcmp() de glibc para implementar la comparación de strings. memcmp() está optimizado para que las comparaciones de dos strings sean lo más rápidas posibles, si están disponibles se utilizan instrucciones de SSE para comparar secciones de memoria de 8 o 16 bytes en una sola instrucción de procesador. Entonces, no es posible realizar ataques de fuerza bruta byte-per-byte (*) en targets que utilicen glibc y sea posible utilizar alguna instrucción del CPU que compare strings en bloques.
  21. • 34 implementaciones específicas de memcmp() • Incluye implementaciones con

    soporte de wide-char (terminan incluyendo las no-wc). • Lo mismo sucede contras funciones de glibc que se utilizan mucho y requieren buena performance. GLibC memcmp()
  22. • glibc-2.23/sysdeps/x86_64/multiarch/me mcmp-sse4.S • Utiliza instrucciones para comparar de a

    128bits. • Son 1776 líneas de assembler de puro amor! • Algún hijo de puta se fue a su casa contento después de esto. GLibC memcmp() optimizado SSE 4.1 - X86_64
  23. Comparación de Strings en Java public boolean equals(Object anObject) {

    if (this == anObject) { return true; } if (anObject instanceof String) { String anotherString = (String) anObject; int n = value.length; if (n == anotherString.value.length) { char v1[] = value; char v2[] = anotherString.value; int i = 0; while (n-- != 0) { if (v1[i] != v2[i]) return false; i++; Naive, pero… después las optimizaciones de la JVM deciden que es mejor ejecutar la versión optimizada de String.equals, la cual tiene optimizaciones similares a memcmp()
  24. String Compare Timing Attacks sobre IoT Cuando el problema es

    complejo, lo mejor es simplificarlo, y eso es lo que hizo Paul McMillan en el research que presentó hace unos años en Ekoparty donde utilizo timing attacks para obtener byte a byte la API key de una lampara HUE de Phillips. Lo que logró al atacar lámparas HUE fue: • CPU más lento, mayor tiempo en ejecutar cada instrucción • Comparacion naive de strings byte per byte • Conexión por medio de un cable de red y utilizando Intel i350
  25. Con código similar en Python obtuve spent_time == 0 start_time

    = Time.now.nsec # Compare the test strings str_a == str_b end_time = Time.now.nsec spent_time = end_time - start_time if spent_time < 0 puts "Go home Ruby, you're drunk. Negative time spent: #{spent_time}" next
  26. Comparación de Strings CPython Extrañamente la comparación de strings en

    CPython no utiliza memcmp() en todos los casos: switch(kind1) { case PyUnicode_1BYTE_KIND: { switch(kind2) { case PyUnicode_1BYTE_KIND: { int cmp = memcmp(data1, data2, len); ... } case PyUnicode_2BYTE_KIND: COMPARE(Py_UCS1, Py_UCS2); break; case PyUnicode_4BYTE_KIND: COMPARE(Py_UCS1, Py_UCS4); break;
  27. Comparación de Strings CPython / COMPARE Donde COMPARE es naive:

    #define COMPARE(TYPE1, TYPE2) \ do { \ TYPE1* p1 = (TYPE1 *)data1; \ TYPE2* p2 = (TYPE2 *)data2; \ TYPE1* end = p1 + len; \ Py_UCS4 c1, c2; \ for (; p1 != end; p1++, p2++) { \ c1 = *p1; \ c2 = *p2; \ if (c1 != c2) \ return (c1 < c2) ? -1 : 1; \ } \ } \ while (0)
  28. Comparación de Strings CPython / COMPARE Entonces la comparación de

    strings con diferentes byte sizes se realiza utilizando una función con un per-byte side channel: Me imagino que es posible identificar frameworks de desarrollo web python que permitan explotar esta debilidad especificando Content-Encoding en los requests. CHAR_OK = b'A'.decode('ascii') CHAR_FAIL = 'á' assert len(CHAR_OK.encode('utf-8')) != len(CHAR_FAIL.encode('utf-8')) CHAR_OK == CHAR_FAIL # naive strcmp
  29. Objetivos • Completar las mediciones locales de tiempos para todos

    los lenguajes, investigar y utilizar técnicas necesarias para reducir jitter • Definir múltiples entornos de prueba y capturar millones de muestras • Probar todas las combinaciones de filtros, métodos de comparación de distribuciones y precisión para determinar cuál funciona mejor para cada entorno. • Desarrollar una aplicación que pueda atacar IoT de manera automática • Mejorar la aplicación anterior para que pueda ser utilizada contra aplicaciones reales
  30. Los repositorios en los cuales estoy trabajando son públicos: •

    https://github.com/andresriancho/pico • https://github.com/andresriancho/pico-string-compare-loc al No dejen de leer las wikis de esos dos repositorios, contienen información interesante sobre el research, links a otras herramientas, etc. Help wanted