Tutoriel Diverted timing attacks

[deathbbs]

Bonjour a tous, un article que j'ai fait il y a quelques temps déjà.

Nous allons nous intéresser ici aux timing attacks. Tout d'abord kesako ?? A la base, les timing attacks sont utilises en cryptographie dans le but de casser des algorithmes de chiffrement. Le principe est simple c'est simplement des statistiques : selon le temps pour exécuter P, N, alors on en déduire un schéma redonnant et donc effectuer des mesures sur les entrées.

Prenons un exemple simple, qui n'a pas (réellement) de rapport avec la cryptographie. Un programme A vous accorde des privilèges si vous lui donnez un mot de passe correct. Dans ce cas l'algo utilisé est assez simple, bien plus qu'en cryptanalyse ; un léger détournement qui ressemble a du "timing bruteforcing".

Le mot de passe est compare a un mot de passe dans la mémoire du processus (avec strcmp par exemple). Le principe sera de calculer le temps mis par le processus pour comparer les mots de passe et en déduire le schéma.

Imaginons que le mot de passe attendu soit : toto. On commence la comparaison avec aa, ba, ca, da ... Voici un tableau explicatif avec des valeurs en temps non explicites (pour simplifier la compréhension on prend comme temps de calcul 1sec / caractère):

Mot de passe : toto

test	|	temps
------		----------
aa	|	1 sec
ba	|	1 sec
...
ta	|	2 sec
ua	|	1 sec
...

Ce que l'on remarque et c'est simplement de la logique, si on compare aa et toto, la fonction de comparaison s’arrêtant au premier caractère faux, il compare donc 1 caractère et met 1 sec. Si maintenant on compare ta et toto, le premier caractère est le même (1sec), donc il compare le suivant et met 1 sec de plus. Le tour est rejoue autant de fois que nécessaire. Si toute les comparaisons mettent 1 sec, c'est qu'il n'y a pas de caractère a la suite. En gros, cette technique s'appuie sur un mélange de statistiques et de brute force. Une sorte de brute force optimisé.

Cas concret maintenant, soit le programme suivant:

#include        <sys/types.h>
#include        <stdint.h>
#include        <stdio.h>
#include        <string.h>

static inline uint64_t counter_read_time(void)
{
uint64_t l;

  __asm__ __volatile__ ("rdtsc\n\t"
                        : "=A" (l));
  return (l);
}

static inline uint64_t counter_elapsed(uint64_t t0, uint64_t t1)
{
  return (t1 - t0);
}

int main(int argc, char *argv[])
{
  uint64_t start;
  uint64_t end;
  uint64_t avg;
  uint64_t cycles_nb;
  size_t i;

  avg = 0;
  if (argc != 2)
    return (1);
  for (i = 0; i < 50000; i++)
  {
    start = counter_read_time();
    if (!strcmp("toto", argv[1]))
    {
      printf("Good\n");
      return (0);
    }
    end = counter_read_time();
    cycles_nb = counter_elapsed(start, end);
    if (avg)
      avg = (avg + cycles_nb) / 2;
    else
      avg = cycles_nb;
  }
  printf("Average: %d\n", avg);
  return (0);
}

Et quelques tests (n'oubliez pas le flag -O0 sinon les optis de gcc vont totalement casser le timer) :

[email protected]:~$ gcc -o test test.c -O0
[email protected]:~$ ./test a
Average: 174
[email protected]:~$ ./test a
Average: 174
[email protected]:~$ ./test a
Average: 171
[email protected]:~$ ./test a
Average: 172
[email protected]:~$ ./test a
Average: 175
[email protected]:~$ ./test t
Average: 175
[email protected]:~$ ./test t
Average: 88
[email protected]:~$ ./test t
Average: 176
[email protected]:~$ ./test t
Average: 175
[email protected]:~$ ./test t
Average: 175
[email protected]:~$ ./test t
Average: 88
[email protected]:~$ ./test ta
Average: 88
[email protected]:~$ ./test ta
Average: 176
[email protected]:~$ ./test ta
Average: 176
[email protected]:~$ ./test ta
Average: 176
[email protected]:~$ ./test ta
Average: 176
[email protected]:~$ ./test ta
Average: 176
[email protected]:~$ ./test to
Average: 175
[email protected]:~$ ./test to
Average: 184
[email protected]:~$ ./test to
Average: 88
[email protected]:~$ ./test to
Average: 176
[email protected]:~$ ./test to
Average: 176
[email protected]:~$ ./test to
Average: 88
[email protected]:~$ ./test to
Average: 175
[email protected]:~$ ./test to
Average: 176
[email protected]:~$ ./test to
Average: 176
[email protected]:~$ ./test to
Average: 184
[email protected]:~$ ./test to
Average: 88
[email protected]:~$ ./test toto
Good
[email protected]:~$ exit

Comme on le voit, c'est loi d’être parfait, c'est aussi le problème de cette technique : comment mesurer efficacement un temps sur un processeur, sachant que des dizaines de variables viennent perturber son déroulement. C'est pour cela que des statistiques sont ensuite faits, a vue d’œil, on remarque que des qu'une lettre est bonne, le timer augment de quelques cycles. Ici, le programme a juste été créé pour l'exemple il est (très) loin d’être parfait mais si on interprète bien les résultats il est suffisamment efficace pour un strcmp.

Si vous voulez de meilleurs résultats, essayez donc avec un strcmp fait maison en python par exemple.

J’espère que ca vous a faite réfléchir en tout cas.

[TorTukiTu]

Sympa ton exemple, death =) , les timing attacks peuvent s'avérer redoutables en local contre un algo vulnérable.

Il existe aussi les vulns type race condition, qui sont peu connues.

Tortue 974.

[deathbbs]

en local

Comme tu l'entends, j'imagine bien comment en réseau ça serait juste impossible.
Ça ne fonctionne pas non plus si le binaire est une VM car d'autres facteurs sont pris en compte lors de l'exec.