Puncte:2

$2^{64}$ versiuni ale aceluiași mesaj

drapel cn

Citesc un manual și acolo ei explică proprietatea funcțiilor hash. În special, ele oferă un exemplu despre cât de puțin probabil ar fi să găsești o a doua valoare de intrare care să se potrivească cu ieșirea hash a intrării inițiale. Iată exemplul:

Arătăm acum cum și-ar putea transforma Oscar capacitatea de a găsi coliziuni (modificând două mesaje) într-un atac. El începe cu două mesaje, de exemplu: $x_1 = \text{ Transferați \$10 în contul Oscar } \ x_2 = \text{ Transferați \10.000 USD în contul lui Oscar} $

Acum se schimbă $x_1$ și $x_2$ în locații „nevizibile”, de exemplu, înlocuiește spații cu file, adaugă spații etc. Sensul mesajelor este același (de exemplu, pentru o bancă), dar hash-ul se schimbă.

Oscar încearcă până la condiție $h(x_1)=h(x_2)$. Rețineți că, dacă un atacator are, de exemplu, $64$ locații pe care le poate modifica sau nu, acest lucru dă $2^{64}$ versiuni ale aceluiaşi mesaj cu $2^{64}$ diferite valori hash.

Poate cineva să explice, vă rog, ce înseamnă $2^{64}$ versiuni ale aceluiași mesaj? Acest lucru a zburat complet peste capul meu. Știu că o funcție hash (de exemplu SHA-256) produce o ieșire 64, astfel încât, de exemplu:

SHA256(Transferă 10 USD în contul lui Oscar)=250e62ddffbdf20a0ea40d69287327e8aff58b6ad49c03dab3f714b596804dc1

Înțeleg că Oscar vrea să modifice Transferați 10.000 USD în contul lui Oscar astfel încât ieșirea, atunci când este conectată la funcția SHA-256, să producă aceeași ieșire ca cea de mai sus. Dar ce înseamnă că atacatorul poate „altera sau nu” cele 64 de locații și cum are această „alterare sau nu”? $2^{64}$ versiuni ale aceluiași mesaj?

kelalaka avatar
drapel in
`Spații goale pentru ce trăim`, în afară de distracție, nu e clar? adăugați 64 de spații albe sau tab, aceasta face ca 64 de poziții posibile să varieze. Apoi aveți o cantitate de date similară cu atacul de ziua de naștere care are 1/2 probabilitate de succes.
Slim Shady avatar
drapel cn
@kelalaka Îmi pare rău, sunt destul de nou în spațiu, așa că nu este clar pentru mine.
kelalaka avatar
drapel in
Apăsați „bara de spațiu” de pe tastatură, ce vedeți?
Slim Shady avatar
drapel cn
@kelalaka modificarea ieșirii funcției hash. Acest lucru este clar pentru mine. Știu că teoretic putem aranja $x_2$ astfel încât rezultatul lui hash să fie același cu $x_1$. Asta e tot ce știu
kelalaka avatar
drapel in
Apropo, care este numele cărții?
Puncte:3
drapel in

Textul citat pare să vorbească despre găsirea unei coliziuni a unei funcții hash de 128 de biți cu atacul Birthday. Într-un atac de naștere, cineva creează în jur $\sqrt{2^{128}} = 2^{64}$ mesaje astfel încât se așteaptă să găsească o pereche de ciocnire cu 1/2 probabilitate.

În atacul descris, Oscar vrea să creeze două mesaje specifice care au aceeași valoare hash.

$x_1$= Transferați $10 în contul Oscar
$x_2$= Transferați 10.000 USD în contul lui Oscar

Pentru a crea $2^{64}$ mesaje, se pot folosi caractere invizibile precum spaţiu și fila. Dacă adăugați 64 de caractere la $x_1$ sau $x_2$ acestea sunt fie tab sau spațiu, atunci puteți obține 64 de locații. Asta face $2^{64}$ mesaje care au aceeași semnificație cu hashuri mari, probabil diferite.

Această modificare invizibilă se aplică pe ambele $x_1$ și $x_2$.

Creat $2^{64}$ corzi diferite pentru $x_1$ și $x_2$ și combinați-le într-un set. În acest set, ne așteptăm la o coliziune. Rețineți că, în acest fel, este posibil să avem o coliziune în cadrul variantei de $x_1$ (sau $x_2$).

Acum, Oscar caută o modalitate de a te înșela. Oscar îți trimite mesajul $x_1$ cu paradigma hash și semn și o verifici. Ulterior, Oscar susține că te-au trimis $x_2$. Îți arată că semnăturile sunt aceleași cu cele precedente și aici avem conflictul de rezolvat.

Pentru alte exemple de utilizare a coliziunii hash în atacuri realiste, consultați această întrebare;


Atacul de coliziune vs al doilea atac pre-imagine

În atac de coliziune căutăm două mesaje $m_1$ și $m_2$ cu $m_1 \neq m_2$ astfel de $h(m_1) = h(m_2)$. Într-un atac de coliziune, atacatorul nu are posibilitatea de a alege valoarea hash, ei caută doar două mesaje care au aceeași valoare hash. Această libertate reduce costul atacului. Costul generic al coliziunii este $\mathcal{O}(\sqrt{2^{n/2}})$-timpul pentru $n$-bit funcție hash de ieșire.

În unele alte scenarii, atacatorul are nevoie al doilea atac pre-imagine; dat un mesaj $m$ și este valoarea hash $x=h(m)$, găsiți alt mesaj $m' \neq m$ astfel încât $h(m)=h(m')$. Acesta este scenariul în care atacatorul creează o falsificare a unei semnături digitale (hash și semn). Având în vedere semnătura, ei încearcă să găsească un alt mesaj $m'$ astfel încât semnătura să fie aceeași cu cea dată.

Două costuri generice ale atacului secundar pre-imagine este $\mathcal{O}(\sqrt{2^n})$-timpul pentru $n$-biți funcție hash.

Definițiile formale pot fi găsite în

jjj avatar
drapel cn
jjj
Nu cred că vorbesc despre un atac de ziua de naștere. Un mesaj pare a fi reparat, altfel s-ar putea modifica ambele la 64 de poziții, făcându-l 2^64 de versiuni diferite fiecare. De asemenea, atacul are sens doar atunci când x1 a fost autorizat cumva (de exemplu, hash a fost semnat).
kelalaka avatar
drapel in
@jjj textele spun (modificând două mesaje) și am făcut un argument simplu pentru a combina toate variantele de $x_1$ și $x_2$ într-un set și să caut coliziune ca date de naștere. Dacă unul este fix, atunci este un atac secundar pre-imagine. Nu am spus hash și semn?
jjj avatar
drapel cn
jjj
Oh, am ratat asta. Încă cred că merită menționat că pentru acest exemplu ar avea în mod normal un hash dat și, prin urmare, un mesaj fix.
kelalaka avatar
drapel in
@jjj mai bine acum?
Puncte:2
drapel in

Către: ["The",""] First International Bank ["Panama",""] Subiect: ["Bani",""] ["Transfer","Transfer"] ["Comandă",""] din contul meu ["Număr","#"]1234[".",""]

["aud de","aș dori să"] instruiesc ["tu ",""] să ["transfer","transfer","mute"] ["Suma","o sumă"] de [" un milion","1.000.000"] ["USD","$"] la ["Următorul",""] cont ["num","#"] 3456.

etc. Acest lucru de mai sus are "$2^{14}*3$" combinații doar pentru începutul unui mesaj relevant. Fără a juca cu spații albe.

kelalaka avatar
drapel in
Frumos, o soluție lingvistică.
dave_thompson_085 avatar
drapel cn
Cuvântul folosit în mod normal acolo în engleză nu este „hear by” ci „hereby” (de asemenea, nu „here by”). Dar acestea ar fi (ambele!) greșeli plauzibile pe care le-ați putea folosi pentru a genera texte care par echivalente.
Puncte:0
drapel kz

Dacă primesc vreun mesaj, pot adăuga un spațiu sau un caracter tabulator pentru a primi două mesaje diferite. Fiecare dintre cele două, pot adăuga un alt spațiu sau filă pentru a obține patru mesaje posibile. Un al treilea caracter oferă 8 mesaje posibile, apoi 16 și așa mai departe.

Dacă iau „trimite 10.000” și adaugă 64 de caractere, iar fiecare dintre ele este fie un spațiu, fie un caracter tabulator, atunci primesc exact 2^64 de mesaje diferite. Și cu un hash pe 64 de biți, există șanse mari ca unul dintre aceste mesaje să aibă același cod hash ca și mesajul „trimite 10”.

Motivul pentru a adăuga spațiu sau tab, și nu orice caracter, este că cititorul nu va vedea aceste caractere. Dacă aș primi „Trimite 10.000 xlfe13^” aș fi suspicios.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.