A02:2021 - Errors criptogràfics - Colisiones Hash

Què són els errors criptogràfics?

Una fallada criptogràfic ocorre quan la protecció de la dada no és adequada, independentment de si la fallada succeeix per un ús incorrecte d'un algorisme criptogràfic, una fallada en la implementació del mateix, o per l'ús de pràctiques insegures. Les vulnerabilitats que es donen poden afectar la confidencialitat i la integritat de la informació d'una aplicació.

Les fallades criptogràfics són un risc de seguretat ja que permeten a un possible actor malintencionat, desxifrar, manipular o accedir a informació que, per disseny, no hauria de tenir accés.

Es pot entendre la criptografia moderna com l'ús d'algorismes robustos, conseqüentment considerats com a assegurances. Entre ells destaquen AES; RSA o SHA-256, tot i això, la seva correcta implementació és crucial. Una generació de claus incorrecta, l'ús d'algorismes obsolets, com SHA1 o MD5; o la posada en producció de generadors de nombres predictibles, poden resultar en atacs contra la criptografia de l'aplicació.

Ús d'algorismes obsolets

Un dels errors criptogràfics més comuns és l'ús funcions de hash i algorismes de xifrat obsolets, referenciats anteriorment, SHA1 i MD5. Tot i que van ser estàndards a la seva època (1995 i 1992, respectivament), avui dia no són considerats segurs a causa dels avenços en les tècniques d'atac, com la recerca de col·lisions de hash. Aquests atacs permeten que un possible actor maliciós generi dues entrades diferents que produeixin el mateix hash, cosa que podria suposar una suplantació d'informació.

També s'han de tenir en compte els algorismes de xifratge simètric, entre els quals també n'hi ha alguns considerats com a obsolets, DES o 3DES, els quals no proporcionen una robustesa adequada a l'època en què ens trobem, atès que amb el temps i els recursos suficients es pot arribar a desxifrar les dades.

Història: MD5 i SHA1

Els algorismes MD5 (Message Digest 5) i SHA1 (Secure Hash Algorithm 1) són funcions hash que es van utilitzar àmpliament per verificar la integritat de les dades. Tot i això, amb el temps es van descobrir vulnerabilitats d'alt impacte en ambdós algorismes, permetent a actors maliciosos dur a terme atacs de col·lisions (entre altres), resultant en una fallada de seguretat. Com a resultat, tant MD5 com SHA1 es consideren obsolets i no són recomanats per al seu ús en funcionalitat que requereixi d'alta seguretat.

MD5 - Resum de missatges 5

Algorisme dissenyat el 1991, genera un hash de 128 bits a partir d'un conjunt de dades de qualsevol mida. Originalment utilitzat per verificar la integritat darxius i imatges, i hashes de contrasenyes.

• Atacs de col·lisió: el 2004 els investigadors Xiaoyun Wang, Dengguo Feng, Xuejia Lai i Hongbo Yu; van demostrar que MD5 és vulnerable a col·lisions.

• Xie, T., Liu, F. i Feng, D. (2013). Atac de col·lisió ràpid a MD5. Arxiu Criptologia ePrint.

• Atacs de preimatge: encara que menys comuns, els atacs de preimatge són teòricament possibles en MD5, un actor maliciós podria intentar reconstruir el missatge original a partir del hash.

• Sasaki, Y. i Aoki, K. (2009). Trobar imatges prèvies en MD5 complet més ràpid que la cerca exhaustiva. In Advances in Cryptology-EUROCRYPT 2009: 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Colònia, Alemanya, 26-30 d'abril de 2009. Proceedings 28 (p. 134-152). Springer Berlin Heidelberg.

SHA1 - Algoritme hash segur 1

SHA1, desenvolupat per la NSA el 1993, genera un hash de 160 bits. Se'n va estandarditzar l'ús, trobant-se en protocols com SSL/TLS i PGP. En els darrers anys s'ha demostrat com és vulnerable a atacs de col·lisió.

El 2017, Google en associació amb la Universitat d'Amsterdam, demostrator que es podrien generar col·lisions a SHA1, publicant https://shattered.io/ de lliure consulta pública.

Col·lisions Hash

Funcions Hash

Una funció hash és un algorisme que pren una entrada de longitud variable i la converteix en una sortida variable (hash o digest). Les funcions hash estan dissenyades per ser unidireccionals, i no és possible recuperar l'entrada a partir de la sortida, i resistents a col·lisions. No obstant, en determinats algoritmes ja ha quedat demostrat com aquesta resiliència davant de col·lisions, no sempre és perfecta.

Però, què són les col·lisions de hash?

Una col·lisió de hash passa quan dues entrades diferents produeixen la mateixa sortida o digest. Aquesta situació desmunta una de les propietats essencials de les funcions hash, la unicitat del digest.

La seguretat de sistemes com les signatures digitals, la integritat de fitxers, i els certificats SSL/TLS, pot ser compromesa mitjançant col·lisions de hash. Si un actor maliciós aconsegueix modificar el contingut d'un missatge sense que s'alteri el vostre hash, pot aconseguir que les modificacions passin inadvertides i es consideri legítim el missatge.

Exemple de col·lisió a MD5

Per a l'exemple de col·lisió, es fan servir dues cadenes de text, les quals es diferencien en un byte. Crèdits a Marc Stevens per la seva publicació .

• Cadena1:

TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak 

• Cadena 2:

TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

⬆

|

⬇

TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak

Per poder demostrar-ho, es realitzarà una petita prova de concepte en C:

#inclou 

#inclou

#inclou 

int main() {

    char *input1 = "TEXTCOLLBYfGiJUETHQ4hAcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak";

    char *input2 = "TEXTCOLLBYfGiJUETHQ4hEcKSMd5zYpgqf1YRDhkmxHkhPWptrkoyz28wnI9V0aHeAuaKnak";

    char sense signar hash1[MD5_DIGEST_LENGTH];

    char sense signar hash2[MD5_DIGEST_LENGTH];

    MD5((carràcter sense signe*)entrada1, strlen(entrada1), hash1);

    MD5((unsigned char*)input2, strlen(input2), hash2);

    for(int i = 0; i 

    printf("\n");

    for(int i = 0; i 

    printf("\n");

    printf(memcmp(hash1, hash2, MD5_DIGEST_LENGTH) == 0? "Col·lisió trobada!\n" : "No hi ha col·lisió\n");

    retorn 0;

}

I s'obté una col·lisió de hash, dues cadenes alfanumèriques diferents resulten al mateix hash MD5. Això portat a un sistema d'accés on les credencials es troben emmagatzemades mitjançant hash MD5, podria suposar un accés no autoritzat amb una credencial diferent de l'original.

Com es troben les col·lisions de hash? → Chosen Prefix Collision

Identificar una col·lisió de hash és com trobar una agulla en un paller, la quantitat de recursos computacionals que requereix per trobar dues cadenes (per exemple) arbitràries les quals resultin al mateix hash, és descomunal.

Per això s'han desenvolupat tècniques com Chosen Prefix Collision (CPC), on es poden seleccionar dos missatges amb prefixos específics i crear variacions que resultin en una col·lisió del hash.

Marc teòric

L'objectiu de l'atac és trobar dos missatges M1 i M2, cadascun amb prefixos coneguts i controlats P1 i P2 , que resultin al mateix digest. Es pot expressar com:

On:

• H és la funció hash (MD5 o SHA1).
• P1 i P2 són els prefixos elegits.
• M1 i M2 són les parts variables a identificar.
• ∣∣ denota concatenació.

El risc que suposa aquest atac en particular és elevat atès que els prefixos poden ser part d'un arxiu o missatge amb una estructura coneguda (com un certificat digital), cosa que podria permetre manipular dades de manera estratègica per aconseguir la col·lisió sense que es modifiquin elements visibles o crítics.

Procés de l'atac

Considerant l'estructura d'una funció hash que es divideix en blocs:

On El meu representa els blocs de mida fixa a l'entrada. El càlcul de la funció hash, H, es fa de manera iterativa sobre aquests blocs, on cada bloc modifica un estat intermedi Si.

Durant l'atac CPC els prefixos P1 i P2 es processaran primer, generant un estat intermedi per al càlcul del hash.

Per aconseguir l'objectiu de trobar dos blocs M1 i M2, que, concatenats amb els prefixos P1 i P2 produeixin el mateix valor final de hash, els blocs M1 i M2 s'han d'ajustar de manera que les diferències entre S1 i S2 es cancel·len als estats intermedis posteriors.

Almenys un bloc El meu ha de compensar la diferència entre els estats intermedis.

On:

• ⊕ representa l'operació XOR.
• ΔS és la diferència introduïda als estats intermedis per equilibrar la disparitat entre S1 i S2.

Simplificant, si s'assumeix que s'aconsegueix forçar una col·lisió d'estats intermedis, s'obtindria al final dels blocs elegits:

Vist l'ajust de M1 i M2 de manera que, malgrat tenir prefixos diferents P1 i P2, es produeix el mateix estat intermedi final S1.

Assolir la igualtat passa per introduir diferències calculades als blocs de missatge M1 i M2, aplicant diferències als bits del bloc de missatge que contrarestin les diferències en els estats intermedis de la funció hash. Aquestes diferències es calcularan de manera que la seva propagació a través de la funció hash comporti el mateix estat final.

Suposant que s'introdueixen diferències al bloc de missatge M1, com ΔM de tal manera que:

Per tal que l'estat intermedi després d'aplicar el bloc M1⊕ΔM sigui igual a l'estat intermedi després d'aplicar el bloc M2.

Conclusió

L'atac Chosen Prefix Collision explota la naturalesa interactiva de les funcions hash. Mitjançant la manipulació de blocs de dades i l'aplicació de diferències calculades, es pot aconseguir que coincideixin els estats intermedis, provocant la col·lisió a la sortida del hash final.

Aquest atac és una prova de les debilitats fonamentals de funcions hash com MD5 i SHA1, principalment davant d'atacs avançats que manipulen les dades d'entrada de manera controlada.

Autor: Daniel Puente