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

String Compare Timing Attacks

String Compare Timing Attacks

Research in progress

andresriancho

April 13, 2017
Tweet

More Decks by andresriancho

Other Decks in Programming

Transcript

  1. /me • Application security expert (web|API) • Developer (Python!) •

    Open Source evangelist • w3af project leader • Independent consultant
  2. Timing Side Channels • Enviamos el mensaje M1 a un

    proceso y devuelve la respuesta R en 3 ms • Enviamos el mensaje M2 al mismo proceso, devuelve nuevamente R pero esta vez tarda 6 ms • Los resultados son consistentes para sucesivas mediciones del tiempo de procesamiento para M1 y M2. • Encontramos un side channel!
  3. 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”.
  4. 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: process_request(user_input)
  5. Que estamos atacando? Si tuviésemos que implementar una funcion de

    comparacion de strings, seguramente se vería así: def compare_strings(str_a, str_b): if len(str_a) != len(str_b): return False for i in xrange(len(str_a)): if str_a[i] != str_b[i]: return False return True
  6. Simple test-case with Atmega328P. Password input from serial compared with

    hardcoded value. • Board Arduino UNO • Compiler AVR-GCC • AVR LibC Arduino String Compare Timing Attacks
  7. Led time on / off Optimization : None Clock :

    16 MHz Invalid Character index • None • 5th • 2nd • 1st
  8. String Compare Timing Attacks sobre IoT Paul McMillan presentó hace

    unos años en Ekoparty donde utilizo timing attacks para obtener byte a byte la API key de una lámpara HUE de Phillips. Lo que logró al seleccionar lámparas HUE como su objetivo 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
  9. Timing Attacks en Web Applications 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 user_input.get('API_KEY') == MASTER_API_KEY: process_request(user_input)
  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 user_input.get('API_KEY') == MASTER_API_KEY: process_request(user_input)
  11. 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
  12. 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
  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. 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
  15. 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)
  16. 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”.
  17. 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 in xrange(len(str_a)): if str_a[i] != str_b[i]: return False return True
  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 / 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 /memcmp-sse4.S • Utiliza instrucciones para comparar de a

    128bits. • Son 1776 líneas de assembler de puro amor! 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. 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;
  25. 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)
  26. 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
  27. 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 web en servidores comunes
  28. Los repositorios en los cuales estoy trabajando son públicos: •

    https://github.com/andresriancho/pico • https://github.com/andresriancho/pico-string-compare-local No dejen de leer las wikis de esos dos repositorios, contienen información interesante sobre el research, links a otras herramientas, etc. Help wanted
  29. For hire Tu empresa necesita estos servicios? • Application Penetration

    Test • Secure Coding Training for Developers • Source Code Review • Cloud Security Assessment Pongámonos en contacto, puedo ayudar a que tu empresa desarrolle aplicaciones web seguras.