Kas ir sadursmes uzbrukums?

Sadursmes uzbrukumi ir nopietna problēma kriptogrāfijas jomā. Noteiktos apstākļos uzbrucējs var tos izmantot, lai mazinātu nodrošināto drošību ciparparaksti , ļaujot tiem krāpnieciski likt datiem izskatīties tā, it kā tie būtu pārbaudīti attiecībā uz to integritāti un autentiskumu. Tas nozīmē, ka sadursmes uzbrukumi var apiet drošības mehānismus, uz kuriem paļaujamies, lai nodrošinātu mūsu tiešsaistes pasaules drošību.

Bet pirms jūs varat īsti saprast kas ir sadursmes uzbrukums , vispirms jāaptver galva kas patiesībā ir sadursme . Lai to izdarītu, mums ir jāsper vēl viens solis atpakaļ un jāpaātrina jūs jaukšana .

Kas ir jaukšana?

Kriptogrāfiskā jaukšanas funkcija ir algoritms, kam ir vairākas specifiskas īpašības kas izrādās neticami noderīgi kriptogrāfijas pasaulē. Viņi izmanto ievadi, ko bieži sauc par ziņojumu, kas pēc tam tiek palaists caur jaucējfunkciju, kā rezultātā tiek iegūta jaucēja, ko dažreiz sauc arī par ziņojuma īssavilkumu.

Ir arī jaucējfunkcijas, kas nav kriptogrāfijas, kas ir vienkāršāki algoritmi, ko bieži izmanto datu glabāšanā un izguvē. Tomēr tie ir tangenciāli sadursmju uzbrukumiem, tāpēc mēs neapgrūtināsim tos padziļināti apspriest.

Kriptogrāfisko jaucējfunkciju īpašības ietver:

• Jaucējfunkcijas ir deterministiskas — Ja viena un tā pati ievade tiek palaista, izmantojot noteiktu jaucējfunkciju, tā vienmēr rada tieši tādu pašu izvadi katru reizi.
• Jaucējfunkcijas izmanto patvaļīga izmēra datu ievades datus un vienmēr izvada noteikta garuma virkni — Jaucējfunkcija var uzņemt jebkura lieluma datus, sākot no vienas rakstzīmes līdz enciklopēdijai, kas pilna ar vārdiem. Neatkarīgi no ievades garuma, dotās jaucējfunkcijas izvade vienmēr ir vienāda garuma.
• Hash funkcijas ir viens no veidiem — Ir viegli iegūt ievadi, palaist to, izmantojot jaucējfunkciju, un pēc tam uzzināt, kāds ir atbilstošais jaucējvārds šai ievadei. Tomēr nav iespējams veikt jaucējkodu un pēc tam izdomāt, kāda ir sākotnējā ievade no jaucējkoda. Ar “vienvirziena” mēs domājam, ka ir praktiski aprēķināt jaucējfunkciju tikai vienā virzienā, nevis otrā virzienā.
• Jaucējfunkcijas var ātri aprēķināt — Lai jaucējfunkcijas būtu praktiskas, mums tās ir vajadzīgas, lai ziņojuma ievadi varētu ātri pārvērst par jaucējfunkciju. Tie būtu daudz mazāk noderīgi, ja process aizņemtu pārāk ilgu laiku un prasītu ievērojamu daudzumu skaitļošanas resursu.
• Nelielas izmaiņas ievadē rada būtiskas izmaiņas izvadē — Pat ja divas ievades ir identiskas, izņemot vienu rakstzīmi, kriptogrāfiskā jaucējfunkcija nodrošinās jaucējus, kuriem, šķiet, nav gandrīz nekā kopīga.
• Nav iespējams atrast divas dažādas ievades, kuru rezultāts ir vienāda izvade — Lai nodrošinātu drošību jaucējfunkciju lietojumos, uzbrucējam nedrīkst būt iespējams atrast divas dažādas ievades, kas rada vienu un to pašu jaucējfunkciju. Ja tiek atrastas divas ievades ar vienādu jaucējkodu, to sauc par a sadursme .

Tātad kriptogrāfiskajām jaucējfunkcijām ir visas šīs maģiskās īpašības, bet kā tās patiesībā izskatās?

Mēs sniegsim jums ātru demonstrāciju ar tiešsaistes hash kalkulators . Mūsu piesaistītais tīmekļa rīks ņem ievades datus un palaiž tos cauri SHA-256 kas ir zelta standarta jaucējfunkcija, un pēc tam nodrošina 256 bitu jaucējfunkciju.

Varat to izmēģināt ar jebkuru vēlamo ievadi, taču mēs apskatīsim dažas, lai parādītu dažas galvenās īpašības. Kad mēs izpildām “Kas ir jaukšana?” izmantojot kalkulatoru, mēs iegūstam šādu jaucēju:

2da0ed1070f7e7306a23785422576c864bdec63a6032482badc26fc5102f9a9c

Hash ir iekšā heksadecimāls , kas ir vienkārši atšķirīgs skaitīšanas veids. Tā vietā, lai izmantotu mums ierasto sistēmu, kurā ir 10 dažādi skaitļi (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), heksadecimālajam ir 16 (0, 1, 2, 3, 4 , 5, 6, 7, 8, 9, a, b, c, d, e, f). Hash ir 64 rakstzīmes garš, un heksadecimālajā apzīmējumā katra rakstzīme ir četri biti. Tas nozīmē ka hash ir 256 biti garš .

Mēģināsim citu ievadi, tikai vienu rakstzīmi “a”. Aprēķinot hash, mēs iegūstam:

ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb

Ņemiet vērā, ka, lai gan ieejām bija ievērojamas lieluma atšķirības, abām izvadēm ir vienāds garums — 64 rakstzīmes vai 256 biti. Kā jau teicām, viena no kriptogrāfiskās jaukšanas funkcijas īpašībām ir tāda, ka tās ņem jebkura garuma ievadi un vienmēr nodrošina fiksēta garuma izvadi. Jūs varētu mēģināt ievadīt veselu grāmatu SHA-256, un jūs joprojām iegūsit 256 bitu jaucēju. .Ņemiet vērā, ka tas faktiski nedarbosies mūsu piesaistītajā kalkulatorā, jo šim konkrētajam tīmekļa rīkam ir ierobežots rakstzīmju skaits, ko tas pieņems kā ievadi. Tomēr tas ir saistīts ar to, kā SHA-256 ir ieviests vietnē, nevis ar SHA-256 ierobežojumu.

Tagad parādīsim, kā pat nelielas izmaiņas ievadē rada ļoti atšķirīgu jaucējfunkciju. Ņemsim vērā mūsu iepriekšējo ievadi “Kas ir jaukšana?”, bet nomainiet jautājuma zīmi pret izsaukuma zīmi “Kas ir jaukšana!” Tās ir salīdzinoši nenozīmīgas izmaiņas, vai ne? Nu, redzēsim, ko mēs iegūstam, izmantojot jaucējfunkciju:

02a3603765eb85b8aa96aa8c18df75675a0670b33eb2c306e54d13a2baabffa5

Ja jūs salīdzināt šo hash ar pirmo, jūs redzēsiet, ka abiem būtībā nav nekā kopīga. Šī ir svarīga kriptogrāfijas jaucējfunkciju daļa, un šis īpašums ir pazīstams kā lavīnas efekts .

Ja esat pats izmēģinājis kalkulatoru, jūs redzēsit, ka šīs jaucējzīmes ir tādas ātri aprēķināts (ja vien jums nav lēns internets). Varat arī mēģināt to pašu ievadi atkal un atkal, un jūs redzēsit, ka ir arī jaucējfunkcija deterministisks — jūs vienmēr iegūsit to pašu rezultātu noteiktai ievadei.

Ir nedaudz grūtāk pierādīt, ka SHA-256 ir a vienvirziena funkcija un ka ir gandrīz neiespējami izdomāt sākotnējo ievadi, ja jums ir tikai hash. Ir arī grūti jums parādīt, ka tas tā ir nav iespējams atrast divus dažādus ievades datus, kas rada vienu un to pašu hash . Jums tikai jāuzticas mums par šiem rekvizītiem, jo ​​tiem ir galvenā nozīme drošu kriptogrāfijas jaucējfunkciju izstrādes procesā.

Jaucēju lietojumi

Tagad jums, iespējams, ir zināms priekšstats par to, kā izskatās jaucējfunkcijas un ko tās var darīt, taču kāda jēga ir pārvērst ievadi ciparu un burtu sajaukumā?

Izrādās, ka visi šie rekvizīti patiesībā ir diezgan noderīgi, un jaucējfunkcijas tiek ieviestas vairākās lielākās sistēmās. Lai adekvāti izprastu sadursmju uzbrukumu briesmas, ir svarīgi saprast, kur faktiski tiek izmantota kriptogrāfiskā jaukšana.

Digitālie paraksti

Ir viena izplatīta lietojumprogramma ciparparaksti . Ja ziņojuma sūtītājs vēlas pierādīt, ka tas tiešām ir no viņa, nevis krāpnieka, un arī to, ka pēc nosūtīšanas ziņojums nav mainīts, viņš to var izdarīt ar ciparparakstu. Tie ietver sertifikātus un publiskās atslēgas algoritmus, piemēram RSA papildus jaukšanai.

Digitālo parakstu īsā versija ir tāda autentiskumu un integritāti var pārbaudīt, ja sūtītājs palaiž savu ziņojumu, izmantojot kriptogrāfijas jaucējfunkciju , un pēc tam izpilda to, veicot aprēķinu kopā ar viņu privāto atslēgu. Pēc tam sūtītājs nosūta šo rezultātu kā ciparparakstu kopā ar savu ziņojumu adresātam.

Kad adresāts saņem ziņojumu, viņš var pārbaudīt tā integritāti un autentiskumu, palaižot ziņojumu, izmantojot jaucējfunkciju, lai iegūtu ziņojuma jaukšanu. Pēc tam viņi paņem no sūtītāja saņemto ciparparakstu un veic dažus aprēķinus ar sūtītāja publisko atslēgu.

Pēc tam viņi var salīdzināt šo rezultātu ar tikko aprēķināto ziņojuma jaucējkodu. Ja adresāta saņemtais ziņojums ir saglabājis savu integritāti un autentiskumu, šīm divām vērtībām jābūt vienādām .

Paroles jaukšana

Paroles atslēgvārda kodvārds autors Geralt licencēts saskaņā ar pixabay licence .

Vēl viens piemērs ir paroļu jaukšana. Ja uzņēmums saglabā jūsu paroli kā vienkāršu tekstu, jūs esat sajukums, ja hakeris uzlaužas un nozog viņu paroļu datu bāzi. Hakeris var vienkārši apskatīt datu bāzi un pēc tam izmantot vienkāršā teksta paroles, lai pieteiktos jebkurā kontā, tostarp jūsu kontā.

Tātad paroļu glabāšana vienkārša teksta veidā ir briesmīga drošībai , jo mēs nevaram garantēt, ka paroļu datubāzes nevarēsim piekļūt hakeriem.

Par laimi, kriptogrāfijas jaucējfunkcijas sniedz mums daudz labāku risinājumu. Tie ļauj izstrādātājiem pārbaudīt paroles, nekad nesaglabājot paroli kā vienkāršu tekstu datu bāzē. Kā jau minējām, būtībā nav iespējams atrast divus dažādus ievades datus, kas rada vienu un to pašu jaucējkodu , un arī nav iespējams veikt jaukšanu un pēc tam noskaidrot, kāda bija sākotnējā ievade.

Tas nozīmē, ka, izveidojot kontu un ievadot savu lietotājvārdu un paroli, izstrādātāji var nekavējoties sajaukt jūsu paroli un saglabāt tikai jaukto, nevis jūsu paroles vienkāršu tekstu . Ikreiz, kad dodaties, lai pieteiktos, viņi vienkārši sajauc jūsu paroli, tiklīdz to ievadāt, un pēc tam salīdzina to ar jaukšanu, ko viņi ir saglabājuši datu bāzē.

Ja abi sakrīt, izstrādātāji pieņem, ka abas reizes ievadījāt vienu un to pašu paroli un ka tādējādi esat viens un tas pats lietotājs. Tātad tie piešķir jums piekļuvi jūsu kontam, nezinot, kāda patiesībā ir jūsu parole .

Ja hakeris nozog paroļu jaucējkodu datu bāzi, viņam ir daudz grūtāk tos ļaunprātīgi izmantot, nekā tad, ja viņš paroles būtu nozadzis vienkāršā tekstā. Ņemot vērā drošo kriptogrāfijas jaucējfunkciju raksturu un to, ka ir maz ticams, ka divas dažādas ievades varētu radīt vienu un to pašu jaucējfunkciju, mums nav pārāk jāuztraucas par to, ka uzbrucējs ļaunprātīgi izmanto sistēmu un ievadīs nepareizu paroli, kas joprojām rada rezultātu. atbilstošajā hashā.

Citi kriptogrāfisko jaucēju lietojumi

Kriptogrāfiskajām jauktām ir virkne citu lietojumu. Tie ietver:

• Ziņojumu autentifikācijas kodi (MAC)
• Blockchain darba pierādījuma sistēmas
• Datu pirkstu nospiedumu noņemšana
• Kontrolsummas, kas atklāj datu bojājumus

Kas ir sadursme?

Šobrīd mēs zinām, ka jaucējvērtības patiešām ir noderīgas. Mēs arī īsi pieminējām ievadā, ka sadursmes ir drauds noteiktos scenārijos, kad tiek ieviestas kriptogrāfijas jaucējfunkcijas. Bet kas patiesībā ir sadursme?

Atcerieties, kā mēs teicām, ka nevajadzētu būt iespējamam, ja divas dažādas ievades kriptogrāfijas jaucējfunkcijā rada vienu un to pašu jaucējfunkciju?

Nu... sadursme ir tad, kad viss nenotiek, kā plānots, un divas atsevišķas ievades faktiski rada tādu pašu jaucējvērtību . Kā jau teicām, tam nevajadzētu notikt, un tas var būt neticami problemātiski, ja tā notiek. Ja sadursmes ir praktiskas, tas ļauj uzbrucējiem pilnībā iedragāt digitālo parakstu integritāti un autentifikācijas aspektus. Tas var radīt visa veida problēmas, tostarp krāpšanu un ļaut uzbrucējiem apiet esošās drošības sistēmas.

Mēs jums atklāsim nelielu noslēpumu: patiesībā nav iespējams izveidot jaucējfunkciju, lai pilnībā izvairītos no sadursmēm.

Tas ir saistīts ar baložu cauruma princips . Jaukšanas kontekstā tas būtībā nosaka, ka, ja ievades datu ir vairāk nekā iespējamo jaucējkodu, tad dažiem ievadiem ir jārada tādas pašas jaucējzīmes.

Kā jau minējām, SHA-256 jaucējvērtības ir 256 bitus garas. Tas nozīmē ka ir maksimālais SHA-256 jaucējvaras izmērs , tāpat kā tad, ja jūsu automašīnas odometrā ir tikai seši cipari, maksimālā vērtība, ko tas var parādīt, ir 999 999. Ja ir maksimālais jaukšanas lielums, tas nozīmē arī to, ka ir ierobežots iespējamo jaucēju skaits.

Daudziem no mums ir grūti iedomāties, cik liels ir 256 biti. Ja jūs saskaitītu visas iespējamās heksadecimālās SHA-256 jaucējzīmes, jūs iegūtu šādu skaitli decimāldaļās:

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,963,

Tas ir patiešām liels skaitlis, taču tas joprojām ir skaitlis, ko varam izrakstīt un parādīt vienā vai divās rindās.

Tagad padomāsim par visām iespējamām dažādajām ievadēm, kuras mēs varētu palaist, izmantojot SHA-256. Jebkas no “0” līdz “aardvark” līdz veselai vārdnīcai vai veseliem Šekspīra darbiem. Tiešām, iespējas ir bezgalīgas . Tas mūs noved pie problemātiska secinājuma: Bezgalība ir daudz lielāka nekā 256 bitu skaitlis, ko mēs rakstījām iepriekš. Saskaņā ar baložu cauruma principu, tas, ka mums ir bezgalīgi daudz ievades, bet ierobežots skaits iespējamo jaucēju, nozīmē, ka katram atsevišķam jaucējfailam ir jābūt daudz dažādu ievades datu, kas to var radīt .

Vai tas nozīmē, ka viss, par ko mēs runājām, ir veidots uz vāja pamata un ka tas viss jebkurā brīdī sabruks?

Nav nepieciešams.

Jūs noteikti būsiet ievērojuši, ka mēs nekad neesam norādījuši, ka kriptogrāfiskā jaucējfunkcija var nekad ir divas atsevišķas ieejas, kas rada vienu un to pašu izvadi. Tā vietā mēs paziņojām, ka tā ir nav iespējams (vai būtībā neiespējami), lai atrastu divas dažādas ievades, kas rada vienu un to pašu izvadi.

Nav īsti svarīgi, vai teorētiski ir iespējamas vairākas dažādas sadursmes. Drošības nolūkos patiešām svarīgi ir tas, ka nevienam vienkārši nav praktiski atrast šīs jaucējkodas. Iespējamās sadursmes var peldēt ēterī, ko viņi vēlas, taču tās nevar radīt mums nekādas problēmas, ja cilvēki tās nevar atrast.

Tātad drošas kriptogrāfijas jaucējfunkcijas mērķis ir pilnībā izvairīties no sadursmēm . Tas būtu muļķīgs uzdevums, jo baložu cauruma princips pierāda, ka tas ir matemātiski neiespējami. Tā vietā mēs tikai vēlamies, lai kriptogrāfijas jaucējfunkcijas, piemēram, SHA-256, būtu izturīgas pret sadursmēm, padarot šīs sadursmes atrast neticami grūti ikvienam.

Dzimšanas dienas paradokss

Dzimšanas dienas torte ar svecēm Annija Spratta licencēta saskaņā ar CC0 1.0 .

Lai noteiktu, cik drošs ir jaukšanas algoritms, mums ir jāsaprot, cik iespējamas ir sadursmes. Viena no lielākajām komplikācijām ir tā, ka tās patiesībā ir daudz lielāka iespējamība, nekā to varētu teikt jūsu intuīcija. Labākais pierādījums tam ir dzimšanas dienas paradokss .

Pieņemsim, ka izvēlaties nejaušu cilvēku izlasi un jūs interesē šajā izlasē atrast cilvēkus, kuriem ir vienāda dzimšanas diena. Jums, iespējams, vajadzētu vairāk nekā simtu, lai būtu cīņas iespēja, vai ne? Galu galā gadā ir 365 dienas.

Nē, ja ir tikai 23 personas, jums jau ir lielāka par 50% iespējamība, ka diviem cilvēkiem grupā būs kopīga dzimšanas diena .

Bet kā tas var būt?

Jūs, iespējams, domājat par to tāpat kā lielākā daļa no mums, proti, jūs domājat atrast atbilstību konkrētam datumam vai konkrētai personai izlasē, nevis aplūkot to, lai redzētu, vai izlasē ir kādi divi cilvēki. dalīties ar dzimšanas dienu.

Parādīsim atšķirību starp šiem diviem dažādajiem skatīšanās veidiem. Ja Džeisons ir dzimis 1. janvārī un jūs vēlējāties izveidot pietiekami lielu izlasi, lai būtu lielāka par 50 procentiem iespēja, ka kāds dalīsies savā dzimšanas dienā 1. janvārī, tad jūsu intuīcija ir pareiza. Jūs vēlētos, lai šajā izlasē būtu aptuveni 183 personas, lai būtu 50 procentu iespēja sakritīs.

Bet mēs nemeklējam a specifisks atbilstību dzimšanas dienas paradoksā, mēs meklējam jebkura atbilst . Ar 23 personām mums faktiski ir daudz dažādu iespējamo sakritību. Mēs ne tikai pārbaudām, vai Džeisonam ir tāda pati dzimšanas diena kā kādam no pārējiem 22 cilvēkiem, bet arī, vai katram no viņiem ir tāda pati dzimšanas diena kā jebkurai citai personai grupā. Kad jūs faktiski saīsināt skaitļus, jūs nonākat pie sekojošā:

(23 x 22)/2 = 253

Tas ir 253 spēles no 23 cilvēku grupas. Ņemot vērā, ka gadā ir tikai 365 dienas, šis sakritību skaits mums rada iespēju, kas ir daudz lielāka par 50 procentiem .

Protams, dzimšanas dienas paradokss negarantē, ka ikvienam būs atbilstošas ​​dzimšanas dienas, tikai to, ka iespēja, ka dzimšanas dienas notiks, ir daudz lielāka, nekā mēs varētu intuitīvi domāt.

Nē, mēs neizmantojām nejaušu pieskārienu, jo esam dzimšanas dienas svinību entuziasti. Dzimšanas dienas paradokss ir tieši saistīts ar hash sadursmju iespējamību.

Ja nedaudz sakratat šo metaforu un domājat par iespējamību, ka radīsies sakritības jaucējkodoli, nevis dzimšanas datumi, mēs saprotam, ka iespēja atrast sadursmi SHA-256 nav 1/115,792,089,237,316,195,423,570,985,008,6,6,8,6,8,6,6,8 0,564,039,457,584,007,913,129,639,936 (mūsu 256 bitu skaitlis ir norādīts decimāldaļās) kā mēs varētu gaidīt.

Iespēja patiesībā ir daudz lielāka, jo mēs meklējam jebkura iespējamā sadursme , nevis tikai konkrēta sadursme noteiktam hash.

Tātad, kāda ir iespēja?

Ja dzimšanas dienas paradokss nebūtu stājies spēkā, mēs būtu gaidījuši, ka pēc 50 procentiem no kopējām kombinācijām tiks atrasts atbilstošs sajaukums. Īsāk sakot, tas ir pēc 2. mēģinājuma²⁵⁵hashes.

Dzimšanas dienas uzbrukumā mēs varam izmantot šādu formulu, lai aptuveni noskaidrotu, cik daudz jaucējkodu mums būtu jāiziet, lai sasniegtu tādu pašu varbūtību atrast atbilstību:

divi^(m/2)

Kur m = hash bitu lielums.

Tāpēc, izpildot skaitļus SHA-256 256 bitu jaukšanas garumam, mēs iegūstam:

divi^(256/2)

divi⁽¹²⁸⁾

Tātad SHA-256 dzimšanas dienas uzbrukums ir samazinājis jaucējkodu skaitu no 2²⁵⁵uz 2¹²⁸. Ja neesat pārāk pazīstams ar šāda veida matemātiku, ir viegli domāt, ka dzimšanas dienas uzbrukums to samazina tikai uz pusi. Patiesībā atšķirība ir daudz lielāka.

Nākamais skaitlis ir 2²⁵⁵rakstīts decimāldaļās:

57,896,044,618,658,097,711,785,492,504,343,953,926,634,992,332,820,282,019,728,792,003,956,569681,

Un sekojošais ir 2¹²⁸

340,282,366,920,938,463,463,374,607,431,768,211,456

Kā redzat, starp abiem skaitļiem ir liela atšķirība, tāpēc dzimšanas dienas uzbrukums ievērojami atvieglo uzbrucējam atbilstošas ​​jaukšanas atrašanu, nekā jūs varētu gaidīt .

Paturot to prātā, īkšķis ir tāds, ka 256 bitu jaucējkods, piemēram, SHA-256, tiek samazināts līdz 128 bitiem, ņemot vērā dzimšanas dienas uzbrukumus, nevis brutālu spēku. Tāpat, MD5 128 biti ir samazināti līdz 64 bitiem pret dzimšanas dienas uzbrukumiem.

Kas ir sadursmes uzbrukums?

Sadursmes uzbrukums ir vienkārši tad, kad uzbrucējs atrod kādu no šīm sadursmēm un izmanto to, lai mazinātu drošību, kuru, domājams, nodrošina hash.

Sadursmes uzbrukumu piemēri

Šeit ir daži izplatīti sadursmes uzbrukumu piemēri:

Brīvā starta sadursmes uzbrukumi

Freestart sadursmes uzbrukumi ir iespējami hash funkcijās, kuru pamatā ir Merkle Damgard celtniecība . Tas nozīmē ka MD5 , SHA-1 un SHA-2 ir neaizsargāti, bet ne SHA-3, kas ir izstrādāts ar sūkļa konstrukciju.

Normālos apstākļos , pirmajā Merkles-Damgarda jaucējfunkcijas kārtā, ieejas ir iepriekš definētu inicializācijas vektoru kopa , kā arī pirmais ziņojumu datu bloks. Iespējams, vēlēsities atsaukties uz šo rakstu par MD5 algoritms ja jums nepieciešama papildu informācija par jaucējfunkciju darbību.

Brīvā starta sadursme ir atšķirīga, jo tā ietver ļaujot uzbrucējam izvēlēties savus inicializācijas vektorus . Tas viņiem ļauj samazināt jaucējfunkcijas drošību. Kāpēc lai kāds to darītu? Pētnieki to dara laboratorijā, jo tas ļauj viņiem rotaļāties ar jaucējfunkcijām un sniedz labāku ieskatu viņu vājajās vietās.

Tie nav praktiski uzbrukumi drošas jaucējfunkcijas ieviešanai , jo patiesībā uzbrucējs nevar izvēlēties inicializācijas vektorus. Tomēr tie ir svarīgi, lai varētu izprast konkrētās jaucējfunkcijas trūkumus un nākotnē izstrādāt labākas kriptogrāfiskās jaucējfunkcijas.

Klasisks sadursmes uzbrukums

Klasiskā sadursmes uzbrukumā mērķis ir atrast divus dažādus ziņojumus, kas abi rada vienu un to pašu jaucējkodu. Ja mēs vēlamies iegūt iedomu un uzrakstīt to matemātiski:

• 1. ziņojums: x
• 2. ziņojums: un
• H(): jaukums no ()

Tāpēc klasiskajā sadursmes uzbrukumā uzbrucējs atrod divus ziņojumus, kur ziņa x nav vienāds ziņa un , bet hash no x ir vienāds ar hash no y . Citiem vārdiem sakot:

x ≠ y

Bet:

H(x) = H(y)

Veiksmīga sadursmes uzbrukuma izredzes ir atkarīgas ne tikai no jaucējfaila lieluma, bet arī no iespējamām kriptogrāfijas jaucējfunkcijas nepilnībām. Kā mēs apspriedām, pat ja jaukšanas funkcijai nav zināmu trūkumu, mums joprojām ir jāuztraucas par dzimšanas dienas uzbrukumiem, nevis tikai brutālā spēka uzbrukumi, kas ir daudz grūtāki, jo uzbrucējam ir sistemātiski jāizskrien cauri katrai kombinācijai, līdz tiek konstatēta sadursme .

Klasisko sadursmju uzbrukumu sekas

Aplūkojot vienādojumu H(x) = H(y), var būt grūti saprast, ko tas patiesībā nozīmē drošībai. Padarīsim to konkrētāku, sniedzot piemēru.

Pieņemsim, ka Džeina strādā uzņēmumā un vēlas ātri kļūt bagāta. Pieņemsim, ka viņa katru nedēļu PDF formātā saņem algas lapas par 1000 ASV dolāru. Katru nedēļu viņas priekšnieks digitāli paraksta algas čekus, lai algu saraksts zinātu, ka tie ir likumīgi.

Priekšnieka ciparparaksts būs balstīts uz algas lapas pdf jauktu . Tāpēc Džeina paņem dokumentu par savu 1000 ASV dolāru algas lapu un sāk ar to ķēpāties. Pirmkārt, viņa maina 1000 USD uz 1 000 000 USD. Bet, kad viņa sajauc šo dokumentu, hash vairs nesakritīs ar ciparparakstu, jo dokuments ir mainījies . Ja viņa mēģina panākt, lai algas maksātu, tad, kad viņi dosies pārbaudīt parakstu, viņi redzēs, ka tas nesakrīt un ka algas lapa ir neleģitīma.

Taču Džeina ir pārāk gudra, lai viņas viltus šādi izjauktu, tāpēc viņa atgriežas pie dokumenta. Viņa sāk eksperimentēt ar dažādiem fontiem, dažādiem izmēriem, mainot piemales, mainot krāsu, mainot formulējumu un vēl tūkstoš sīku izmaiņu. Viņa atkārtoti sajauc dokumentu, lai noskaidrotu, vai izmaiņas viņai atbilst. Galu galā, pēc neskaitāmām izmaiņām un daudz kafijas, notiek brīnums, un hash ir tieši tāds pats kā sākotnējās 1000 USD algas lapas jauktais.

Visas šīs izmaiņas ir bijušas salīdzinoši nelielas. Pat lietas, kas tikai nedaudz maina dokumenta izskatu, radīs pilnīgi atšķirīgas jaucējzīmes viņa ir spējusi izveidot dokumentu, kas šķiet likumīgs, bet patiesībā tā nav .

Viss, kas Džeinai ir jādara, ir jānoņem šī sava 1 000 000 ASV dolāru algas biļetena versija algu sarakstā kopā ar oriģinālo ciparparakstu. Algas var pacelt uzaci, bet kad viņi dodas pārbaudīt ciparparakstu, viss izdodas. Viņiem tas šķiet likumīgi , un viņiem nav pietiekami atalgots, lai uzdotu jautājumus, tāpēc viņi apstiprina Džeinas miljonu dolāru algu. Brīdī, kad grāmatvedības nodaļa noskaidro Džeinas viltīgo maldināšanu, viņa jau atrodas pludmalē, malkojot mohito valstī, kas netiek izdota.

Tas ir nedaudz pārspīlēts piemērs, taču tas parāda klasisko sadursmju uzbrukumu radītos draudus. Kad tie ir iespējami, tie ļauj uzbrucējam iedragāt digitālo parakstu integritāti un autentiskumu , ļaujot viņiem radīt visa veida nepatikšanas, piemēram, krāpšanu. Tāpēc mūsu kriptogrāfijas jaukšanas algoritmiem ir jābūt izturīgiem pret sadursmēm.

Izvēlētā prefiksa sadursmes uzbrukumi

Izvēlētā prefiksa sadursmes uzbrukumi ir vēl viens sadursmes veids, pret kuru Merkle-Damgard jaucējfunkcijas ir neaizsargātas. Tie ir ievērojami sarežģītāki, taču tādos apstākļos, kad tie ir iespējami, tie rada daudz lielākus draudus nekā klasiskie sadursmes uzbrukumi. .

Atšķirībā no klasiskajiem sadursmes uzbrukumiem, ko mēs aprakstījām iepriekš, izvēlētā prefiksa sadursme ietver papildu ierobežojumus. Tā vietā, lai tikai varētu atrast visas iespējamās sadursmes, uzbrucējam ir jāspēj atrast sadursmes, kas ietver divus iepriekš noteiktus prefiksus.

Pretiniekam tiek doti divi ziņojumu prefiksi, kas būtībā nozīmē, ka viņam tiek dotas divas atsevišķas datu virknes. Pēc tam pretinieks tiek aicināts atrast atsevišķu ziņojumu katram prefiksam, kur gan prefiksa, gan ziņojuma kombinācijai ir viens un tas pats jaukums. Mēs nemelosim, var būt nedaudz grūti aplauzt galvu, ja nenodarbojaties ar kriptogrāfiju.

Formālākā apzīmējumā prefiksi ir P un P’, savukārt ziņojumi ir M un M’. Tātad, ņemot vērā P un P’, hakeram jāatrod ziņojumi M un M’, kur:

H(P || M) = H(P’ || M’)

Iepriekš minētajā vienādojumā, || apzīmē sasaisti , kas būtībā nozīmē, ka prefikss un ziņojums ir savienoti viens ar otru.

Izvēlēto prefiksu sadursmes uzbrukumu sekas

Izvēlēta prefiksa sadursmes uzbrukuma rezultāts ir ļoti līdzīgs klasisko sadursmes uzbrukumu rezultātiem. Būtībā uzbrucējs var apdraudēt autentifikācijas un integritātes pasākumus, ļaujot tiem veikt krāpšanu un maldināšanu, tāpat kā mēs to demonstrējām Klasisko sadursmju uzbrukumu sekas sadaļā.

Galvenā atšķirība ir tā, ka izvēlēto prefiksu sadursmes ir daudz grūtāk panākt papildu ierobežojumu dēļ. Tomēr, ja tie ir iespējami, uzbrucējam ir daudz vieglāk izveidot dokumentus, kas rada atbilstošus jaucējus.

Uzbrucējiem nav jācenšas veikt bezgalīgas izmaiņas, cerot galu galā nākt klajā ar citu dokumentu, kas rada tādu pašu jaucējkrānu. Tā vietā viņi var vienkārši izveidot divus dažādus dokumentus, papildināt tos tā, lai tie būtu vienāda garuma, un pēc tam pievienot īpaši aprēķinātu datu virkni, kā rezultātā abiem dokumentiem ir vienādas jaucējzīmes. Tas ievērojami atvieglo dažādu dokumentu izveidi, kuriem joprojām ir atbilstošas ​​jaucējzīmes.

Preimage uzbrukumi

Priekšattēlu uzbrukumi ir saistīti ar sadursmju uzbrukumiem, taču tie ietver mēģinājumu atrast ziņojumus, kuru rezultātā tiek izveidoti specifiski jaucēji. Mēs par tiem sīkāk iedziļināsimies nākamajā rakstā, taču šobrīd jums ir jāzina, ka:

• Priekšattēla uzbrukums — Ietver dotā jaucējkoda ņemšanu un pēc tam sākotnējās ievades izdomāšanu, kas to radīja.
• Otrs priekšattēla uzbrukums — ietver noteiktas ievades ņemšanu un citas ievades atrašanu, kur abas ievades rada vienu un to pašu jaucējkodu.

Sadursmes MD5

MD5 ir veca jaucējfunkcija, kas vairs netiek uzskatīta par drošu daudzām lietojumprogrammām. Tas rada 128 bitu jaucējus, kas Ja ņem vērā dzimšanas dienas uzbrukumus, tas patiešām nozīmē, ka tam ir tikai 64 biti drošības .

Deviņdesmitajos gados gan pseido-sadursmi, gan daļēji brīvā starta sadursmi atklāja atsevišķi pētnieki . Lai gan šīs bija satraucošas apsūdzības par MD5 turpmāko drošību, arī nebija patiesas sadursmes .

Tikai 2004. gadā akadēmiķu komanda publicēja pilnas MD5 sadursmes. Viņi spēja atrast MD5 sadursmes mazāk nekā stundas laikā ar IBM P690. Tas parādīja, ka MD5 patiešām ir bojāts, un pasaulei bija ātri jāatsakās no MD5, lai novērstu sadursmju uzbrukumu plašu izplatību reālajā pasaulē.

Izvēlēta prefiksa sadursmes uzbrukums vispirms tika parādīts pret MD5 in 2007. gads . Pētnieki to paveica ar paredzamajām izmaksām divi^piecdesmit . Tas darbojas kaut kur valstībā tūkstoš triljoni mēģinājumu pirms gaidāma sadursme. Tomēr tajā laikā praktiskie uzbrukuma pielietojumi bija ierobežoti.

Pētnieki pārbaudīja arī klasiskās sadursmes MD5, un viņi to atklāja jaucējfunkcijas nepilnības ļāva izveidot divus X.509 sertifikātus ar vienu un to pašu parakstu . Tas nozīmēja svarīgas reālās pasaules sekas, jo tas nozīmēja, ka mēs vairs nevarējām uzticēties to X.509 sertifikātu autentiskumam, kuri izmantoja MD5 jaucējus.

Ir notikušas vairākas citas sadursmes pret MD5, gan teorētiskas, gan praktiskas. Tomēr, tā kā algoritms jau ir labi un patiesi bojāts daudziem mērķiem, nav vērts tajos iedziļināties.

Sadursmes SHA-1

SHA-1 ražo 160 bitus garus jaucējus, kas praksē nodrošina 80 bitu drošību pret dzimšanas dienas uzbrukumiem. 2005. gadā viena akadēmiķu komanda konstatētas sadursmes 53 kārtu samazinātā SHA-1 versijā. Pilnam SHA-1 faktiski ir 80 kārtas, kas būtībā ir to reižu skaits, kad ievades tiek sajauktas, izmantojot algoritmu. Lai gan 53 raundu sadursme ir nozīmīga, tas joprojām ir tālu no pilnas 80 raundu sadursmes.

Arī tajā gadā atsevišķa pētnieku komanda ierosināja uzbrukumu konstatētas sadursmes mazāk nekā divi⁶⁹operācijas (tas ir 590 295 810 35 8 705 651 712 mēģinājumi) , kas bija būtisks uzlabojums brutālā spēka uzbrukumos. Viņu pieeja tika balstīta uz diferenciālu uzbrukumu, kā arī ziņojumu modifikāciju un vairāku bloku sadursmes paņēmieniem.

Līdz 2005. gada augustam uzbrukums tika uzlabots tiktāl, ka SHA-1 sadursmes varēja konstatēt divi⁶³operācijas .

2006. gadā tika novērots ievērojams sadursmju uzlabojums, samazinot SHA-1 kārtu, pētniekam publicējot atklājumus par sadursmi 64 kārtas . 2010. gadā bija vēl viens lēciens, un cits pētnieks to izvirzīja 73 kārtas . Šī bija tikai vēl viena zīme, ka SHA-1 dienas ir skaitītas.

2011. gadā NIST novecojis SHA-1 , norādot, ka to vairs nevajadzētu ieviest. 2012. gadā Marks Stīvenss lēsa, ka diferenciālā ceļa uzbrukums varētu izjaukt vienu SHA-1 jaucēju par maksu 2,77 miljoni ASV dolāru .

Pirmais brīvā starta sadursme pret SHA-1 tika konstatēts 2015. Uzbrukums, dublēts ar radošo nosaukumu SHAPING , 64 GPU klasterī bija nepieciešamas tikai 10 dienas.

SHAppeningam sekoja SADALĪTS , turpinot kriptogrāfijas vārdu spēli. SHAttered notika 2017. gadā, un tā bija pirmā klasiskā sadursme, kas atklāta SHA-1. Tik skaidri demonstrējot pilnīgu sadursmi, tas bija pilnīgi skaidrs SHA-1 vairs nevarēja garantēt failu vai ciparparakstu integritāti un autentifikāciju .

2020. gadā akadēmiķi publicēja izvēlēta prefiksa sadursmes uzbrukumu pret SHA-1. Raksta nosaukums apstiprināja jaunizveidoto tradīciju un SHA-1 ir Shambles parādīja, ka uzbrucējiem tagad ir vēl vieglāk izjaukt integritātes un autentifikācijas pasākumus. Lai gan SHA-1 jau sen tika uzskatīts par nedrošu, šī bija pirmā publiski atklātā izvēlētā prefiksa sadursme.

Lai gan SHA-1 nav drošs lietošanai tādās lietās kā ciparparaksti, tas joprojām ir pareizi ieviests uz jaucējkodā balstītā ziņojumu autentifikācijas kodā (HMAC).

Sadursmes SHA-2

SHA-2 ir pašlaik tiek uzskatīts par zelta standartu kriptogrāfijas algoritmos , un tas ir plaši ieviests visā mūsu digitālajā pasaulē.

Faktam, ka tas joprojām tiek uzskatīts par drošu, vajadzētu dot jums mājienu, ka sadursmes šajā posmā nav pārāk ietekmējušas to. Ja būtu atrastas klasiskās sadursmes vai izvēlēto prefiksu sadursmes, mums visiem būtu ļoti jāuztraucas par mūsu tiešsaistes drošību.

Lai gan tas joprojām tiek uzskatīts par drošu, kriptogrāfi ir smagi strādājuši, cenšoties to izjaukt. SHA-256 ir 256 bitu algoritms, kas nodrošina 128 bitu drošību pret dzimšanas dienas uzbrukumiem . SHA-512 bitu garums ir divreiz lielāks, nodrošinot 256 bitu drošību pret dzimšanas dienas uzbrukumiem.

Vēl 2008. gadā varēja atrast labāko samazināto kārtu uzbrukumu sadursmes 24 no SHA-256 80 kārtām un 24 no SHA-512 80 kārtām. 2011. gadā varēja izraisīt augstākas pakāpes diferenciāls uzbrukums pseido-sadursmes 33. no SHA-256 64 kārtām.

A papīrs 2013. gadā demonstrēja sadursmes pret 31 SHA-256 kārtu , un daļēji brīvā starta sadursmes pret 38 raundiem. 2014. gadā a papīra zondēšana SHA-512 diferenciālās sadursmes meklēšanā izmantoja sazarošanas heiristiku, kā rezultātā 38 no 80 raundiem notika pseido sadursme.

2016. gadā pētnieki analizēja gan SHA-256, gan SHA-512 . Viņi atrada praktiskas sadursmes pret 28 no SHA-256 64 kārtām un sadursmes pret 27 no SHA-512 80 kārtām . Viņi arī konstatēja pseido sadursmi pret 39 SHA-512 kārtām.

Katrs no šiem uzbrukumiem joprojām ir tālu no tā, lai radītu nozīmīgus draudus SHA-2 drošībai. Šajā posmā mums nav pārāk jāuztraucas par sadursmēm ar SHA-2. Tomēr joprojām ir ļoti svarīgi, lai pētnieki turpinātu pētīt SHA-2 un meklēt trūkumus. Ja viņi to nedarīs, nacionālās valstis un organizētie noziedznieki joprojām to darīs, un viņi mums neteiks, kad viņiem izdosies atrast iespējamas sadursmes.

Sadursmes SHA-3

SHA-3 ir jaunākais Secure Hash algoritmu līnijā. Mēs neredzam, ka SHA-3 tiek ieviests pārāk bieži, jo SHA-2 joprojām tiek uzskatīts par drošu , un šajā posmā nav lielas jēgas tērēt pūles, lai pārietu.

Lai gan tas ir jaunāks, tas ne vienmēr ir drošāks par SHA-2. Abiem ir krasi atšķirīgs iekšējais dizains un SHA-3 nav tik daudz pētīts kā SHA-2, jo tas ir salīdzinoši nesen . Tā vietā, lai to uzskatītu par SHA-2 jauninājumu, labāk to uzskatīt par rezerves daļu, jo mēs patiešām nezinām, kurš algoritms izturēs laika pārbaudi.

Tomēr divu pilnīgi atšķirīgu kriptogrāfijas jaukšanas algoritmu priekšrocība ir tāda, ka, ja tiek konstatēts uzbrukums vienam no tiem, tiek pieņemts, ka otrs joprojām būs izturīgs. Tas nozīmē, ka vajadzības gadījumā mēs varētu ātri pārslēgties uz otru.

Tagad, kad jūs saprotat SHA-3 lomu, mēs varam apskatīt dažus no labākajiem uzbrukumiem pret to. 2012. gadā a papīrs tika izdots kas parādīja sadursmes līdz pat piecās algoritma kārtās kas kļūs par SHA-3. Pētnieki izmantoja vispārinātas iekšējās atšķirības, lai mērķētu uz vairākām algoritma versijām, kas pazīstamas kā Keccak.

Pētnieki atklāja sadursmes gan Keccak-384, gan Keccak-512 trīskārtu versijām. Viņi arī atrada uzbrukumu, kas bija 2^{Četri. Pieci}reizes ātrāk nekā dzimšanas dienas uzbrukums pret 4 raundu Keccak-384. Pret Keccak-256 viņiem izdevās atrast sadursmes piecus raundus . Tomēr šie mēģinājumi bija tālu no tā, lai radītu draudus algoritmiem, kuriem katram ir 24 kārtas.

Līdz 2019. gadam SHA-3 algoritms bija pabeigts, un akadēmiķu grupa publicēja citu rakstu par uzbrukumiem tai. Atšķirības starp Keccak un SHA-3 galīgo versiju ir tik nelielas, ka šīs divas drošības analīzes būtībā pārbaudīja vienu un to pašu.

Šis otrais raksts tika veidots, pamatojoties uz agrāko pētnieku darbu, un šoreiz to veidoja akadēmiķi spēj panākt sadursmes pret sešām SHA-3 kārtām . Lai gan šis lēciens uzrādīja zināmu progresu, tas joprojām ir tālu no apdraudējuma līdz pilnām 24 SHA-3 kārtām.

Jūsu sistēmu aizsardzība pret sadursmes uzbrukumiem

Vidējais Džo nevar darīt pārāk daudz, lai nodrošinātu sevi pret sadursmēm, izņemot tādas pamata lietas kā atjaunināšana uz jaunākajām versijām lai pārliecinātos, ka viņi neizmanto ievainojamu programmatūru no 2002. gada.

Izstrādātājiem ir jānodrošina, ka viņi izmanto tikai tos kriptogrāfijas jaukšanas algoritmus, kas ir droši savam mērķim . Tādu lietu gadījumā kā ciparparaksti ir jāizmanto tādi algoritmi kā SHA-2 vai SHA-3, lai nodrošinātu parakstu integritāti un autentifikāciju.

Turklāt izstrādātājiem ir jāreģistrējas ik pēc dažiem gadiem, lai sekotu līdzi izmantoto algoritmu drošības statusam. Ja uzbrukumi viņu ieviestajam jaukšanas algoritmam kļūst arvien smagāki, tiem jāsāk pārslēgšanās process. Ja viņi to nedara, viņu sistēmas var būt neaizsargātas pret sadursmju uzbrukumiem un krāpšanu, kas tos ieskauj.