1. Scenariu
Să presupunem că avem o sursă care generează o valoare aleatorie pe, de exemplu, minut. Deci avem valoare aleatorie $x_1$ în $1$primul minut, $x_2$ în $2$al doilea minut, $\ldots$, $x_n$ în $n$al-lea minut și așa mai departe.
Distribuția valorilor $x_1, x_2, \ldots$ nu este aleatoriu în întregime uniform, dar urmează următoarea regulă: pentru oricare $i \ge 1$, $x_i = (y_i, y_{i+1})$, Unde, $y_i$ este identificatorul unic al $x_i$, și $y_{i+1}$ este identificatorul unic al viitorului $x_{i+1}$ care va sosi în minutul următor.
Cu alte cuvinte, în orice moment $i$al-lea minut, curentul $x_i$, și următorul $x_{i+}$ sunt cunoscute, dar cea de după $x_{i+2}$ este absolut necunoscut sau aleatoriu. Mai jos este un exemplu:
Minutul 1: x_1 = (334234 , 234829129 )
Minutul 2: x_2 = (234829129, 983220 )
Minutul 3: x_3 = (983220 , 831231236347)
...
Minutul n: x_n = (643532754, 3534611 )
O modalitate de a le distruge $n$ valorile, în ordine, este să trimiți fiecare valoare pe măsură ce ajunge, de ex. $h_1 = f(x_1)$, apoi înlănțuiește-l cu următorul nou sosit, de ex. $h_2 = f(x_2 \parallel h_1)$.
Cu alte cuvinte, hash-ul listei ordonate de intrare, în $n$al-lea minut este definit recursiv ca $h_n = f(x_n \parallel h_{n-1})$, cu cazul de bază fiind $h_1 = f(x_1)$.
Avantajul acestei abordări este că, pentru cine rulează acest proces de la început, în fiecare minut, atât timpul de rulare, cât și timpul spațiu-timp sunt în $O(1)$, deoarece poate stoca în cache hash-ul din minutul anterior.
Dezavantajul acestei abordări este că, pentru cineva care nu a urmat procesul și dorește să verifice dacă $h_n$ este într-adevăr hash-ul întregii secvențe, va trebui să o ia de la început cu $h_1$și repetați întregul lanț până când $h_n$. În mod efectiv, acest proces de verificare va dura $O(n)$ spaţiu şi $O(n)$ timp.
2. Gaură de vierme
Ar fi bine dacă este posibil ca, la fiecare $n$ multe lanțuri hashed, putem descoperi a gaură de vierme $w_n$ care are următoarele proprietăți:
- Odata ce $n$hașul, $h_n$, este în mod legitim calculat off $h_1$ urmând recursiunea completă mai devreme, abia apoi gaura de vierme $w_n$ devine descoperit. Altfel, găsirea $w_n$ este practic imposibil.
- Pentru un dat $h'_n$ haș care se pretinde a fi $h_n$, gaura de vierme poate scurta verificarea după cum urmează:
$$
w_n(h_1, h'_n) = \begin{cases}
1 & \text{dacă $h'_n = h_n$}\
0 & \text{else}\
\end{cazuri}
$$
- Cel mai prost timp de rulare asimptotic, precum și cel mai prost spațiu asimptotic pentru calcul $w_n(h_1, h'_n)$ nu este mai rău decât $O(\log n)$. Dacă este posibil să ajungi $O(1)$, asta e chiar mai bine desigur.
Notă. Aceasta este diferită de pre-imagine atacul funcțiilor de hashing. Diferența fiind următoarea:
Atacurile pre-imagine permit atacatorului să falsifice un arbitrar intrare care oferă un hash țintă dorit.
Această gaură de vierme $w_n$ nu permite falsificarea vreunei intrări arbitrare, ci mai degrabă dezvăluie o cale de scurtătură ascunsă care funcționează numai pentru conectarea unei anumite intrări care permite conectarea $h_n$ înapoi la $h_1$și că singura modalitate de a descoperi o astfel de gaură de vierme este calculând în mod legitim $h_n$ primul.
Poate că putem numi o astfel de gaură de vierme a fi un atac condiționat înainte de imagine care nu aduce beneficii adversarului.
3. Întrebare
Sunt cunoscute sau chiar posibile astfel de găuri de vierme de verificare?
