(niekedy hashovanie, anglicky hashing) - prevod poľa vstupných údajov ľubovoľnej dĺžky na výstupný bitový reťazec pevnej dĺžky. Takéto transformácie sa tiež nazývajú hašovacie funkcie alebo redukčné funkcie a ich výsledky sa nazývajú haš, hašovací kód alebo súhrn správy.
Hašovanie sa používa na porovnávanie údajov: ak majú dve polia rôzne hašovacie kódy, je zaručené, že polia budú odlišné; ak sú rovnaké, polia sú s najväčšou pravdepodobnosťou rovnaké. Vo všeobecnom prípade neexistuje žiadna individuálna zhoda medzi zdrojovými údajmi a hašovacím kódom v dôsledku skutočnosti, že počet hodnôt hašovacej funkcie je menší ako počet variantov vstupného poľa; existuje veľa polí, ktoré dávajú rovnaké hash kódy - takzvané kolízie. Pravdepodobnosť kolízií hrá dôležitú úlohu pri hodnotení kvality hašovacích funkcií.
Existuje mnoho hashovacích algoritmov s rôznymi charakteristikami (bitová kapacita, výpočtová zložitosť, kryptografická sila atď.). Výber jednej alebo druhej hašovacej funkcie je určený špecifikami riešeného problému. Najjednoduchšie príklady hašovacích funkcií sú kontrolný súčet alebo CRC.
Kontrolné súčty
Nekomplikované, extrémne rýchle a jednoducho implementované hardvérové algoritmy používané na ochranu pred neúmyselným skreslením vrátane hardvérových chýb.Rýchlosť výpočtu je desiatky a stokrát rýchlejšia ako kryptografické hašovacie funkcie a oveľa jednoduchšia v hardvérovej implementácii.
Cenou za takú vysokú rýchlosť je nedostatočná kryptografická sila – jednoduchá možnosť upraviť správu na vopred známe množstvo. Kontrolné súčty (typické: 32 bitov) sú tiež zvyčajne menšie ako kryptografické hash (typické: 128, 160 a 256 bitov), čo znamená, že môžu nastať neúmyselné kolízie. Najjednoduchším prípadom takéhoto algoritmu je rozdelenie správy na 32- alebo 16-bitové slová a ich súčet, čo sa používa napríklad v TCP/IP.
Spravidla je takýto algoritmus potrebný na sledovanie typických hardvérových chýb, ako je niekoľko po sebe idúcich chybných bitov danej dĺžky. Takzvaná rodina algoritmov „kódy cyklickej redundancie“ spĺňajú tieto požiadavky. Patrí medzi ne napríklad CRC32, ktorý sa používa v ethernetových zariadeniach a vo formáte súboru ZIP.
Kryptografické hašovacie funkcie
Medzi mnohými existujúcimi hašovacími funkciami je zvykom rozlišovať kryptograficky silné hašovacie funkcie používané v kryptografii. Aby bola funkcia hash H považovaný za kryptograficky silný, musí spĺňať tri základné požiadavky, na ktorých je založená väčšina použití hašovacích funkcií v kryptografii:- Nevratnosť: pre danú hodnotu hash m musí byť výpočtovo nemožné nájsť blok údajov X, pre ktoré H(X) = m.
- Odolnosť proti kolíziám prvého druhu: pre danú správu M musí byť výpočtovo nemožné vyzdvihnúť ďalšiu správu N, pre ktoré H(N) = H(M).
- Odolné voči kolíziám typu II: musí byť výpočtovo nemožné spárovať pár správ (M, M"), ktorý má rovnaký hash.
- Invertibilná funkcia nie je odolná voči kolíziám prvého a druhého druhu.
- Funkcia, ktorá nie je odolná voči kolíziám prvého druhu, nie je odolná voči kolíziám druhého druhu; naopak to nie je pravda.
Narodeninový útok vám umožňuje nájsť kolízie pre hašovaciu funkciu s dĺžkou hodnôt n bitov v priemere vo výpočtoch približne 2 n/2 hašovacej funkcie. Preto n-bitová hašovacia funkcia sa považuje za kryptoodolnú, ak sa výpočtová zložitosť hľadania kolízií blíži k 2 n/2.
Pre kryptografické hašovacie funkcie je tiež dôležité, že pri najmenšej zmene argumentu sa hodnota funkcie veľmi zmení (lavínový efekt). Najmä hodnota hash nesmie uniknúť informácie ani o jednotlivých bitoch argumentu. Táto požiadavka je kľúčom ku kryptografickej sile hašovacích algoritmov, ktoré hašujú heslo používateľa na získanie kľúča
Používanie hašovacích funkcií
Hashovacie funkcie sa používajú aj v niektorých dátových štruktúrach – hašovacích tabuľkách, Bloomových filtroch a karteziánskych stromoch. Požiadavky na hashovaciu funkciu sú v tomto prípade odlišné:- dobrá miešateľnosť údajov
- rýchly výpočtový algoritmus
Vo všeobecnosti možno túto aplikáciu opísať ako kontrolu niektorých informácií, aby boli zhodné s originálom, bez použitia originálu. Na zosúladenie sa používa hašovacia hodnota overovaných informácií. Existujú dve hlavné oblasti tejto aplikácie:
- Kontrola chýb- Napríklad kontrolný súčet môže byť prenášaný cez komunikačný kanál spolu s hlavným textom. Na prijímacej strane môže byť kontrolný súčet prepočítaný a porovnaný s prenášanou hodnotou. Ak sa zistí nezrovnalosť, znamená to, že počas prenosu došlo k skresleniu a je možné požiadať o opakovanie.
Domácim analógom hašovania môže byť v tomto prípade technika, keď sa pri pohybe uchováva v pamäti počet kusov batožiny. Potom si na kontrolu nemusíte pamätať každý kufor, ale stačí ich spočítať. Zápas bude znamenať, že sa nestratí žiadny kufor. To znamená, že počet kusov batožiny je jej hash kód. Túto metódu možno jednoducho rozšíriť na ochranu pred falšovaním prenášaných informácií (metóda MAC). V tomto prípade je hašovanie vykonávané krypto-silnou funkciou správy kombinovanou s tajným kľúčom, ktorý pozná iba odosielateľ a príjemca správy. Kryptanalytik teda nebude schopný rekonštruovať kód pomocou zachytenej správy a hodnoty hašovacej funkcie, to znamená, že nebude môcť správu sfalšovať.
- Urýchlite získavanie údajov- Napríklad, keď sa textové polia zapisujú do databázy, ich hash kód možno vypočítať a údaje umiestniť do sekcie zodpovedajúcej tomuto hash kódu. Potom pri vyhľadávaní údajov budete musieť najskôr vypočítať hash kód textu a okamžite budete vedieť, v ktorej sekcii ho musíte hľadať, to znamená, že budete musieť hľadať nie v celej databáze, ale iba v jednej jeho časti (výrazne sa tým urýchli vyhľadávanie).
Bežným analógom hashovania v tomto prípade môže byť umiestňovanie slov do slovníka v abecednom poradí. Prvé písmeno slova je jeho hash kód a pri vyhľadávaní neprezeráme celý slovník, ale len požadované písmeno.
Hašovanie(z anglického hashing) - prevod vstupných dát ľubovoľnej dĺžky na výstupný bitový reťazec pevnej dĺžky takým spôsobom, že zmena vstupných dát vedie k nepredvídateľnej zmene výstupných dát. Takéto transformácie sa tiež nazývajú hašovacie funkcie alebo konvolučné funkcie a ich výsledky sa nazývajú hašovací alebo hašovací kód.
Hash problémy
Kontrola prístupovej frázy
Dnes je nebezpečné ukladať heslá na cieľové objekty, pretože odtiaľ ich môžu útočníci ukradnúť a použiť na vlastné účely. Preto sa tam ukladajú iba hashe hesiel, ktoré sa nedajú vrátiť späť a heslo sa nedá zistiť. Pri kontrole hesla sa zadané heslo hashuje a hodnoty hash sa porovnávajú.
Najbežnejšie algoritmy: MD5 (MD4, MD2), SHA1.
Urýchlite získavanie údajov
Napríklad v databáze pri písaní textových polí možno ich hash kód vypočítať a zapísať do samostatného poľa. Potom pri vyhľadávaní údajov budete musieť vypočítať hash kód údajov a prehľadávať nie celú databázu, ale iba jednu jej časť.
Výpočet kontrolného súčtu.
Na kontrolu chýb v pakete sa často používa kontrolný súčet, ktorý sa prenáša spolu so správou. Na prijímacej strane, keď je správa prijatá, sa znova vypočíta kontrolný súčet a ak sa hodnota zhoduje s odoslanou, správa bola odoslaná bez chýb.
Výpočet elektronického digitálneho podpisu.
Elektronický digitálny podpis sa používa na ochranu elektronického dokumentu pred falšovaním. Získané v dôsledku konverzie informácií pomocou súkromného kľúča vám umožňuje identifikovať vlastníka podpisového kľúča a zistiť, či nedošlo k skresleniu informácií v elektronickom dokumente.
Požiadavky na hashovací algoritmus
Hašovaciu funkciu možno použiť na argument ľubovoľnej veľkosti.
Výstupná hodnota má pevnú veľkosť.
Rýchlosť výpočtu hašovacej funkcie musí byť taká, aby rýchlosť generovania digitálneho podpisu pri použití hašovacej funkcie výrazne prevyšovala rýchlosť generovania digitálneho podpisu pri použití samotnej správy.
Hašovacia funkcia je jednosmerná funkcia. Pre akékoľvek m je teda výpočtovo nemožné nájsť takýto otvorený text X, h(X) = m
Pravdepodobnosť, že sa hodnoty hash dvoch rôznych dokumentov (bez ohľadu na ich dĺžku) budú zhodovať, by mala byť zanedbateľná.
AlgoritmusM.D.5
MD5(Message Digest 5) je hashovací algoritmus vyvinutý R. Rivestom z Massachusetts Institute of Technology (MIT) v roku 1991.
Podrobný popis algoritmu možno nájsť v RFC 1321.
Na výstupe algoritmus vytvára 128-bitový súhrn správy (odtlačok prsta). Dĺžka pôvodnej správy môže byť ľubovoľná.
Algoritmus MD5 je zraniteľný voči niektorým útokom, ako je napríklad možnosť vytvorenia dvoch správ s rovnakým hashovacím súčtom, preto sa jeho použitie v nových projektoch neodporúča.
AlgoritmusSHA-1
Hašovací algoritmus SHA (Secure Hash Algorithm) bol prijatý ako americký štandard v roku 1992.
Popísané v RFC 3174.
Navrhnuté na použitie v spojení s algoritmom digitálneho podpisu. Po zadaní otvoreného textu algoritmus vytvorí 160-bitovú výstupnú správu (digest), ktorá sa používa na generovanie digitálneho podpisu.
Hašovací algoritmus SHA sa nazýva bezpečný, pretože je navrhnutý tak, že je výpočtovo nemožné zrekonštruovať správu zodpovedajúcu danému súhrnu a tiež nájsť dve rôzne správy, ktoré poskytnú rovnaký súhrn.
Rozdiely medzi algoritmami SHA a MD5 sú nasledovné:
1. SHA vytvára 160-bitovú hodnotu hash a je odolnejší voči útokom hrubou silou ako MD5, ktorý vytvára 128-bitovú hodnotu hash.
2. Funkcia kompresie SHA zahŕňa 80 kôl, nie 64 ako v MD5.
3. Proces miešania je komplikovaný.
Rodina algoritmovSHA-2
Algoritmy podrodiny SHA-2 , rovnako ako algoritmus SHA-1 , boli vyvinuté americkou národnou bezpečnostnou agentúrou a publikované Národným inštitútom pre štandardy a technológie (NIST) vo federálnom štandarde spracovania informácií FIPS PUB 180–2 v auguste 2002.
Používajú sa algoritmy rodiny SHA-2 SSL, SSH, S/ MIME, DNSSEC, X.509 , PGP, IPSec, pri prenose súborov cez sieť ( BitTorrent).
Algoritmyhašovanie
MD5 md5 = nový MD5CryptoServiceProvider();
string stringToHash = "Jedzte viac týchto mäkkých francúzskych rožkov a vypite čaj";
byte hash = md5.ComputeHash(Encoding.Unicode.GetBytes(stringToHash));
Console.WriteLine(ByteHelper.ByteArrayToHexString(hash));
string otherStringToHash = "Rýchla hnedá líška skáče cez lenivého psa";
HashAlgorithm sha512 = HashAlgorithm.Create("SHA512");
Console.WriteLine(
ByteHelper.ByteArrayToHexString(
sha512.ComputeHash(
Encoding.Unicode.GetBytes(
Hash funkcie nachádzajú svoje uplatnenie v širokej škále odvetví informačných technológií. Sú navrhnuté tak, aby na jednej strane výrazne zjednodušili výmenu údajov medzi používateľmi a spracovanie súborov používaných na rôzne účely a na druhej strane optimalizovali algoritmy na zabezpečenie kontroly prístupu k relevantným zdrojom. Hašovacia funkcia je jedným z kľúčových nástrojov na zabezpečenie ochrany údajov heslom, ako aj na organizáciu výmeny dokumentov podpísaných elektronickým digitálnym podpisom. Existuje veľké množstvo štandardov, prostredníctvom ktorých je možné vykonávať ukladanie súborov do vyrovnávacej pamäte. Mnohé z nich vyvinuli ruskí špecialisti. Aké typy hašovacích funkcií môžu byť prezentované? Aké sú hlavné mechanizmy ich praktického uplatnenia?
Čo to je?
Najprv preskúmame koncept hašovacej funkcie. Pod týmto pojmom sa zvyčajne rozumie algoritmus na konverziu určitého množstva informácií na kratší sled znakov pomocou matematických metód. Praktický význam hašovacej funkcie možno vidieť v rôznych oblastiach. Môžu sa teda použiť pri kontrole integrity súborov a programov. Kryptografické hašovacie funkcie sa používajú aj v šifrovacích algoritmoch.
Charakteristika
Pozrime sa na kľúčové charakteristiky skúmaných algoritmov. Medzi nimi:
- prítomnosť interných algoritmov na konverziu údajov pôvodnej dĺžky na kratšiu sekvenciu znakov;
- otvorený pre kryptografické overenie;
- prítomnosť algoritmov, ktoré vám umožňujú spoľahlivo šifrovať pôvodné údaje;
- prispôsobivosť na dešifrovanie pri použití malého výpočtového výkonu.
Medzi ďalšie dôležité vlastnosti hašovacej funkcie patria:
- schopnosť spracovať počiatočné dátové polia ľubovoľnej dĺžky;
- generovať hashované bloky s pevnou dĺžkou;
- rovnomerne distribuovať funkčné hodnoty na výstupe.
Uvažované algoritmy tiež predpokladajú citlivosť na vstupné dáta na 1-bitovej úrovni. To znamená, že aj keď sa relatívne vzaté zmení aspoň 1 písmeno v zdrojovom dokumente, hašovacia funkcia bude vyzerať inak.
Požiadavky na hašovacie funkcie
Existuje množstvo požiadaviek na hašovacie funkcie určené na praktické využitie v určitej oblasti. Po prvé, zodpovedajúci algoritmus musí byť citlivý na zmeny vo vnútornej štruktúre hašovaných dokumentov. To znamená, že v hašovacej funkcii, ak hovoríme o textovom súbore, by sa mali rozpoznať preusporiadanie odsekov a pomlčky. Na jednej strane sa obsah dokumentu nemení, na druhej sa upravuje jeho štruktúra a tento proces treba pri hashovaní rozpoznať. Po druhé, príslušný algoritmus musí transformovať údaje takým spôsobom, aby spätná operácia (premena hashu na pôvodný dokument) bola v praxi nemožná. Po tretie, hashovacia funkcia musí zahŕňať použitie algoritmov, ktoré prakticky eliminujú možnosť vytvorenia rovnakej postupnosti znakov vo forme hashu, inými slovami, objavenie sa takzvaných kolízií. Na ich podstatu sa pozrieme o niečo neskôr.
Uvedené požiadavky, ktoré musí spĺňať algoritmus hašovacej funkcie, je možné dosiahnuť najmä použitím komplexných matematických prístupov.
Štruktúra
Pozrime sa, aká môže byť štruktúra uvažovaných funkcií. Ako sme uviedli vyššie, jednou z hlavných požiadaviek na uvažované algoritmy je zabezpečiť jednosmerné šifrovanie. Človek, ktorý má iba hash, by z neho prakticky nemal dostať originálny dokument.
V akej štruktúre môže byť zastúpená hašovacia funkcia používaná na takéto účely? Príklad jej zloženia môže byť nasledovný: H (hash, teda hash) = f (T (text), H1), kde H1 je algoritmus spracovania textu T. Táto funkcia hashuje T takým spôsobom, že bez znalosti H1 sa dá otvoriť ako plnohodnotný jeden súbor bude takmer nemožné.
Používanie hašovacích funkcií v praxi: sťahovanie súborov
Poďme si teraz podrobnejšie preštudovať možnosti využitia hašovacích funkcií v praxi. Pri písaní skriptov na sťahovanie súborov z internetových serverov je možné použiť vhodné algoritmy.
Vo väčšine prípadov je pre každý súbor určený určitý kontrolný súčet - to je hash. Musí byť rovnaký pre objekt umiestnený na serveri a stiahnutý do počítača používateľa. Ak tomu tak nie je, súbor sa nemusí otvoriť alebo sa nemusí správne spustiť.
Hash funkcia a digitálny podpis
Používanie hašovacích funkcií je bežné pri organizovaní výmeny dokumentov obsahujúcich digitálny podpis. V tomto prípade je podpisovaný súbor hašovaný, aby si jeho príjemca mohol overiť, že je pravý. Hoci hašovacia funkcia nie je formálne zahrnutá v štruktúre elektronického kľúča, možno ju zaznamenať do flash pamäte hardvéru používaného na podpisovanie dokumentov, ako je napríklad eToken.
Elektronický podpis je šifrovanie súboru pomocou verejných a súkromných kľúčov. To znamená, že správa zašifrovaná pomocou súkromného kľúča sa pripojí k zdrojovému súboru a digitálny podpis sa overí pomocou verejného kľúča. Ak sa hašovacia funkcia oboch dokumentov zhoduje, súbor v držbe príjemcu sa rozpozná ako pravý a podpis odosielateľa sa rozpozná ako správny.
Hašovanie, ako sme uviedli vyššie, nie je priamo súčasťou digitálneho podpisu, ale umožňuje veľmi efektívne optimalizovať algoritmy na používanie elektronického podpisu. Takže v skutočnosti môže byť zašifrovaný iba hash a nie samotný dokument. V dôsledku toho sa výrazne zvyšuje rýchlosť spracovania súborov a zároveň je možné poskytnúť efektívnejšie mechanizmy ochrany digitálnych podpisov, pretože dôraz pri výpočtových operáciách v tomto prípade nebude kladený na spracovanie pôvodných údajov, ale na zabezpečenie kryptografickej sily podpisu. Hašovacia funkcia tiež umožňuje podpisovať rôzne typy údajov, nielen text.
Kontrola hesiel
Ďalšou možnou oblasťou použitia hašovania je organizácia algoritmov na overenie hesiel vytvorených na obmedzenie prístupu k určitým zdrojom súborov. Ako možno použiť určité typy hašovacích funkcií na riešenie takýchto problémov? Veľmi jednoduché.
Faktom je, že na väčšine serverov, ku ktorým je obmedzený prístup, sú heslá uložené vo forme hashovaných hodnôt. Je to celkom logické – ak by boli heslá prezentované vo forme obyčajného textu, hackeri, ktorí k nim získali prístup, mohli ľahko prečítať tajné údaje. Na druhej strane nie je ľahké vypočítať heslo na základe hashu.
Ako sa overuje prístup používateľa pri použití príslušných algoritmov? Heslo zadané používateľom sa porovná s tým, čo je zaznamenané v hašovacej funkcii, ktorá je uložená na serveri. Ak sa hodnoty textových blokov zhodujú, používateľ získa potrebný prístup k zdrojom.
Najjednoduchšiu hashovaciu funkciu možno použiť ako nástroj na kontrolu hesla. V praxi však IT špecialisti najčastejšie používajú zložité viacstupňové kryptografické algoritmy. Spravidla sú doplnené o používanie štandardov na prenos dát cez zabezpečený kanál – aby hackeri nemohli zistiť alebo vypočítať heslo prenášané z počítača používateľa na servery – predtým, než sa skontroluje proti blokom hashovaných textov.
Kolízie hašovacích funkcií
Teória hašovacích funkcií poskytuje taký jav, ako je kolízia. Čo je jej podstatou? Hašovacia kolízia je situácia, v ktorej dva rôzne súbory majú rovnaký hašovací kód. To je možné, ak je cieľová sekvencia znakov krátka. V tomto prípade bude pravdepodobnosť zhody hash vyššia.
Aby sa predišlo kolíziám, odporúča sa najmä použiť duálny algoritmus nazývaný hašovanie hašovacej funkcie. Zahŕňa vytvorenie otvoreného a uzavretého kódu. Mnoho programátorov pri riešení dôležitých problémov odporúča nepoužívať hašovacie funkcie v prípadoch, keď to nie je potrebné a vždy otestovať zodpovedajúce algoritmy pre najlepšiu kompatibilitu s určitými kľúčmi.
História vzhľadu
Za zakladateľov teórie hašovacích funkcií možno považovať výskumníkov Cartera, Wegmana, Simonsona a Bierbrauera. V prvých verziách sa príslušné algoritmy používali ako nástroje na generovanie jedinečných obrazov sekvencií znakov ľubovoľnej dĺžky s následným účelom ich identifikácie a kontroly pravosti. Na druhej strane, hash, v súlade so špecifikovanými kritériami, musel mať dĺžku 30-512 bitov. Za obzvlášť užitočnú vlastnosť zodpovedajúcich funkcií sa považovala ich vhodnosť na použitie ako zdroja na rýchle vyhľadávanie súborov alebo ich triedenie.
Populárne hašovacie štandardy
Uvažujme teraz, v ktorých populárnych štandardoch môžu byť zastúpené hašovacie funkcie. Medzi nimi je CRC. Tento algoritmus je cyklický kód, nazývaný aj kontrolný súčet. Tento štandard sa vyznačuje jednoduchosťou a zároveň univerzálnosťou – dá sa s ním hashovať najširšie spektrum dát. CRC je jedným z najbežnejších nekryptografických algoritmov.
Na druhej strane, štandardy MD4 a MD5 sú široko používané v šifrovaní. Ďalším populárnym kryptografickým algoritmom je SHA-1. Vyznačuje sa najmä veľkosťou hashu 160 bitov, ktorá je väčšia ako MD5 – tento štandard podporuje 128 bitov. Existujú ruské normy upravujúce používanie hašovacích funkcií - GOST R 34.11-94, ako aj GOST R 34.11-2012, ktoré ho nahradili. Je možné poznamenať, že hodnota hash, ktorú poskytujú algoritmy prijaté v Ruskej federácii, je 256 bitov.
Príslušné normy možno klasifikovať z rôznych dôvodov. Napríklad existujú tie, ktoré používajú blokové a špecializované algoritmy. Jednoduchosť výpočtov založených na prvom type noriem je často sprevádzaná ich nízkou rýchlosťou. Preto sa ako alternatíva k blokovým algoritmom môžu použiť tie, ktoré zahŕňajú menšie množstvo potrebných výpočtových operácií. Medzi vysokorýchlostné štandardy zvyčajne patria najmä vyššie spomínané MD4, MD5, ako aj SHA. Pozrime sa bližšie na špecifiká špeciálnych hashovacích algoritmov s použitím SHA ako príkladu.
Vlastnosti algoritmu SHA
Využitie hašovacích funkcií založených na štandarde SHA sa najčastejšie realizuje pri vývoji nástrojov digitálneho podpisu pre dokumenty DSA. Ako sme uviedli vyššie, algoritmus SHA podporuje hash 160 bitov (poskytuje takzvaný „výber“ sekvencie znakov). Na začiatku uvažovaný štandard rozdeľuje dátové pole na bloky po 512 bitoch. V prípade potreby, ak dĺžka posledného bloku nedosahuje zadanú číslicu, doplní sa štruktúra súboru o 1 a požadovaný počet núl. Na konci príslušného bloku je tiež kód, ktorý určuje dĺžku správy. Uvažovaný algoritmus používa 80 logických funkcií, prostredníctvom ktorých sa spracúvajú 3 slová, prezentované v 32 bitoch. Štandard SHA tiež umožňuje použitie 4 konštánt.
Porovnanie hashovacích algoritmov
Pozrime sa, ako korelujú vlastnosti hašovacích funkcií súvisiacich s rôznymi štandardmi, na príklade porovnania charakteristík ruskej normy GOST R 34.11-94 a americkej SHA, ktorú sme skúmali vyššie. V prvom rade treba poznamenať, že algoritmus vyvinutý v Ruskej federácii predpokladá implementáciu 4 šifrovacích operácií na 1 cyklus. To zodpovedá 128 nábojom. Na druhej strane, počas 1 kola, keď sa používa SHA, sa očakáva, že sa vypočíta približne 20 príkazov, pričom celkovo je 80 kôl. Použitie SHA teda umožňuje spracovať 512 bitov zdrojových údajov v rámci 1 cyklu. Zatiaľ čo ruský štandard je schopný vykonávať operácie v cykle 256 bitov dát.
Špecifiká najnovšieho ruského algoritmu
Vyššie sme poznamenali, že norma GOST R 34.11-94 bola nahradená novšou normou - GOST R 34.11-2012 „Stribog“. Pozrime sa na jeho špecifiká podrobnejšie.
Pomocou tohto štandardu je možné implementovať kryptografické hašovacie funkcie, ako v prípade vyššie diskutovaných algoritmov. Možno poznamenať, že najnovší ruský štandard podporuje 512-bitový blok vstupných údajov. Hlavné výhody GOST R 34.11-2012:
- vysoká úroveň zabezpečenia proti prelomeniu kódov;
- spoľahlivosť podporovaná použitím osvedčených návrhov;
- rýchly výpočet hašovacej funkcie, absencia transformácií v algoritme, ktoré komplikujú návrh funkcie a spomaľujú výpočet.
Zaznamenané výhody nového ruského kryptografického šifrovacieho štandardu umožňujú jeho použitie pri organizovaní toku dokumentov, ktoré spĺňajú najprísnejšie kritériá, ktoré sú predpísané v ustanoveniach regulačných právnych predpisov.
Špecifiká kryptografických hašovacích funkcií
Pozrime sa bližšie na to, ako sa dajú typy algoritmov, ktoré skúmame, použiť v oblasti kryptografie. Kľúčovou požiadavkou na zodpovedajúce funkcie je odolnosť voči kolíziám, o ktorej sme sa zmienili vyššie. To znamená, že duplicitné hodnoty hašovacej funkcie by sa nemali generovať, ak sú tieto hodnoty už prítomné v štruktúre susedného algoritmu. Kryptografické funkcie musia spĺňať aj ostatné kritériá uvedené vyššie. Je jasné, že vždy existuje určitá teoretická možnosť obnovenia pôvodného súboru na základe hashu, najmä ak je k dispozícii výkonný výpočtový nástroj. Očakáva sa však, že takýto scenár bude minimalizovaný vďaka spoľahlivým šifrovacím algoritmom. Preto bude veľmi ťažké vypočítať hašovaciu funkciu, ak jej výpočtová sila zodpovedá vzorcu 2^(n/2).
Ďalším dôležitým kritériom kryptografického algoritmu je zmena hashu v prípade opravy pôvodného dátového poľa. Vyššie sme uviedli, že štandardy šifrovania musia byť citlivé na 1 bit. Táto vlastnosť je teda kľúčovým faktorom pri zabezpečení spoľahlivej ochrany prístupu k súborom heslom.
Iteračné schémy
Pozrime sa teraz na to, ako možno skonštruovať kryptografické hašovacie algoritmy. Medzi najbežnejšie schémy riešenia tohto problému patrí použitie iteračného sekvenčného modelu. Je založená na použití takzvanej kompresnej funkcie, pri ktorej je počet vstupných bitov podstatne väčší ako tie zachytené na výstupe.
Samozrejme, kompresná funkcia musí spĺňať potrebné kritériá kryptografickej pevnosti. V interaktívnej schéme je prvá operácia na spracovanie vstupného dátového toku rozdelená do blokov, ktorých veľkosť je vypočítaná v bitoch. Zodpovedajúci algoritmus tiež používa dočasné premenné daného počtu bitov. Ako prvá hodnota sa používa dobre známe číslo, zatiaľ čo nasledujúce bloky údajov sa kombinujú s hodnotou príslušnej funkcie ako výstup. Hodnota hash sa stáva výstupnými bitmi pre poslednú iteráciu, ktorá berie do úvahy celý vstupný tok vrátane prvej hodnoty. Poskytuje sa takzvaný „lavínový efekt“ hašovania.
Hlavným problémom, ktorý charakterizuje hašovanie implementované ako iteratívna schéma, je to, že hašovacie funkcie sa niekedy ťažko zostavujú, ak vstupný tok nie je identický s veľkosťou bloku, na ktorý je pôvodné dátové pole rozdelené. Ale v tomto prípade môže hašovací štandard obsahovať algoritmy, pomocou ktorých môže byť pôvodný tok rozšírený tak či onak.
V niektorých prípadoch môžu byť v procese spracovania údajov v rámci iteratívnej schémy použité takzvané viacpriechodové algoritmy. Naznačujú vznik ešte intenzívnejšieho „lavínového efektu“. Takýto scenár zahŕňa vytváranie opakovaných súborov údajov a až na druhom mieste dochádza k expanzii.
Blokový algoritmus
Kompresná funkcia môže byť tiež založená na blokovom algoritme, ktorým sa vykonáva šifrovanie. Na zvýšenie úrovne bezpečnosti teda môžete ako kľúč použiť dátové bloky, ktoré sú predmetom hashovania v aktuálnej iterácii, a ako vstup výsledok operácií získaných počas vykonávania kompresnej funkcie predtým. Výsledkom je, že posledná iterácia poskytne výstup algoritmu. Bezpečnosť hashovania bude korelovať s robustnosťou použitého algoritmu.
Ako sme však uviedli vyššie, vzhľadom na rôzne typy hašovacích funkcií sú blokové algoritmy často sprevádzané potrebou použiť veľký výpočtový výkon. Ak nie sú dostupné, rýchlosť spracovania súborov nemusí byť dostatočná na vyriešenie praktických problémov spojených s používaním hašovacích funkcií. Požadovanú kryptografickú silu možno zároveň dosiahnuť malým počtom operácií so zdrojovými dátovými tokmi, najmä algoritmy, ktoré sme uvažovali – MD5, SHA a ruské kryptografické šifrovacie štandardy – sú prispôsobené na riešenie takýchto problémov.
Verím, že veľa ľudí vie, že od roku 2007 americký Národný inštitút pre štandardy a technológie (NIST) organizuje súťaž o vývoj hašovacieho algoritmu, ktorý nahradí SHA-1, a rodinu algoritmov SHA-2. Avšak z nejakého dôvodu bola táto téma na stránke zanedbaná. To je vlastne to, čo ma k vám priviedlo. Dávam do pozornosti sériu článkov venovaných hashovacím algoritmom. V tejto sérii si spoločne preštudujeme základy hašovacích funkcií, zvážime najznámejšie hašovacie algoritmy, ponoríme sa do atmosféry súťaže SHA-3 a zvážime algoritmy, ktoré tvrdia, že ju vyhrali, a určite ich otestujeme. Ak je to možné, zohľadnia sa aj ruské hašovacie štandardy.
O mne
Študentka Katedry informačnej bezpečnosti.O hašovaní
V súčasnosti takmer žiadna kryptografická aplikácia nie je úplná bez použitia hashovania.Hašovacie funkcie sú funkcie určené na „komprimovanie“ ľubovoľnej správy alebo súboru údajov, zvyčajne zapísaných v binárnej abecede, do určitého bitového vzoru s pevnou dĺžkou nazývaného konvolúcia. Hashovacie funkcie majú rôzne aplikácie pri vykonávaní štatistických experimentov, testovaní logických zariadení a vytváraní algoritmov na rýchle vyhľadávanie a kontrolu integrity záznamov v databázach. Hlavnou požiadavkou na hašovacie funkcie je rovnomerné rozloženie ich hodnôt, keď sú hodnoty argumentov náhodne vybrané.
Kryptografická hašovacia funkcia je akákoľvek hašovacia funkcia, ktorá je kryptograficky stabilná, to znamená, že spĺňa množstvo požiadaviek špecifických pre kryptografické aplikácie. V kryptografii sa hašovacie funkcie používajú na riešenie nasledujúcich problémov:
- budovanie systémov monitorovania integrity údajov počas ich prenosu alebo uchovávania,
- autentifikácia zdroja údajov.
Akákoľvek funkcia sa nazýva hašovacia funkcia h:X -> Y, ľahko vypočítateľný a taký, že pre akúkoľvek správu M význam h(M) = H (konvolúcia) má pevnú dĺžku bitu. X- súbor všetkých správ, Y- súbor binárnych vektorov pevnej dĺžky.
Hašovacie funkcie sú spravidla postavené na základe takzvaných jednokrokových kompresných funkcií y = f(x 1, x 2) dve premenné, kde x 1, x 2 A r- binárne vektory dĺžky m, n A n podľa toho a n je konvolučná dĺžka a m- dĺžka bloku správ.
Ak chcete získať hodnotu h(M) správa sa najskôr rozdelí na bloky dĺžky m(zároveň, ak dĺžka správy nie je násobkom m potom sa posledný blok doplní nejakým špeciálnym spôsobom, kým nie je dokončený) a potom k výsledným blokom M 1, M 2,.., M N na výpočet konvolúcie použite nasledujúci postupný postup:
H o = v,
Hi = f(Mi,Hi-1), i = 1,.., N,
h(M) = HN
Tu v- nejaká konštanta, často nazývaná inicializačný vektor. Ona sa dostane von
z rôznych dôvodov a môže to byť tajná konštanta alebo súbor náhodných údajov (napríklad vzorka dátumu a času).
Pri tomto prístupe sú vlastnosti hašovacej funkcie úplne určené vlastnosťami jednokrokovej kompresnej funkcie.
Existujú dva dôležité typy kryptografických hašovacích funkcií – kľúčové a bezkľúčové. Kľúčové hašovacie funkcie sa nazývajú overovacie kódy správ. Umožňujú bez ďalších prostriedkov zaručiť správnosť zdroja údajov a integritu údajov v systémoch s používateľmi, ktorí si navzájom dôverujú.
Bezkľúčové hašovacie funkcie sa nazývajú kódy detekcie chýb. Umožňujú zaručiť integritu údajov pomocou dodatočných prostriedkov (napríklad šifrovanie). Tieto hašovacie funkcie možno použiť v systémoch s dôveryhodnými aj nedôverčivými používateľmi.
O štatistických vlastnostiach a požiadavkách
Ako som už povedal, hlavnou požiadavkou na hašovacie funkcie je rovnomerné rozloženie ich hodnôt, keď sú hodnoty argumentov náhodne vybrané. Pre kryptografické hašovacie funkcie je tiež dôležité, že pri najmenšej zmene argumentu sa hodnota funkcie výrazne zmení. Toto sa nazýva lavínový efekt.
Kľúčové hašovacie funkcie majú nasledujúce požiadavky:
- nemožnosť výroby,
- nemožnosť úpravy.
Prvá požiadavka znamená, že je veľmi ťažké nájsť správu so správnou hodnotou kolapsu. Druhým je vysoká zložitosť výberu pre danú správu so známou hodnotou konvolúcie inej správy so správnou hodnotou konvolúcie.
Požiadavky na bezkľúčové funkcie sú:
- jednosmernosť,
- odolnosť proti nárazom,
- odpor k nájdeniu druhého predobrazu.
Jednosmernosť sa týka vysokej náročnosti nájdenia správy na základe danej konvolučnej hodnoty. Treba poznamenať, že v súčasnosti sa nepoužívajú žiadne hašovacie funkcie s osvedčenou jednosmernosťou.
Odolnosť proti kolízii sa vzťahuje na obtiažnosť nájsť pár správ s rovnakými hodnotami konvolúcie. Zvyčajne práve nájdenie spôsobu konštrukcie kolízií kryptoanalytikmi slúži ako prvý signál, že algoritmus zastaráva a je potrebné ho rýchlo nahradiť.
Odolnosť voči nájdeniu druhého predobrazu sa týka obtiažnosti nájdenia druhej správy s rovnakou hodnotou konvolúcie pre danú správu so známou hodnotou konvolúcie.
Toto bola teoretická časť, ktorá sa nám bude hodiť v budúcnosti...
O populárnych hašovacích algoritmoch
Algoritmy CRC16/32- kontrolný súčet (nie kryptografická konverzia).
Algoritmy MD2/4/5/6. Sú výtvorom Rona Rivesta, jedného z autorov algoritmu RSA.
Algoritmus MD5 bol kedysi veľmi populárny, ale prvé predpoklady pre hackovanie sa objavili koncom deväťdesiatych rokov a teraz jeho popularita rýchlo klesá.
Algoritmus MD6 je z konštrukčného hľadiska veľmi zaujímavý algoritmus. Bol nominovaný do súťaže SHA-3, ale autori ho, žiaľ, nestihli uviesť do štandardu a tento algoritmus nie je na zozname kandidátov, ktorí postúpili do druhého kola.
Algoritmy pravítka SHA Algoritmy, ktoré sú dnes široko používané. Existuje aktívny prechod zo štandardov verzie SHA-1 na SHA-2. SHA-2 je súhrnný názov pre algoritmy SHA224, SHA256, SHA384 a SHA512. SHA224 a SHA384 sú v podstate analógy SHA256 a SHA512, iba po výpočte konvolúcie sa niektoré informácie v nej zahodia. Mali by sa používať iba na zabezpečenie kompatibility s vybavením starších modelov.
ruský štandard - GOST 34.11-94.
V ďalšom článku
Prehľad MD algoritmov (MD4, MD5, MD6).
Literatúra
A. P. Alferov, Základy kryptografie.
Bruce Schneier, Aplikovaná kryptografia.
čo je hash? Hašovacia funkcia je matematická transformácia informácií na krátky reťazec špecifickej dĺžky.
Prečo je to potrebné? Analýza pomocou hašovacích funkcií sa často používa na monitorovanie integrity dôležitých súborov operačného systému, dôležitých programov a dôležitých údajov. Kontrola sa môže vykonávať podľa potreby alebo pravidelne.
Ako sa to robí? Najprv určite integritu súborov, ktoré je potrebné monitorovať. Pre každý súbor sa pomocou špeciálneho algoritmu vypočíta jeho hash hodnota a výsledok sa uloží. Po požadovanom čase sa vykoná podobný výpočet a výsledky sa porovnajú. Ak sú hodnoty odlišné, informácie obsiahnuté v súbore boli zmenené.
Aké vlastnosti by mala mať hašovacia funkcia?
- musí byť schopný vykonávať ľubovoľnú konverziu údajov na pevnú dĺžku;
- musí mať otvorený algoritmus, aby bolo možné preskúmať jeho kryptografickú silu;
- musí byť jednostranný, to znamená, že na základe výsledku by nemalo byť matematicky možné určiť počiatočné údaje;
- musí „odolať“ kolíziám, to znamená, že nesmie produkovať rovnaké hodnoty pre rôzne vstupné údaje;
- nemal by vyžadovať veľké výpočtové zdroje;
- pri najmenšej zmene vstupných údajov by sa mal výsledok výrazne zmeniť.
Aké sú populárne hašovacie algoritmy? V súčasnosti sa používajú nasledujúce hašovacie funkcie:
- CRC – kód cyklickej redundancie alebo kontrolný súčet. Algoritmus je veľmi jednoduchý a má veľké množstvo variácií v závislosti od požadovanej dĺžky výstupu. Nie kryptografické!
- MD 5 je veľmi populárny algoritmus. Rovnako ako jeho predchádzajúca verzia, MD 4 je kryptografická funkcia. Veľkosť hashu je 128 bitov.
- SHA -1 je tiež veľmi populárna kryptografická funkcia. Veľkosť hashu je 160 bitov.
- GOST R 34.11-94 je ruský kryptografický štandard pre výpočty hašovacích funkcií. Veľkosť hashu je 256 bitov.
Kedy môže správca systému použiť tieto algoritmy?Často pri sťahovaní akéhokoľvek obsahu, napríklad programov z webovej stránky výrobcu, hudby, filmov alebo iných informácií, existuje hodnota kontrolných súčtov vypočítaná pomocou určitého algoritmu. Z bezpečnostných dôvodov musíte po stiahnutí nezávisle vypočítať hašovaciu funkciu a porovnať hodnotu s tým, čo je uvedené na webovej stránke alebo v prílohe k súboru. Už ste to niekedy robili?
Čo je pohodlnejšie na výpočet hash? Teraz existuje veľké množstvo podobných nástrojov, platených aj bezplatných. Osobne sa mi páčil HashTab. Po prvé, počas inštalácie je nástroj zabudovaný ako karta vo vlastnostiach súboru, po druhé, umožňuje vám vybrať veľké množstvo hashovacích algoritmov a po tretie je zadarmo na súkromné nekomerčné použitie.
čo je ruština? Ako už bolo spomenuté vyššie, v Rusku existuje hašovací štandard GOST R 34.11-94, ktorý je široko používaný mnohými výrobcami nástrojov informačnej bezpečnosti. Jedným z týchto nástrojov je program na opravu a sledovanie počiatočného stavu softvérového balíka FIX. Tento program je prostriedkom na sledovanie efektívnosti využívania informačnej bezpečnosti.
OPRAVA (verzia 2.0.1) pre Windows 9x/NT/2000/XP
- Výpočet kontrolných súčtov zadaných súborov pomocou jedného z 5 implementovaných algoritmov.
- Fixácia a následné sledovanie počiatočného stavu softvérového balíka.
- Porovnanie verzií softvérových balíkov.
- Fixácia a kontrola adresárov.
- Kontrola zmien v zadaných súboroch (adresároch).
- Generovanie reportov vo formátoch TXT, HTML, SV.
- Výrobok má do 1.6.2013 certifikát FSTEC pre NDV 3 č.913.
A čo digitálny podpis? Výsledok výpočtu hašovacej funkcie spolu s tajným kľúčom používateľa ide na vstup kryptografického algoritmu, kde sa vypočíta elektronický digitálny podpis. Presne povedané, funkcia hash nie je súčasťou algoritmu digitálneho podpisu, ale často sa to robí zámerne, aby sa vylúčil útok pomocou verejného kľúča.
V súčasnosti mnoho aplikácií elektronického obchodu umožňuje uložiť tajný kľúč používateľa v súkromnej oblasti tokenov (ruToken, eToken) bez technickej možnosti ho odtiaľ získať. Samotný token má veľmi obmedzenú pamäťovú oblasť, meranú v kilobajtoch. Ak chcete podpísať dokument, neexistuje spôsob, ako preniesť dokument do samotného tokenu, ale je veľmi jednoduché preniesť hash dokumentu do tokenu a ako výsledok získať elektronický digitálny podpis.
