No puedo explicar los datos del intento de ataque del canal lateral

8

Encontré la función de comparación a continuación (ligeramente modificada) de una biblioteca criptográfica que estaba usando. Tenía curiosidad por la vulnerabilidad potencial a los ataques de canal lateral. Específicamente, la comparación de caracteres solo se realiza si el carácter que se está comparando está dentro de los límites de las dos cadenas. Sospeché que esto podría permitir a un atacante determinar la longitud de la cadena.

Quizás esta diferencia es simplemente demasiado pequeña para estar sujeta a un ataque de tiempo, pero jugué con un intento a continuación. Básicamente, creo cadenas de longitudes crecientes y las comparo con una cadena inicial dada. Esperaba ver un crecimiento lineal en el tiempo de comparación, tanto antes como después del punto donde la segunda cuerda se hace más larga, pero quizás con una pendiente diferente, ya que las operaciones realizadas son diferentes.

En cambio, veo los datos a continuación (note que la cadena que se está comparando tiene una longitud de 27 caracteres). Cualquier explicación de por qué no tengo idea de lo que estoy hablando sería muy apreciada :)

Una pequeña nota, probé con -O0 en caso de que alguna extraña optimización tuviera la culpa. Lo único que puedo hacer desde aquí es comenzar a excavar en el ensamblaje generado.

#include<string.h>#include<sys/time.h>#include<stdio.h>intCompareStrings(constchar*s1,constchar*s2){inteq=1;ints1_len=strlen(s1);ints2_len=strlen(s2);if(s1_len!=s2_len){eq=0;}constintmax_len=(s2_len<s1_len)?s1_len:s2_len;//topreventtimingattacks,shouldcheckentirestring//don'texitafterfoundtobefalseinti;for(i=0;i<max_len;++i){if(s1_len>=i&&s2_len>=i&&s1[i]!=s2[i]){eq=1;}}returneq;}doubletime_diff(structtimevalx,structtimevaly){doublex_ms,y_ms,diff;x_ms=(double)x.tv_sec*1000000+(double)x.tv_usec;y_ms=(double)y.tv_sec*1000000+(double)y.tv_usec;diff=(double)y_ms-(double)x_ms;returndiff;}voidtest_with_length(char*str1,intn){charstr2[n+1];structtimevaltp1;structtimevaltp2;inti;for(i=0;i<n;i++){str2[i]='a';}str2[n]='
#include<string.h>#include<sys/time.h>#include<stdio.h>intCompareStrings(constchar*s1,constchar*s2){inteq=1;ints1_len=strlen(s1);ints2_len=strlen(s2);if(s1_len!=s2_len){eq=0;}constintmax_len=(s2_len<s1_len)?s1_len:s2_len;//topreventtimingattacks,shouldcheckentirestring//don'texitafterfoundtobefalseinti;for(i=0;i<max_len;++i){if(s1_len>=i&&s2_len>=i&&s1[i]!=s2[i]){eq=1;}}returneq;}doubletime_diff(structtimevalx,structtimevaly){doublex_ms,y_ms,diff;x_ms=(double)x.tv_sec*1000000+(double)x.tv_usec;y_ms=(double)y.tv_sec*1000000+(double)y.tv_usec;diff=(double)y_ms-(double)x_ms;returndiff;}voidtest_with_length(char*str1,intn){charstr2[n+1];structtimevaltp1;structtimevaltp2;inti;for(i=0;i<n;i++){str2[i]='a';}str2[n]='%pre%';gettimeofday(&tp1,NULL);for(i=0;i<20000000;i++){CompareStrings(str1,str2);}gettimeofday(&tp2,NULL);printf("%d %.01f\n", n, time_diff(tp1, tp2));
}

int main() {
    char *str1 = "XXXXXXXXXXXXXXXXXXXXXXXXXXX";

    int i = 0;
    for (i = 1; i <= 100; i++) {
        test_with_length(str1, i);
    }
}
'; gettimeofday(&tp1, NULL); for (i = 0; i < 20000000; i++) { CompareStrings(str1, str2); } gettimeofday(&tp2, NULL); printf("%d %.01f\n", n, time_diff(tp1, tp2)); } int main() { char *str1 = "XXXXXXXXXXXXXXXXXXXXXXXXXXX"; int i = 0; for (i = 1; i <= 100; i++) { test_with_length(str1, i); } }
    
pregunta Michael Mior 13.09.2012 - 01:18
fuente

2 respuestas

6

Primero, algunos comentarios sobre el código:

  • Sus llamadas a strlen son una caja negra, no es posible saber cómo reaccionan a los ataques de tiempo.
  • Su bucle de comparación se cierra después de agotar la cadena más corta, dejando escapar la longitud más corta.
  • No eliminó el sesgo generado por el bucle en test_with_length .
  • Los accesos a la matriz son no O (1) complejidad de tiempo, especialmente si cada elemento es más pequeño que el ancho de palabra de su CPU.

Una mejor manera de compensar tales ataques:

bool CompareStr(char* strA, char* strB)
{
    bool result = true;
    int lenA, lenB = 0;

    while(strA[n] != 0)
        lenA++;
    while(strB[n] != 0)
        lenB++;

    int maxLen = (lenA > lenB) ? lenA : lenB;

    // compensate for array access to some extent
    int diff = (lenA > lenB) ? lenA - lenB : lenB - lenA;
    char dummy = '
 xor ecx, ecx                         ; clear counter to 0
 mov dword ptr ds:[0040AAAA], 1       ; set result to true
loopStart:
 mov ah, byte ptr ds:[ecx+00401234]   ; read char from string A
 mov bh, byte ptr ds:[ecx+00402468]   ; read char from string B
 cmp ah, bh                           ; compare the chars
 jz match                             ; are they equal?
 mov dword ptr ds:[0040AAAA], 0       ; strings don't match! set result to true
match:
 cmp ah, 0                            ; are we at the end of string A?
 jz done
 cmp bh, 0                            ; are we at the end of string B?
 jz done
 inc ecx                              ; increment counter and continue loop
 jmp loopStart
done:
 ret
'; for(int i = 0; i < diff; i++) { dummy = strA[0]; } // better way to avoid timing attacks for(int i = 0; i < maxLen; i++) { if ( ((i >= lenA) ? strA[0] : strA[i]) != ((i >= lenB) ? strB[0] : strB[i]) ) result = false; } return false; } // compute loop overhead time_pre_loop = getTime(); for(int i = 0; i < LOOP_COUNT; i++) { } time_post_loop = getTime(); double diff = time_diff(time_post_loop, time_pre_loop); time_pre_test = getTime(); for(int i = 0; i < LOOP_COUNT; i++) CompareStr(strA, strB); time_post_test = getTime(); double result = time_diff(time_post_test, time_pre_test) - diff;

De todos modos, aquí es donde comienza la parte divertida. Considere el siguiente código de ensamblaje que podría usarse para calcular si dos cadenas son iguales, con la optimización anticipada eliminada como una defensa de ataque de sincronización básica:

int r, d = 0;
int* bufferA = (int*)stringA;
int* bufferB = (int*)stringB;
for(int i = 0; i < BUFFER_SIZE; i += 4)
{
    d = bufferA[i] ^ bufferB[i]; // if equal, d = 0
    r |= d; // if all cases are 0, r will be 0
}
return r; // result is 0 if equal, non-zero if not equal

En realidad hay algunos ataques de tiempo aquí. Las dos primeras instrucciones son O (1) . Sin embargo, las dos lecturas de un solo byte que siguen no lo son.

Mientras que las lecturas de memoria son generalmente O (1) , en la práctica no lo serán. De hecho, no encajan en el modelo big-O en absoluto. En un sistema de 32 bits, cada lectura de 4to byte será más rápida que las demás. En un sistema de 64 bits, cada 4º byte será más rápido y cada 8º byte será aún más rápido. Esto se debe a lecturas de memoria no alineadas. La CPU es excelente para obtener bloques de datos que están alineados con el tamaño de su bus, pero no tan bueno para obtener bytes individuales aleatorios. La CPU intentará optimizar esto canalizando las instrucciones y cargando el bloque en su caché L2, lo que hace que este problema sea más sutil, pero sigue ahí.

El siguiente truco es para cadenas que son más grandes que el caché de la CPU. Si tiene una cadena que excede este tamaño (generalmente 128 KB o más para el caché L2), verá leves retrasos en las recuperaciones de memoria cada vez que una lectura exceda ese límite. Esto suele ser solo un pequeño retraso, ya que la memoria caché L3 se utilizará para almacenar el siguiente bloque, pero podemos ver una diferencia aún mayor para cadenas más grandes (8 MB +) ya que las recuperaciones de memoria deben realizarse desde la memoria del sistema.

Si consideramos una copia de memoria de bloque como O (n), donde n es la longitud de la memoria, esto tiene sentido en algo , pero no describe adecuadamente las pequeñas variaciones en el tiempo causadas por las idiosincrasias de implementación.

Finalmente, podemos ver que la instrucción mov dword ptr ds:[0040AAAA], 0 se ejecuta cuando una cadena no coincide con otra. Esto filtra información de dos maneras:

  • Nos permite estimar la longitud relativa de la cadena más corta identificando el tiempo extra que se usa al configurar repetidamente el resultado.
  • Si podemos medir con precisión, nos permite identificar qué caracteres son diferentes.

Como podemos ver, es bastante difícil prevenir estos problemas. Aquí está mi intento por un sistema mejor, asumiendo que las cadenas de longitud fija se alinean con los bytes nulos:

bool CompareStr(char* strA, char* strB)
{
    bool result = true;
    int lenA, lenB = 0;

    while(strA[n] != 0)
        lenA++;
    while(strB[n] != 0)
        lenB++;

    int maxLen = (lenA > lenB) ? lenA : lenB;

    // compensate for array access to some extent
    int diff = (lenA > lenB) ? lenA - lenB : lenB - lenA;
    char dummy = '
 xor ecx, ecx                         ; clear counter to 0
 mov dword ptr ds:[0040AAAA], 1       ; set result to true
loopStart:
 mov ah, byte ptr ds:[ecx+00401234]   ; read char from string A
 mov bh, byte ptr ds:[ecx+00402468]   ; read char from string B
 cmp ah, bh                           ; compare the chars
 jz match                             ; are they equal?
 mov dword ptr ds:[0040AAAA], 0       ; strings don't match! set result to true
match:
 cmp ah, 0                            ; are we at the end of string A?
 jz done
 cmp bh, 0                            ; are we at the end of string B?
 jz done
 inc ecx                              ; increment counter and continue loop
 jmp loopStart
done:
 ret
'; for(int i = 0; i < diff; i++) { dummy = strA[0]; } // better way to avoid timing attacks for(int i = 0; i < maxLen; i++) { if ( ((i >= lenA) ? strA[0] : strA[i]) != ((i >= lenB) ? strB[0] : strB[i]) ) result = false; } return false; } // compute loop overhead time_pre_loop = getTime(); for(int i = 0; i < LOOP_COUNT; i++) { } time_post_loop = getTime(); double diff = time_diff(time_post_loop, time_pre_loop); time_pre_test = getTime(); for(int i = 0; i < LOOP_COUNT; i++) CompareStr(strA, strB); time_post_test = getTime(); double result = time_diff(time_post_test, time_pre_test) - diff;

Esto es casi perfectamente O (n) por las siguientes razones:

  • Xwise a nivel de bit de los ints alineados es O (1)
  • Bitwise o de ints alineados es O (1)
  • Las lecturas de la memoria están alineadas.
  • Ninguna longitud se filtra, debido al BUFFER_LENGTH padding.
  • Sin ramas, excluyendo el bucle.
respondido por el Polynomial 13.09.2012 - 08:42
fuente
2

Primero, hay un error en tu función de comparación; el " eq = 1; " en el bucle debe leer " eq = 0; ". Sin embargo, no debería cambiar el tiempo, suponiendo que el compilador no juega con el optimizador. Para hacer que su código sea más resistente a los juegos de optimización, debe poner la función de referencia (su CompareStrings() ) y el código de referencia ( test_with_length() ) en módulos distintos (archivos fuente C compilados por separado, y orar para que el compilador no realice interferencias). Optimizaciones de módulo: gcc debería ser seguro para eso).

Lo que ves se ve correcto. Las dos llamadas strlen() deben tener un costo que se incremente de forma más o menos lineal con la suma de las longitudes de las dos cadenas; pero strlen() juega algunos juegos ingeniosos para ser más rápido. En particular, strlen() intentará leer bytes de datos por partes completamente alineadas (quizás 4, 8, 16 bytes), y esto funcionará porque el compilador conoce el control de acceso a la memoria mediante MMU funciona en la granularidad de una página, por lo que es posible realizar accesos" seguros "fuera de los límites en muchos casos. Las cadenas pequeñas tendrán versiones especializadas, y las longitudes aquí (a lo sumo 100 bytes) son demasiado pequeñas para mostrar comportamientos asintóticos.

Es probable que el costo de los dos strlen() sea pequeño con respecto al bucle for . Sin embargo, introducirá algo de "ruido" en el gráfico, por lo que no debes mirar los puntos demasiado de cerca.

El bucle for se ejecutará para los pasos max_len , que es la longitud del más largo de las dos cadenas. Por lo tanto, como primera aproximación, esperamos que el costo de ese bucle sea lineal en la longitud de la mayor de las dos cadenas, por lo que debería ver un tiempo aproximadamente constante cuando la longitud del segundo operando crece de 1 a 27, luego un aumento - que es lo que ves en el gráfico.

    
respondido por el Tom Leek 16.09.2012 - 16:46
fuente

Lea otras preguntas en las etiquetas