N-hash

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. ledna 2015; ověření vyžaduje 21 úprav .

N-hash
Vytvořeno	1990
zveřejněno	1990
Velikost hash	128 bit
Počet kol	12 nebo 15
Typ	hashovací funkce

N-Hash je kryptografická hašovací funkce založená na cyklické funkci FEAL . V současnosti považován za nejistý [1] .

Byl vyvinut v roce 1990 společností Nippon Telegraph and Telephone (která také vyvinula FEAL).

Původně měla funkce N-Hash vyřešit problém záměny informací na cestě mezi dvěma telefonními uživateli (Nippon Telegraph a Telephone - telekomunikační společnost) a urychlit načítání dat. Pokud například osoba odešle SMS zprávu, bude před doručením zkontrolována její pravost pomocí hashovací funkce. A pokud uživatel produktů Nippon Telegraph a Telephone potřebuje rychle najít něčí kontakt v telefonu, pak použití N-Hash může zjednodušit proces hledání jména v seznamu. To je způsobeno tím, že první písmeno kontaktu je deklarováno jako hash kód (malá definující část kontaktu) jména.

Origins

Algoritmus N-Hash je založen na blokovém šifrovacím algoritmu FEAL . Největší telekomunikační společnost Nippon Telegraph and Telephone vytvořila FEAL na základě DES . Ale ačkoli tento algoritmus překonává DES v rychlosti, je velmi nespolehlivý a snadno zranitelný: kryptoanalytik potřeboval k prolomení algoritmu velmi málo informací. Bylo to hackování algoritmu FEAL, které vedlo v roce 1990 ke vzniku hashovací funkce N-Hash. N-Hash je také rychlejší než DES: ve srovnání s 9Kbps DES běží N-Hash rychlostí 24Kbps pro 15kolové schéma a 29Kbps pro 12kolové schéma. Nippon Telegraph and Telephone zároveň dosáhly zvýšení spolehlivosti oproti FEAL [1] .

Algoritmus N-Hash byl nějakou dobu používán společností Nippon Telegraph and Telephone v souladu s cíli této funkce, ale po chvíli byla vyvinuta narozeninová metoda , která tento algoritmus snadno prolomila. V souvislosti s hackem byl opuštěn nejen N-Hash, ale téměř všechny funkce založené na blokových šifrách, protože všechny mají stejný problém: jsou snadno zranitelné vůči narozeninové metodě. Místo toho nyní používají spolehlivější funkce založené na technologiích MD: MD5 , SHA-1 a další uvedené v seznamu funkcí, které jsou v současnosti považovány za spolehlivé (podle normy ISO / IEC 10118).

Použití

Funkce N-Hash se používala krátce na začátku 90. let, dokud nebyla prolomena narozeninovou metodou.

N-Hash byl určen k vyřešení problému falšování dat:
- Pro moderního člověka lze tento problém snadno popsat na příkladu interakce mezi člověkem a internetovým obchodem . Když si uživatel objedná produkt v internetovém obchodě, obchod mu zašle číslo objednávky, částku platby atd. Dále, když se uživatel pokusí zaplatit za objednávku například pomocí Webmoney , Webmoney vypočítá hash kód přijatého zprávu a porovná ji s hash kódem přijatým z internetového obchodu. Pokud se tyto hash kódy shodují, pak jsou informace zaslané uživatelem pravdivé. Pokud se neshodují, je informace určena jako nepravdivá a platba neproběhne.
Další případ použití je jednoduchý: seřaďte své kontakty na svém mobilním telefonu podle abecedy a vyhledejte kontakt podle prvního písmene. První písmeno tohoto jména je vybráno jako hash kód jména, takže když osoba stiskne určité písmeno ve svém telefonu, vyhledá se hash kód, který odpovídá tomuto písmenu, a na obrazovce se zobrazí kontakty, které na něj začínají.

Vlastnosti N-Hash

Jednosměrný

Definice: Nechť je zpráva nějaké délky. $M$

Funkce se nazývá jednosměrná, jestliže z rovnosti $H$ $h=H(M)$

snadno:

najít hash kód s vědomím zprávy $h$ $M$

velmi pracné:

najít zprávu pomocí známého hash kódu (tj. pokud hacker zná hashovací kód hesla , pak pomocí něj heslo nenajde); $M$ $h$
najít zprávu odlišnou od , tak, aby se jejich hash kódy shodovaly. $M$ $M'$ $H(M')=H(M)$

Jednodušší definici lze napsat takto:

Jednosměrnost je " otisk prstu ":

Pokud je uvedena konkrétní osoba, můžete jí sejmout otisk prstu;
Není možné najít osobu podle otisku prstu (pokud neexistuje databáze s otisky všech lidí, ale žádná neexistuje);
Je nemožné najít druhého člověka se stejným otiskem prstu jako ten druhý.

Jednosměrnost řeší velmi důležitý problém. Zvažme to na příkladu.

Alice a Bob tradičně označují předměty přenosu informací. Příklady

Řekněme, že Alice podepsala smlouvu s hash kódem, který Alice a Bob znali . Pokud by to nebylo jednosměrné, pak by Bob mohl najít tak odlišnou smlouvu , která by mohla tvrdit, že Alice podepsala . $M$ $h=H(M)$ $H$ $M'$ $H(M')=H(M)$ $M'$
Předpokládejme, že Alice má stejný otisk prstu h s nějakým zločincem, pak by Bob mohl tvrdit, že tento zločinec je Alice.

Odolnost proti kolizi

Aby Alice nepoužila „narozeninovou“ metodu k oklamání Boba, je velmi vhodné zavést ještě silnější podmínku, než je jednosměrná podmínka. H je takové, že je obtížné najít zprávy a , takže jejich hash kódy se shodují. To znamená, že je nemožné najít dva lidi se stejnými otisky prstů. $M$ $M'$ $H(M)=H(M')$

Tato podmínka se nazývá odolnost proti kolizi a neplatí pro hashovací funkci N-Hash.

Kvůli nestabilitě kolize může Alice oklamat Boba tímto způsobem (metoda "narozeniny"):

Alice píše dvě verze smlouvy: jedna je pro Boba výhodná a druhá ne;
Provedením malých změn v každé smlouvě (například mezera je nahrazena dvěma mezerami) zajistí, že existuje dostatek verzí smluv k výběru a pro které se hash kódy shodují (verze je výhodná pro Boba, ale ne) (pokud má smlouva 34 řádků, pak provedením nebo neprovedením změn na každém z řádků je snadné získat verze smluv); $M$ $M'$ $M$ $M'$ $2^{{34}}$
Nyní může Alice dokázat, že Bob podepsal . $M'$

Aby k takovému problému nedošlo, stačí provést kosmetické úpravy podepsané smlouvy. A i když tato akce nijak nemění hashovací funkci H, a tudíž nijak neovlivňuje její odolnost vůči kolizím, touto akcí však osoba obdrží novou verzi smlouvy, jejíž hash kód neodpovídá hash kódu verze smlouvy útočníka. To znamená, že pokud Bob na 5. řádku někde vloží čárku nebo dvě tečky místo jedné, pak Alice nebude schopna prokázat, že podepsal další smlouvu (protože jeho hash kód již neodpovídá hash kódu Alicině smlouvě).

Můžete si vzít příklad z reálného života: když notář orazítkuje podepsanou smlouvu, provede tam kosmetické změny.

Branky N-Hash

Abyste porozuměli tomu, jak funkce N-Hash funguje, musíte přejít na více vědeckou řeč. Níže jsou uvedeny cíle této funkce, nikoli na příkladech, ale podle toho, jak jsou implementovány a s příslušnou terminologií .

Zajištění integrity informací [1] :

Tato vlastnost je nezbytná pro vyloučení možnosti útočníka vložit do původní zprávy nějaké nepravdivé informace. Pro zajištění integrity musí být možné detekovat jakékoli změny v textu zprávy (nahrazení, vložení, smazání). Integrita je zajištěna zavedením redundantních informací do původní zprávy, která bude testovací kombinací. Tato kombinace se nazývá kontrolní součet a lze ji vypočítat pomocí speciálního algoritmu. Protože tento algoritmus závisí na tajném klíči , je nepravděpodobné , že by do zprávy byly vloženy falešné informace .

$M_{new}=M+''salt''$ , kde salt je redundantní informace, M je zpráva - kontrolní součet; $H(salt)=S$

Ze vzorce vyplývá, že pokud se změní sůl, změní se i S (kontrolní součet), což znamená, že obojí a změněno . $M_{new}$ $M$

To znamená, že můžeme dojít k závěru, že byly přidány nepravdivé informace.

Komprese dokumentu :

Funkce N-Hash pracuje s M zprávami libovolné délky. V tomto případě je výstupem hash kód pevné délky 128 bitů. Toho je dosaženo díky skutečnosti, že zpráva je rozdělena do bloků o velikosti 128 bitů a algoritmus pracuje sekvenčně s každým z bloků. $M_{i}$

Zajištění spolehlivosti elektronických dat [1] :

Tato vlastnost platí pro jednosměrné funkce, což je N-Hash. Spolehlivost zprávy M je kontrolována dvojím nalezením konečného hash kódu (message digest) (odesílající a přijímající strany). Výsledky se porovnávají a pokud se shodují, pak jsou informace spolehlivé. Bezúhonnost nezaručuje platnost .

Zajištění soukromí :

na stránkách, kde je třeba zadat přihlašovací jméno a heslo , je heslo po zadání přeloženo do hash kódu. To znamená, že zpočátku uživatel zadá heslo M, ale pro vstup do chráněné oblasti se použije hash kód . Pomocí známého hash kódu h a funkce H je velmi obtížné vypočítat M, což zajišťuje důvěrnost hesla. $h=H(M)$

Ověření uživatele :

Autentizace je postup pro ověření uživatele nebo dat pomocí určitých kritérií.

Nabízí se otázka, jak hashovací funkce zajišťuje pravdivost autentizace. To lze snadno ukázat na příkladu.

Když uživatel zadá uživatelské jméno a heslo na jakékoli stránce , jeho heslo se převede na hash kód a přenese se přes síť k ověření. K přihlášení pod cizím účtem samozřejmě stačí zjistit hash kód hesla a poté pomocí vzorce (h-hash code, M - password) heslo najít. Ale N-Hash, což je jednosměrná funkce, zajišťuje bezpečnost hesla, protože řešení této rovnice pro jednosměrné funkce je velmi pracné (bez použití osobního počítače). $h=H(M)$

Algoritmus

Algoritmus N-Hash je založen na cyklickém opakování (12 nebo 15krát - počet kol) operací. Na vstupu je hašovací kód a může být libovolný, výstupem je hašovací kód h zprávy M , který je nutné hašovat. Velikost odchozího hash kódu je pevná a rovná se 128 bitům, přičemž velikost M je libovolná [2] . ${\displaystyle h_{0))$

Základní označení

$M$ — zpráva, která má být hašována;
$M_{i}$ — blok zpráv o délce 128 bitů. Aby bylo možné zprávu hashovat , je nutné ji rozdělit do bloků ; $M$ $M_{i}$
$Ahoj}}$ — hash kód i-tého kroku;
$\nu=1010...1010$ — konstantní, 128 bitů dlouhá;
$||$ - zřetězení ;
${\displaystyle V_{j}=\delta ||A_{j1}||\delta ||A_{j2}||\delta ||A_{j3}||\delta ||A_{j4))$ kde k=1, 2, 3, 4; , délka 24 bitů; $A_{jk}=4*(j-1)+k$ $\delta =00..00$
EXG - funkce, která prohodí vysoké a nízké bity (64 nízkých a 64 vysokých);
PS - transformační funkce;

Popis algoritmu

Diagram vpravo ukazuje schematická označení operací, která jsou přítomna v následujících diagramech.

Souřadnicové (párové) sčítání znamená sčítání modulo 2 ;
Je-li x vstupem funkce f , pak výstupem je f(x) .

Jeden N-Hash cyklus

Níže je jeden cyklus N-Hash algoritmu.

Vstupem funkce g je hash kód (i-1)-tého kroku a i-tého bloku zpráv . V tomto případě se volí libovolně: například může být nula. A také se přivádí na výstup pro operaci sčítání modulo 2, to znamená, že výsledek (hašovací kód dalšího kroku) bude vypadat takto: ( zatím něco neznámého ). $h_{{i-1}}$ $M_{i}$ ${\displaystyle h_{0))$ $h_{{i-1}}$ $h_{i-1}\oplus$
Z diagramu je vidět, že se přivádí nejen na XOR , ale i na výstup operace sčítání modulo 2. To znamená, že nyní v souladu s prvním odstavcem výsledek vypadá takto: ( něco, co zůstává zatím neznámý ). $M_{i}$ $h_{i-1}\oplus M_{i}$

Zbývající neznámé něco se najde po průchodu kaskádou osmi transformačních funkcí. Jeho získání lze popsat takto:

Funkce EXG zamění vysoké a nízké číslice a přidá k výsledku , poté se k výsledku přidá modulo 2 s . $h_{{i-1}}$ $\nu$ $M_{i}$
Jak je vidět z diagramu, výsledek je postupně přiváděn na vstupy j transformačních funkcí, jejichž druhým argumentem je součet , kde j=1, ... , 8. ${\displaystyle h_{i-1}\oplus V_{j))$
Výsledkem je hash kód i-tého kroku : $Ahoj}}$

${\displaystyle h_{i}=M_{i}\oplus g(M_{i},h_{i-1})\oplus h_{i-1))$ .

Transformační funkce

Vyvstává otázka, jak funguje transformační funkce . $PS(X,P)$

Zvažte horní část okruhu k zaměřovacímu kříži.

Původní zpráva je rozdělena do bloků bitů. $X$ $128/4=32$

Mezivýstupy budeme považovat za vstupy do spodní části obvodu. a jsou přiváděny na mezivýstupy , zatímco operace a jsou přiváděny na další dva výstupy . Nyní je možné přeznačit výsledky na mezivýstupech a jejich prostřednictvím, podobně jako v horní části, najít výsledky na výstupu spodní části, tedy celého obvodu jako celku. $X_{1}$ $X_{2}$ ${\displaystyle f(X_{1},P_{1})\oplus X_{2}\oplus X_{4))$ ${\displaystyle f[f(X_{1},P_{1})\oplus X_{2},P_{2}]\oplus X_{1}\oplus X_{3))$

Po provedení všech nezbytných výpočtů dostaneme, že když je aplikováno na vstup , výstupní zpráva může být reprezentována jako zřetězení zpráv ${X=X_{1}\paralelní X_{2}\paralelní X_{3}\paralelní X_{4}}$ ${Y=Y_{1}\paralelní Y_{2}\paralelní Y_{3}\paralelní Y_{4}}$

${\displaystyle {Y_{4}=X_{2}\oplus X_{4}\oplus f(X_{1},P_{1)))))$ ;
${Y_{3}=f[f(X_{1},P_{1})\oplus X_{2},P_{2}]\oplus X_{1}\oplus X_{3))$ ;
${\displaystyle {Y_{2}=X_{2}\oplus Y_{4}\oplus f(Y_{3},P_{3)))))$ ;
${Y_{1}=f[f(Y_{3},P_{3})\oplus Y_{4},P_{4}]\oplus X_{1}\oplus Y_{3))$ .

Nalezení funkce f(x, P)

Protože funkce f pracuje s argumenty, jejichž délka je 32 bitů, pak z vyhledávacího schématu funkce f(x, P) máme:

Hodnota je rozdělena na části po 8 bitech. $x\oplus P$
Zapišme tyto části jako , i=1,…,4 a zavedeme nový zápis: $x_{i}\oplus P_{i}$
- ${Z_{1}=x_{1}\oplus P_{1))$ ;
- ${Z_{2}=x_{2}\oplus P_{2))$ ;
- ${Z_{3}=x_{3}\oplus P_{3))$ ;
- ${Z_{4}=x_{4}\oplus P_{4))$ ;

Argumenty funkce (první šipka zleva) jsou a . ${S_{0))$ ${\displaystyle Z_{1))$ ${S_{1}[Z_{1}\oplus Z_{2},Z_{3}\oplus Z_{4}]}$

Argumenty funkce (druhá šipka zleva) jsou a . ${S_{1))$ ${Z_{1}\oplus Z_{2}}$ ${Z_{3}\oplus Z_{4}}$

To znamená, že dvě složky výstupní zprávy jsou již známé a stejné

- ${A_{1}=S_{0}(Z_{1},S_{1}[Z_{1}\oplus Z_{2},Z_{3}\oplus Z_{4}])}$ ;
- ${A_{2}=S_{1}[Z_{1}\oplus Z_{2},Z_{3}\oplus Z_{4}]}$ ;

Dále použijeme již přijaté odcházející části zprávy na výstupu pro usnadnění zápisu:

- ${A_{3}=S_{0}[Z_{3}\oplus Z_{4},A_{2}]}$ ;
- ${~A_{4}=S_{1}[Z_{4},A_{3}]}$ ;

Potom může být výstupní zpráva reprezentována jako . ${A=A_{1}||A_{2}||A_{3}||A_{4))$

A to se ví
- ${S_{0))$ =( levá 2bitová rotace )(a+b) mod 256
- ${S_{1))$ =( 2bitové otáčení doleva )(a+b+1) mod 256

Zabezpečení hašovacích funkcí

Hašovací funkce je bezpečná , když kryptoanalytik potřebuje mnoho informací k prolomení hashe (takže je nepravděpodobné, že by prolomil) a pokud hash dosud nebyl prolomen [3] .

Aby byla hašovací funkce bezpečná, musí být splněny následující podmínky:

Se změnami v textu zprávy (vložení, permutace atd.) by se měl změnit i hash kód zprávy; $M$

Jinak by se člověk, který zadá své uživatelské jméno a heslo pro vstup na Wikipedii , mohl dostat na stránku jiného účastníka.

Nemožnost najít zprávu pomocí známého hash kódu z ; $M$ $h$ $h=H(M)$

Pokud tato podmínka není splněna, pak umožňuje zjistit hesla uživatelů Wikipedie.

Úkol najít zprávy a takové, aby jejich hash kódy byly stejné, musí být velmi časově náročné. $M_{{1}}$ $M_{{2}}$ ${\displaystyle h_{1}=h_{2))$

Jinak by bylo možné najít dvě hesla se stejnými hash kódy.

N-Hash není bezpečná funkce, protože pro ni není splněna poslední podmínka.

Kryptoanalýza N-Hash

N-Hash je v současnosti považován za nezabezpečenou funkci. Tento obrázek uvádí všechny zabezpečené jednosměrné funkce v současnosti podle ISO/IEC 10118 [1] :

Z algoritmů vytvořených jako N-Hash založených na blokových šifrách jsou za bezpečné považovány pouze MDC-2 a MDC-4 .

N-Hash se vyznačuje následujícím problémem:

Vzhledem k tomu, že délka hash kódu je rovna délce bloku šifrovacího algoritmu, je algoritmus nestabilní proti narozeninovému útoku .

Útoky na hashovací funkce

Tento obrázek ukazuje klasifikaci útoků na všechny hashovací algoritmy obecně.

Algoritmově závislé útoky jsou útoky založené na vlastnostech konkrétního algoritmu.

Například N-Hash byl úspěšně napaden pomocí diferenciální metody , útoku s pevným bodem a setkání uprostřed .

Algoritmicky nezávislé útoky lze aplikovat na jakoukoli hashovací funkci, ale to nevylučuje skutečnost, že pro některé algoritmy jsou velmi časově náročné kvůli velkému množství informací nebo rychlosti kódu.

Efektivní útoky na N-Hash

Útoky založené na algoritmech Diferenciální metoda

Den Boer navrhl metodu pro konstrukci kolize pro jednokolové N-Hash schéma.

Biham a Shamir úspěšně použili diferenciální kryptoanalýzu ke kompromitaci 6-kolového N-Hash schématu. Metoda, kterou navrhli pro konstrukci kolize , funguje pro jakoukoli hodnotu N, která je násobkem tří, a zároveň se pro N ≤ 12 ukazuje jako efektivnější než přístup založený na narozeninovém paradoxu .

Pro 12kolové schéma je složitost konstrukce kolizí navrhovanou metodou odhadována na 256 operací (složitost metody založené na narozeninovém paradoxu je 264 operací).

Algoritmově nezávislé útoky

Zvětšení délky hash kódu a tajného klíče zkomplikuje práci kryptoanalytika. Můžete se pokusit udělat výpočty příliš časově náročné pro osobní počítač a vyžadovat velké zdroje. Pak bude muset kryptoanalytik buď hledat superpočítač, nebo napsat virus, který na základě paralelizace procesu prolomení hashovací funkce použije k řešení problému několik osobních počítačů najednou [3] .

Následující metody ochrany hashovací funkce [4] jsou také účinné :

použití kontrolních součtů v různých fázích hašování;
ověřování správnosti informací;
vložit do zprávy informace typu salt .

Výsledky

V současné době není N-Hash široce používán, protože není bezpečný a byl hacknut před více než 10 lety.
Nyní existuje speciální název pro hašovací funkce, jako je N-Hash - key , tedy jednosměrný, ale ne odolný proti kolizi:
- Pokud si strany navzájem důvěřují (tedy každá ze stran má jistotu, že ta druhá nenahradí smlouvu, jako v případě Alice a Boba), lze N-Hash použít.

Porovnání N-Hash s jinými hašovacími funkcemi

Algoritmus	Délka hodnoty hash	Rychlost šifrování (KB/s)
Simultánní Davies-Meyerův okruh (s IDEA )	128	22
Davies-Meyer (s DES)	64	9
Hashovací funkce GOST	256	jedenáct
HAVAL (3 sady)	variabilní	168
HAVAL (4 sady)	variabilní	118
HAVAL (5 sad)	variabilní	98
MD2	128	23
MD4	128	236
MD5	128	174
N-Hash (12 fází)	128	29
N-Hash (15 fází)	128	24
RIPE-MD	128	182
SHA-1	160	75
Snefru (4 průchody)	128	48
Snefru (8 sad)	128	23

Poznámky

↑ 1 2 3 4 5 Hashovací funkce (nepřístupný odkaz - historie ) . Cryptomash. Staženo: 27. listopadu 2008. (neurčitý) (nepřístupný odkaz)
↑ Bruce Schneier. Kapitola 18. Jednosměrné hashovací funkce // Aplikovaná kryptografie . - 2. vyd. Archivováno 28. února 2014 na Wayback Machine
↑ 1 2 Hlavní problém kryptografie // CIO: journal. - 17. května 2005. - č. 5 . Archivováno z originálu 29. května 2008.
↑ Kryptoanalýza hashovacích funkcí (nepřístupný odkaz- historie ) . Cryptomash. Staženo: 27. listopadu 2008. (neurčitý) (nepřístupný odkaz)

Viz také

Odkazy

Literatura

A. Ščerbakov, A. Domašev. Aplikovaná kryptografie. - M .: Ruské vydání, 2003. - 404 s. — ISBN 5-7502-0215-1 .
Bruce Schneier. Aplikovaná kryptografie. - 2. vyd. - M .: Triumph, 2002. - 816 s.

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA