(někdy hash, anglicky hash) - převod pole vstupních dat libovolné délky na výstupní bitový řetězec pevné délky. Takové transformace se také nazývají hashovací funkce nebo redukční funkce a jejich výsledky se nazývají hash, hash code nebo message digest.
Hašování se používá k porovnání dat: pokud mají dvě pole různé hashovací kódy, je zaručeno, že se pole budou lišit; pokud jsou stejné, pole jsou s největší pravděpodobností stejná. V obecném případě neexistuje žádná individuální korespondence mezi zdrojovými daty a hashovacím kódem kvůli skutečnosti, že počet hodnot hashovací funkce je menší než počet variant vstupního pole; existuje mnoho polí, která dávají stejné hash kódy – tzv. kolize. Pravděpodobnost kolizí hraje důležitou roli při posuzování kvality hašovacích funkcí.
Existuje mnoho hashovacích algoritmů s různými vlastnostmi (bitová kapacita, výpočetní složitost, kryptografická síla atd.). Volba té či oné hashovací funkce je dána specifiky řešeného problému. Nejjednoduššími příklady hašovacích funkcí jsou kontrolní součet nebo CRC.
Kontrolní součty
Nekomplikované, extrémně rychlé a snadno implementovatelné hardwarové algoritmy používané k ochraně před neúmyslným zkreslením, včetně hardwarových chyb.Rychlost výpočtu je desítky a stovkykrát rychlejší než kryptografické hašovací funkce a mnohem jednodušší v hardwarové implementaci.
Cenou za tak vysokou rychlost je nedostatečná kryptografická síla – snadná příležitost upravit zprávu na předem známou částku. Kontrolní součty (typické: 32 bitů) mají také obvykle menší šířku než kryptografické hash (typické: 128, 160 a 256 bitů), což znamená, že může dojít k neúmyslným kolizím. Nejjednodušším případem takového algoritmu je rozdělení zprávy na 32 nebo 16bitová slova a jejich sečtení, což se používá například v TCP/IP.
Zpravidla je takový algoritmus vyžadován pro sledování typických hardwarových chyb, jako je několik po sobě jdoucích chybných bitů dané délky. Rodina algoritmů tzv. "cyklické redundantní kódy" tyto požadavky splňují. Patří mezi ně například CRC32, používaný v ethernetových zařízeních a ve formátu souborů ZIP.
Kryptografické hašovací funkce
Mezi mnoha existujícími hašovacími funkcemi je obvyklé rozlišovat kryptograficky silné hašovací funkce používané v kryptografii. V zájmu hašovací funkce H považován za kryptograficky silný, musí splňovat tři základní požadavky, na kterých je založena většina použití hašovacích funkcí v kryptografii:- Nevratnost: pro danou hash hodnotu m musí být výpočetně nemožné najít blok dat X, pro který H(X) = m.
- Odolnost proti srážkám prvního druhu: pro danou zprávu M musí být výpočetně neproveditelné vyzvednutí další zprávy N, pro který H(N) = H(M).
- Odolné vůči kolizím typu II: musí být výpočetně neproveditelné spárovat pár zpráv (M, M"), mající stejný hash.
- Invertibilní funkce není odolná proti srážkám prvního a druhého druhu.
- Funkce, která není odolná proti srážkám prvního druhu, není odolná proti srážkám druhého druhu; obráceně to není pravda.
Narozeninový útok umožňuje najít kolize hashovací funkce s délkou hodnot n bitů v průměru ve výpočtech asi 2 n/2 hashovací funkce. Proto n-bitová hašovací funkce je považována za kryptoodolnou, pokud se výpočetní složitost hledání kolizí pro ni blíží 2 n/2.
U kryptografických hashovacích funkcí je také důležité, že při sebemenší změně argumentu se hodnota funkce velmi změní (lavinový efekt). Zejména hodnota hash nesmí unikat informace ani o jednotlivých bitech argumentu. Tento požadavek je klíčem ke kryptografické síle hashovacích algoritmů, které hashují uživatelské heslo pro získání klíče.
Použití hashovacích funkcí
Hashovací funkce se používají i v některých datových strukturách – hashovacích tabulkách, Bloomových filtrech a kartézských stromech. Požadavky na hashovací funkci jsou v tomto případě odlišné:- dobrá mixovatelnost dat
- rychlý výpočetní algoritmus
Obecně lze tuto aplikaci popsat jako kontrolu některých informací, aby byly shodné s originálem, bez použití originálu. Pro odsouhlasení se používá hash hodnota ověřovaných informací. Existují dvě hlavní oblasti této aplikace:
- Kontrola chyb- Například kontrolní součet může být přenášen komunikačním kanálem spolu s hlavním textem. Na přijímací straně lze kontrolní součet přepočítat a porovnat s přenášenou hodnotou. Pokud je zjištěna nesrovnalost, znamená to, že během přenosu došlo ke zkreslení a lze požadovat opakování.
Domácím analogem hašování může být v tomto případě technika, kdy je při pohybu uchováván počet zavazadel v paměti. Pro kontrolu si pak nemusíte pamatovat každý kufr, ale stačí je spočítat. Shoda bude znamenat, že se žádný kufr neztratí. To znamená, že počet zavazadel je jejich hash kód. Tuto metodu lze snadno rozšířit o ochranu před falšováním přenášených informací (metoda MAC). V tomto případě je hašování prováděno krypto-silnou funkcí na zprávě v kombinaci s tajným klíčem, který zná pouze odesílatel a příjemce zprávy. Kryptanalytik tedy nebude schopen rekonstruovat kód pomocí zachycené zprávy a hodnoty hashovací funkce, to znamená, že nebude schopen zprávu podvrhnout.
- Zrychlete načítání dat- Například při zápisu textových polí do databáze lze vypočítat jejich hash kód a data umístit do sekce odpovídající tomuto hash kódu. Při vyhledávání dat si pak budete muset nejprve spočítat hash kód textu a hned budete vědět, ve které sekci jej musíte hledat, to znamená, že budete muset hledat ne v celé databázi, ale pouze v jedné jeho části (to velmi urychluje vyhledávání).
Obvyklou analogií hašování v tomto případě může být umístění slov do slovníku v abecedním pořadí. První písmeno slova je jeho hash kód a při vyhledávání neprohlížíme celý slovník, ale pouze požadované písmeno.
Hašování(z anglického hashing) - převod vstupních dat libovolné délky na výstupní bitový řetězec pevné délky tak, že změna vstupních dat vede k nepředvídatelné změně výstupních dat. Takové transformace se také nazývají hašovací funkce nebo konvoluční funkce a jejich výsledky se nazývají hašovací nebo hašovací kód.
Hash problémy
Kontrola přístupové fráze
Dnes je nebezpečné ukládat hesla na cílové objekty, protože odtud je mohou útočníci ukrást a použít pro vlastní účely. Ukládají se tam tedy pouze hashe hesel, které nelze vrátit zpět a heslo nelze zjistit. Při kontrole hesla se zadané heslo hashuje a hodnoty hash se porovnávají.
Nejběžnější algoritmy: MD5 (MD4, MD2), SHA1.
Zrychlete načítání dat
Například v databázi lze při psaní textových polí vypočítat jejich hash kód a zapsat jej do samostatného pole. Při vyhledávání dat pak budete muset vypočítat hash kód dat a prohledávat nikoli celou databázi, ale pouze její jednu část.
Výpočet kontrolního součtu.
Ke kontrole chybovosti paketu se často používá kontrolní součet, který je přenášen spolu se zprávou. Na přijímací straně, když je zpráva přijata, je znovu vypočítán kontrolní součet a pokud se hodnota shoduje s přenesenou, byla zpráva odeslána bez chyb.
Výpočet elektronického digitálního podpisu.
Elektronický digitální podpis se používá k ochraně elektronického dokumentu před paděláním. Získané v důsledku převodu informací pomocí soukromého klíče vám umožňuje identifikovat vlastníka podpisového klíče a prokázat absenci zkreslení informací v elektronickém dokumentu.
Požadavky na hashovací algoritmus
Hašovací funkci lze použít na argument libovolné velikosti.
Výstupní hodnota má pevnou velikost.
Rychlost výpočtu hašovací funkce musí být taková, aby rychlost generování digitálního podpisu při použití hašovací funkce výrazně převyšovala rychlost generování digitálního podpisu při použití samotné zprávy.
Hašovací funkce je jednosměrná funkce. Pro jakékoli m je tedy výpočetně nemožné najít takový otevřený text X, h(X) = m
Pravděpodobnost, že se hodnoty hash dvou různých dokumentů (bez ohledu na jejich délku) budou shodovat, by měla být zanedbatelná.
AlgoritmusM.D.5
MD5(Message Digest 5) je hashovací algoritmus vyvinutý R. Rivestem z Massachusetts Institute of Technology (MIT) v roce 1991.
Podrobný popis algoritmu lze nalézt v RFC 1321.
Na výstupu algoritmus vytvoří 128bitový výtah zprávy (otisk prstu). Délka původní zprávy může být libovolná.
Algoritmus MD5 je zranitelný vůči některým útokům, jako je možnost vytvoření dvou zpráv se stejným hashovým součtem, proto se jeho použití v nových projektech nedoporučuje.
AlgoritmusSHA-1
Hašovací algoritmus SHA (Secure Hash Algorithm) byl přijat jako americký standard v roce 1992.
Popsáno v RFC 3174.
Navrženo pro použití ve spojení s algoritmem digitálního podpisu. Když je zadán prostý text, algoritmus vytvoří 160bitovou výstupní zprávu (digest), která se používá ke generování digitálního podpisu.
Hašovací algoritmus SHA se nazývá bezpečný, protože je navržen tak, že je výpočetně nemožné rekonstruovat zprávu odpovídající danému výtahu a také najít dvě různé zprávy, které poskytnou stejný výtah.
Rozdíly mezi algoritmy SHA a MD5 jsou následující:
1. SHA vytváří 160bitovou hašovací hodnotu a je odolnější vůči útokům hrubou silou než MD5, který vytváří 128bitovou hašovací hodnotu.
2. Kompresní funkce SHA zahrnuje 80 kol, nikoli 64 jako v MD5.
3. Proces míchání je komplikovaný.
Rodina algoritmůSHA-2
Algoritmy podrodiny SHA-2 , stejně jako algoritmus SHA-1 , byly vyvinuty americkou Národní bezpečnostní agenturou a publikovány Národním institutem pro standardy a technologie (NIST) ve federálním standardu pro zpracování informací FIPS PUB 180–2 v srpnu 2002.
Používají se algoritmy rodiny SHA-2 SSL, SSH, S/ MIM, DNSSEC, X.509 , PGP, IPSec, při přenosu souborů po síti ( BitTorrent).
Algoritmyhašování
MD5 md5 = nový MD5CryptoServiceProvider();
string stringToHash = "Jezte ještě trochu těchto měkkých francouzských rohlíků a vypijte čaj";
byte hash = md5.ComputeHash(Encoding.Unicode.GetBytes(stringToHash));
Console.WriteLine(ByteHelper.ByteArrayToHexString(hash));
string otherStringToHash = "Rychlá hnědá liška skáče přes líného psa";
HashAlgorithm sha512 = HashAlgorithm.Create("SHA512");
Console.WriteLine(
ByteHelper.ByteArrayToHexString(
sha512.ComputeHash(
Encoding.Unicode.GetBytes(
Hashovací funkce nacházejí uplatnění v celé řadě odvětví informačních technologií. Jsou navrženy tak, aby na jedné straně výrazně zjednodušily výměnu dat mezi uživateli a zpracování souborů používaných pro různé účely a na druhé straně optimalizovaly algoritmy pro zajištění řízení přístupu k relevantním zdrojům. Hashovací funkce je jedním z klíčových nástrojů pro zajištění ochrany dat heslem a také pro organizaci výměny dokumentů podepsaných elektronickým digitálním podpisem. Existuje velké množství standardů, jejichž prostřednictvím lze provádět ukládání souborů do mezipaměti. Mnohé z nich byly vyvinuty ruskými specialisty. Jaké typy hashovacích funkcí lze prezentovat? Jaké jsou hlavní mechanismy jejich praktické aplikace?
co to je?
Nejprve prozkoumáme koncept hashovací funkce. Tento termín je obvykle chápán jako algoritmus pro převod určitého množství informací na kratší sekvenci znaků pomocí matematických metod. Praktický význam hashovací funkce lze vidět v různých oblastech. Lze je tedy použít při kontrole integrity souborů a programů. Kryptografické hašovací funkce se také používají v šifrovacích algoritmech.
Charakteristika
Podívejme se na klíčové vlastnosti studovaných algoritmů. Mezi nimi:
- přítomnost vnitřních algoritmů pro převod dat původní délky na kratší sekvenci znaků;
- otevřený pro kryptografické ověření;
- přítomnost algoritmů, které vám umožňují spolehlivě zašifrovat původní data;
- přizpůsobivost k dešifrování při použití malého výpočetního výkonu.
Mezi další důležité vlastnosti hashovací funkce patří:
- schopnost zpracovávat počáteční pole dat libovolné délky;
- generovat hashované bloky pevné délky;
- rovnoměrně distribuovat funkční hodnoty na výstupu.
Uvažované algoritmy rovněž předpokládají citlivost na vstupní data na úrovni 1 bitu. To znamená, že i když se relativně vzato změní alespoň 1 písmeno ve zdrojovém dokumentu, hashovací funkce bude vypadat jinak.
Požadavky na hashovací funkce
Na hashovací funkce určené pro praktické použití v konkrétní oblasti existuje řada požadavků. Za prvé, odpovídající algoritmus musí být citlivý na změny ve vnitřní struktuře hašovaných dokumentů. To znamená, že v hashovací funkci, pokud mluvíme o textovém souboru, by měly být rozpoznány přeuspořádání odstavců a pomlčky. Jednak se nemění obsah dokumentu, jednak se upravuje jeho struktura a tento proces je třeba při hašování rozpoznat. Za druhé, daný algoritmus musí transformovat data takovým způsobem, aby zpětná operace (převod hashe na původní dokument) byla v praxi nemožná. Za třetí, hashovací funkce musí zahrnovat použití algoritmů, které prakticky eliminují možnost vytvoření stejné sekvence znaků ve formě hashe, jinými slovy výskyt takzvaných kolizí. Na jejich podstatu se podíváme o něco později.
Uvedené požadavky, které musí algoritmus hashovací funkce splňovat, lze dosáhnout především použitím komplexních matematických přístupů.
Struktura
Podívejme se, jaká může být struktura uvažovaných funkcí. Jak jsme uvedli výše, jedním z hlavních požadavků na uvažované algoritmy je zajistit jednosměrné šifrování. Člověk, který má pouze hash, by z něj neměl prakticky získat původní dokument.
V jaké struktuře může být reprezentována hashovací funkce používaná pro takové účely? Příklad jejího složení by mohl být následující: H (hash, tedy hash) = f (T (text), H1), kde H1 je algoritmus zpracování textu T. Tato funkce hashuje T takovým způsobem, že bez znalosti H1 jej lze otevřít jako plnohodnotný jeden soubor bude téměř nemožné.
Použití hašovacích funkcí v praxi: stahování souborů
Pojďme si nyní podrobněji prostudovat možnosti využití hašovacích funkcí v praxi. Použití vhodných algoritmů lze využít při psaní skriptů pro stahování souborů z internetových serverů.
Ve většině případů je pro každý soubor určen určitý kontrolní součet - to je hash. Musí být stejný pro objekt umístěný na serveru a stažený do počítače uživatele. Pokud tomu tak není, soubor se nemusí otevřít nebo se nemusí správně spustit.
Hash funkce a digitální podpis
Používání hashovacích funkcí je běžné při organizování výměny dokumentů obsahujících digitální podpis. V tomto případě je podepisovaný soubor hašován, aby jeho příjemce mohl ověřit, že je pravý. Přestože hashovací funkce není formálně zahrnuta ve struktuře elektronického klíče, lze ji zaznamenat do flash paměti hardwaru používaného k podepisování dokumentů, jako je eToken.
Elektronický podpis je šifrování souboru pomocí veřejných a soukromých klíčů. To znamená, že zpráva zašifrovaná pomocí soukromého klíče je připojena ke zdrojovému souboru a digitální podpis je ověřen pomocí veřejného klíče. Pokud se hašovací funkce obou dokumentů shoduje, je soubor držený příjemcem rozpoznán jako pravý a podpis odesílatele je rozpoznán jako správný.
Hašování, jak jsme již uvedli výše, není přímou součástí digitálního podpisu, ale umožňuje velmi efektivně optimalizovat algoritmy pro použití elektronického podpisu. Takže ve skutečnosti lze zašifrovat pouze hash a ne samotný dokument. V důsledku toho se výrazně zvyšuje rychlost zpracování souborů a zároveň je možné poskytnout účinnější mechanismy ochrany digitálního podpisu, protože důraz ve výpočetních operacích v tomto případě nebude kladen na zpracování původních dat, ale na zajištění kryptografické síly podpisu. Hašovací funkce také umožňuje podepisovat různé typy dat, nejen text.
Kontrola hesel
Další možnou oblastí použití hašování je organizace algoritmů ověřování hesel vytvořených za účelem omezení přístupu k určitým souborovým zdrojům. Jak lze určité typy hashovacích funkcí použít k řešení takových problémů? Velmi jednoduché.
Faktem je, že na většině serverů, ke kterým je omezen přístup, jsou hesla uložena ve formě hashovaných hodnot. To je celkem logické – pokud by hesla byla prezentována ve formě prostého textu, hackeři, kteří k nim získali přístup, mohli snadno číst tajná data. Na druhé straně není snadné vypočítat heslo na základě hashe.
Jak se ověřuje uživatelský přístup při použití dotyčných algoritmů? Heslo zadané uživatelem je porovnáno s tím, co je zaznamenáno v hashovací funkci, která je uložena na serveru. Pokud se hodnoty textových bloků shodují, uživatel získá potřebný přístup ke zdrojům.
Nejjednodušší hashovací funkci lze použít jako nástroj pro kontrolu hesla. V praxi však IT specialisté nejčastěji používají složité vícestupňové kryptografické algoritmy. Zpravidla jsou doplněny o použití standardů pro přenos dat zabezpečeným kanálem - aby hackeři nemohli zjistit nebo vypočítat heslo přenášené z počítače uživatele na servery - dříve, než je zkontrolováno proti blokům hashovaných textů.
Kolize hashovací funkce
Teorie hašovacích funkcí umožňuje takový jev, jako je kolize. Jaká je jeho podstata? Hašovací kolize je situace, kdy dva různé soubory mají stejný hašovací kód. To je možné, pokud je délka cílové sekvence znaků malá. V tomto případě bude pravděpodobnost shody hash vyšší.
Aby se předešlo kolizím, doporučuje se zejména použít duální algoritmus zvaný hašovací funkce hash. Zahrnuje tvorbu otevřeného a uzavřeného kódu. Mnoho programátorů při řešení důležitých problémů doporučuje nepoužívat hashovací funkce v případech, kdy to není nutné, a vždy otestovat odpovídající algoritmy pro nejlepší kompatibilitu s určitými klíči.
Historie vzhledu
Za zakladatele teorie hašovacích funkcí lze považovat badatele Cartera, Wegmana, Simonsona a Bierbrauera. V prvních verzích byly odpovídající algoritmy použity jako nástroje pro generování jedinečných obrazů sekvencí znaků libovolné délky s následným účelem jejich identifikace a kontroly pravosti. Na druhé straně, hash, v souladu se stanovenými kritérii, musel mít délku 30-512 bitů. Za zvláště užitečnou vlastnost odpovídajících funkcí byla považována jejich vhodnost použití jako zdroje pro rychlé vyhledávání souborů nebo jejich třídění.
Populární hashovací standardy
Podívejme se nyní, ve kterých populárních standardech mohou být hashovací funkce zastoupeny. Mezi ně patří CRC. Tento algoritmus je cyklický kód, nazývaný také kontrolní součet. Tento standard se vyznačuje jednoduchostí a zároveň univerzálností – lze s ním hashovat nejširší spektrum dat. CRC je jedním z nejběžnějších nekryptografických algoritmů.
Standardy MD4 a MD5 jsou zase široce používány v šifrování. Dalším populárním kryptografickým algoritmem je SHA-1. Zejména se vyznačuje velikostí hashe 160 bitů, která je větší než MD5 – tento standard podporuje 128 bitů. Existují ruské normy upravující používání hašovacích funkcí - GOST R 34.11-94, stejně jako GOST R 34.11-2012, které je nahradily. Lze poznamenat, že hodnota hash poskytovaná algoritmy přijatými v Ruské federaci je 256 bitů.
Dotyčné normy lze klasifikovat z různých důvodů. Existují například ty, které používají blokové a specializované algoritmy. Jednoduchost výpočtů vycházejících z prvního typu norem je často doprovázena jejich nízkou rychlostí. Proto lze jako alternativu k blokovým algoritmům použít ty, které vyžadují menší množství nutných výpočetních operací. Mezi vysokorychlostní standardy obvykle patří zejména výše zmíněné MD4, MD5 a také SHA. Podívejme se blíže na specifika speciálních hashovacích algoritmů využívajících jako příklad SHA.
Vlastnosti algoritmu SHA
Využití hašovacích funkcí založených na standardu SHA se nejčastěji provádí při vývoji nástrojů digitálního podpisu pro dokumenty DSA. Jak jsme uvedli výše, algoritmus SHA podporuje hash 160 bitů (poskytuje takzvaný „výběr“ sekvence znaků). Zpočátku uvažovaný standard rozděluje datové pole na bloky po 512 bitech. V případě potřeby, pokud délka posledního bloku nedosahuje zadané číslice, je struktura souboru doplněna o 1 a požadovaný počet nul. Na konci odpovídajícího bloku je také napsán kód, který určuje délku zprávy. Uvažovaný algoritmus používá 80 logických funkcí, jejichž prostřednictvím jsou zpracovávána 3 slova, prezentovaná ve 32 bitech. Standard SHA také umožňuje použití 4 konstant.
Porovnání hashovacích algoritmů
Podívejme se, jak korelují vlastnosti hašovacích funkcí souvisejících s různými standardy, na příkladu srovnání charakteristik ruské normy GOST R 34.11-94 a americké SHA, kterou jsme zkoumali výše. Nejprve je třeba poznamenat, že algoritmus vyvinutý v Ruské federaci předpokládá implementaci 4 šifrovacích operací za 1 cyklus. To odpovídá 128 ranám. Na druhé straně se během 1 kola při použití SHA očekává výpočet asi 20 příkazů, zatímco celkem je 80 kol. Použití SHA tedy umožňuje zpracovat 512 bitů zdrojových dat během 1 cyklu. Zatímco ruský standard je schopen provádět operace v cyklu 256 bitů dat.
Specifika nejnovějšího ruského algoritmu
Výše jsme poznamenali, že norma GOST R 34.11-94 byla nahrazena novější - GOST R 34.11-2012 „Stribog“. Pojďme prozkoumat jeho specifika podrobněji.
Pomocí tohoto standardu lze implementovat kryptografické hašovací funkce, jako v případě výše diskutovaných algoritmů. Je možné poznamenat, že nejnovější ruský standard podporuje 512bitový vstupní datový blok. Hlavní výhody GOST R 34.11-2012:
- vysoká úroveň zabezpečení proti prolomení kódů;
- spolehlivost podpořená použitím osvědčených konstrukcí;
- rychlý výpočet hashovací funkce, absence transformací v algoritmu, které komplikují návrh funkce a zpomalují výpočet.
Zmíněné výhody nového ruského kryptografického šifrovacího standardu umožňují jeho použití při organizaci toku dokumentů, které splňují nejpřísnější kritéria předepsaná v ustanoveních regulačních právních předpisů.
Specifika kryptografických hašovacích funkcí
Podívejme se blíže na to, jak lze typy algoritmů, které zkoumáme, použít v oblasti kryptografie. Klíčovým požadavkem na odpovídající funkce je odolnost proti kolizím, kterou jsme zmínili výše. To znamená, že by se neměly generovat duplicitní hodnoty hashovací funkce, pokud jsou tyto hodnoty již přítomny ve struktuře sousedního algoritmu. Kryptografické funkce musí také splňovat další kritéria uvedená výše. Je jasné, že vždy existuje nějaká teoretická možnost obnovení původního souboru na základě hashe, zvláště pokud je k dispozici výkonný výpočetní nástroj. Očekává se však, že takový scénář bude minimalizován díky spolehlivým šifrovacím algoritmům. Bude tedy velmi obtížné vypočítat hašovací funkci, pokud její výpočetní síla odpovídá vzorci 2^(n/2).
Dalším důležitým kritériem kryptografického algoritmu je změna hashe v případě opravy původního datového pole. Výše jsme poznamenali, že šifrovací standardy musí být citlivé na 1 bit. Tato vlastnost je tedy klíčovým faktorem pro zajištění spolehlivé ochrany přístupu k souborům heslem.
Iterativní schémata
Podívejme se nyní na to, jak lze sestavit kryptografické hashovací algoritmy. Mezi nejběžnější schémata řešení tohoto problému patří použití iterativního sekvenčního modelu. Je založena na použití tzv. kompresní funkce, při které je počet vstupních bitů výrazně větší než ty zachycené na výstupu.
Samozřejmě, kompresní funkce musí splňovat nezbytná kritéria kryptografické pevnosti. V interaktivním schématu je první operace pro zpracování vstupního datového toku rozdělena do bloků, jejichž velikost se počítá v bitech. Odpovídající algoritmus také používá dočasné proměnné daného počtu bitů. Jako první hodnota je použito dobře známé číslo, zatímco následující bloky dat jsou kombinovány s hodnotou příslušné funkce jako výstup. Hodnota hash se stane výstupními bity pro poslední iteraci, která bere v úvahu celý vstupní tok, včetně první hodnoty. Je zajištěn takzvaný „lavinový efekt“ hašování.
Hlavním problémem, který charakterizuje hašování implementované jako iterativní schéma, je to, že hašovací funkce se někdy obtížně konstruují, pokud vstupní proud není identický s velikostí bloku, do kterého je původní pole dat rozděleno. Ale v tomto případě může hashovací standard obsahovat algoritmy, pomocí kterých lze původní stream tak či onak rozšířit.
V některých případech mohou být v procesu zpracování dat v rámci iterativního schématu použity tzv. víceprůchodové algoritmy. Naznačují vytvoření ještě intenzivnějšího „lavinového efektu“. Takový scénář zahrnuje vytváření opakovaných datových souborů a až na druhém místě dochází k expanzi.
Blokový algoritmus
Kompresní funkce může být také založena na blokovém algoritmu, kterým se provádí šifrování. Za účelem zvýšení úrovně zabezpečení tedy můžete jako klíč použít datové bloky, které jsou předmětem hashování v aktuální iteraci, a jako vstup výsledek operací získaných během provádění kompresní funkce předtím. Výsledkem je, že poslední iterace poskytne výstup algoritmu. Bezpečnost hashování bude korelovat s robustností použitého algoritmu.
Jak jsme však uvedli výše, s ohledem na různé typy hašovacích funkcí jsou blokové algoritmy často doprovázeny potřebou použití velkého výpočetního výkonu. Pokud nejsou k dispozici, rychlost zpracování souborů nemusí být dostatečná k vyřešení praktických problémů spojených s používáním hashovacích funkcí. Požadované šifrovací síly lze zároveň dosáhnout malým počtem operací se zdrojovými datovými toky, zejména námi zvažované algoritmy – MD5, SHA a ruské šifrovací standardy – jsou přizpůsobeny řešení takových problémů.
Věřím, že mnoho lidí ví, že od roku 2007 pořádá americký Národní institut pro standardy a technologie (NIST) soutěž o vývoj hashovacího algoritmu, který nahradí SHA-1, a rodiny algoritmů SHA-2. Toto téma však bylo z nějakého důvodu na webu opomíjeno. To je vlastně to, co mě k vám přivedlo. Upozorňuji na sérii článků věnovaných hašovacím algoritmům. V této sérii společně prostudujeme základy hašovacích funkcí, zvážíme nejznámější hašovací algoritmy, ponoříme se do atmosféry soutěže SHA-3 a zvážíme algoritmy, které tvrdí, že ji vyhrají, a určitě je otestujeme. Pokud je to možné, budou zváženy také ruské hašovací standardy.
O mně
Student katedry informační bezpečnosti.O hašování
V dnešní době se téměř žádná kryptografická aplikace neobejde bez použití hashování.Hashovací funkce jsou funkce navržené ke „komprimaci“ libovolné zprávy nebo souboru dat, obvykle zapsaných v binární abecedě, do určitého bitového vzoru s pevnou délkou nazývaného konvoluce. Hashovací funkce mají různé aplikace při provádění statistických experimentů, testování logických zařízení a vytváření algoritmů pro rychlé vyhledávání a kontrolu integrity záznamů v databázích. Hlavním požadavkem na hashovací funkce je rovnoměrné rozložení jejich hodnot, když jsou hodnoty argumentů náhodně vybrány.
Kryptografická hašovací funkce je jakákoli hašovací funkce, která je kryptograficky stabilní, to znamená, že splňuje řadu požadavků specifických pro kryptografické aplikace. V kryptografii se hashovací funkce používají k řešení následujících problémů:
- budování systémů monitorování integrity dat během jejich přenosu nebo ukládání,
- ověřování zdroje dat.
Libovolná funkce se nazývá hashovací funkce h:X -> Y, snadno vypočitatelné a takové, že pro jakoukoli zprávu M význam h(M) = H (konvoluce) má pevnou délku bitu. X- sada všech zpráv, Y- množina binárních vektorů pevné délky.
Hašovací funkce jsou zpravidla budovány na základě tzv. jednokrokových kompresních funkcí y = f(x 1, x 2) dvě proměnné, kde x 1, x 2 A y- binární vektory délky m, n A n podle toho a n je délka konvoluce a m- délka bloku zpráv.
Chcete-li získat hodnotu h(M) zpráva je nejprve rozdělena na bloky délky m(zároveň, pokud délka zprávy není násobek m pak se nějakým zvláštním způsobem doplňuje poslední blok, dokud není kompletní) a poté k výsledným blokům M 1, M 2,.., M N použijte následující postupný postup pro výpočet konvoluce:
H o = v,
Hi = f(Mi,Hi-1), i = 1,.., N,
h(M) = HN
Tady proti- nějaká konstanta, často nazývaná inicializační vektor. Ona se dostane ven
z různých důvodů a může to být tajná konstanta nebo soubor náhodných dat (například vzorek data a času).
S tímto přístupem jsou vlastnosti hašovací funkce zcela určeny vlastnostmi jednokrokové kompresní funkce.
Existují dva důležité typy kryptografických hašovacích funkcí – klíčové a bezklíčové. Klíčové hašovací funkce se nazývají ověřovací kódy zpráv. Umožňují bez dalších prostředků zaručit jak správnost zdroje dat, tak integritu dat v systémech s uživateli, kteří si navzájem důvěřují.
Bezklíčové hašovací funkce se nazývají kódy detekce chyb. Umožňují zaručit integritu dat pomocí dalších prostředků (například šifrování). Tyto hashovací funkce lze použít v systémech s důvěřivými i nedůvěřivými uživateli.
O statistických vlastnostech a požadavcích
Jak jsem již řekl, hlavním požadavkem na hashovací funkce je rovnoměrné rozložení jejich hodnot, když jsou hodnoty argumentů náhodně vybrány. U kryptografických hashovacích funkcí je také důležité, že při sebemenší změně argumentu se hodnota funkce velmi změní. Tomu se říká lavinový efekt.
Funkce hašování klíčů mají následující požadavky:
- nemožnost výroby,
- nemožnost úpravy.
První požadavek znamená, že je velmi obtížné najít zprávu se správnou hodnotou sbalení. Druhým je vysoká složitost výběru pro danou zprávu se známou hodnotou konvoluce jiné zprávy se správnou hodnotou konvoluce.
Požadavky na bezklíčové funkce jsou:
- jednosměrnost,
- odolnost proti nárazům,
- odolnost vůči nalezení druhého předobrazu.
Jednosměrnost se týká vysoké obtížnosti nalezení zprávy na základě dané konvoluční hodnoty. Je třeba poznamenat, že v současné době nejsou používány žádné hashovací funkce s osvědčenou jednosměrností.
Odolnost proti kolizi se týká obtížnosti nalezení dvojice zpráv se stejnými hodnotami konvoluce. Obvykle je to objev metody pro konstrukci kolizí kryptoanalytiky, který slouží jako první signál, že algoritmus zastarává a že je třeba jej rychle nahradit.
Odolnost proti nalezení druhého předobrazu se týká obtížnosti nalezení druhé zprávy se stejnou hodnotou konvoluce pro danou zprávu se známou hodnotou konvoluce.
Toto byla teoretická část, která se nám bude hodit v budoucnu...
O populárních hashovacích algoritmech
Algoritmy CRC16/32- kontrolní součet (ne kryptografická konverze).
Algoritmy MD2/4/5/6. Jsou výtvorem Rona Rivesta, jednoho z autorů algoritmu RSA.
Algoritmus MD5 byl kdysi velmi populární, ale první předpoklady pro hacking se objevily na konci devadesátých let a nyní jeho obliba rapidně klesá.
Algoritmus MD6 je z konstrukčního hlediska velmi zajímavý algoritmus. Byl nominován do soutěže SHA-3, ale bohužel jej autoři nestihli uvést do standardu a tento algoritmus není na seznamu kandidátů, kteří postoupili do druhého kola.
Algoritmy pravítka SHA Algoritmy, které jsou dnes široce používány. Dochází k aktivnímu přechodu ze standardů verze SHA-1 na SHA-2. SHA-2 je souhrnný název pro algoritmy SHA224, SHA256, SHA384 a SHA512. SHA224 a SHA384 jsou v podstatě analogy SHA256 a SHA512, pouze po výpočtu konvoluce jsou některé informace v ní zahozeny. Měly by být používány pouze pro zajištění kompatibility s vybavením starších modelů.
ruský standard - GOST 34.11-94.
V dalším článku
Přehled MD algoritmů (MD4, MD5, MD6).
Literatura
A. P. Alferov, Základy kryptografie.
Bruce Schneier, aplikovaná kryptografie.
Co je to hash? Hašovací funkce je matematická transformace informace do krátkého řetězce specifické délky.
Proč je to nutné? Analýza pomocí hašovacích funkcí se často používá ke sledování integrity důležitých souborů operačního systému, důležitých programů a důležitých dat. Kontrolu lze provádět podle potřeby nebo pravidelně.
Jak se to dělá? Nejprve určete integritu souborů, které je třeba monitorovat. Pro každý soubor se pomocí speciálního algoritmu vypočítá jeho hash hodnota a výsledek se uloží. Po požadované době se provede podobný výpočet a výsledky se porovnají. Pokud se hodnoty liší, informace obsažené v souboru byly změněny.
Jaké vlastnosti by měla mít hashovací funkce?
- musí být schopen provádět libovolnou konverzi dat na pevnou délku;
- musí mít otevřený algoritmus, aby bylo možné prozkoumat jeho kryptografickou sílu;
- musí být jednostranné, to znamená, že by na základě výsledku nemělo být matematicky možné určit výchozí údaje;
- musí „odolat“ kolizím, to znamená, že nesmí produkovat stejné hodnoty pro různá vstupní data;
- by neměly vyžadovat velké výpočetní zdroje;
- při sebemenší změně vstupních dat by se měl výsledek výrazně změnit.
Jaké jsou oblíbené hashovací algoritmy? V současné době se používají následující hashovací funkce:
- CRC – kód cyklické redundance nebo kontrolní součet. Algoritmus je velmi jednoduchý a má velké množství variací v závislosti na požadované délce výstupu. Ne kryptografická!
- MD 5 je velmi populární algoritmus. Stejně jako předchozí verze je MD 4 kryptografická funkce. Velikost hashe je 128 bitů.
- SHA -1 je také velmi oblíbená kryptografická funkce. Velikost hashe je 160 bitů.
- GOST R 34.11-94 je ruský kryptografický standard pro výpočty hašovacích funkcí. Velikost hashe je 256 bitů.
Kdy může správce systému použít tyto algoritmy?Často při stahování jakéhokoli obsahu, například programů z webových stránek výrobce, hudby, filmů nebo jiných informací, existuje hodnota kontrolních součtů vypočtená pomocí určitého algoritmu. Z bezpečnostních důvodů musíte po stažení nezávisle vypočítat hashovací funkci a porovnat hodnotu s tím, co je uvedeno na webu nebo v příloze k souboru. Už jsi to někdy dělal?
Co je pro výpočet hashe pohodlnější? Nyní existuje velké množství podobných nástrojů, placených i bezplatných. Osobně se mi líbil HashTab. Za prvé, během instalace je nástroj zabudován jako karta ve vlastnostech souboru, za druhé vám umožňuje vybrat velké množství hashovacích algoritmů a za třetí je zdarma pro soukromé nekomerční použití.
co je to ruština? Jak bylo uvedeno výše, v Rusku existuje hashovací standard GOST R 34.11-94, který je široce používán mnoha výrobci nástrojů pro bezpečnost informací. Jedním z těchto nástrojů je program pro opravu a sledování počátečního stavu softwarového balíku FIX. Tento program je prostředkem ke sledování efektivity využívání informační bezpečnosti.
OPRAVA (verze 2.0.1) pro Windows 9x/NT/2000/XP
- Výpočet kontrolních součtů zadaných souborů pomocí jednoho z 5 implementovaných algoritmů.
- Fixace a následné sledování výchozího stavu softwarového balíku.
- Porovnání verzí softwarových balíků.
- Fixace a kontrola adresářů.
- Sledování změn v zadaných souborech (adresářích).
- Generování reportů ve formátech TXT, HTML, SV.
- Výrobek má do 1.6.2013 certifikát FSTEC pro NDV 3 č. 913.
A co digitální podpis? Výsledek výpočtu hashovací funkce spolu s tajným klíčem uživatele jde na vstup kryptografického algoritmu, kde je vypočítán elektronický digitální podpis. Přísně vzato, hashovací funkce není součástí algoritmu digitálního podpisu, ale často se tak děje záměrně, aby se vyloučil útok pomocí veřejného klíče.
V současné době mnoho aplikací pro e-commerce umožňuje uložit tajný klíč uživatele v oblasti soukromého tokenu (ruToken, eToken), aniž by bylo technicky možné jej odtud získat. Samotný token má velmi omezenou paměťovou oblast, měřenou v kilobajtech. Chcete-li podepsat dokument, neexistuje způsob, jak přenést dokument do samotného tokenu, ale je velmi jednoduché přenést hash dokumentu do tokenu a jako výsledek získat elektronický digitální podpis.
