BLAKE (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. június 7-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A BLAKE  egy kriptográfiai hash függvény , amelyet Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan fejlesztett ki.

A hash funkciónak két változata létezik: BLAKE-256 és BLAKE-512.

Történelem

A BLAKE-t először mutatták be az USA Nemzeti Szabványügyi és Technológiai Intézete által megrendezett kriptográfiai algoritmusok versenyén (  NIST hash function verseny , orosz SHA-3 (verseny) ). BLAKE a verseny öt döntőse egyike lett ( angol  finalists ).

Biztonság

A BLAKE hash függvény három korábban vizsgált komponensből épül fel:

Teljesítmény és megvalósítás

Teljesítmény két különböző processzoron:

processzor Sebesség (ciklusok/bájt)
BLAKE-256 BLAKE-512
Intel Core i5-2400M (Sandy Bridge) 7.49 5.64
AMD FX-8120 (bulldózer) 11.83 6.88

Megvalósítási lehetőség különböző mikrokontrollereken:

mikrokontroller BLAKE-256 BLAKE-512
RAM (byte) ROM (byte) RAM (byte) ROM (byte)
Cortex-M3 alapú mikrokontroller (32 bites processzor) 280 1320 516 1776
ATmega1284P mikrokontroller (8 bites processzor) 267 3434 525 6350

Teljesítmény FPGA -n ( eng.  FPGA ):

A Xilinx Virtex 5 FPGA -n a BLAKE-256 56 cellán van megvalósítva, és több mint 160 Mbps átviteli sebességet érhet el, a BLAKE-512 pedig 108 cellán és 270 Mbps-ig terjedő sebességgel.

ASIC teljesítmény :

180 nm-es ASIC -en a BLAKE-256 13,5 kGE -vel valósítható meg. A 90 nm-es ASIC -en a BLAKE-256 38 kGE-vel és 10 Gb/s-os teljesítménnyel, míg a BLAKE-512 79 kGE-vel és 15 Gb/s-on valósul meg [2] .

Algoritmus

Ahogy korábban említettük, a BLAKE hash függvény három korábban tanult komponensből épül fel:

Tekintsük a BLAKE-256 algoritmust [3]

A BLAKE-256 32 bites szavakkal működik, és 32 bájtos hash-t ad vissza.

Konstansok

Léteznek kezdeti állandók, az ún. KEZDETI ÉRTÉKEK (IV):

IV0 = 6A09E667 IV1 = BB67AE85 IV2 = 3C6EF372 IV3 = A54FF53A IV4 = 510E527F IV5 = 9B05688C IV6 = 1F83D9AB IV7 = 5BE0CD19

16 állandó (a pi első számjegyei):

c 0 = 243F6A88 c 1 = 85A308D3 c 2 = 13198A2E c 3 = 03707344 c 4 = A4093822 c 5 = 299F31D0 c 6 = 082EFA98 c 7 = EC4E6C89 c 8 = 452821E6 c 9 = 38D01377 c 10 = BE5466CF c 11 = 34E90C6C c 12 = C0AC29B7 c 13 = C97C50DD c 14 = 3F84D5B5 c 15 = B5470917

permutációk {0,…,15} (minden BLAKE függvényben használatos):

σ0 = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 σ 1 = 14 10 4 8 9 15 13 6 1 12 0 2 11 7 5 3 σ 2 = 11 8 12 0 5 2 15 13 10 14 3 6 7 1 9 4 σ 3 = 7 9 3 1 13 12 11 14 2 6 5 10 4 0 15 8 σ 4 = 9 0 5 7 2 4 10 15 14 1 11 12 6 8 3 13 σ5 = 2 12 6 10 0 11 8 3 4 13 7 5 15 14 1 9 σ 6 = 12 5 1 15 14 13 4 10 0 7 6 3 9 2 8 11 σ 7 = 13 11 7 14 12 1 3 9 5 0 15 4 8 6 2 10 σ8 = 6 15 14 9 11 3 0 8 12 2 13 7 1 4 10 5 σ9 = 10 2 8 4 7 6 1 5 15 11 9 14 3 12 13 0

Tömörítési funkciók

A BLAKE-256 algoritmus tömörítési funkciója bemenetként:

Így 30 szót kap bemenetként (8+16+4+2=30, 30*4 = 120 bájt = 960 bit). A tömörítési függvény csak a láncváltozók új értékét adja vissza: h' = h' 0 ,…,h' 7 . A következőkben a h'=tömörítés(h, m, s, t) értéket fogjuk jelölni .

Inicializálás

16 változó ( v 0 ,…,v 15 ), amelyek leírják a v aktuális állapotát , a bemeneti adatoktól függően kezdeti értékekkel inicializálódnak, és 4×4-es mátrixként jelennek meg :

←

Kerek funkció

A v állapot inicializálása után 14 körből álló sorozat indul. A kör egy állapotművelet , amely a következő blokkra osztott számításokat hajtja végre:

G 0 (v 0 , v 4 , v 8 , v 12 ) G 1 (v 1 , v 5 , v 9 , v 13 ) G 2 (v 2 , v 6 , v 10 , v 14 ) G 3 (v 3 , v 7 , v 11 , v 15 ) G 4 (v 0 , v 5 , v 10 , v 15 ) G 5 ( v 1 , v 6 , v 11 , v 12 ) G 6 ( v 2 , v 7 , v 8 , v 13 ) G 7 ( v 3 ) , v 4 , v 9 , v 14 )

az r. körben a számítási blokk a következőképpen működik:

j ← σ r%10 [2×i] k ← σ r%10 [2×i+1] a ← a + b + (m j ⊕ c k ) d ← (d ⊕ a) >>> 16 c ← c + d b ← (b ⊕ c) >>> 12 a ← a + b + (m k ⊕ c j ) d ← (d ⊕ a) >>> 8 c ← c + d b ← (b ⊕ c) >>> 7

Az első négy G 0 ,…,G 3 blokk párhuzamosan számolható, mivel mindegyik megváltoztatja az állapotmátrix változók saját specifikus oszlopát . Nevezzük a számítási eljárást G 0 ,…,G 3 oszloplépésnek . Hasonlóképpen G 4 ,…,G 7 is kiszámítható párhuzamosan , de ezek viszont megváltoztatják a v állapotmátrix minden átlóját . Ezért a számítási eljárást G 4 ,…,G 7 átlós lépésnek nevezzük . A G i párhuzamos számításának lehetőségét grafikusan mutatjuk be.

A 9-nél nagyobb r számokkal rendelkező köröknél a σ r%10 permutációt használjuk , például a 13. körben σ 3 .

Utolsó lépés

Minden kör után a h' 0 ,…,h' 7 láncváltozók új értékét kiszámítjuk az állapotmátrix változóiból, a bemeneti változókból és a sóból :

h' 0 ← h 0 ⊕ s 0 ⊕ v 8 h 1 ← h 1 ⊕ s 1 ⊕ v 9 h' 2 ← h 2 ⊕ s 2 ⊕ v 10 h ' 3 ← h 3 ⊕ h s 4 ← h 4 ⊕ s 4 ⊕ v 12 óra 5 ← h 5 ⊕ s 5 ⊕ v 13 óra 6 ← h 6 ⊕ s 6 ⊕ v 14 óra 7 ← h 7 ⊕ v 715

Üzenetkivonat

Leírjuk az l<2^64 bit hosszúságú m üzenet kivonatolási folyamatát. Először az üzenetet 512 bit (64 bájt) többszörösére tölti ki a kitöltési funkció , majd blokkonként feldolgozza a tömörítési funkció .

A kitöltési funkcióban az üzenetet először bitekkel töltjük ki úgy, hogy a modulo 512 hossza 447 legyen: először 1 kerül hozzáadásra, majd a szükséges számú nulla. Ezt követően az l üzenethosszúság még egy 1 és 64 bites reprezentációja hozzáadódik a legjelentősebb bittől a legkevésbé jelentősig. Így az üzenet hossza 512 többszöröse lesz [Comm. 1] . A kitöltés biztosítja, hogy az üzenet hossza 512 bit többszöröse legyen.

Az üzenet kivonatának kiszámításához a kitöltési függvény eredményét 16 szavas m 0 ,…,m N-1 blokkra osztjuk . Legyen L i  az eredeti üzenet bitjeinek száma m 0 ,…,m i blokkban , azaz nem számítva ki azokat a biteket, amelyeket a kitöltési eljárásban adtak hozzá. Például, ha az üzenet 600 bites, akkor a kitöltési eljárás után 1024 bites lesz, és két blokkra oszlik: m 0 és m 1 . Ezenkívül L 0 = 512, L 1 = 600. Bizonyos esetekben az utolsó blokk nem tartalmazza az eredeti üzenet egy részét. Például, ha az eredeti üzenet 1020 bites, akkor a kitöltési eljárás eredményeként 1536 bites lesz, m 0 pedig 512 bites az eredeti üzenetből, m 1  - 508 és m 2  - 0 Állítsa be : L 0 = 512, L 1 = 1020 és L 2 = 0. Vagyis a szabály a következő: ha az utolsó blokkban nincsenek az eredeti üzenet bitjei, akkor az L N-1 számlálót állítsuk 0-ra. Ez garantálja, hogy ha i ≠ j , akkor L i ≠ L j . A sóértéket a felhasználó határozza meg, vagy 0-ra állítja, ha nem használja ( s 0 =s 1 =s 2 =s 3 =0 ). Az üzenet hash kiszámítása a következőképpen történik:

h 0 ← IV ha i=0,...,N-1 h i+1 ← tömörítés(h i ,m i ,s,l i ) vissza h N .

A kivonatolási folyamat vizuálisan látható a folyamatábrán:

A függvény 64 bites verziójának algoritmusa megegyezik: a shift értékek rendre 32, 25, 16 és 11, a körök száma 16-ra nő.

Különbségek a ChaCha negyedéves algoritmusától

BLAKE hashek

BLAKE-512 ("") = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B 628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8 BLAKE-512(" A gyors barna róka átugrik a lusta kutyán ") = 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD 2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451

BLAKE2

A BLAKE2 ( BLAKE2 weboldal ) a BLAKE továbbfejlesztett változata, amely az SHA-3 hash függvényverseny öt döntőse egyike (főleg jobb teljesítmény), amelyet 2012. december 21-én mutattak be. Fejlesztők: Jean-Philippe Aumasson , Samuel Neves , Zooko Wilcox-O'Hearn és Christian Winnerlein . A korábban széles körben használt MD5 és SHA-1 alternatívájaként hozták létre, amelyekben sebezhetőséget találtak.

Különbségek a BLAKE-től

A BLAKE2-ben, a BLAKE-kal ellentétben, a kerek függvényben nincs konstans hozzáadása. Az eltolási állandók is módosultak, az összeadás egyszerűsödött, bekerült egy paraméterblokk, ami hozzáadódik az inicializálási vektorokhoz. Ezenkívül a körök száma 16-ról 12-re csökkent a BLAKE2b funkciónál (a BLAKE-512-vel analóg), és 14-ről 10-re a BLAKE2-eknél (a BLAKE-256-hoz analóg). Ennek eredményeként a bitenkénti ciklusok száma a BLAKE-256 esetében 7,49-ről és a BLAKE-512 esetében 5,64-ről 5,34-re, illetve 3,32-re csökkent a Blake2s és Blake2b esetében.


BLAKE2 hash

BLAKE2b-512 ("") = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419 D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE BLAKE2b-512 (" A gyors barna róka átugrik a lusta kutyán ") = A8ADD4BDDDFD93E4877D2746E62817B116364A1FA7BC148D95090BC7333B3673 F82401CF7AA2E4CB1ECD90296E3F14CB5413F8ED77BE73045B13914CDCD6A918
BLAKE2s-256("")
= 69217A3079908094E11121D042354A7C1F55B6482CA1A51E1B250DFD1ED0EEF9

BLAKE2s-256("The quick brown fox jumps over the lazy dog")
= 606BEEEC743CCBEFF6CBCDF5D5302AA855C256C29B88C8ED331EA1A6BF3C8812

BLAKE2s-128("")
= 64550D6FFE2C0A01A14ABA1EADE0200C

BLAKE2s-128("The quick brown fox jumps over the lazy dog ")
= 96FD07258925748A0D2FB1C8A1167A73

Megjegyzések

  1. ↑ Például egy 447 bites üzenet hozzáad 1-et, majd 511 nullát (a hossza 447 + 512 lesz), majd további 1-et és az l = 447 - 00 ... 0110111111 szám 64 bites reprezentációját. . Így a hossz 447+512+1+64 = 1024 lesz, ami 512 többszöröse

Források

  1. ↑ 1 2 BLAKE dokumentáció a hivatalos weboldalon Archiválva : 2017. december 9. a Wayback Machine -nél , 3. o. Bevezetés.
  2. ↑ A BLAKE hivatalos weboldala . Letöltve: 2013. december 21. Az eredetiből archiválva : 2018. április 16..
  3. ↑ BLAKE dokumentáció a hivatalos weboldalon Archiválva : 2017. december 9. a Wayback Machine -nél, 8. oldal Specifikáció.

Irodalom

Eli Biham és Orr Dunkelman. Keretrendszer az iteratív hash függvényekhez - HAIFA . - ePrint, 2007. - 207 p.

Linkek

 Hash függvények
Általános rendeltetésű
Kriptográfia
Kulcsgenerálási funkciók
Csekkszám ( összehasonlítás )
Hashes