Com que darrerament torno a fer coses relacionades amb la criptografia… doncs venen ganes de parlar-ne. Avui, doncs, un consell que molta gent deu saber imagino, però no tothom. A veure si sé ser una mica didàctic.

El hash i la signatura

Quan signeu un document electrònicament (i això passa més sovint del que us penseu, encara que no us n’adoneu) el que feu realment és aplicar primer una funció matemàtica (anomenada hash) que redueix totes les dades a un sol número molt més petit (de 160 bits en el hash més habitual). Aquest número depèn absolutament de les dades originals; si en modifiquem només 1 bit el resultat del hash varia completament. Aquest hash és també una funció en un sol sentit: és a dir, que no podem obtenir les dades del hash (la qual cosa és lògica si ho penseu, ja que només té 160 bits, mentre que les dades poden tenir megues o gigues).

Llavors, un cop tenim aquest número que només depèn de les dades, es “signa” aquest número (s’aplica l’operació de clau privada sobre aquest valor).

Si volgués signar unes dades que produïssin exactament el mateix hash amb la mateixa clau, llavors el resultat seria exactament el mateix. O sigui que una de les coses que podria intentar un atacant és agafar una signatura nostra i generar un missatge que donés el mateix hash (per exemple algun document que em comprometi a donar-li diners) i reaprofitar la signatura.

Afortunadament, un hash de 160 bits resulta en unes 2^160 possibilitats, que és un número de quasi 50 xifres. O sigui que és molt i molt difícil generar missatges fins trobar un altre que doni el mateix hash.

Aniversaris

Canvio de tema, de moment, si heu fet probabilitat, coneixereu la paradoxa de l’aniversari. Imagineu-vos-ho: tenim 23 persones en una festa. Suposem que la probabilitat de néixer a qualsevol dia de l’any és la mateixa (que no és veritat, ja que hi ha èpoques on és més probable néixer). Quina probabilitat hi ha que, com a mínim, dues persones facin l’aniversari el mateix dia?

La resposta intuïtiva per la majoria de la gent és un valor baix. Però no! És del 50.7%! I si posem 50 persones llavors ja és del 97%.

Doncs bé, amb unes matemàtiques molt semblants a les que permeten resoldre aquest problema, veiem que si tenim un hash i volem trobar unes altres dades que generin el mateix hash, doncs hem de provar 2^N missatges (on N és el nombre de bits del hash, en l’exemple anterior 160). Però, i aquí hi ha l’aniversari, si el que vull és generar simultàniament 2 missatges, doncs necessito fer 2^(N/2) missatges, que és molt i molt menys (l’arrel quadrada de l’anterior).

Imagineu que sóc un superdelinqüent i que vull que algú em signi un document que segurament no vol signar. Què puc fer? Doncs faig petites variacions d’ambdós missatges de manera que encara resultin legítims (en molts formats de fitxer això és fàcil, però també us podeu imaginar que afegeixo espais o coses per l’estil). Llavors faig hash de tot fins que trobo una parella de missatge legítim i fraudulent amb el mateix hash.

A continuació li dono el missatge a la víctima, que el signa, i jo obtinc la signatura, i la utilitzo amb les dades fraudulentes. Voilà!

Amb el hash SHA-1 encara més

Això és cert amb tots els algorismes de hash. També amb el SHA-1, que és el que més s’utilitza. Aquest atac encara és més rellevant després de les investigacions de Xiaoyun Wang, Yiqun Lisa Yin i Hongbo Yu que tants titulars van omplir fa uns mesos. Ells han aconseguit generar parelles de missatges que generin el mateix hash amb 2^69 operacions, i no amb 2^80 (el hash SHA-1 té 160 bits). Això redueix en 2^11 vegades (2048) el temps necessari per obtenir-les. El que abans eren anys ara són dies.

Aquest atac facilita molt generar dos missatges a la vegada que generin el mateix hash; per ara, generar un hash igual a un missatge que ja tenim continua essent molt i molt més complicat.

El consell

El consell és fàcil ara doncs: no signeu mai documents que us passin terceres persones. Quan us n’enviïn algun, feu alguna petita modificació (si és text afegiu un espai, per exemple) i signeu-ne el resultat. Aquesta tercera persona podria haver preparat dos missatges i enviar-nos el que voldríem signar, tal i com he explicat abans. Però si fem això l’obliguem a calcular un missatge fraudulent que doni el mateix hash que el missatge que hem generat, cosa que, com hem vist, és molt i molt més complicat.

Per evitar el birthday attack hi ha solucions tècniques, que bàsicament consisteixen en variar el missatge que es signa amb un nombre aleatori, salt value, que fa impossible precalcular-los (o combinacions més complicades com el PSS de RSA que actuen sobre el hash però compliquen més l’esquema)… però segurament les vostres eines criptogràfiques no ho utilitzen. Més val prevenir, no?

This entry was posted on Thursday, May 19th, 2005 at 00:01 and is filed under Formiguer, Seguretat. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.