[C/C++] BruteForce

[b0fh]

La récursion, apprenez a l'aimer !

Code C :


#include <stdio.h>
#include <stdlib.h>

void generate(char *start, char *buf, char *end, char *alpha) {
        if (buf == end)
                puts(start);
        else
                for (char *p = alpha; *p; p++) {
                        *buf = *p;
                        generate(start, buf+1, end, alpha);
                }
}

int main(int argc, char **argv) {
        char *buf;
        size_t len;

        if (3 != argc) {
                fprintf(stderr, "Usage: bf <length> <alphabet>\n");
                exit(1);
        }

        len = atoi(argv[1]);
        buf = (char *)malloc((len+1) * sizeof(char));
        buf[len] = '\0';

        generate(buf, buf, buf+len, argv[2]);

}
 

Comment, vous dites que la récursion c'est lent ?

Code :

max@truite:~$ gcc -O3 -o bf-gruik bf-gruik.c -lm
max@truite:~$ gcc -O3 -std=c99 -o bf bf.c
max@truite:~$ time ./bf 13 abcd >/dev/null

real    0m8.145s
user    0m8.017s
sys    0m0.112s
max@truite:~$ time ./bf-gruik 13 abcd >/dev/null

real    0m12.428s
user    0m12.321s
sys    0m0.088s

max@truite:~$ diff <(./bf-gruik 5 abcde) <(./bf 5 abcde) && echo ok
ok

[InstinctHack]

>_<""""
je lutte depuis 3 heures avec

Code C :


gcc test.c -lssl -lcrypt -o e
 

fallait faire

Code C :


gcc test.c -lssl -lcrypto -o e
 

Go me pendre

[k-otik]

Si je peux me permettre de faire un commentaire sans vous embêtez.

Il faut éviter les algorithmes de protection variable dans le temps !
Que ce soit des return ou break dans des boucles de comparison.

Je dis ca, car quand on code des bruteforcers on apprend aussi à coder l'inverse.

Un autre exemple que j'ai vu, ceci est une comparison octet par octet en python.

Code :

if h.hexdigest()==hash

C'est comme ca qu'on pouvait (et peut encore http://www.cvedetails.com/cve/CVE-2009-3875/) bypasser par analyse temporelle statistique certains algorithmes d'authentification.

[InstinctHack]

Si je peux me permettre de faire un commentaire sans vous embêtez.

Il faut éviter les algorithmes de protection variable dans le temps !
Que ce soit des return ou break dans des boucles de comparison.

Je dis ca, car quand on code des bruteforcers on apprend aussi à coder l'inverse.

Un autre exemple que j'ai vu, ceci est une comparison octet par octet en python.

Code :

if h.hexdigest()==hash

C'est comme ca qu'on pouvait (et peut encore http://www.cvedetails.com/cve/CVE-2009-3875/) bypasser par analyse temporelle statistique certains algorithmes d'authentification.

TOP 1 du jairiencompris ! \o/

return, break c'est quoi le mal ?
if h.hexdigest()==hash, c'est quoi le probleme ?
"analyse temporelle statistique" ça ressemble à du français, mais ça n'en n'est pas :p

Tu peux expliquer plus en détail, s'il te plait ?

[gruik]

Si je peux me permettre de faire un commentaire sans vous embêtez.

god que tu es embêtant non bien sûr c'est le principe d'un forum de partager ses avis et ses expériences donc tu peux allègrement te permettre sans embêter, je m'en porte garant personnellement, foi de veau !

Il faut éviter les algorithmes de protection variable dans le temps !
Que ce soit des return ou break dans des boucles de comparison.
(...)
C'est comme ca qu'on pouvait (...) bypasser par analyse temporelle statistique certains algorithmes d'authentification.

oui je crois voir ce que tu veux dire, et c'est très vrai effectivement même si ça s'applique essentiellement aux routines d'ident/authent, j'ai souvenir d'un exploit similaire au début des années 2000 contre PAM et/ou openssh

sinon mignon ce CVE je m'en souvenais plus, mais k-otik, k-otik... tu serais pas du côté de montpellier toi par hasard ?

[b0fh]

Ben, ce type de problème est plutôt présent dans les cas ou on essaie de deviner une clef secrète ou un padding ou un sel; ici à priori on suppose que le hash est connu.

Mais admettons que le serveur aie du code comme

Code :

h == hash

, et que l'attaquant contrôle h mais ne connaisse pas hash.

Le problème est que, en comparant des strings, le temps de comparaison est proportionnel au nombre de mots communs en début de la chaine. Donc plutôt que de devoir bruteforcer un hash complet, il peut essayer plusieurs h ayant des débuts différents, mesurer le temps de réponse du serveur, et garder le plus long; et ainsi reconstruire hash en temps linéaire plutôt qu'exponentiel.

Pour éviter ça, il faut t'assurer que le temps de comparaison ne dépende pas de tes données. Et donc pas de break/continue, qui changent le nombre d'itérations de tes boucles.

L'attaque fameuse était celle de S. Vaudenay contre OpenSSL, qui vérifiait qu'un paquet entrant était valide en testant qu'il avait un padding et un MAC correct. Mais dans les vieilles versions, le MAC n'était pas testé si le padding était incorrect, ce qui permettait de distinguer les deux erreurs en mesurant le temps de réponse. Et pour le mode CBC, ça permet de réaliser l'attaque dite du Padding Oracle, qui permet de casser un cleartext byte par byte a condition d'avoir a disposition une boite noire qui dise pour chaque ciphertext si le padding est correct ou pas.

[Dobry]

Je n'ai pas eu le temps de regarder les codes (même si je vais tenter celle en recursive avant de regarder la solution, un peu d'entrainement ne fera pas de mal). Mais merci pour cette explication sur l'analyse temporel statique, je n'étais pas du tout au courant de ce genre de procédé !

[k-otik]

b0fh a très bien répondu .

Le problème est que, en comparant des strings, le temps de comparaison est proportionnel au nombre de mots communs en début de la chaine. Donc plutôt que de devoir bruteforcer un hash complet, il peut essayer plusieurs h ayant des débuts différents, mesurer le temps de réponse du serveur, et garder le plus long; et ainsi reconstruire hash en temps linéaire plutôt qu'exponentiel.

Pour éviter ça, il faut t'assurer que le temps de comparaison ne dépende pas de tes données. Et donc pas de break/continue, qui changent le nombre d'itérations de tes boucles.

C'est une type de side-channel attack que je trouve très élégant. Avec des applications diverses si on élargit l'éventail au-delà de l'attaque de serveur de distribution de clé.

Permet de vérifier rapidement la présence d'él'ements divers dans des bases de données (nom d'utilisateur, champs de table etc..). Des délais de quelques microsecondes sont facilement décelables statitisquement au milieu du bruit (fluctuations poisonniennes liées au changement de contexts du thread, le pigeon sur le fil qui modifie la dispersion du signal etc) si l'algorithme de comparaison des données du client et du serveur n'est pas constant dans le temps.

En effet,

Code :

==

est très anodin mais ceci cache une comparaison octect par octect dont le temps d'exécution croit avec l'exactitude des premiers octets comparés comme :

Code :

for(int i = 0; i <client_input_data_len; i++)
    if(client_input_data[i] != server_test_data[i]) return false;

Ici la comparaison est linéaire, tout dépend de l'algorithme. Mais en restant évasif, quelqu'un pourrait comprendre qu'en "bruteforcant" avec des entrées qui ont par exemple des distances de Levenshtein différentes à la valeur comparée, on peut mesurer en MOYENNE des écarts systématiques dans les délais de réponse du serveur.

Le sujet est riche, en passant par le champ time-stamps du protocol TCP/IP, à d'autres protocoles modernes. En gros, tout traitement de données client-serveur qui n'est pas invariant dans le temps est intéressant

Je pourrais partager l'idée peut-être qu'il existerait des banques qui utiliseraient des dispositifs QKD (quantum key distribution) pour la cryptographie et l'échange de données sur quelques kilomètres reposant sur l'intrication EPR entre des modes comprimés de la lumière. La création de clés a usage unique (non composites) étant le résultat de plusieurs mesures effectuées sur l'une des deux quadratures de la lumière (phase ou amplitude). Si vous êtes encore entrain de lire , le choix de la mesure de la phase ou de l'amplitude se faisant aléatoirement avec un phase-shifter de 90 degree, un attaquant pourrait reconstituer la séquence de mesures (phase amplitude amplitude phase phase etc..) car la bande passante des phase-shifter telecom est faible (cela prend un certain temps de passer d'une quadrature à une autre) .. enfin bref gruik j'espère que tu te portes garant pour le blabla que je pourrai raconter

[gruik]

enfin bref gruik j'espère que tu te portes garant pour le blabla que je pourrai raconter

tout à fait tout à fait, le premier qui moufte c'est ma main dans l'array

[notfound]

La récursion, apprenez a l'aimer !

Code BASH :


max@truite:~$ gcc -O3 -o bf-gruik bf-gruik.c -lm
max@truite:~$ gcc -O3 -std=c99 -o bf bf.c
max@truite:~$ time ./bf 13 abcd >/dev/null

real    0m8.145s
user    0m8.017s
sys     0m0.112s
max@truite:~$ time ./bf-gruik 13 abcd >/dev/null

real    0m12.428s
user    0m12.321s
sys     0m0.088s

max@truite:~$ diff <(./bf-gruik 5 abcde) <(./bf 5 abcde) && echo ok
ok


 

EPIC WIN !