BLAKE (hash-funktio)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7. kesäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

BLAKE  on Jean-Philippe Aumassonin, Luca Henzenin, Willi Meierin, Raphael C.-W. Phanin kehittämä kryptografinen hash-funktio .

Hajautusfunktiosta on kaksi muunnelmaa: BLAKE-256 ja BLAKE-512.

Historia

Ensimmäistä kertaa BLAKE esiteltiin Yhdysvaltain kansallisen standardointi- ja teknologiainstituutin järjestämässä kryptografisten algoritmien kilpailussa (  NIST hash function competition , Russian SHA-3 (kilpailu) ). BLAKEsta tuli yksi kilpailun viidestä finalistista ( englantilaiset  finalistit ).

Turvallisuus

BLAKE-tiivistefunktio on rakennettu kolmesta aiemmin tutkitusta komponentista:

Suorituskyky ja toteutus

Suorituskyky kahdella eri prosessorilla:

prosessori Nopeus (sykliä/tavu)
BLAKE-256 BLAKE-512
Intel Core i5-2400M (Sandy Bridge) 7.49 5.64
AMD FX-8120 (puskutraktori) 11.83 6.88

Mahdollisuus toteuttaa erilaisissa mikrokontrollereissa:

mikro-ohjain BLAKE-256 BLAKE-512
RAM (tavu) ROM (tavu) RAM (tavu) ROM (tavu)
Cortex-M3-pohjainen mikro-ohjain (32-bittinen prosessori) 280 1320 516 1776
ATmega1284P mikro-ohjain (8-bittinen prosessori) 267 3434 525 6350

Suorituskyky FPGA :lla ( eng.  FPGA ):

Xilinx Virtex 5 FPGA : ssa BLAKE-256 on toteutettu 56 solussa ja voi saavuttaa yli 160 Mbps:n suorituskyvyn, ja BLAKE-512 on toteutettu 108 solussa ja nopeuksilla jopa 270 Mbps.

ASIC- suorituskyky :

180 nm ASIC :lla BLAKE-256 voidaan toteuttaa 13,5 kGE:llä . 90 nm ASIC :ssa BLAKE-256 on toteutettu 38 kGE:ssä ja se voi saavuttaa 10 Gb/s suorituskyvyn, kun taas BLAKE-512 on toteutettu 79 kGE:ssä ja 15 Gb/s:ssa [2] .

Algoritmi

Kuten aiemmin mainittiin, BLAKE-hajautusfunktio on rakennettu kolmesta aiemmin opitusta komponentista:

Harkitse BLAKE-256-algoritmia [3]

BLAKE-256 toimii 32-bittisillä sanoilla ja palauttaa 32-tavun tiivisteen.

Vakiot

On alkuvakiot, ns. ALKUARVAT (IV):

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

16 vakiota (pi:n ensimmäiset numerot):

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

permutaatiot {0,…,15} (käytetään kaikissa BLAKE-funktioissa):

σ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

Pakkaustoiminnot

BLAKE-256-algoritmin pakkaustoiminto ottaa syötteenä:

Siten se vastaanottaa 30 sanaa syötteenä (8+16+4+2=30, 30*4 = 120 tavua = 960 bittiä). Pakkausfunktio palauttaa vain ketjumuuttujien uuden arvon: h' = h' 0 ,…,h' 7 . Seuraavassa merkitään h'=pakkaus(h, m, s, t).

Alustus

16 muuttujaa, v 0 ,…,v 15 , jotka kuvaavat v:n nykyistä tilaa , alustetaan alkuarvoilla syöttötiedon mukaan ja esitetään 4×4 -matriisina :

←

Pyöreä funktio

Kun tila v on alustettu, aloitetaan 14 kierroksen sarja. Kierros on tilatoiminto , joka suorittaa laskutoimituksia, jotka on jaettu seuraaviin lohkoihin:

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 )

r:nnellä kierroksella laskentalohko toimii seuraavasti:

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

Ensimmäiset neljä lohkoa G 0 ,…,G 3 voidaan laskea rinnakkain, koska jokainen muuttaa omaa tilamatriisimuuttujiensa saraketta . Kutsutaan laskentaproseduuria G 0 ,…,G 3 sarakeaskel . Vastaavasti G 4 ,…,G 7 voidaan laskea rinnakkain , mutta ne puolestaan ​​muuttavat tilamatriisin v kutakin diagonaalia . Siksi kutsumme laskentamenettelyä G 4 ,…,G 7 diagonaaliaskel . Mahdollisuus rinnakkaiseen laskentaan G i esitetään graafisesti.

Kierroksilla, joiden luvut r ovat suurempia kuin 9, käytetään permutaatiota σ r%10 , esimerkiksi 13. kierroksella σ 3 .

Viimeinen vaihe

Kaikkien kierrosten jälkeen ketjumuuttujien h' 0 ,…,h' 7 uusi arvo lasketaan tilamatriisimuuttujista, syöttömuuttujista ja suolasta :

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 31 h s 4 ← h 4 ⊕ s 4 ⊕ v 12 h 5 ← h 5 ⊕ s 5 ⊕ v 13 h 6 ← h 6 ⊕ s 6 ⊕ v 14 h 7 ← h 7 ⊕ s

Viestin hajautus

Kuvataan prosessi, jossa tiivistetään viesti m , jonka pituus on l<2^64 bittiä. Ensin viesti täytetään 512 bitin (64 tavun ) kerrannaisella täyttötoiminnolla , sitten lohko lohkolta sen käsittelee pakkaustoiminto .

Täytetoiminnossa viesti täytetään ensin biteillä siten, että sen pituus modulo 512 on 447: ensin lisätään 1, sitten tarvittava määrä nollia. Tämän jälkeen lisätään vielä yksi 1- ja 64-bittinen esitys viestin pituudesta l merkittävimmästä bitistä vähiten merkitsevään. Siten viestin pituudesta tulee 512:n kerrannainen [Comm. 1] . Täyte varmistaa, että viestin pituudesta tulee 512 bitin kerrannainen.

Viestin hajautusarvon laskemiseksi täytefunktion tulos jaetaan 16 sanan lohkoihin m 0 ,…,m N-1 . Olkoon L i  alkuperäisen viestin bittien lukumäärä lohkoissa m 0 ,…,m i , eli pois lukien ne bitit, jotka on lisätty täyteproseduurissa. Esimerkiksi, jos sanoman pituus on 600 bittiä, niin täytetoimenpiteen jälkeen sen pituus on 1024 bittiä ja se jaetaan kahteen lohkoon: m 0 ja m 1 . Lisäksi L 0 = 512, L 1 = 600. Joissakin tapauksissa viimeinen lohko ei sisällä osaa alkuperäisestä viestistä. Esimerkiksi, jos alkuperäisessä viestissä on 1020 bittiä, niin täytetoimenpiteen tuloksena sen pituus on 1536 bittiä ja m 0 :ssa on 512 bittiä alkuperäisestä viestistä, m 1  - 508 ja m 2  - 0 Aseta L 0 = 512, L 1 = 1020 ja L 2 = 0. Eli sääntö on seuraava: jos viimeisessä lohkossa ei ole alkuperäisen viestin bittejä, aseta laskuri L N-1 arvoon 0. Tämä takaa, että jos i ≠ j , niin L i ≠ L j . Suola-arvo on käyttäjän määrittelemä tai asetettu arvoon 0, jos sitä ei käytetä ( s 0 =s 1 =s 2 =s 3 =0 ). Viestin hash lasketaan seuraavasti:

h 0 ← IV kun i=0,...,N-1 h i+1 ← pakkaa(h i ,m i ,s,l i ) paluu h N .

Hajautusprosessi esitetään visuaalisesti vuokaaviossa:

Toiminnon 64-bittisen version algoritmi on identtinen: siirtoarvot ovat vastaavasti 32, 25, 16 ja 11, kierrosten määrä kasvaa 16:een.

Erot ChaChan neljänneskierrosalgoritmiin

BLAKE hashes

BLAKE-512("") = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B 628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8 BLAKE-512(" Nopea ruskea kettu hyppää laiskan koiran yli ") = 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD 2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451

BLAKE2

BLAKE2 (BLAKE2- verkkosivusto ) on parannettu versio BLAKEsta, joka on yksi SHA-3- hajautustoimintokilpailun viidestä finalistista (pääasiassa parannettu suorituskyky), joka esiteltiin 21. joulukuuta 2012. Kehittäjät: Jean-Philippe Aumasson , Samuel Neves , Zooko Wilcox-O'Hearn ja Christian Winnerlein . Se luotiin vaihtoehtona aiemmin laajalti käytetyille MD5 :lle ja SHA-1 :lle, joissa havaittiin haavoittuvuuksia.

Erot BLAKEsta

BLAKE2:ssa, toisin kuin BLAKEssa, pyöreäfunktiossa ei lisätä vakioita. Myös siirtovakiot on muutettu, yhteenlaskua on yksinkertaistettu, parametrien lohko on lisätty, joka lisätään alustusvektoreihin. Lisäksi kierrosten määrää on vähennetty 16:sta 12:een BLAKE2b-toiminnolle (analogisesti BLAKE-512:lle) ja 14:stä 10:een BLAKE2:lle (analogisesti BLAKE-256:lle). Tämän seurauksena jaksojen määrä bittiä kohden pieneni 7,49:stä BLAKE-256:lle ja 5,64:stä BLAKE-512:lle 5,34:ään ja 3,32:een Blake2:ssa ja Blake2b:ssä.


BLAKE2 hashes

BLAKE2b-512("") = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419 D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE BLAKE2b-512(" Nopea ruskea kettu hyppää laiskan koiran yli ") = 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

Kommentit

  1. ↑ Esimerkiksi viestiin, jonka pituus on 447 bittiä, lisätään 1, sitten 511 nollaa (pituudesta tulee 447 + 512), sitten toinen 1 ja 64-bittinen esitys luvusta l = 447 - 00 ... 0110111111 . Siten pituudesta tulee yhtä suuri kuin 447+512+1+64 = 1024, mikä on 512:n kerrannainen

Lähteet

  1. ↑ 1 2 BLAKE-dokumentaatio virallisella verkkosivustolla Arkistoitu 9. joulukuuta 2017 Wayback Machinessa , s.3 Johdanto.
  2. ↑ BLAKEn virallinen verkkosivusto . Haettu 21. joulukuuta 2013. Arkistoitu alkuperäisestä 16. huhtikuuta 2018.
  3. ↑ BLAKE-dokumentaatio virallisella verkkosivustolla Arkistoitu 9. joulukuuta 2017 Wayback Machinessa , s.8 Specification.

Kirjallisuus

Eli Biham ja Orr Dunkelman. Viitekehys iteratiivisille hash-funktioille - HAIFA . - ePrint, 2007. - 207 s.

Linkit

 Hash-funktiot
yleinen tarkoitus
Kryptografinen
Avainten luontitoiminnot
Tarkista numero ( vertailu )
Hashes