Atac de natalici

Un atac de natalici (o, en anglés, birthday attack) és un tipo d'atac criptográfico que es basa en la matemàtica darrere de la paradoxa del natalici, fent us d'una situació de compromís espai-temps informàtica. Concretament, si una funció matemàtica produïx $H$ resultats diferents igualment provables i $H$ és lo suficientment gran, llavors, despuix d'evaluar la funció sobre $1.2\sqrt{H}$ arguments distints, s'espera trobar un parell d'arguments $x_1$ i $x_2$ diferents de manera tal que $f(x_1)=f(x_2)$, fet conegut com una colisió.

La matemàtica

Per a demostrar el resultat anterior, comencem en el desenroll en series de Taylor de la provabilitat de que dos persones complixquen els anys en el mateix dia. En este cas, reemplacem el número de dies en un any en el número de resultats únics, $H$:

$p(n)=1-\overline{p}(n)\approx 1-e^{-(n(n-1))/2\cdot H}\approx 1-e^{-n^2/2\cdot H},$

a on $n$ és el número d'intents per a una colisió. Invertint esta expressió,

$n(p)\approx \sqrt{2\cdot H\cdot \ln \left(\frac{1}{1-p}\right)},$

i assignant una provabilitat de colisió de 0.5 (condició de que siga tan possible com a impossible), apleguem a

$n(0.5)=1.1774\sqrt{H}$.

Com a eixemple, si s'usa un hash de 64 bits, hi haurà aproximadament 1.8 × 10¹⁹ resultats distints. Si totes són igualment provables (el millor dels casos), llavors prendria solament uns 5.1 × 10⁹ intents aproximadament generar una colisió usant força bruta. Atres eixemples són com es mostra a continuació:

Bits	Eixides possibles	Provabilitat desijada de colisions aleatòries
		10-12	10-9	10-6	0.1%	1%	25%	50%	75%
64	1.8 × 1019	6.1 × 103	1.9 × 105	6.1 × 106	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	3.4 × 1038	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	1.2 × 1077	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	3.9 × 10115	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	1.3 × 10154	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	1.9 × 1077

Esta taula mostra el número de hashes que són necessaris per a alcançar la provabilitat d'èxit donada, assumint que tots els hashes són igualment provables

És fàcil vore que si els resultats de la funció no estan distribuïdes uniformemente (és dir, si no són igualment provables), llavors les colisions 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 de natalicis i permet que s'estime la vulnerabilitat de funcions de hash populars, tals com MD5 i SHA (Bellare i Kohno, 2004).

Les firmes digitals poden ser susceptibles d'un atac de natalici. Un mensage $m$ típicament es firma computant primer $f(m)$, a on $f$ és una funció de hash criptográfica i despuix s'usa alguna clave secreta per a firmar $f(m)$. Supongam que Alice vol enganyar a Bob per a que ferm un contracte fraudulent. Alice prepara un contracte bo $m$ i un de mal $m^{\prime }$. Aixina, ella busca un número de posicions a on $m$ puga ser modificat sense canviar el significat, com per eixemple insertant menges, llínees en blanc, canviant l'espayat entre oracions, usant sinònims, etc. Combinant estos canvis, Alice podria crear un número immens de variacions de $m$, totes elles contractes bons. De manera similar, podria crear un número immens de contractes fraudulents $m^{\prime }$. Llavors, ella aplica una funció de hash a totes eixes variacions fins que trobe una versió del contracte bo i una atra del mal que posseïxquen el mateix valor hash, $f(m)=f(m^{\prime })$. Després, li presenta la versió bona a Bob per a que la ferma. Una volta que Bob la firma, Alice pren la firma i li l'adjunta al contracte fraudulent. Les firma digital "prova" llavors que Bob va firmar el contracte fraudulent. (Nota: este esquema diferix lleument del problema original del natalici, puix Alice no guanya res per trobar dos contractes bons o dos contractes fraudulents que produïxen el mateix hash; no obstant, en este esquema les provabilitats són sorprenentment altes.)

Per a impedir este atac, la llongitut dels resultats de la funció hash deuen ser lo suficientment grans de manera que l'atac de natalici es torne computacionalment impossible, per eixemple, unes dos voltes més gran de lo que es requeriria per a previndre un atac de força bruta. També s'ha recomanat que Bob realise canvis menors en qualsevol document que li siga presentat per a ser firmat. No obstant, açò no resol el problema, perque ara Alice sospita que Bob intenta usar un atac de natalici.

L'atac de natalici pot ser usat per a accelerar el còmput de logaritmes discrets. Supongam que $x$ i $y$ són elements d'un grup i que $y$ és una potència de $x$. Volem trobar l'exponent de $x$ que dona $y$. Un atac de natalici computa $x^r$ per a varis sancers $r$ elegits aleatoriamente i computa $y{x}^{-s}$ per a varis sancers $s$ elegits aleatoriamente. Passat un temps, es trobarà un parell $x^r=y{x}^{-s}$, lo que significa que $y=x^{r+s}$.

Si el grup té $n$ elements, el método més simple de provar tots els exponents pren entorn $n/2$ intents en promig. L'atac de natalici és considerablement més ràpit i implica menys de $2\sqrt{n}$ intents en promig.

Existixen tècniques basades en repetició iterativa que poden reduir considerablement els requeriments d'almagasenament dels atacs de natalicis.

Eixemple

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

{Estimat|Volgut} client,

{Nos posem en contacte en vosté|Li escrivim}
per a {anunciar-li|informar-li} sobre la {charra|conferència}
que es {realisarà|portarà a terme} el dia 1 de giner de 2007,
a les 12 hores en {el nostre auditórium|nostres premisses},
{que brindarà|a càrrec de} un {reconegut|prestigiós}
{autor|escritor} de {varis|numerosos} {llibres|documents}
sobre ciència i tecnologia.

{La charrada|La trobada} {consistirà en|comprendrà} els
següents {tòpics|continguts}: {Internet, |Web 2.0, }

{I-learning i VoIP|VoIP i I-learning}.

{Esta|La present} invitació és {només|únicament} per als
nostres {més exclusius clients|clients més exclusius} i
és per {això|esta raó}, que {esperem|desigem} contar en
la seua presència.

Sense {més|atre particular}, {li saludem|nos despedim de
vosté} {atentament|cordialment}.

Seleccionant entre una de les dos opcions que es presenten, es pot crear 2²⁴ mensages distints. Normalment els processadors de text poden configurar-se per a generar documents d'esta manera.

Vore també

• Atac Meet-in-the-middle

Referències

• Mihir Bellare, Tadayoshi Kohno: Hash Function Balanç and Its Impact on Birthday Attacks. EUROCRYPT 2004: pp. 401-418.