Univerzálne hašovanie je hašovanie, ktoré používa viac ako jednu špecifickú hašovaciu funkciu, ale vyberá z danej rodiny pomocou náhodného algoritmu. Použitie univerzálneho hashovania zvyčajne vedie k nízkej miere kolízií. Univerzálne hašovanie má mnoho aplikácií, napríklad pri implementácii hašovacích tabuliek a kryptografie.
Popis
Povedzme, že chceme mapovať kľúče z priestoru na čísla. Na vstupe dostane algoritmus určitú množinu údajov a rozmerov, ktoré nie sú vopred známe. Cieľom hašovania je zvyčajne získať čo najmenší počet kolízií, čo je ťažké dosiahnuť pomocou špecifickej hašovacej funkcie.
Ako riešenie takéhoto problému je možné náhodne vybrať funkciu zo špecifickej množiny nazývanej univerzálna rodina.
Kolízia hašovacej funkcie
Kolízia (niekedy konflikt alebo kolízia) hašovacej funkcie je definovaná ako dva bloky vstupných údajov, ktoré vytvárajú rovnaké hašovacie kódy.
V hašovacích tabuľkách
Väčšina raných prác popisujúcich hašovanie bola venovaná metódam riešenia kolízií v hašovacích tabuľkách, pretože hašovacie funkcie sa používali na vyhľadávanie veľkých súborov. V hašovacích tabuľkách sa používajú dve hlavné metódy:
Reťazová metóda (metóda priameho prepojenia)
Otvorená metóda adresovania
Prvým spôsobom je udržiavať prepojené zoznamy, jeden pre každú hodnotu hash. V zozname sú uložené kľúče, ktoré dávajú rovnakú hodnotu hash kódu. Vo všeobecnosti, ak máme kľúče a zoznamy, priemerná veľkosť hašovacej tabuľky bude a hašovanie zníži priemerné množstvo práce v porovnaní so sekvenčným vyhľadávaním približne o faktor.
Druhou metódou je uloženie párov kľúč-hodnota do poľa tabuľky. Týmto spôsobom sa úplne zbavíme referencií a jednoducho si prezeráme záznamy v tabuľke, kým nenájdeme požadovaný kľúč alebo prázdnu pozíciu. Sekvencia, v ktorej sa prezerajú bunky tabuľky, sa nazýva sekvencia sondy.
Kryptografická soľ
Existuje niekoľko metód na ochranu pred falšovaním hesiel a podpisov, ktoré fungujú, aj keď kryptoanalytik vie, ako vytvoriť kolízie pre použitú hashovaciu funkciu. Jednou z takýchto metód je pridanie kryptografickej soli (reťazca náhodných údajov) k vstupným údajom (niekedy sa soľ pridáva aj do hash kódu), čo značne sťažuje analýzu výsledných hashovacích tabuliek. Táto metóda sa napríklad používa na ukladanie hesiel v operačných systémoch podobných UNIX.
Používanie hašovacích funkcií
Hashovacie funkcie sú široko používané v kryptografii, ako aj v mnohých dátových štruktúrach – hašovacích tabuľkách, Bloomových filtroch a karteziánskych stromoch.
Kryptografické hašovacie funkcie
Medzi mnohými existujúcimi hašovacími funkciami je obvyklé rozlišovať kryptograficky silné hašovacie funkcie používané v kryptografii, pretože sú na ne kladené ďalšie požiadavky. Aby bola hašovacia funkcia považovaná za kryptograficky silnú, musí spĺňať tri základné požiadavky, ktoré sú základom pre väčšinu použití hašovacích funkcií v kryptografii:
Tieto požiadavky nie sú nezávislé:
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.
Treba poznamenať, že existencia ireverzibilných hašovacích funkcií, pre ktoré je teoreticky nemožný výpočet akéhokoľvek inverzného obrazu danej hašovacej hodnoty, nebola dokázaná. Nájdenie inverzného je zvyčajne len výpočtovo náročná úloha.
Narodeninový útok vám umožňuje nájsť kolízie pre hašovaciu funkciu s dĺžkou hodnôt n bitov v priemere na približne výpočet hašovacej funkcie. Preto n A-bitová hašovacia funkcia sa považuje za kryptoodolnú, ak sa výpočtová zložitosť hľadania kolízií blíži k .
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.
Hašovanie sa často používa v algoritmoch digitálneho podpisu, kde nie je šifrovaná samotná správa, ale jej hašovací kód, ktorý skracuje čas výpočtu a tiež zvyšuje šifrovaciu silu. Vo väčšine prípadov sa namiesto hesiel ukladajú aj hodnoty ich hash kódov.
Anotácia: Táto prednáška formuluje koncept hašovacej funkcie a poskytuje aj stručný prehľad algoritmov na generovanie hašovacích funkcií. Okrem toho sa zvažuje možnosť použitia blokových šifrovacích algoritmov na generovanie hašovacej funkcie.
Účel prednášky: zoznámiť sa s pojmom hašovacia funkcia, ako aj s princípmi fungovania takýchto funkcií.
Koncept hašovacej funkcie
Hash funkcia je matematická alebo iná funkcia, ktorá pre reťazec ľubovoľnej dĺžky vypočíta nejakú celočíselnú hodnotu alebo iný reťazec s pevnou dĺžkou. Matematicky sa to dá zapísať takto:
kde M je pôvodná správa, niekedy nazývaná prototyp a h je výsledok nazývaný hash hodnota (a tiež hash kód alebo prehľad správ(z angličtiny prehľad správ)).
Význam hašovacej funkcie je určiť charakteristickú vlastnosť predobrazu – hodnotu hašovacej funkcie. Táto hodnota má zvyčajne určitú pevnú veľkosť, napríklad 64 alebo 128 bitov. Hash kód možno ďalej analyzovať, aby sa vyriešil akýkoľvek problém. Hašovanie možno použiť napríklad na porovnanie údajov: ak majú dve dátové polia rôzne hashovacie kódy, polia budú zaručene odlišné; ak sú rovnaké, polia sú s najväčšou pravdepodobnosťou rovnaké. Vo všeobecnosti neexistuje žiadna individuálna zhoda medzi zdrojovými údajmi a hašovacím kódom, pretože počet hodnôt hašovacej funkcie je vždy menší ako počet možností vstupných údajov. V dôsledku toho existuje veľa vstupných správ, ktoré poskytujú rovnaké hash kódy (takéto situácie sa nazývajú kolízie). Pravdepodobnosť kolízií hrá dôležitú úlohu pri hodnotení kvality hašovacích funkcií.
Hash funkcie sú široko používané v modernej kryptografii.
Najjednoduchšiu hašovaciu funkciu je možné skonštruovať pomocou operácie „sum modulo 2“ takto: získame vstupný reťazec, sčítame všetky bajty modulo 2 a výsledný bajt vrátime ako hodnotu hash. Dĺžka hodnoty hašovacej funkcie bude v tomto prípade 8 bitov, bez ohľadu na veľkosť vstupnej správy.
Povedzme napríklad, že pôvodná správa preložená do digitálnej podoby bola nasledujúca (v šestnástkovej sústave):
Skonvertujme správu do binárnej formy, zapíšme bajty pod seba a pripočítajme bity v každom stĺpci modulo 2:
0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101
Výsledkom (0110 0101 (2) alebo 65 (16)) bude hodnota hash.
Takúto hashovaciu funkciu však nemožno použiť na kryptografické účely, ako je generovanie elektronického podpisu, pretože je celkom jednoduché zmeniť obsah podpísanej správy bez zmeny hodnoty kontrolného súčtu.
Preto uvažovaná hašovacia funkcia nie je vhodná pre kryptografické aplikácie. V kryptografii sa hašovacia funkcia považuje za dobrú, ak je ťažké vytvoriť dva predobrazy s rovnakou hašovacou hodnotou a tiež ak výstup funkcie nemá explicitnú závislosť od vstupu.
Sformulujme základné požiadavky na kryptografické hašovacie funkcie:
- hašovacia funkcia musí byť použiteľná na správu akejkoľvek veľkosti;
- výpočet funkčnej hodnoty by sa mal vykonať dostatočne rýchlo;
- Vzhľadom na známu hodnotu hašovacej funkcie by malo byť ťažké (prakticky nemožné) nájsť vhodný inverzný obraz M;
- vzhľadom na známu správu M by malo byť ťažké nájsť ďalšiu správu M' s rovnakou hodnotou hash ako pôvodná správa;
- malo by byť ťažké nájsť nejaký pár náhodne odlišných správ s rovnakou hodnotou hash.
Vytvorenie hašovacej funkcie, ktorá spĺňa všetky vyššie uvedené požiadavky, nie je ľahká úloha. Je tiež potrebné pamätať na to, že vstup funkcie prijíma dáta ľubovoľnej veľkosti a výsledok hash by nemal byť rovnaký pre dáta rôznych veľkostí.
V súčasnosti sa v praxi ako hašovacie funkcie používajú funkcie, ktoré spracovávajú vstupnú správu blok po bloku a vypočítavajú hašovaciu hodnotu h i pre každý blok M i vstupnej správy podľa závislostí formulára.
hj =H(Mi,hi-1),
kde h i-1 je výsledok získaný pri výpočte hašovacej funkcie pre predchádzajúci blok vstupných údajov.
Výsledkom je, že výstup hašovacej funkcie h n je funkciou všetkých n blokov vstupnej správy.
Použitie blokových šifrovacích algoritmov na generovanie hašovacej funkcie
Blokovú hašovaciu funkciu môžete použiť ako hašovaciu funkciu. Ak je použitý blokový algoritmus kryptograficky silný, potom bude hašovacia funkcia založená na ňom bezpečná.
Najjednoduchší spôsob, ako použiť blokový algoritmus na získanie hash kódu, je zašifrovať správu v režime CBC. V tomto prípade je správa reprezentovaná ako sekvencia blokov, ktorých dĺžka sa rovná dĺžke bloku šifrovacieho algoritmu. V prípade potreby sa posledný blok vyplní vpravo nulami, aby sa vytvoril blok požadovanej dĺžky. Hodnota hash bude posledným zašifrovaným blokom textu. Za predpokladu, že sa použije silný blokový šifrovací algoritmus, výsledná hodnota hash bude mať nasledujúce vlastnosti:
- Je takmer nemožné vypočítať hodnotu hash pre dané otvorené pole informácií bez znalosti šifrovacieho kľúča;
- Bez znalosti šifrovacieho kľúča je takmer nemožné vybrať otvorené dáta pre danú hodnotu hašovacej funkcie.
Takto vygenerovaná hash hodnota sa zvyčajne nazýva vkladanie imitácie alebo autentifikátor a používa sa na kontrolu integrity správy. Imitačná vložka je teda kontrolná kombinácia, ktorá závisí od otvorených údajov a tajných informácií o kľúči. Účelom použitia imitatívneho vkladania je odhaliť všetky náhodné alebo zámerné zmeny v informačnom poli. Hodnota získaná hašovacou funkciou pri spracovaní vstupnej správy sa pripojí k správe v čase, keď je známe, že správa je správna. Príjemca overí integritu správy tak, že vypočíta imitovanú správu prijatej správy a porovná ju s prijatým hash kódom, ktorý musí byť prenesený bezpečným spôsobom. Jednou z takýchto bezpečných metód by mohlo byť zašifrovanie imitatívnej vložky súkromným kľúčom odosielateľa, t.j. vytvorenie podpisu. Je tiež možné zašifrovať výsledný hash kód pomocou symetrického šifrovacieho algoritmu, ak odosielateľ a príjemca majú spoločný symetrický šifrovací kľúč.
Špecifikovaný proces získavania a používania imitácií vložiek je opísaný v domácej norme GOST 28147-89. Norma navrhuje použiť spodných 32 bitov bloku získaného na výstupe celej operácie šifrovania správy v režime reťazenia šifrových blokov na riadenie integrity prenášanej správy. Rovnakým spôsobom môžete použiť akýkoľvek blok bloku na vytvorenie simulovanej vložky. symetrický šifrovací algoritmus.
Ďalší možný spôsob použitia blokovej šifry na generovanie hash kódu je nasledujúci. Pôvodná správa sa spracováva postupne v blokoch. Posledný blok je v prípade potreby doplnený nulami, niekedy sa k poslednému bloku pridá dĺžka správy vo forme binárneho čísla. V každej fáze zašifrujeme hodnotu hash získanú v predchádzajúcej fáze, pričom ako kľúč použijeme aktuálny blok správy. Posledná prijatá zašifrovaná hodnota bude konečným výsledkom hashovania.
V skutočnosti existuje niekoľko ďalších možných schém na použitie blokovej šifry na generovanie hašovacej funkcie. Nech M i je blok pôvodnej správy, h i je hodnota hašovacej funkcie v i-tom štádiu, f je blokový šifrovací algoritmus použitý v režime jednoduchého nahradzovania a nech je operácia sčítania modulo 2. Potom sú možné napríklad nasledujúce schémy na generovanie hašovacej funkcie:
Vo všetkých týchto schémach sa dĺžka vygenerovanej hodnoty hash rovná dĺžke šifrovacieho bloku. Všetky tieto, ako aj niektoré ďalšie schémy na použitie blokového šifrovacieho algoritmu na výpočet hash hodnôt, sa dajú použiť v praxi.
Hlavnou nevýhodou hašovacích funkcií navrhnutých na základe blokových algoritmov je relatívne nízka rýchlosť prevádzky. Požadovanú kryptografickú silu je možné dosiahnuť menším počtom operácií so vstupnými údajmi. Existujú rýchlejšie hašovacie algoritmy navrhnuté nezávisle, od začiatku, na základe požiadaviek na šifrovaciu silu (najbežnejšie z nich sú MD5, SHA-1, SHA-2 a GOST R 34.11-94).
Hašovanie a šifrovanie sú dve slová, ktoré sa často používajú zameniteľne, ale niekedy nesprávne.
Rozumiete rozdielu medzi týmito dvoma slovami a situáciami, v ktorých by ste mali použiť jeden z týchto dvoch prípadov?
V dnešnom príspevku rozoberiem hlavné rozdiely medzi hashovaním a šifrovaním a kedy a prečo sa každý používa.
Hašovanie - čo to je?
Hash je hodnota alebo číslo vygenerované zo sekvencie textu.
Výsledný riadok alebo číslo s pevnou dĺžkou sa bude výrazne líšiť v závislosti od menších zmien vo vstupe.
Najlepšie hashovacie algoritmy sú navrhnuté tak, aby nebolo možné vrátiť hash do jeho pôvodnej sekvencie.
Populárne algoritmy
MD5. MD5 je najznámejšia hašovacia funkcia.
Tento algoritmus vytvára 16-bitovú hodnotu hash, zvyčajne vyjadrenú ako 32-miestne hexadecimálne číslo.
Nedávno bolo objavených niekoľko slabých miest v MD5 a boli publikované dúhové tabuľky [veľké a verejne dostupné], čo ľuďom umožnilo úplne zmeniť hash MD5. Preto sa tento algoritmus považuje za trochu zastaraný. Môžete tiež zaznamenať značný počet kolízií.
SHA – Existujú tri rôzne algoritmy SHA – SHA-0, SHA-1 a SHA-2.
SHA-0 sa používa veľmi zriedkavo, pretože mal chybu zabezpečenia, ktorá bola opravená v SHA-1.
SHA-1 je bežný používaný algoritmus SHA a vytvára 20-bitovú hash hodnotu.
SHA-2 pozostáva zo série 6 hashovacích algoritmov a považuje sa za najsilnejší.
Kedy by sa malo použiť hashovanie?
Pri ukladaní hesiel vo formáte hash je pre útočníka s prístupom k nespracovaným údajom veľmi ťažké ich invertovať (na ich generovanie použite silný hashovací algoritmus a vhodný modifikátor).
Pri ukladaní hesla ho hashujte soľou a potom pri akýchkoľvek budúcich pokusoch o prihlásenie hashujte heslo, ktoré používateľ zadá, a porovnajte ho s uloženým hashom.
Ak sa tieto dva hashe zhodujú, potom je prakticky isté, že používateľ zadávajúci heslo zadal to správne.
Hašovanie je skvelé riešenie na použitie v akejkoľvek forme, ak chcete porovnať hodnotu s uloženou sumou, ale z bezpečnostných dôvodov nemôžete uložiť jej jednoduchú reprezentáciu.
Ďalším prípadom použitia by bolo napríklad overenie, či sa posledných pár číslic kreditnej karty zhoduje so vstupom používateľa, alebo porovnanie hash súboru, ktorý máme, s hashom uloženého súboru v databáze, aby sme sa uistili, že sú totožné. .
Šifrovanie – čo to je?
Šifrovanie prevádza akékoľvek údaje na sériu znakov, ktoré sú pre ľudské oko nečitateľné a nemajú pevnú dĺžku.
Po prvé, aký je hlavný princíp šifrovania? Presne tak – prítomnosť príjemcu – prijímača, ak chcete.
Hlavný rozdiel medzi šifrovaním a hašovaním je v tom, že zašifrované sekvencie možno vrátiť späť do ich pôvodnej dešifrovanej podoby za predpokladu, že je k dispozícii príslušný kľúč.
Existujú dva hlavné typy šifrovania, symetrické šifrovanie a šifrovanie verejným kľúčom.
Pri šifrovaní symetrickým kľúčom je kľúč potrebný na šifrovanie aj dešifrovanie rovnaký kľúč.
To je pravdepodobne to, čo si väčšina ľudí myslí, keď počujú o šifrovaní.
Šifrovanie verejným kľúčom má dva rôzne kľúče na porovnanie, jeden, ktorý zašifruje sekvenciu (verejný kľúč) a jeden, ktorý ju dešifruje (súkromný kľúč).
Verejný kľúč je dostupný pre každého, kto chce šifrovať správy, ale prístup k súkromnému kľúču má iba určený príjemca, a teda možnosť dešifrovať správy, ktoré mu boli predtým určené.
Populárne algoritmy
AES. AES je zlatý štandard, pokiaľ ide o symetrické šifrovanie a odporúča sa pre väčšinu prípadov s 256-bitovou veľkosťou kľúča.
PGP. PGP je najpopulárnejší šifrovací algoritmus s verejným kľúčom.
Kedy by sa malo použiť šifrovanie?
Šifrovanie by sa malo použiť, keď je potrebné dešifrovať prijatú správu.
Ak by ste napríklad chceli niekomu poslať zabezpečenú správu, namiesto hashovania by ste použili šifrovanie, pretože správa s príjemcom nič neurobí, ak ju nedokáže dešifrovať.
Ak by samotné údaje nemali byť známe v ich pôvodnej podobe, v tomto prípade sa odporúča použiť hašovanie, pretože je bezpečnejšie.
9.1. Hašovacie funkcie založené na blokových šifrách
Hashovacie funkcie sú nevyhnutným prvkom množstva kryptografických schém. Tento termín sa vzťahuje na funkcie, ktoré mapujú správy ľubovoľnej dĺžky (niekedy je dĺžka správy obmedzená, ale o dosť veľké číslo) do hodnôt s pevnou dĺžkou. Tie sa často nazývajú hash kódy. Každá hašovacia funkcia h má teda veľký počet kolízií, t.j. párov hodnôt x≠y takých, že h(x)=h(y). Hlavnou požiadavkou, ktorú kryptografické aplikácie kladú na hašovacie funkcie, je nedostatok účinných algoritmov na detekciu kolízií.
Schémy elektronického podpisu sú hlavnou aplikáciou hašovacích funkcií v kryptografii. Keďže v praxi používané schémy elektronického podpisu nie sú vhodné na podpisovanie správ ľubovoľnej dĺžky a postup pozostávajúci z rozdelenia správy do blokov a generovania podpisu pre každý blok zvlášť je mimoriadne neefektívny, jediným rozumným riešením sa zdá byť aplikácia tzv. podpisovú schému k hash kódu správy. Je ľahké pochopiť, že prítomnosť efektívnych metód na vyhľadávanie kolízií pre hašovaciu funkciu podkopáva silu protokolu elektronického podpisu. Hash funkcie sa používajú aj v niektorých autentifikačných protokoloch na zníženie ich zložitosti komunikácie, t. j. na skrátenie dĺžky odosielaných správ a v niektorých iných kryptografických protokoloch.
Viac nájdete v čítačke |
Hašovacia funkcia je transformácia, ktorá preberá dáta ľubovoľnej dĺžky na hodnotu (konvolúciu) pevnej dĺžky. Najjednoduchším príkladom sú kontrolné súčty (napr. crc32). Existujú kryptografické a programátorské hashe. Kryptografický hash sa líši od programátorského hashu v nasledujúcich dvoch vlastnostiach: nevratnosť a bezkolíznosť. Označme m ako pôvodné dáta a h(m) ako ich hash. Nevratnosť znamená, že ak je známe číslo h0, potom je ťažké vybrať m také, aby h(m) = h0. Bezkolízne znamená, že je ťažké nájsť m1 a m2 také, že m1 sa nerovná m2, ale h(m1) = h(m2).
Kryptografické hašovacie funkcie sú rozdelené do dvoch tried:
- hašovacie funkcie bez kľúča (kódy MDC (Modification (Manipulation) Detect Code)),
- hašovacie funkcie s kľúčom (kódy MAC (Message Authentication Code)).
- Bezkľúčové hašovacie funkcie sú rozdelené do dvoch podtried:
- slabé hašovacie funkcie,
- silné hašovacie funkcie.
Slabá hašovacia funkcia je jednosmerná funkcia H(x), ktorá spĺňa nasledujúce podmienky:
- argument X
- význam H(x)
- význam H(x)ľahko vypočítať;
- pre akékoľvek pevné x je výpočtovo nemožné nájsť iné x"!=x, také že H(x")=H(x). Spárovať x"!=x, Kedy H(x")=H(x) sa nazýva kolízia hašovacej funkcie.
Silná hašovacia funkcia je jednosmerná funkcia H(x), ktorá spĺňa podmienky 1–3 pre slabú hašovaciu funkciu a vlastnosť 4": 4"), je výpočtovo nemožné nájsť žiadny pár x"!=x taký, že H( x") = H (x).
Keďže vlastnosti 1–2 naznačujú, že množina definícií hašovacej funkcie je oveľa širšia ako množina hodnôt, musia existovať kolízie. Vlastnosť 4 vyžaduje, že ich nájdenie pre danú hodnotu x je takmer nemožné. Požiadavka 4" znamená, že pre silnú hašovaciu funkciu je výpočtovo nemožné nájsť vôbec nejakú kolíziu.
Hašovacia funkcia s kľúčom (MAC) je funkcia H(k,x), ktorá spĺňa nasledujúce vlastnosti:
- argument X funkcie H(k, x) môže to byť reťazec bitov ľubovoľnej dĺžky;
- význam H(k, x) musí to byť bitový reťazec s pevnou dĺžkou;
- pre akékoľvek k A Xľahko vypočítať H(k, x);
- pre hocikoho X musí byť ťažké vypočítať H(k, x), nevediac k;
- musí byť ťažké určiť k aj pri veľkom počte neznámych párov (x, H(k, x)) s vybranou sadou X alebo vypočítajte z týchto informácií H(k, x") Pre x"!=x.
Prečo je potrebná hašovacia funkcia? Faktom je, že veľa kryptografických transformácií (najmä výpočet a overenie elektronického digitálneho podpisu, EDS) sa vykonáva na dátach pevnej veľkosti. Preto pred umiestnením elektronického podpisu pod multimegabajtový súbor sa z neho zvyčajne vypočíta hodnota hašovacej funkcie a z tejto hodnoty sa vypočíta digitálny podpis. Okrem toho je vhodné napríklad ukladať heslá do databázy nie v čistom texte, ale v hašovanej forme (to sa robí vo všetkých Unixoch).
Niektoré algoritmy hashovacích funkcií:
- MD 2. Prehľad správ. Algoritmus kryptografického zosúladenia. Generuje 128-bitový blok zo správy ľubovoľnej dĺžky.
- MD 4.Ďalší konvolučný algoritmus. Generuje 128-bitový blok.
- MD 5. Výrazne prerobený MD 4. Autor je rovnaký - Riverst.
- SHA. Výsledný hash je 160-bitový.
- GOST R34.11–94. Ruský algoritmus. Dĺžka konvolúcie je 256 bitov (veľmi vhodné na generovanie kľúča pre GOST 28147–89 pomocou hesla).
Základnou myšlienkou používania kryptografických funkcií je, že hodnoty hash slúžia ako kompaktná reprezentácia vstupného binárneho reťazca a možno ich použiť, ako keby boli s týmto reťazcom jednoznačne identifikované, aj keď pre doménu definície D a rozsahy R s (čo znamená kardinality množín), funkcia typu „veľa-jeden“ znamená, že existencia kolízie (páry vstupov s rovnakým výstupom) je nevyhnutný. Rozsah hašovacej funkcie nie je jasne definovaný: používa sa „na implementáciu postupov elektronického digitálneho podpisu (EDS) pri prenose, spracovaní a uchovávaní informácií v automatizovaných systémoch.
- súbor binárnych reťazcov dĺžky n trocha;
— binárny reťazec pozostávajúci z n nuly;
- sčítanie binárnych slov A A B Autor: .
Správy ľubovoľnej dĺžky možno komprimovať pomocou hašovacej funkcie s pevnou veľkosťou vstupu, a to dvoma spôsobmi:
- sekvenčné (iteratívne);
- paralelný.
9.2. Najdôležitejšie prakticky používané perzistentné hašovacie funkcie
Tvorcovia GOST R34.11–94 sa vybrali prvou cestou a použili metódu sekvenčného hašovania pomocou hašovacej funkcie s pevnou vstupnou veľkosťou (pozri obr. 1), teda kompresnú funkciu s koeficientom 2.
Ryža. 1. Metóda sekvenčného hashovania.
Ak potrebujete správu hash 
, potom sa hašovanie vykoná takto:
Tu je funkcia kompresie a – spojka variabilná.
Ak posledný blok obsahuje menej ako n bit, potom sa „napcháva“, kým nedosiahne dĺžku n. Na rozdiel od štandardných predpokladov, ktoré predpokladajú, že správa už bola predtým rozdelená na bloky a posledný blok bol „vyplnený“ (to zodpovedá formátovaniu vstupnej správy a priori) pred začatím hashovania, v GOST R34.11–94 hashovacia procedúra čaká na koniec správy (formátovanie vstupných správ a posteriori). „Padding“ sa vykonáva nasledovne: posledný blok sa posunie doprava a potom sa uvoľnené bity naplnia nulami, kým sa nedosiahne dĺžka 256 bitov. Hašovací algoritmus podľa GOST R34.11–94 možno klasifikovať ako odolný voči kolízii ( n= 256, preto by útok narodeninového paradoxu vyžadoval približne operácie hashovania) kódu, ako aj detekciu úprav ( Zrážka Odolný Hash Funkcia, CRHF). Hašovaciu funkciu v súlade s GOST R34.11–94 je možné ľahko previesť na overovací kód správy pomocou akejkoľvek známej metódy (napríklad HMAC, tajná predpona, prípona, shell atď.).
Viac nájdete v čítačke |
Vývojári však poskytli ďalšie ochranné opatrenia, pre ktoré paralelne počítajú:
Vypočítané hodnoty vo funkcii konečnej kompresie sa používajú na výpočet konečného hashu (pozri obrázok 2).
Ryža. 2. Všeobecná schéma hašovacej funkcie podľa GOST R34.11–94.
Poznámka 1 („plnka“). V prenášanej správe nie je potrebné uvádzať, koľko núl bolo pridaných do posledného bloku, pretože dĺžka správy sa podieľa na hashovaní.
Ryža. 3. „Vyplnenie“ správy.
Poznámka 2. Podľa GOST R34.11–94 počiatočný vektor IV –
ľubovoľné pevné slovo dlhé 256 bitov 
). V tomto prípade, ak to nie je a priori známe overovateľovi integrity správy, potom sa musí preniesť spolu so správou so zárukou integrity. Pri malých správach môže byť úloha nepriateľa sťažená, ak vektor IV
vyberte si z malej množiny platných hodnôt (to však zvyšuje pravdepodobnosť, že oponent uhádne hodnotu hash). Môže sa tiež nastaviť v rámci organizácie alebo domény ako konštanta (zvyčajne ako v príklade testu).
Secure Hash Algorithm - 1 (SHA-1) bol vyvinutý Národným inštitútom pre štandardy a technológie (NIST) a publikovaný ako Federal Information Standard (FIPS PUB 180) v roku 1993.
Algoritmus prijíma správu s maximálnou bitovou dĺžkou ako vstup a ako výstup vytvára súhrn správy 160 bitov. Algoritmus obsahuje niekoľko krokov.
Krok 1: Pridajte chýbajúce bity. Správa sa pridáva tak, že jej dĺžka je násobkom 448 mod 512 (dĺžka 448 mod 512). Pridávanie sa vykonáva vždy, aj keď už má správa požadovanú dĺžku. Počet bitov, ktoré sa majú pridať, je teda v rozsahu od 1 do 512. Sčítanie pozostáva z jednotky, za ktorou nasleduje požadovaný počet núl.
Krok 2: Pridajte dĺžku. K správe je pripojený blok 64 bitov. Tento blok sa považuje za 64-bitové celé číslo bez znamienka a obsahuje dĺžku pôvodnej správy pred pripojením. Výsledkom prvých dvoch krokov je správa, ktorej dĺžka je násobkom 512 bitov. Rozšírená správa môže byť reprezentovaná ako sekvencia 512-bitových blokov Y0, Y1,..., YL-1. Celková dĺžka rozšírenej správy je teda L * 512 bitov (výsledkom je násobok šestnástich 32-bitových slov).
Krok 3: Inicializujte vyrovnávaciu pamäť SHA-1. Na uloženie medziproduktov a konečných výsledkov výpočtu hashovacej funkcie sa používa 160-bitová vyrovnávacia pamäť. Buffer môže byť reprezentovaný ako päť 32-bitových registrov na uloženie čísel A, B, C, D a E. Tieto registre sú inicializované nasledujúcimi hexadecimálnymi číslami: A=67452301; B=EFCDAB 89; C=98BADCFE; D = 10325476; E=C3D2E1F0.
Krok 4: Spracujte správu v 512-bitových (16-slovných) blokoch. Základom algoritmu je modul pozostávajúci z 80 cyklických ošetrení, označených ako HSHA. Všetkých 80 cyklov spracovania každého bloku má rovnakú štruktúru.
Ryža. 4. Spracovanie ďalšieho 512-bitového bloku.
Každá slučka berie ako vstup aktuálny 512-bitový blok, ktorý sa spracováva, a 160-bitovú hodnotu vyrovnávacej pamäte ABCDE a upravuje obsah tejto vyrovnávacej pamäte. Každá slučka používa ďalšiu konštantu, ktorá má iba štyri rôzne hodnoty:
5A827999 (celočíselná časť); |
|
6 ED 9 EBA 1 (celočíselná časť); |
|
8 F 1 BBCDC (celočíselná časť); |
|
CA 62 C 1 D 6 (celočíselná časť čísla). |
Na získanie výstupu z 80. cyklu sa pripočíta k hodnote. Pridávanie modulov sa vykonáva nezávisle pre každé z piatich slov vo vyrovnávacej pamäti s každým zo zodpovedajúcich slov v .
Krok 5: výstup. Po spracovaní všetkých 512-bitových blokov správ je výstupom L-tej fázy algoritmu 160-bitový súhrn správ. Pozrime sa bližšie na operačnú logiku v každom z 80 cyklov spracovania pre jeden 512-bitový blok. Nové (vypočítané) hodnoty pre premenné A, B, C, D, E na výstupe každého cyklu spracovania môžu byť reprezentované takto:
Tu: A, B, C, D, E – päť 32-bitových slov z vyrovnávacej pamäte; t – číslo cyklu 0 ≤ t ≤ 79; – elementárna logická funkcia; – cyklický posun 32-bitového argumentu doľava o s bitov; – 32-bitové slovo získané z aktuálneho vstupného 512-bitového bloku; – prídavná konštanta; znamienko „+“ – pridanie modulu.
Ryža. 5. Logika na vykonanie samostatnej slučky.
Každá atómová funkcia prijíma tri 32-bitové slová ako vstup a vytvára jedno 32-bitové slovo ako výstup. Elementárna funkcia vykonáva súbor bitových logických operácií, t.j. n-tý bit výstupu je funkciou n-tých bitov troch vstupov. Funkcie ft (B, C, D) sú nasledovné:
Číslo cyklu |
ft (B, C, D) |
|
|
V praxi sa používajú iba tri rôzne funkcie. Pre 0 ≤t ≤19 je funkcia podmienená: ak B, potom C inak D. Pre 20 ≤t ≤39 a 60 ≤t ≤79 funkcia vytvára paritný bit. Pre 40 ≤ t ≤ 59 je funkcia pravdivá, ak sú pravdivé dva alebo tri argumenty. 32-bitové slová sa získajú z nasledujúceho 512-bitového bloku správ nasledovne.
Ryža. 6. Získanie premenných vstupných hodnôt pre každú slučku
z nasledujúceho (aktuálneho) 512-bitového spracovaného bloku.
Prvých 16 hodnôt je prevzatých priamo zo 16 slov aktuálneho bloku. Zvyšné hodnoty sa určujú takto: . V prvých 16 cykloch spracovania pozostáva vstup z 32-bitového slova daného bloku. Pre zvyšných 64 cyklov sa vstup skladá z XORingu niekoľkých slov z bloku správ.
Algoritmus SHA-1 možno zhrnúť takto:
kde IV je počiatočná hodnota vyrovnávacej pamäte premenných A, B, C, D, E;
– výsledok spracovania q-tého bloku správ;
L – počet blokov v správe vrátane polí dodatku a dĺžky;
Σ 32 – súčet modulo, vykonávaný samostatne pre každé slovo vyrovnávacej pamäte;
SHA – hodnota súhrnu správ.
Hašovanie hesla je metóda, ktorá používateľom umožňuje zapamätať si nie 128 bajtov, t. j. 256 hexadecimálnych číslic kľúča, ale nejaký zmysluplný výraz, slovo alebo sekvenciu znakov nazývaných heslo. Pri vývoji akéhokoľvek kryptografického algoritmu je skutočne potrebné vziať do úvahy, že v polovici prípadov je koncovým používateľom systému osoba a nie automatický systém. To vyvoláva otázku, či je vhodné a dokonca reálne, aby si človek zapamätal 128-bitový kľúč (32 hexadecimálnych číslic). Hranica zapamätateľnosti leží na hranici 8 – 12 podobných symbolov, a preto, ak donútime používateľa ovládať kľúč, prakticky ho donútime napísať kľúč napríklad na nejaký papier alebo elektronické médium. v textovom súbore. To, prirodzene, výrazne znižuje bezpečnosť systému.
Na vyriešenie tohto problému boli vyvinuté metódy, ktoré konvertujú hovorený zmysluplný reťazec ľubovoľnej dĺžky – heslo – na špecifikovaný kľúč vopred určenej dĺžky. V drvivej väčšine prípadov sa na túto operáciu využívajú takzvané hašovacie funkcie (z anglického hashing – jemné krájanie a miešanie).
Hašovacia funkcia je matematická alebo algoritmická transformácia daného bloku údajov, ktorá má nasledujúce vlastnosti:
- hašovacia funkcia má nekonečnú doménu;
- hašovacia funkcia má konečný rozsah;
- je to nezvratné;
- zmena vstupného informačného toku o 1 bit zmení približne polovicu všetkých bitov výstupného toku, t.j. výsledok hašovacej funkcie.
Tieto vlastnosti vám umožňujú zadávať heslá do hašovacej funkcie, t.j. textové reťazce ľubovoľnej dĺžky v akomkoľvek národnom jazyku a obmedzením rozsahu hodnôt funkcie na rozsah, kde N je dĺžka kľúča v bitoch. , získať na výstupe bloky informácií pomerne rovnomerne rozložené v rozsahu hodnôt – kľúčov.
Je ľahké vidieť, že požiadavky podobné bodom 3 a 4 požiadaviek hašovacej funkcie spĺňajú blokové šifry. To naznačuje jeden z možných spôsobov implementácie silných hašovacích funkcií – vykonávanie blokových kryptografických transformácií na materiáli reťazca hesla. Táto metóda sa v rôznych obmenách používa takmer vo všetkých moderných kryptosystémoch. Materiál reťazca hesla sa opakovane postupne používa ako kľúč na zašifrovanie nejakého predtým známeho bloku údajov – výstupom je zašifrovaný blok informácií, ktorý jednoznačne závisí len od hesla a zároveň má pomerne dobré štatistické charakteristiky. Takýto blok alebo niekoľko takýchto blokov sa používa ako kľúč pre ďalšie krypto transformácie.
Povaha použitia blokovej šifry na hashovanie je určená pomerom veľkosti bloku použitého kryptografického algoritmu a bitovej hĺbky požadovaného výsledku hashovania.
O hodnotách hash MD5 a prijatá odpoveď ma zmiatla. Jednou z hlavných vlastností, ako som pochopil, kryptografickej hašovacej funkcie je, že nie je možné nájsť dve rôzne správy (vstupy) s rovnakou hašovacou hodnotou.
Konsenzuálna odpoveď na otázku však znie: Prečo nie sú hodnoty hash MD5 reverzibilné? Pretože nekonečný počet vstupných riadkov bude generovať rovnaký výstup. Toto sa mi zdá úplne protichodné.
Tiež skutočnosť, že algoritmy sú verejné, ale hodnoty hash sú stále nezvratné, je pre mňa trochu ohromujúce. Je to preto, že v hašovacej funkcii vždy dochádza k strate údajov, takže neexistuje spôsob, ako zistiť, aké údaje boli vyhodené?
Čo sa stane, keď je veľkosť vstupných údajov menšia ako pevná veľkosť výstupných údajov (napr. hashovanie hesla „abc“)?
Dobre, pozrime sa, či mám toto právo:
- V skutočnosti je veľmi ťažké odvodiť z hashu pretože existuje nekonečný počet vstupných riadkov, ktoré budú generovať rovnaký výstup(nevratná vlastnosť).
- Avšak Vyhľadávanie dokonca aj jedna inštancia viacerých vstupných reťazcov, ktoré generujú rovnaký výstup, je tiež skutočne veľmi náročná (vlastnosť odolná voči kolíziám).
6 odpovedí
Môžete byť zmätení, pretože odpoveď na otázku, ktorú citujete, je mätúca. Jednou z požiadaviek na kryptografickú hašovaciu funkciu je, že musí byť odolná voči preimage. To znamená, že ak poznáte MD5(x), ale nie správu x, potom je ťažké nájsť nejaké x" (buď rovné x alebo odlišné od x) také, že MD5(x") = MD5(x).
Stabilita predobrazu je iná vlastnosť ako reverzibilita. Funkcia je invertibilná, ak je dané y = f(x), existuje práve jedno x, ktoré sedí (ľahko alebo nie). Napríklad definujme f (x) = x mod 10. Potom f nie je invertibilné. Z f(x) = 7 nemôžete povedať, či x bolo 17, 27 alebo niečo iné. Ale f nie je stabilný, pretože hodnoty x" sú také, že f(x) = 7 je ľahké nájsť. x" = 17, 27, 12341237 atď. všetci pracujú.
Keď robíte kryptografiu, zvyčajne chcete funkcie, ktoré sú odolné voči preimage (a ďalšie vlastnosti, ako je odolnosť proti kolíziám), nielen veci, ktoré nie sú invertovateľné.
Upozornenie: dlhá odpoveď
Myslím si, že všetkým týmto odpovediam chýba veľmi dôležitá vlastnosť kryptografických hašovacích funkcií: nielenže nie je možné vypočítať pôvodnú správu, ktorá bola hašovaná, aby vytvorila daný haš, nie je možné vypočítať žiadnu správu, ktorá by hašovala hodnotu hašovania. Toto sa nazýva prozreteľnosť odporu.
(Pod pojmom „nemožné“ mám na mysli, že nikto nevie, ako to urobiť za kratší čas, než je potrebný na uhádnutie všetkých možných správ, kým neuhádnete tú, ktorá bola zahašovaná do vášho hashu.)
(Napriek všeobecnému presvedčeniu, že MD5 je nespoľahlivý, MD5 je stále odolný voči preimage. Každý, kto mi neverí, mi môže dať čokoľvek, čo hašuje . Čo MD5 nemá, je odolnosť voči kolízii, čo je niečo úplne iné.)
Ak teda jediným dôvodom, prečo ste v kryptografickej hašovacej funkcii nemohli „pracovať spätne“, bolo to, že hašovacia funkcia zahodí údaje na vytvorenie hašovacej funkcie, potom to nezaručuje odolnosť prozreteľnosti: stále môžete „pracovať dozadu“ a len vložiť náhodné údaje všade tam, kde hašovacia funkcia zahodí údaje, a kým neprídete s originálnou správou, stále prídete so správou, ktorá hashuje požadovanú hodnotu hašovacej funkcie. Ale ty nemôžeš.
Vynára sa teda otázka: prečo nie? (Alebo inými slovami, ako urobíte predobraz funkcie stabilný?)
Odpoveď je, že kryptografické hašovacie funkcie napodobňujú chaotické systémy. Vezmú vašu správu, rozdelia ju na bloky, zmiešajú tieto bloky, zablokujú niektoré bloky, zmiešajú tieto bloky a opakujú to mnohokrát (dobre, jedna kryptografická hašovacia funkcia to robí, iné majú svoje vlastné metódy). Keďže bloky interagujú navzájom, blok C musí nielen interagovať s blokom D, aby vytvoril blok A, ale musí interagovať s blokom E, aby vytvoril blok B. Teraz, samozrejme, môžete nájsť hodnoty blokov C, D , E, ktoré vygenerujú bloky A a B vo vašej hash hodnote, ale keď pôjdete ďalej dozadu, budete potrebovať blok F, ktorý interaguje s C, aby urobil D a s E, aby urobil B, a takýto blok nemôže robiť ako v rovnaký čas! Určite ste uhádli nesprávne hodnoty C, D a E.
Aj keď nie všetky kryptografické hašovacie funkcie sú presne také, ako tie, ktoré sú opísané vyššie pri blokovej komunikácii, majú rovnakú myšlienku: ak sa pokúsite „pracovať dozadu“, skončíte s mnohými slepými uličkami a stratíte čas, keď vyskúšate dostatok hodnôt. Vytvorenie predbežného obrazu je rádovo stovky až milióny rokov (v závislosti od hašovacej funkcie), čo nie je oveľa lepšie ako čas potrebný na vyskúšanie správ, kým nenájdete fungujúcu.
č. veľký ako aleph-0.)
Okrem iných funkcií vypĺňajú cieľový priestor rovnomerne dobré hashe. Zlé hashe vypĺňajú priestor hrudkovitým spôsobom a prichádzajú s rovnakým hashom pre mnohé bežné vstupy.
Predstavte si hlúpu hashovaciu funkciu sum(), ktorá len pridá všetky číslice vstupného čísla: podarí sa jej zmapovať, ale na spodnom konci je veľa kolízií (vstupy s rovnakým výstupom ako 3 a 12 a 21). výstupný priestor a horný koniec priestoru je takmer prázdny. V dôsledku toho veľmi zle využíva priestor, je ľahko napadnuteľný atď.
Takže dobrý hash, ktorý dokonca využíva cieľový priestor, sťaží nájdenie dvoch vstupov s rovnakým výstupom, jednoducho náhodou: ak je MD5 dokonalý, pravdepodobnosť, že dva vstupy budú mať rovnaký výstup, bude 2^-128. To sú celkom slušné šance: to najlepšie, čo môžete urobiť bez toho, aby ste sa uchýlili k väčšiemu výstupnému priestoru. (V skutočnosti MD5 nie je dokonalý, čo je jedna z vecí, ktoré ho robia zraniteľným.)
Stále však bude platiť, že veľké množstvo vstupov sa bude mapovať na akýkoľvek daný hash, keďže vstupný priestor je „nekonečný“ a delenie nekonečna číslom 2^128 vám stále dáva nekonečno.
2: Áno, hašovanie vždy spôsobuje stratu údajov, pokiaľ váš výstupný priestor nie je rovnaký alebo väčší ako váš vstupný priestor – v takom prípade pravdepodobne hašovať nemusíte!
3: Pre menšie prívody je najlepšou praxou prívod fyziologického roztoku. V skutočnosti je to dobrá prax pre akékoľvek kryptografické hašovanie, pretože inak by vám útočník mohol poskytnúť konkrétne vstupy a pokúsiť sa zistiť, aký hash používate. „Soľ“ je len zhluk ďalších informácií, ktoré pridáte (alebo pridáte) k svojmu vstupu; potom dostanete výsledok.
upraviť. V kryptografii je tiež dôležité, aby bola hašovacia funkcia intuitívne odolná voči preimage útokom, je ťažké uhádnuť vstup pre daný výstup, aj keď poznáme mnoho ďalších vstupno-výstupných párov, funkcia „sum“ by sa dala uhádnuť celkom jednoducho (. ale keďže ničí údaje, nemusí byť ľahké vrátiť späť).
Toto sú vlastnosti hašovacích funkcií vo všeobecnosti.
Pozor, MD5 by sa už nemal používať kvôli zraniteľnostiam, ktoré sa v ňom nachádzajú. Pozrite si časť Zraniteľnosť a externé odkazy s podrobnosťami o týchto útokoch. http://en.wikipedia.org/wiki/Md5 Kolíziu MD5 môžete urobiť zmenou iba 128 bitov v správe.
SHA-1 je bezpečný pre jednoduché hašovanie, aj keď existujú niektoré útoky, ktoré ho oslabia pre dobre financované organizácie (vlády, veľké korporácie).
SHA-256 je bezpečným východiskovým bodom pre technológie v priebehu niekoľkých nasledujúcich desaťročí.
