Atac d'aniversari

Un atac d'aniversari (o, anglès, birthday attack ) és un tipus d'atac criptogràfic que es basa en la matemàtica darrere de la paradoxa de l'aniversari, fent ús d'una situació de compromís espaitemps informàtica. Concretament, si una funció matemàtica produeix $H$ resultats diferents igualment probables i $H$ és prou gran, llavors, després d'avaluar la funció sobre $1/2{\sqrt {H}}$ arguments diferents, s'espera trobar un parell d'arguments $x_{1}$ i $x_{2}$ diferents de manera que $f(x_{1})=f(x_{2})$ , fet conegut com una col·lisió.

La matemàtica[modifica]

Per demostrar el resultat anterior, vam començar amb el desenvolupament en sèries de Taylor de la probabilitat que dues persones compleixin els anys en el mateix dia. En aquest cas, substituïm el nombre de dies en un any amb el nombre de resultats únics, $H$ :

P(n)=1-{\bar {p}}(n)\approx 1-i^{-(n(n-1))/2\cdot H}\approx 1-e^{-n^{2}/{2\cdot H}},

on $n$ és el nombre d'intents per a una col·lisió. Invertint aquesta expressió,

N(p)\approx {\sqrt {2\cdot H\cdot \ln \left({1 \over 1-p}\right)}},

i assignant una probabilitat de col·lisió de 0.5 (condició que sigui tant possible com impossible), arribem a

N(0,5)=1.1774{\sqrt {H}}

.

Com a exemple, si s'usa un hash de 64 bits, hi haurà aproximadament 1/8 × 10 ¹⁹ resultats diferents. Si totes són igualment probables (el millor dels casos), llavors prendria només uns 5/1 × 10 ⁹ intents aproximadament generar una col·lisió utilitzant força bruta. Altres exemples són com es mostra a continució:

Bits	Sortides possibles	Possibilitat desitjada de col·lisions aleatòries
Bits	Sortides possibles	10 ^-12	10 ^-9	10 ^-6	0,1%	1%	25%	50%	75%
64	1/8 × 10 ¹⁹	6/1 × 10 ³	1/9 × 10 ⁵	6/1 × 10 ⁶	1/9 × 10 ⁸	6/1 × 10 ⁸	3/3 × 10 ⁹	5/1 × 10 ⁹	7/2 × 10 ⁹
128	3/4 × 10 ³⁸	2/6 × 10 ¹³	8/2 × 10 ¹⁴	2/6 × 10 ¹⁶	8/3 × 10 ¹⁷	2/6 × 10 ¹⁸	1/4 × 10 ¹⁹	2/2 × 10 ¹⁹	3/1 × 10 ¹⁹
256	1/2 × 10 ⁷⁷	4/8 × 10 ³²	1.5 × 10 ³⁴	4/8 × 10 ³⁵	1.5 × 10 ³⁷	4/8 × 10 ³⁷	2/6 × 10 ³⁸	4.0 × 10 ³⁸	5/7 × 10 ³⁸
384	3/9 × 10 ¹¹⁵	8/9 × 10 ⁵¹	2/8 × 10 ⁵³	8/9 × 10 ⁵⁴	2/8 × 10 ⁵⁶	8/9 × 10 ⁵⁶	4/8 × 10 ⁵⁷	7/4 × 10 ⁵⁷	1.0 × 10 ⁵⁸
512	1/3 × 10 ¹⁵⁴	1/6 × 10 ⁷¹	5/2 × 10 ⁷²	1/6 × 10 ⁷⁴	5/2 × 10 ⁷⁵	1/6 × 10 ⁷⁶	8/8 × 10 ⁷⁶	1/4 × 10 ⁷⁷	1/9 × 10 ⁷⁷

Aquesta taula mostra el nombre de hashes que són necessaris per assolir la probabilitat d'èxit donada, assumint que tots els hashes són igualment probables

És fàcil veure que si els resultats de la funció no estan distribuïdes uniformement (és a dir, si no són igualment probables), llavors les col·lisions poden ser trobades molt més ràpidament. La noció de 'balanç' d'una funció de hash quantifica la resistència de la funció a atacs d'aniversari i permet que es consideri la vulnerabilitat de funcions de hash populars, com ara MD5 i SHA (Bellariva i Kohn, 2004).

Les signatures digitals poden ser susceptibles d'un atac d'aniversari. Un missatge $m$ típicament es firma computant primer $f(m)$ , on $f$ és una funció de hash criptogràfica i després es fa servir alguna clau secreta per signar $f(m)$ . Suposem que Alice vol enganyar Bob perquè signi un contracte fraudulent. Alice prepara un contracte bo $m$ i un dolent $m'$ . Així, ella busca un nombre de posicions on $m$ pugui ser modificat sense canviar el significat, com per exemple inserint comes, línies en blanc, canviant l'espaiat entre oracions, usant sinònims, etc. Combinant aquests canvis, Alice podria crear un nombre immens de variacions de $m$ , totes elles contractes bons. De manera similar, podria crear un nombre immens de contractes fraudulents $m'$ . Llavors, ella aplica una funció de hash a totes aquestes variacions fins que trobi una versió del contracte bo i una altra del dolent que tinguin el mateix valor hash, $f(m)=f(m')$ . Després, li presenta la versió bona a Bob perquè la ferma. Quan Bob la signatura, Alice pren la signatura i es l'adjunta al contracte frudulento. Les signatura digital "prova" llavors que Bob va signar el contracte fraudulent. (Nota: aquest esquema difereix lleugerament del problema original de l'aniversari, ja que Alice no guanya res per trobar dos contractes bons o dos contractes fraudulents que produeixen el mateix hash, però, en aquest esquema les probabilitats són sorprenentment altes.)

Per impedir aquest atac, la longitud dels resultats de la funció hash han de ser prou grans de manera que l'atac d'aniversari es torni computacionalment impossible, per exemple, unes dues vegades més gran del que es requeriria per prevenir un atac de força bruta. També s'ha recomanat que Bob realitzi canvis menors en qualsevol document que li sigui presentat per a ser signat. Tanmateix, això no resulve el problema, perquè ara Alice sospita que Bob voleu utilitzar un atac d'aniversari.

L'atac d'aniversari pot ser usat per accelerar el còmput de logaritmes discrets. Suposem que $x$ i $i$ són elements d'un grup i que $i$ és una potència de $x$ . Volem trobar l'exponent de $x$ que dona $i$ . Un atac d'aniversari computa $x^{r}$ per a diversos enters $r$ elegits aleatòriament i computa $ix^{-s}$ per a diversos enters $s$ elegits aleatòriament. Passat un temps, es trobarà un parell $x^{r}=ix^{-s}$ , el que significa que $i=x^{r+s}$ .

Si el grup té $n$ elements, el mètode més simple de provar tots els exponents presa al voltant $n/2$ intents de mitjana. L'atac d'aniversari és considerablement més ràpid i implica menys de $2{\sqrt {n}}$ intents de mitjana.

Hi ha tècniques basades en repetició iterativa que poden reduir considerablement els requeriments d'emmagatzematge dels atacs d'aniversari.

Exemple[modifica]

El següent és un exemple de com crear variacions d'una carta sense alterar el contingut.

{Benvolgut|Estimat}client,

{Ens posem en contacte amb vostè|Le estem escrivint}
per{anunciar|informar}sobre la{xerrada|conferència}
que{realitzarà|durà a terme}el dia 1 de gener de 2007,
a les 12 hores a{nostre auditorium|les nostres premisses},
{Que brindarà|a càrrec de 'un{reconegut|prestigiós}
{Autor|escriptor}d'{diversos|nombrosos}{llibres|documents}
sobre ciència i tecnologia.

{La xerrada|La trobada}{consistirà en|comprendrà}els
següents{tòpics|continguts}:{Internet,|El web 2.0,}
{E-learning i VoIP|VoIP i E-learning '.

{Aquesta|Aquesta}invitació és{només|únicament 'per
nostres{més exclusius clients|clients més exclusius}i
és per{això|això}, que{esperem|desitgem}comptar amb
la seva presència.

Sense{més|altre particular},{li saludem|ens acomiadem d'
Vostè}{atentament|cordialment}.

Seleccionant entre una de les dues opcions que es presenten, es pot crear 2 ²⁴ missatges diferents. Normalment els processadors de text poden configurar per a generar documents d'aquesta manera.

Vegeu també[modifica]

Atac Meet-in-the-middle

Referències[modifica]

Mihir Bellariva, Tadayoshi Kohn: Hash Function Balanç and Its Impact on Birthday Attacks. EUROCRYPT 2004: pp401-418

Enllaços externs[modifica]

"What is a digital signature and what is authentication?" Arxivat 2004-09-13 a Wayback Machine. Del FAQ de RSA. (en anglès)
"Parallel Collision search with cryptanalytic applications Arxivat 2008-12-30 a Wayback Machine., Michael Wiener and Paul C. van Oorschot (en anglès)
Article sobre funcions hash i els atacs d'aniversari Arxivat 2007-09-29 a Wayback Machine. a Netmedia.
SHA-1 i les col·lisions d'aniversari a Kriptópolis.
Debilitat de l'SHA-1 per D. Fernando Acer, militar espanyol expert en seguretat informàtica.