Kriptográfiai hash függvény

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. május 11-én felülvizsgált verziótól ; az ellenőrzések 58 szerkesztést igényelnek .

A kriptográfiai hash függvények a kivonatoló függvények külön osztálya , amelyek bizonyos tulajdonságokkal rendelkeznek, amelyek alkalmassá teszik őket a kriptográfiában való használatra .

Építési alapelvek

Iteratív szekvenciális áramkör

Általános esetben a hash függvény felépítése egy iteratív szekvenciális sémán alapul. Az algoritmus magja egy tömörítési függvény , amely k bemenetet n kimeneti bitre konvertál , ahol n a hash függvény hossza, k pedig tetszőleges n -nél nagyobb szám . Ebben az esetben a tömörítési függvénynek meg kell felelnie a kriptográfiai erősség minden feltételének .

A bemeneti adatfolyam ( k − n ) bites blokkokra van felosztva . Az algoritmus egy n bites ideiglenes változót használ, melynek kezdeti értéke valamilyen jól ismert szám. Minden következő adatblokk kombinálva van a zsugorító függvény kimeneti értékével az előző iterációnál. A hash függvény értéke az utolsó iteráció kimeneti n bitje. A hash függvény kimeneti értékének minden bitje a teljes bemeneti adatfolyamtól és a kezdeti értéktől függ. Így lavinahatás érhető el .

Ha egy iteratív séma alapján hash függvényeket tervezünk, akkor a bemeneti adatfolyam méretével van probléma. A bemeneti adatfolyam méretének ( k-n ) többszörösének kell lennie . Általános szabály, hogy az algoritmus elindítása előtt az adatokat valamilyen előre ismert módon bővítik.

Az egymenetes algoritmusok mellett léteznek többmenetes algoritmusok, amelyekben a lavinahatás tovább fokozódik. Ebben az esetben az adatokat először megismétlik, majd a kívánt méretre bővítik.

A szimmetrikus blokk algoritmuson alapuló összehúzó függvény

A szimmetrikus blokk titkosítási algoritmus használható tömörítési függvényként . A nagyobb biztonság érdekében kulcsként használhatja a kivonatolásra szánt adatblokkot ebben az iterációban, és bemenetként az előző tömörítési függvény eredményét. Ekkor az utolsó iteráció eredménye lesz az algoritmus kimenete. Ilyen esetben a hash függvény biztonsága az alkalmazott algoritmus biztonságán alapul.

Általában egy hash függvény felépítésénél egy bonyolultabb rendszert használnak. A szimmetrikus blokk-titkosítási algoritmus általánosított sémája az ábrán látható. 2.

Így 64 opciót kapunk a kontrakciós függvény felépítésére. A legtöbbjük vagy triviális, vagy nem biztonságos. Az alábbiakban felsoroljuk a négy legbiztonságosabb sémát minden típusú támadáshoz.

A blokk algoritmusok alapján tervezett hash függvények fő hátránya az alacsony sebesség. A szükséges kriptográfiai erősség a bemeneti adatokon végzett kisebb számú művelettel is elérhető. Vannak gyorsabb kivonatolási algoritmusok, amelyeket saját maga tervezett, a semmiből, a kriptográfiai erősség követelményei alapján. Ezek közül a leggyakoribb az MD5 , SHA-1 , SHA-2 .

Követelmények

A kriptográfiai hash függvények követelményei a következők:

1. Első előkép keresési ellenállása : Adott egy hash , nehéz lehet olyan üzenetet találni , amely . Ez a tulajdonság az egyirányú függvény fogalmához kapcsolódik . Azok a funkciók, amelyek nem rendelkeznek ezzel a tulajdonsággal, sebezhetőek az első preimage támadásokkal szemben . $h$ $m$ $h=hash(m)$

2. Ellenállás a második előkép keresésével szemben : adott üzenet esetén nehéznek kell lennie egy másik üzenetet találni (nem egyenlő a -val ), hogy . Ezt a tulajdonságot néha gyenge ütközésállóságnak is nevezik. Azok a funkciók, amelyek nem rendelkeznek ezzel a tulajdonsággal, ki vannak téve a második előkép-keresési támadásoknak. $m_1$ $m_2$ $m_1$ $hash(m_{1})=hash(m_{2})$

3. Ütközésekkel szembeni ellenállás

A hash függvény ütközése egy értékpár és ′, ′, amelyre . Mivel a lehetséges nyílt szövegek száma nagyobb, mint a konvolúció lehetséges értékeinek száma, akkor néhány konvolúcióhoz sok előkép létezik, és ezért a hash függvények ütközései szükségszerűen léteznek. Legyen például a hash előkép hossza 6 bit, a konvolúció hossza pedig 4 bit. Ekkor a különböző hajtások száma , a hash előképek száma pedig , azaz 4-szer több, ami azt jelenti, hogy az összes hajtásból legalább egy 4 előképnek felel meg. $m$ $m$ $m\neq m$ $H(m)=H(m')$ $2^{4}=16$ $2^6=64$

A hash függvény ütközésekkel szembeni ellenállása azt jelenti, hogy nincs hatékony polinomiális algoritmus az ütközések megtalálására.

Ezek a tulajdonságok nem függetlenek:

Az invertálható függvény instabil a második előkép és az ütközések helyreállításához.
Az a funkció, amely nem ellenáll a második előkép visszaállításának, nem ellenáll az ütközéseknek; fordítva nem igaz.
A funkció ütközésálló, második előképálló.
Az ütközésálló hash függvény nem feltétlenül egyirányú.

A kriptográfia számára fontos, hogy a hash értékek sokat változzanak az argumentum legkisebb változásával ( lavinahatás ). A hash érték nem szivároghat ki információt még az argumentum egyes bitjeiről sem.

A modern orosz GOST R 34.11-2012 (Stribog) szabvány kidolgozásakor a következő követelményeket fogalmazták meg a kriptográfiai hash függvényekre:

Az előkép kiszámításának nehézsége: ha a függvény értéke ismert, akkor nehéz lehet olyan üzenetet találni, amelynek hash függvénye megegyezik az ismertével;
A második előkép számításának biztonsága: legyen egy érték, és ennek az értéknek a hash kódja ismert. Ekkor a támadónak nehéznek kell lennie másik ilyen értéket találnia, hogy a hash függvénye egybeessen az első érték hash függvényével;
Nehézségek az ütközések megtalálásában: nehéznek kell lennie két olyan üzenet megtalálása, amelyek nem egyenlőek, de azonos hash kódokkal rendelkeznek;
Ellenállás az előkép meghosszabbításával szemben: ha a támadó nem ismeri az üzenetet, de tudja a hosszát és a hash kódot, akkor nehéz lehet olyan üzenetet felvennie, amely az eredetihez hozzáadva valamilyen ismert hash függvényt ad. . Más szóval, a támadónak nem szabadna megtörténnie, hogy megváltoztasson valamit azáltal, hogy hozzáadja az üzenetet, miközben megismeri a kimenetet. Ez másképp is megfogalmazható: a hash függvényt nem kell jól "kitömni".

4. Álvéletlenség : Nehéz lehet megkülönböztetni a hash-alapú pszeudo-véletlenszám-generátort a véletlenszám-generátortól, például átmegy a szokásos véletlenszerűségi teszteken .

Bizonyíthatóan biztonságos hash függvények

A hash függvény biztonságát valamilyen matematikai probléma összetettsége biztosíthatja, feltéve, hogy bizonyíték van arra, hogy a követelmények megsértését célzó támadások éppoly nehézkesek, mint e probléma megoldása. [egy]

Egy kriptográfiai hash függvény bizonyíthatóan ütközésbiztos, ha az ütközések megtalálásának problémája polinomiális időben közvetíthető egy polinomidőben megoldhatatlannak tekintett feladatból . Más szóval, ha az algoritmus lehetővé tenné a polinomiális időben történő ütközések megtalálásának problémáját, ha létezik olyan redukáló algoritmus , amely polinomiális időben is működik, akkor az utóbbi lehetővé tenné, hogy az algoritmus polinomiális időben oldja meg a problémát , ami ellentmond annak összetettségének. , ami azt jelenti, hogy az ütközések megtalálásának problémája nem egyszerűbb, mint a feladat . $P$ $A$ $R$ $A$ $P$ $P$

Az első és második előkép keresésével szembeni bizonyítható biztonságot hasonlóképpen határozzuk meg.

A második előkép keresésével szembeni ellenállás az ütközésekkel szembeni bizonyított ellenállásból következik, ezért a gyakorlatban néha csak az első előkép megtalálásával szembeni ellenállás és az ütközésekkel szembeni ellenállás igazolódik elméletileg. [2]

Néhány olyan probléma, amelyek polinomiális időben megoldhatatlanok, és amelyek felhasználhatók ilyen függvények létrehozására:

A bizonyítékokon alapuló megközelítés hátrányai

A komplexitás elméleti garanciái mellett a bizonyítékokon alapuló megközelítésnek jelentős hátrányai is vannak:

A jelenlegi bizonyíthatóan biztonságos kivonatolási algoritmusok számításilag túl bonyolultak ahhoz, hogy a gyakorlatban használhatók legyenek. A hagyományos hash függvényekhez képest meglehetősen lassúak.
A bizonyíthatóan biztonságos hash függvények létrehozása sokkal időigényesebb, mint a klasszikus megközelítések.
Maga a biztonsági igazolás gyakran olyan problémán alapul, amely a szükséges átlagos vagy legrosszabb eset bonyolultságú. A legrosszabb eset komplexitása leggyakrabban kóros helyzeteket ír le, nem pedig a feladatra jellemzőeket. Még az átlagosan bonyolult problémává való redukálás is korlátozott biztonságot nyújt, mivel olyan algoritmus található, amely könnyedén megoldja a problémát a problémaadatok egy bizonyos részhalmazára. Így például kimutatták, hogy az eredeti cikkben a gyors szindróma alapú hash függvény három paramétere közül kettő esetében optimálisabb támadások léteznek, mint az alkotók által a biztonság bizonyítására javasoltak. [3]

A SWIFFT egy példa egy hash függvényre, amely valamelyest megkerüli a leírt biztonsági problémát. Kimutatható, hogy minden olyan algoritmushoz, amely időben valószínőséggel megtöri a SWIFFT-et, létezik olyan algoritmus, amely a legrosszabb esetben is idıben megold egy bizonyos matematikai problémát a és függvényében . [négy] $P$ $T$ $T'$ $P$ $T$

Példák bizonyíthatóan biztonságos hash függvényekre

A VSH – Very Smooth Hash függvény – egy bizonyíthatóan biztonságos ütközésálló függvény, amely azon támaszkodik, hogy nehéz megtalálni a nem triviális négyzetgyököket egy n összetett szám modulo alapján (ami olyan nehéz, mint n faktorálás ).
MuHASH
ECOH - Csak elliptikus görbe hash - elliptikus görbék , részhalmazösszeg-probléma és polinomiális összegzés ötletén alapuló hash függvényA biztonsági bizonyíték a mögöttes matematikai probléma NP-teljességének feltételezésére támaszkodott, de egy sebezhetőséget találtak Wagner általánosított "születésnapi" támadásában a második előkép keresésével kapcsolatban. [5]
FSB – Fast Syndrome-Based hash function – Kimutatható, hogy az FSB feltörése legalább olyan nehéz, mint a hagyományos szindróma dekódolásként ismert NP-teljes probléma megoldása. [6]
SWIFFT - A SWIFFT az FFT -n alapul, és bizonyíthatóan biztonságos egy meglehetősen gyenge feltételezés mellett, amely a legrosszabb esetre vonatkozik a rövid vektorok ciklikus/ideális rácsban való megtalálásának nehézségére. [7]
Chaum, van Heijst, Pfitzmann hash függvény - olyan függvény, amelyben az ütközések megtalálása ugyanolyan munkaigényes, mint egy véges csoport diszkrét logaritmusának megtalálásakor . $F_{2p+1}$
A hátizsák-alapú hash-függvények a hátizsák-problémán alapuló hash-függvények családja .
Van egy általános megközelítés a bizonyíthatóan biztonságos kivonatolási algoritmusok bármilyen megfelelő szigma protokollon alapuló felépítésére . A VSH gyorsabb verziója (úgynevezett VSH*) ily módon beszerezhető.

Az ideális kriptográfiai hash függvény

Az ideális kriptográfiai hash függvény egy kriptográfiai hash függvény, amelynek öt alapvető tulajdonsága van:

Determinizmus . Ugyanazon bemeneti adatok mellett a hash függvény eredménye ugyanaz lesz (mindig ugyanaz az üzenet vezet ugyanahhoz a hash-hez);
A hash érték nagy sebességű kiszámítása bármely adott üzenethez;
Képtelenség üzenetet generálni a hash értékéből, kivéve az összes lehetséges üzenet létrehozását;
Lavina hatás. Egy kis változtatás az üzenetekben olyan mértékben megváltoztatja a hash értékeket, hogy az új hash értékek nem egyeznek meg a régi hash értékekkel;
Képtelenség megtalálni két különböző üzenetet azonos hash értékkel.

Így egy ideális kriptográfiai hash függvénynek, amelynek hossza n (vagyis a kimenet n bit), legalább műveletekre van szükség az előkép kiszámításához. $2^{n}$

A támadó a következő módon keres egy előképet egy ideális hash függvényhez: van egy h száma, és meg kell találnia m-t úgy, hogy H(m) = h. Ha ez egy ideális hash függvény, akkor a támadó csak végig tudja menni az összes lehetséges M-en, és ellenőrizni tudja, hogy ebből az üzenetből mennyivel egyenlő a hash függvény. A számítás eredménye, ha m-t teljesen iteráljuk, valójában egy véletlen szám. Ha a h szám 0-tól ig terjedő tartományban van , akkor átlagosan a támadó iterációkat fog tölteni a kívánt h keresésével. Így az előkép kiszámítása feleannyi iterációt vesz igénybe, mint ideális esetben. $2^{n}$ $2^{{n-1}}$

Marad a második előkép számítása . Az ütközések keresése során a pontszám , és ez nem teljesen pontos eredmény. Ez az értékelés az úgynevezett " Születésnapi Paradoxon " értékeléséből származik. $2^{n}$ $2^{n}$

Ha egy támadó programot akar írni az ütközések megtalálására, akkor az lenne az optimális, ha először beszerezne magának egy szótárt az ütközésekről. Ennek megfelelően a következő üzenetből kiszámítja a hash függvényt, és ellenőrzi, hogy ez a hash függvény a következő üzenethez tartozik-e vagy sem. Ha igen, akkor a rendszer megtalálja az ütközést, majd az eredeti üzenet a megadott hash kóddal megtalálható a szótárban. Ha nem, akkor feltölti a szótárt. A gyakorlatban ez a módszer nem valósul meg, mert nem lenne elég memória egy ilyen szótárhoz.

Birthday Attack

A születésnapi támadás a kriptoanalízisben a születésnapi paradoxonon alapuló hash függvény ütközésészlelési módszerének elnevezése. A paradoxon lényege, hogy egy 23 fős vagy több fős csoportban a születésnapok (nap és hónap) egybeesésének valószínűsége legalább két fő esetében meghaladja az 50%-ot. Például, ha egy osztályban 23 vagy több diák van, akkor valószínűbb, hogy valamelyik osztálytárs születésnapja ugyanarra a napra esik, mint hogy mindenkinek meglegyen a maga egyedi születésnapja.

Avalanche Effect

Tekintsük ezt a hatást és szerepét a blokklánc-kivonatolási folyamat példáján. Ez a tulajdonság azt jelenti, hogy ha kis változtatásokat végzünk a bemeneti karakterláncon, akkor a hash-ek (vagyis a kriptográfiai függvény kimenete) drasztikusan különböznek egymástól. Vizsgáljuk meg ezt a tulajdonságot egy egyszerű példán. Vegyük például az MD családból származó hash függvény eredményét - MD5. A bevitelnél olyan értékeket adunk meg, amelyek csak az első karakterek esetében különböznek egymástól - a karakterláncok szinte azonosak. A hash-eik (a hash függvény eredménye) azonban eltérőek.

Példa az MD5 titkosítási algoritmus működésére
Bemenet	Kimenet
bitcoin	0xCD5B1E4947E304476C788CD474FB579A
bitcoin	0xD023EC040F79F1A9B2AC960B43785089

"Magas entrópia"

A jó hash függvények "Magas entrópia " tulajdonsággal rendelkeznek. Ez azt jelenti, hogy az adattömbök hash-ei a kivonatolási folyamat során a rendszerben maximálisan eloszlanak, azaz információ értelemben nagy entrópiával rendelkezzenek. Mint tudják, az entrópia az információ értelmében egy bizonyos rendszer bizonytalanságának mértéke, különösen egy szimbólum megjelenésének kiszámíthatatlansága.

Tehát vegyük például az egyenletet , ahol egy karakterlánc és egy karakterlánc összefűzése , és egy kriptográfiai hash függvény. Ha az érték magas entrópiaindexszel rendelkezik, akkor szinte lehetetlen olyan értéket találni, amely kielégíti az egyenletet. $OUTPUT=H(K|INPUT)$ $K|BEMENET$ $K$ $INPUT$ $H$ $K$ $INPUT$

A "nagy entrópia" kifejezés a hash függvényekkel összefüggésben azt az állapotot jelenti, amelyben a lehetséges opciók olyan széles skálájából választanak ki egy értéket, hogy a véletlenszerű kiválasztással történő kitalálásnak nincs esélye a sikerre. Például egy 1 és 10 közötti számnak alacsony az entrópiája, míg az 1 és 1 közötti számoknak, fordítva, magas az entrópiája. $2^{256}$

MD és SHA hash függvénycsalád

A mai napig a hash-függvények alkalmazásainak túlnyomó többségét az MD5 , SHA-1 , SHA-256 algoritmusok „átvették” , Oroszországban pedig a GOST R 34.11-2012 (Stribog) . Természetesen sok más, kevésbé ismert vagy csak szűk közösségekben elterjedt algoritmus létezik (például RIPEMD , TIGER , Panama stb.), azonban ezek az algoritmusok nem annyira elterjedtek. Az alábbiakban az MD4 hash függvényeinek elemzése látható , amely az MD5 elődje volt, valamint az SHA hash függvényt.

Típusú	Leírás
MD4	A leggyorsabb, 32 bites gépekre optimalizálva az MD funkciók családjából. A Massachusettsi Egyetem professzora, Ronald Rivest által 1990-ben kifejlesztett hash függvény, amelyet először az RFC 1186-ban írtak le. Három, egyenként 16 lépésből álló hurkot tartalmaz. 1993-ban leírták az MD4 feltörő algoritmust, így ma már nem ajánlott valós alkalmazásokhoz használni ezt a funkciót.
MD5	Az MD-funkciók családjából a leggyakoribb. Hasonló az MD4-hez, de a biztonsági fejlesztések révén 33%-kal lassabb, mint az MD4. Négy, egyenként 16 lépésből álló ciklust tartalmaz. Adatintegritás-ellenőrzést biztosít. Az első sikeres kísérletek ennek a hash-függvénynek a feltörésére 1993-ig nyúlnak vissza: Bert den Boer és Anton Bossilaris kutatók kimutatták, hogy az algoritmusban lehetségesek pszeudoütközések. 1996-ban Hans Dobbertin megmutatta az ütközések lehetőségét, és elméletileg leírta a hackelési algoritmust. 2004. augusztus 24-én négy független kutató - Wang Xiaoyun, Feng Dengguo, Lai Xuejia és Yu Hongbo - olyan algoritmus-sebezhetőséget fedezett fel, amely lehetővé teszi az ütközések megtalálását analitikai módszerrel, többé-kevésbé elfogadható időn belül. 2005-ben Vlastimil Klima kiadott egy algoritmust az ütközések néhány órán belüli észlelésére. 2006. március 18-án egy kutató közzétett egy algoritmust, amely egy perc alatt találja meg az ütközéseket, amit később "alagútnak" neveztek. A mai napig az MD5 nem ajánlott valós alkalmazásokhoz.
SHA-1 (Biztonságos Hash 1. algoritmus)	1993-ban az NSA a NIST - szel együttműködve kifejlesztette a Secure Hash Algorithm (jelenleg SHA-0 néven ismert) (a FIPS PUB 180-ban megjelent) biztonságos kivonatolási szabványt. Az NSA azonban hamarosan visszavonta ezt a verziót egy felfedezett hibára hivatkozva, amelyet soha nem hoztak nyilvánosságra. És lecserélték egy átdolgozott változatra, amelyet 1995-ben tettek közzé a FIPS PUB 180-1-ben. Ez a verzió az úgynevezett SHA-1 . Később, az 1998-as CRYPTO konferencián két francia kutató bemutatta az SHA-0 algoritmus elleni támadást, amely nem működött az SHA-1 algoritmuson. Ez egy hiba lehetett, amelyet az NSA fedezett fel. Az SHA-1 160 bites értéket hoz létre, amelyet üzenetkivonatnak is neveznek. Négy szakaszt tartalmaz. Mind az MD5, mind az SHA-1 az MD4 továbbfejlesztett kiterjesztései. Különbségek: Az SHA-1-ben a negyedik szakasz ugyanazt a funkciót használja, mint a második szakasz. Az MD5-ben minden művelet egyedi növekményes állandót használ. Az SHA-1-ben az állandókat mind a négy csoporthoz újra felhasználják. Az SHA-1-hez hozzáadtunk egy ötödik változót. Az SHA-1 ciklikus hibajavító kódot használ. Az MD5 négy különböző elemi logikai függvényt tartalmaz, míg az SHA-1 három. Az MD5-ben a kivonat hossza 128 bit, az SHA-1-ben 160 bit. Az SHA-1 több kört tartalmaz (64 helyett 80-at), és 160 bites pufferrel fut az MD5 128 bites pufferéhez képest . Tehát az SHA-1-nek körülbelül 25%-kal lassabban kell futnia, mint az MD5-nek ugyanazon a hardveren.
SHA-2	Titkosító algoritmusok családja – hash függvények, beleértve az SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 és SHA-512/224 algoritmusokat. 2003-ban Gilbert és Handschuh tanulmányt végzett az SHA-2-vel kapcsolatban , de nem találtak sebezhetőséget. 2008 márciusában azonban Somitra Kumar Sanadiya és Palash Sarkar indiai kutatók közzétették az SHA-256 és SHA-512 22 iterációja során talált ütközéseket. Ugyanezen év szeptemberében bemutattak egy módszert ütközések létrehozására az SHA-2 csonka változataihoz (21 iteráció). Tanulmányok kimutatták [8] , hogy az SHA-2 algoritmusok 2-3-szor lassabban működnek, mint az MD5 , SHA-1 hash algoritmusok .
SHA-256	Külön kiemelkedik az SHA-256 algoritmus, amelyet bitcoin és más kriptovaluták hash-algoritmusaiban használnak. Ahogy a kriptográfiai hash függvény neve is sugallja, a kimeneti hash 256 bit hosszú, a megfelelő entrópia 1-től 2-ig terjedő értékek halmazaként definiálható 256 hatványáig - hatalmas számú érték, ami feltörést okoz. és a visszafejtés egy rendkívül időigényes folyamat, amely szekvenciális felsoroláson alapul.
SHA-3 ( Keccak)	Az SHA-3 hash függvény (más néven Keccak) egy változó bitfüggvény, amelyet Joan Dymen vezette szerzőcsoport fejlesztett ki . 2012. október 2-án Keccak lett az US National Institute of Standards and Technology által rendezett kriptográfiai algoritmusok versenyének győztese [9] . 2015. augusztus 5-én a függvényalgoritmust jóváhagyták és FIPS 202 [10] [11] szabványként tették közzé . Az SHA-3 függvényalgoritmus a kriptográfiai szivacs elvén épül fel .

Alkalmazások

Elektronikus aláírás

Annak érdekében, hogy megbizonyosodjon arról, hogy az üzenetet egy adott feladó küldte, az üzenettel együtt egy úgynevezett elektronikus aláírást is továbbítanak. A címzett ellenőrzi, hogy az elektronikus aláírás valóban az adott üzenethez tartozik-e.

Tekintettel arra, hogy a titkosítás nyilvános kulccsal történő alkalmazása (aláírás, aláírások ellenőrzése stb.) nagyon lassú folyamat, sőt, ha a teljes üzenetet aláírja, akkor ennek az aláírásnak a mérete összemérhető lesz az üzenet méretével. üzenetet, ne írja alá az üzenetet, és egy hash funkciót az üzenetből. Ezután a címzett az aláírás visszafejtésekor egy hash függvényt kap. Ezután összehasonlítja a kapott üzenetből származó hash függvényt és a visszafejtés eredményeként kapott hash függvényt. Tekintettel arra, hogy a hash függvény fix hosszúságú, kisebb, mint maga az üzenet. Ez lehetővé teszi a digitális aláírás gyors kiszámítását. Ennek az aláírásnak a mérete kicsi lesz az üzenet méretéhez képest.

Jelmondat ellenőrzése

A legtöbb esetben a jelmondatok nem tárolódnak a célpontokon, csak a hash értékeik kerülnek tárolásra. Nem tanácsos jelmondatokat tárolni, mert ha egy frázisokat tartalmazó fájlhoz illetéktelen hozzáfér a támadó, akkor az összes jelmondatot ismeri és azonnal fel tudja használni, a hash értékek tárolásakor pedig csak a hash értékeket tanulja meg amelyek nem visszafordíthatók az eredeti adatokra, ebben az esetben - jelmondattá. A hitelesítési eljárás során a rendszer kiszámítja a beírt jelszó hash értékét, és összehasonlítja a tárolt jelmondattal.

Ebben az esetben például a GNU/Linux és a Microsoft Windows XP . Csak a felhasználói fiókokból származó jelmondatok hash értékeit tárolják .

Ez a rendszer magában foglalja az üzenet továbbítását egy biztonságos csatornán keresztül, vagyis egy olyan csatornán, amelyről a kriptoanalitikus nem tudja elfogni az üzeneteket vagy elküldeni a sajátját. Ellenkező esetben elfoghatja a jelszót, és további illegális hitelesítésre használhatja fel. Megvédheti magát az ilyen támadásoktól a kihívás-válasz módszerrel .

Hagyja, hogy egy név nevű kliens hitelesítsen egy jelmondattal, átadja a kiszolgálónak. A szerver tárolja a H hash értéket ( pass , R 2 ) , ahol R 2 egy pszeudovéletlen, előre kiválasztott szám. A kliens kérést küld ( név , R 1 ), ahol R 1 egy álvéletlen, minden alkalommal új számot. Válaszul a szerver elküldi az R 2 értéket . A kliens kiszámítja a H hash értéket ( R 1 , H ( pass , R 2 )) és elküldi a szervernek. A szerver kiszámolja a H értéket is ( R 1 , H ( pass , R 2 )) és összeveti a kapott értékkel. Ha az értékek egyeznek, a hitelesítés helyes.

Ilyen helyzetben a jelszót nem tárolják nyíltan a szerveren, és a kriptoanalizátor a kliens és a szerver közötti összes üzenet elfogása után sem tudja visszaállítani a jelszót, és a továbbított hash értéke minden alkalommal más.

Bitcoin hashing

A bitcoin fizetési rendszer tranzakciói , amelyek egy bizonyos adattömbként jelennek meg, blokkokba vannak egyesítve (a továbbiakban az összes blokk összességét blokkláncnak nevezzük ), és egy hash algoritmuson mennek keresztül, azaz a mező adatait a bemenetre táplálják. egy kriptográfiai hash függvény. Minden tranzakció jelzi, hogy az összegeket honnan terhelik, és hová kerülnek. A címzett megadásához a nyilvános kulcsát (egy egyedi azonosítót a bitcoin hálózatban) használják. Ahhoz, hogy a címzett a kapott pénzt a bitcoin protokollon belül felhasználhassa (saját pénztárcája - Wallet értékesítését kizárjuk), új tranzakciót kell létrehoznia, amely átveszi a devizát az előzőből, és átirányítja egy másik címre a nyilvános kulcs. Ennek megfelelően az új tranzakció a bitcoin hálózat többi felhasználójának tranzakcióival együtt egy új blokkba kerül. Így nő a blokkok száma a blokkláncban. Azonban minden tranzakciót jóvá kell hagyni – a rendszernek konszenzusra kell jutnia. Ennek többféle módja is van, de a Bitcoin a Proof-of-Work (PoW) elvét használja. A tranzakció elfogadása után valódinak minősül, és a kriptovaluta egyik pénztárcából a másikba kerül.

A Bitcoin rendszer egy decentralizált rendszer, dedikált blokkgeneráló központok nélkül. Minden résztvevő átveheti a naplózásra váró tranzakciók halmazát, és új blokkot alkothat. Sőt, az olyan rendszerekben, mint a BitCoin, egy ilyen résztvevő (bányász) bónuszt is kap bizonyos összeg vagy jutalék formájában a blokkba elfogadott tranzakciók után.

De a decentralizált rendszerekben nem lehet egyszerűen egy blokkot felvenni és alkotni. A rendszernek konszenzusra kell jutnia, azaz jóváhagyást kell kapnia. Ennek többféle módja is van, de a Bitcoin a Proof-of-Work (PoW) elvét használja. Az ilyen rendszerek megbízhatósága éppen azon alapszik, hogy egy új blokkot nem lehet gyorsabban (átlagosan) kialakítani, mint egy adott idő alatt. Például 10 perc alatt (BitCoin).

A BitCoin blokklánc blokkstruktúrája

terület	Leírás	méret
Varázslat sz	érték mindig 0xD9B4BEF9	4 bájt
blokk mérete	a blokk végéig következő bájtok száma	4 bájt
blokkfejléc	6 elemből áll	80 bájt
tranzakciószámláló	pozitív egész szám	1-4 bájt
tranzakciók	a <nem üres> tranzakciók listája	<Tranzakciószámláló> - sok tranzakció

A Blockheader struktúra a BitCoin blokklánc blokkban

terület	Célja	Frissítés, amikor…	méret
változat	blokk verziószám	Frissítette a szoftvert, és az új verziót adott meg	négy
hashPrevBlock	Az előző blokkfejléc 256 bites hash-je	Új blokk érkezik	32
hashMerkelRoot	256 bites hash a blokkban lévő összes tranzakció alapján	A tranzakciót elfogadják	32
Idő	aktuális időbélyeg másodpercben 1970-01-01 T00:00 UTC óta	Néhány másodpercenként	négy
bitek	jelenlegi cél kompakt formátumban	A nehézség be van állítva	négy
semmi	32 bites szám (0-val kezdődik)	A hash elfáradt (növekmény)	négy

A nehézség a nulla bitek száma, amelyek a célszám elején lesznek .

A cél az a szám, amelynél a blokk kivonatának kisebbnek kell lennie ahhoz, hogy a blokk érvényesnek minősüljön. A cél vagy pontosabban a nehézség a hálózat aktuális teljesítményétől függ, és a nehézséget n (BitCoin hálózatban - 2016) blokkonként meg kell változtatni, hogy 10 percenként egy blokk keletkezzen. Tegyük fel, hogy 2016-os blokkok jönnek létre a hálózatban, és minden kliens ellenőrzi, hogy mennyi ideig hozták létre az egyes blokkokat. Ha ez az idő hosszabb a számítottnál, azaz több mint 10 perc, akkor a bonyolultság csökken.

A nonce egy véletlen szám, amelyet a bányászoknak fel kell venniük ahhoz, hogy blokkot készítsenek.

A bitcoin adatstruktúra szerkezete

Amint fentebb említettük, a Bitcoin-tranzakciók egy csoportja az adatblokk összekapcsolt blokkjaként jelenik meg - blokklánc . Maga a blokklánc eszközstruktúrája linkelt listaként jelenik meg mutatókkal.

Minden blokkhoz tartozik egy mutató, amely az előző adatblokkra mutató hivatkozást tartalmaz. Így ahhoz, hogy n + 1 blokkra menjünk, követni kell az előző n blokk mutatóit. Ennek megfelelően a mutatók csak azután adják hozzá egy új blokk címét, miután az eredeti adatblokk átment a bitcoin hash algoritmuson – ez lehetővé teszi, hogy a kapcsolat megbízható és biztonságos legyen.

Egy ilyen rendszert kisebb valószínűséggel támadnak meg behatolók, akik megpróbálhatják megváltoztatni a blokklánc adatait, például, hogy saját tranzakciójukat hajtsák végre a kiválasztott címen. Mint már említettük, a blokklánc egyes blokkjainak hash-je nem csak a saját, hanem az előző blokk tartalmától is függ. Így az eredeti blokkban lévő adatok bármilyen változása a többi blokk adatainak változását vonja maga után. Ez garantálja a blokklánc megváltoztathatatlanságát és a rendszer biztonságát, hiszen rendkívül nehéz „hamisítani” a blokkláncot. Azonban meg kell jegyezni, hogy minden blokk hash-jének egyedinek kell lennie, különben a támadási kísérletek nyomon követése lehetetlenné válik.

Merkle fa

Minden tranzakció hexadecimális formátumú karakterláncként jelenik meg, amelyek kivonatolásra kerülnek a tranzakcióazonosítók megszerzéséhez. Ezek alapján épül fel egy blokk hash, amelyet a következő blokk figyelembe vesz, biztosítva a változhatatlanságot és a koherenciát. Egyetlen blokk hash értéket gyűjt a Merkle fa segítségével .

A Merkle-fa egy teljes bináris fa , amelynek levélcsúcsai a tranzakciókból származó hash -eket , a belső csúcsok pedig a gyermekcsúcsokban hozzáadott értékekből származó hash-eket, a fa gyökércsomópontja (Top Hash) pedig a teljes adathalmaz.

A Merkle-fa felépítése a bitcoin blokklánchoz a következő:

$H(L_{i})$ - a tranzakcióból származó hash függvény eredménye $L_{i}$

A blokkokban elhelyezett tranzakciók hash-eit kiszámítjuk: H(L1), H(L2), H(L3) stb.
A kivonatokat a rendszer a tranzakciók kivonatainak összegéből számítja ki, például H(H(L1) + H(L2)). Mivel a Merkle-fa bináris, az elemek számának minden iterációnál párosnak kell lennie. Ezért, ha egy blokk páratlan számú tranzakciót tartalmaz, akkor az utóbbi megkettőződik és hozzáadódik önmagához: hash (H(L3) + H(L3)).
Ezen túlmenően a hash-eket a rendszer a hash-ek összegéből ismét kiszámítja. A folyamatot addig ismételjük, amíg egyetlen hash-t nem kapunk - a Merkle-fa gyökerét. Ez egy kriptográfiai bizonyíték a blokk integritására (vagyis arra, hogy minden tranzakció a megadott sorrendben történik). A gyökér értéke a blokk fejlécében van rögzítve.

Ugyanakkor például az L1 tranzakció elköltésekor a blokkból eltávolítható az arra vonatkozó adat, és csak a hash marad meg a blokk ellenőrzésére. Amikor az L1 és L2 tranzakciót elköltjük, akkor a blokkellenőrzés céljából törölhetjük a hash-eiket (Hash 0-0 és Hash 0-1), így csak a Hash 0 marad meg. Abban a pillanatban, amikor az összes tranzakciót felhasználják, akkor az összes hash törölhető, kivéve a Top Hash-t, mivel ezekre a tranzakciókra vonatkozó információkra már nincs szükség.

Így ahhoz, hogy egy új láncblokkhoz hash-t kapjunk, minden korábbi tranzakciós hash-t figyelembe kell venni. Az előző blokkok legalább egyikének kivonatának megváltoztatása a következő blokk hash-ének megváltozásához vezet, illetve az ilyen tranzakció azonnal érvénytelennek minősíthető.

Bitcoin bányászat

A bányászat a munkabizonyítás elvével kapcsolatos konszenzus megtalálásának folyamata – jóváhagyás beszerzése egy új blokk létrehozásához. Valójában a BitCoin hálózatban ez a blokkból származó hash megszámlálására és a célszámmal való összehasonlítására vonatkozik : ha a hash kisebb, mint a cél , akkor új blokkot generál, ellenkező esetben nem.

A bányászok biztosítják a blokklánc folyamatos növekedését. Ehhez hatalmas számítási teljesítményt használnak - minden bányász hozzájárul a teljes bitcoin hashrate (számítási teljesítmény) növeléséhez. Az egyes bányászok bitcoin-kivonatolási műveleteinek részesedése a teljes hashrate-mutatótól függ – minél magasabb a hálózat teljes hashrate-je, annál több számítási munkát kell elvégeznie a bányásznak rövidebb idő alatt, hogy fenntartsa bányászati jutalma átlagos nagyságát.

A nonce karakterláncba való behelyettesítésének folyamata addig folytatódik, amíg meg nem találjuk a helyes megoldást. Néha a próbálkozások száma elérheti a milliókat is. Az a bányász, aki először találja meg a megfelelő megoldást, hozzáadja a blokkot a blokklánchoz, és ezért jutalmat kap.

A nonce kiválasztási folyamat a brute force módszeren alapul . Ezért a bányászati berendezés folyamatosan véletlenszerű karakterláncokat generál, amíg meg nem találja a kívánt nonce értéket .

Példák az SHA-256 hash funkciót használó kriptovalutákra a titkosításhoz

Az SHA-256 a kriptovaluták klasszikus algoritmusa: erre épül a fő kriptovaluta, a Bitcoin. Ennek megfelelően ezt az algoritmust használják a Bitcoin fork-okban is: Bitcoin Cash-ben, Bitcoin SV-ben. Ugyanakkor a Bitcoin Goldban a bányászok egy kriptofunkciót használnak - az Equihash-t

Rajtuk kívül az SHA-256-ot a következőkben is használják:

Steemit;
peercoin ;
NameCoin ;
Ocoin;
Zetacoin;
emercoin .

Ezenkívül az SHA-256 algoritmust szubrutinként használják a Litecoin kriptovalutában, és a bányászat fő algoritmusa a Scrypt.

Lásd még

Jegyzetek

↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. Gyors, bizonyíthatóan biztonságos kriptográfiai kivonatoló funkció . - 2003. - 230. sz . - P. 3-4 . Az eredetiből archiválva : 2019. december 8.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. Gyors, bizonyíthatóan biztonságos kriptográfiai kivonatoló funkció . - 2003. - 230. sz . - S. 3 . Az eredetiből archiválva : 2019. december 8.
↑ Jean-Sebastien Coron, Antoine Joux. Egy bizonyíthatóan biztonságos kriptográfiai hash-függvény kriptoanalízise . - 2004. - 013. sz . - S. 1.3 . Az eredetiből archiválva : 2019. december 7.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Szerény javaslat az FFT-kivonatoláshoz // Gyors szoftvertitkosítás. — Springer, Berlin, Heidelberg, 2008.02.10. — 65. o . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Archiválva az eredetiből 2019. április 8-án.
↑ Michael A. Halcrow, Niels Ferguson. Második kép előtti támadás csak az elliptikus görbe hash ellen (ECOH) . - 2009. - 168. sz . Az eredetiből archiválva : 2018. december 24.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. Gyors, bizonyíthatóan biztonságos kriptográfiai kivonatoló funkció . - 2003. - 230. sz . Az eredetiből archiválva : 2019. december 8.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Szerény javaslat az FFT-kivonatoláshoz // Gyors szoftvertitkosítás. — Springer, Berlin, Heidelberg, 2008.02.10. - P. 54-72 . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Archiválva az eredetiből 2019. április 8-án.
↑ Népszerű kriptoalgoritmusok sebesség -összehasonlítása . www.cryptopp.com. Letöltve: 2017. december 22. Az eredetiből archiválva : 2017. július 2.
↑ Swenson, Gayle . A NIST kiválasztja a Secure Hash Algorithm (SHA-3) verseny győztesét (eng.) , a NIST (2012. október 2.). Archiválva az eredetiből 2012. október 5-én. Letöltve: 2017. december 23.
↑ Hernandez, Paul . A NIST kiadja az SHA-3 Cryptographic Hash Standard , NIST szabványt ( 2015. augusztus 5.). Az eredetiből archiválva : 2018. január 24. Letöltve: 2017. december 23.
↑ Morris J. Dworkin. SHA-3 szabvány: Permutáció-alapú hash és kiterjeszthető kimeneti függvények // Szövetségi inf. folyamat. Stds. (NIST FIPS) - 202. - 2015-08-04. Archiválva az eredetiből 2017. szeptember 17-én.

Irodalom

Bruce Schneier. Alkalmazott kriptográfia. Protokollok, algoritmusok, forrásszövegek C nyelven. - M . : Triumph, 2002. - ISBN 5-89392-055-4 .
Laponina O.R. A biztonság kriptográfiai alapjai . - M . : Internet University of Information Technologies - INTUIT.ru, 2004. - P. 320. - ISBN 5-9556-00020 -5.

Linkek

Információ az elektronikus digitális aláírásról . (határozatlan)
A Keccak hash-függvény és a szivacskonstrukció mint univerzális kriptoprimitív, pgpru.com, 2010-2013 (fordítva a noekon.org oldalról)
A hivatalos GOST R 34.11-2012 szabvány szövege a Wikiforrásban

Hash függvények
Általános rendeltetésű	Adler-32 CRC Fletcher ellenőrző összeg FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH – Hash Tree jenkins hash hash összeg
Kriptográfia	Stribog GOST R 34.11-94 Öv BLAKE BMW CubeHash VISSZHANG edonkey2k FSB Fúga 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 Bőr Snefru Tigris Örvény
Kulcsgenerálási funkciók	bcrypt PBKDF2 scrypt Argon2 Lyra2
Csekkszám ( összehasonlítás )	Ellenőrző összeg Verhouff algoritmusa Hold algoritmus Damm algoritmus Vonalkód bankszámlák bankkártyák VAN SNILS OKPO ÓN OKATO ISBN OGRN és OGRNIP VIN
Hashes	A csekkszámok összehasonlítása Hitelesítési protokollok Vonalkód összehasonlítás Kriptográfia Mágneses kapcsolat Merkle aláírása ed2k URNA