BLAKE (hashfunktion)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 juni 2019; kontroller kräver 2 redigeringar .

BLAKE  är en kryptografisk hashfunktion utvecklad av Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan.

Det finns två varianter av hash-funktionen: BLAKE-256 och BLAKE-512.

Historik

För första gången presenterades BLAKE vid tävlingen för kryptografiska algoritmer, som hölls av National Institute of Standards and Technology i USA (  NIST hash function competition , Russian SHA-3 (competition) ). BLAKE blev en av de fem finalisterna i tävlingen ( engelska  finalister ).

Säkerhet

BLAKE hash-funktionen är byggd av tre tidigare inlärda komponenter:

Prestanda och implementering

Prestanda på två olika processorer:

CPU Hastighet (cykler/byte)
BLAKE-256 BLAKE-512
Intel Core i5-2400M (Sandy Bridge) 7,49 5,64
AMD FX-8120 (Bulldozer) 11,83 6,88

Möjlighet att implementera på olika mikrokontroller:

mikrokontroller BLAKE-256 BLAKE-512
RAM(byte) ROM(byte) RAM(byte) ROM(byte)
Cortex-M3-baserad mikrokontroller (32-bitars processor) 280 1320 516 1776
ATmega1284P mikrokontroller (8-bitars processor) 267 3434 525 6350

Prestanda på FPGA ( eng.  FPGA ):

På Xilinx Virtex 5 FPGA är BLAKE-256 implementerad på 56 celler och kan uppnå en genomströmning på mer än 160 Mbps, och BLAKE-512 är implementerad på 108 celler och i hastigheter upp till 270 Mbps.

ASIC prestanda :

Vid 180nm ASIC kan BLAKE-256 implementeras vid 13,5 kGE. På en 90nm ASIC är BLAKE-256 implementerad vid 38 kGE och kan uppnå 10 Gb/s prestanda, medan BLAKE-512 implementeras vid 79 kGE och vid 15 Gb/s [2] .

Algoritm

Som nämnts tidigare är BLAKE-hashfunktionen byggd av de tre tidigare inlärda komponenterna:

Tänk på BLAKE-256-algoritmen [3]

BLAKE-256 arbetar på 32-bitars ord och returnerar en 32-byte hash.

Konstanter

Det finns initiala konstanter, de så kallade. URSPRUNGLIGA VÄRDEN (IV):

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

16 konstanter (första siffrorna i pi):

c 0 = 243F6A88 c 1 = 85A308D3 c 2 = 13198A2E c 3 = 03707344 c 4 = A4093822 c 5 = 299F31D0c6 = 082EFA98 c7 = 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

permutationer {0,…,15} (används i alla BLAKE-funktioner):

σ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

Komprimeringsfunktioner

BLAKE-256-algoritmens komprimeringsfunktion tar som indata:

Således tar den emot 30 ord som inmatning (8+16+4+2=30, 30*4 = 120 byte = 960 bitar). Komprimeringsfunktionen returnerar endast det nya värdet för kedjevariablerna: h' = h' 0 ,…,h' 7 . I det följande kommer vi att beteckna h'=compress(h, m, s, t).

Initiering

16 variabler, v 0 ,…,v 15 , som beskriver det aktuella tillståndet för v , initieras med initiala värden beroende på indata och presenteras som en 4×4 -matris :

←

Runda funktion

Efter att tillståndet v har initierats startas en serie på 14 omgångar. En runda är en tillståndsoperation som utför beräkningar uppdelade i följande block:

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 )

på den fjärde omgången fungerar beräkningsblocket enligt följande:

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

De första fyra blocken G 0 ,..., G 3 kan beräknas parallellt, eftersom vart och ett ändrar sin egen specifika kolumn av tillståndsmatrisvariabler. Låt oss kalla beräkningsproceduren G 0 ,...,G 3 kolumnsteg . På liknande sätt kan G 4 ,..., G 7 beräknas parallellt , men de ändrar i sin tur varje diagonal i tillståndsmatrisen v . Därför kallar vi beräkningsproceduren G 4 ,...,G 7 diagonalsteg . Möjligheten till parallell beräkning av Gi presenteras grafiskt.

På omgångar med siffror r större än 9 används permutationen σ r%10 , till exempel på den 13:e omgången används σ 3 .

Sista steget

Efter alla omgångar beräknas det nya värdet av kedjevariablerna h' 0 ,…,h' 7 från tillståndsmatrisvariablerna, ingångsvariablerna och från saltet :

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 ⊕ 1 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

Meddelandehashning

Låt oss beskriva processen att hasha ett meddelande m med längden l<2^64 bitar. Först utfylls meddelandet med data för en multipel av 512 bitar (64 byte) av utfyllnadsfunktionen , sedan, block för block, bearbetas det av komprimeringsfunktionen .

I utfyllnadsfunktionen utfylls meddelandet först med bitar så att dess längd modulo 512 är lika med 447: först läggs 1 till, sedan det erforderliga antalet nollor. Därefter adderas ytterligare en 1- och 64-bitars representation av meddelandelängden l från den mest signifikanta biten till den minst signifikanta. Således blir meddelandelängden en multipel av 512 [Komm. 1] . Utfyllnad säkerställer att meddelandelängden blir en multipel av 512 bitar.

För att beräkna hashen för meddelandet delas resultatet av utfyllnadsfunktionen in i block med 16 ord m 0 ,...,m N-1 . Låt L i  vara antalet bitar av det ursprungliga meddelandet i block m 0 ,…,m i , det vill säga exklusive de bitar som lades till i utfyllnadsproceduren. Till exempel, om meddelandet har en längd på 600 bitar, kommer det efter utfyllnadsproceduren att ha en längd på 1024 bitar och kommer att delas upp i två block: m 0 och m 1 . Dessutom är Lo = 512, L1 = 600. I vissa fall innehåller det sista blocket inte en bit av det ursprungliga meddelandet. Till exempel, om det ursprungliga meddelandet har 1020 bitar, kommer det, som ett resultat av utfyllnadsproceduren, att ha en längd på 1536 bitar och m 0 kommer att ha 512 bitar av det ursprungliga meddelandet, m 1  - 508 och m 2  - 0 Set Lo = 512, L1 = 1020 och L2 = 0 . Det vill säga, regeln är som följer: om det inte finns några bitar av det ursprungliga meddelandet i det sista blocket, sätt sedan räknaren LN -1 till 0. Detta garanterar att om i ≠ j , så L i ≠ Lj . Saltvärdet är användardefinierat eller satt till 0 om det inte ska användas ( s 0 =s 1 =s 2 =s 3 =0 ). Meddelandets hash beräknas på detta sätt:

h 0 ← IV för i=0,...,N-1 h i+1 ← komprimera(h i ,m i ,s,l i ) returnera h N .

Hashingprocessen presenteras visuellt i flödesschemat:

Algoritmen för 64-bitarsversionen av funktionen är identisk: skiftvärdena är 32, 25, 16 respektive 11, antalet omgångar ökas till 16.

Skillnader från ChaChas quarterround-algoritm

BLAKE hash

BLAKE-512("") = A8CFBBD73726062DF0C6864DDA65DEFE58EF0CC52A5625090FA17601E1EECD1B 628E94F396AE402A00ACC9EAB77B4D4C2E852AAAA25A636D80AF3FC7913EF5B8 BLAKE-512(" Den kvicka bruna räven hoppar över den lata hunden ") = 1F7E26F63B6AD25A0896FD978FD050A1766391D2FD0471A77AFB975E5034B7AD 2D9CCF8DFB47ABBBE656E1B82FBC634BA42CE186E8DC5E1CE09A885D41F43451

BLAKE2

BLAKE2 ( BLAKE2- webbplats ) är en förbättrad version av BLAKE, en av de fem finalisterna i hash-funktionstävlingen SHA-3 (främst förbättrad prestanda), som introducerades den 21 december 2012. Utvecklare: Jean-Philippe Aumasson , Samuel Neves , Zooko Wilcox-O'Hearn och Christian Winnerlein . Det skapades som ett alternativ till MD5 och SHA-1 , som användes flitigt tidigare, där sårbarheter hittades.

Skillnader från BLAKE

I BLAKE2, till skillnad från BLAKE, finns det ingen addition av konstanter i den runda funktionen. Skiftkonstanterna har också ändrats, tillägget har förenklats, ett block med parametrar har lagts till som läggs till initialiseringsvektorerna. Dessutom har antalet omgångar minskat från 16 till 12 för BLAKE2b-funktionen (analogt med BLAKE-512) och från 14 till 10 för BLAKE2:or (analogt med BLAKE-256). Som ett resultat reducerades antalet cykler per bit från 7,49 för BLAKE-256 och 5,64 för BLAKE-512 till 5,34 och 3,32 för Blake2s respektive Blake2b.


BLAKE2 hash

BLAKE2b-512("") = 786A02F742015903C6C6FD852552D272912F4740E15847618A86E217F71F5419 D25E1031AFEE585313896444934EB04B903A685B1448B755D56F701AFE9BE2CE BLAKE2b-512(" Den kvicka bruna räven hoppar över den lata hunden ") = 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

Kommentarer

  1. ↑ Till exempel kommer ett meddelande med en längd på 447 bitar att lägga till 1, sedan 511 nollor (längden blir 447 + 512), sedan ytterligare 1 och en 64-bitars representation av talet l = 447 - 00 ... 0110111111 . Således blir längden lika med 447+512+1+64 = 1024, vilket är en multipel av 512

Källor

  1. ↑ 1 2 BLAKE-dokumentation på den officiella webbplatsen Arkiverad 9 december 2017 på Wayback Machine , s.3 Introduktion.
  2. ↑ BLAKE officiella webbplats . Hämtad 21 december 2013. Arkiverad från originalet 16 april 2018.
  3. ↑ BLAKE-dokumentation på den officiella webbplatsen Arkiverad 9 december 2017 på Wayback Machine , s.8 Specifikation.

Litteratur

Eli Biham och Orr Dunkelman. Ett ramverk för iterativa hashfunktioner - HAIFA . - ePrint, 2007. - 207 sid.

Länkar

 Hash-funktioner
generell mening
Kryptografisk
Nyckelgenereringsfunktioner
Kontrollnummer ( jämförelse )
Hashes