BLAKE及BLAKE2演算法詳解
- 2020 年 3 月 6 日
- 筆記
1 簡介
哈希演算法 (Hash Algorithm) 是將任意長度的數據映射為固定長度數據的演算法，也稱為消息摘要。
一般情況下，哈希演算法有兩個特點：
- 原始數據的細微變化（比如一個位翻轉）會導致結果產生巨大差距
- 運算過程不可逆，理論上無法從結果還原輸入數據
因此，哈希演算法主要用於數據完整性校驗和加密/簽名。而哈希演算法的安全性就在於碰撞難易度，即已知結果，構建出具有相同結果的輸入數據的難易度。
2 BLAKE
BLAKE演算法於2008年提出，它包含兩個版本，一種基於32位word用於產生最長256位的哈希結果，一種基於64位word用於產生最長512位的哈希結果，BLAKE演算法核心操作是不斷地將8個散列中間結果和16個輸入word進行組合，從而產生下一輪組合的8個中間結果。按照最終截斷的哈希長度，BLAKE-256和BLAKE-224使用32位字分別產生256位和224位的哈希結果（也稱消息摘要），而BLAKE-512和BLAKE-384使用64位字併產生512位和384位哈希結果。演算法核心變數如下：
1 typedef struct 2 { 3 uint32_t h[8], s[4], t[2]; 4 int buflen, nullt; 5 uint8_t buf[64]; 6 } state256; 7 8 typedef state256 state224; 9 10 typedef struct 11 { 12 uint64_t h[8], s[4], t[2]; 13 int buflen, nullt; 14 uint8_t buf[128]; 15 } state512; 16 17 typedef state512 state384; 18 19 const uint8_t sigma[][16] = 20 { 21 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, 22 {14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 }, 23 {11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 }, 24 { 7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 }, 25 { 9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 }, 26 { 2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 }, 27 {12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11 }, 28 {13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10 }, 29 { 6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5 }, 30 {10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13 , 0 }, 31 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, 32 {14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 }, 33 {11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 }, 34 { 7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 }, 35 { 9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 }, 36 { 2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 } 37 }; 38 39 const uint32_t u256[16] = 40 { 41 0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344, 42 0xa4093822, 0x299f31d0, 0x082efa98, 0xec4e6c89, 43 0x452821e6, 0x38d01377, 0xbe5466cf, 0x34e90c6c, 44 0xc0ac29b7, 0xc97c50dd, 0x3f84d5b5, 0xb5470917 45 }; 46 47 const uint64_t u512[16] = 48 { 49 0x243f6a8885a308d3ULL, 0x13198a2e03707344ULL, 50 0xa4093822299f31d0ULL, 0x082efa98ec4e6c89ULL, 51 0x452821e638d01377ULL, 0xbe5466cf34e90c6cULL, 52 0xc0ac29b7c97c50ddULL, 0x3f84d5b5b5470917ULL, 53 0x9216d5d98979fb1bULL, 0xd1310ba698dfb5acULL, 54 0x2ffd72dbd01adfb7ULL, 0xb8e1afed6a267e96ULL, 55 0xba7c9045f12c7f99ULL, 0x24a19947b3916cf7ULL, 56 0x0801f2e2858efc16ULL, 0x636920d871574e69ULL 57 }; 58 59 60 static const uint8_t padding[129] = 61 { 62 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 63 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 64 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 65 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 66 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 67 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 68 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 69 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 70 };
blake256核心計算過程如下：
1 void blake256_compress( state256 *S, const uint8_t *block ) 2 { 3 uint32_t v[16], m[16], i; 4 #define ROT(x,n) (((x)<<(32-n))|( (x)>>(n))) 5 #define G(a,b,c,d,e) 6 v[a] += (m[sigma[i][e]] ^ u256[sigma[i][e+1]]) + v[b]; 7 v[d] = ROT( v[d] ^ v[a],16); 8 v[c] += v[d]; 9 v[b] = ROT( v[b] ^ v[c],12); 10 v[a] += (m[sigma[i][e+1]] ^ u256[sigma[i][e]])+v[b]; 11 v[d] = ROT( v[d] ^ v[a], 8); 12 v[c] += v[d]; 13 v[b] = ROT( v[b] ^ v[c], 7); 14 15 for( i = 0; i < 16; ++i ) m[i] = U8TO32_BIG( block + i * 4 ); 16 17 for( i = 0; i < 8; ++i ) v[i] = S->h[i]; 18 19 v[ 8] = S->s[0] ^ u256[0]; 20 v[ 9] = S->s[1] ^ u256[1]; 21 v[10] = S->s[2] ^ u256[2]; 22 v[11] = S->s[3] ^ u256[3]; 23 v[12] = u256[4]; 24 v[13] = u256[5]; 25 v[14] = u256[6]; 26 v[15] = u256[7]; 27 28 /* don't xor t when the block is only padding */ 29 if ( !S->nullt ) 30 { 31 v[12] ^= S->t[0]; 32 v[13] ^= S->t[0]; 33 v[14] ^= S->t[1]; 34 v[15] ^= S->t[1]; 35 } 36 37 for( i = 0; i < 14; ++i ) 38 { 39 /* column step */ 40 G( 0, 4, 8, 12, 0 ); 41 G( 1, 5, 9, 13, 2 ); 42 G( 2, 6, 10, 14, 4 ); 43 G( 3, 7, 11, 15, 6 ); 44 /* diagonal step */ 45 G( 0, 5, 10, 15, 8 ); 46 G( 1, 6, 11, 12, 10 ); 47 G( 2, 7, 8, 13, 12 ); 48 G( 3, 4, 9, 14, 14 ); 49 } 50 51 for( i = 0; i < 16; ++i ) S->h[i % 8] ^= v[i]; 52 53 for( i = 0; i < 8 ; ++i ) S->h[i] ^= S->s[i % 4]; 54 }
詳細實現可參考網上開源程式碼，BLAKE源碼：https://github.com/veorq/BLAKE
四種演算法對空字元串的哈希結果如下：
BLAKE-224("") = 7dc5313b1c04512a174bd6503b89607aecbee0903d40a8a569c94eed BLAKE-256("") = 716f6e863f744b9ac22c97ec7b76ea5f5908bc5b2f67c61510bfc4751384ea7a BLAKE-384("") = c6cbd89c926ab525c242e6621f2f5fa73aa4afe3d9e24aed727faaadd6af38b620bdb623dd2b4788b1c8086984af8706 BLAKE-512("") = a8cfbbd73726062df0c6864dda65defe58ef0cc52a5625090fa17601e1eecd1b628e94f396ae402a00acc9eab77b4d4c2e852aaaa25a636d80af3fc7913ef5b8
3 BLAKE2
BLAKE2演算法基於BLAKE演算法，於2012年被提出，BLAKE2不再向blake round函數中對輸入字添加常量，修改了兩個旋轉常量及padding等，並在BLAKE2b（對應BLAKE-512）中將rounds的數量由16減少為12，在BLAKE2s（對應BLAKE-256）中將rounds數量由14減少為10，同樣的，BLAKE2b產生1到64位元組的消息摘要，BLAKE2s產生1到32位元組的消息摘要，同時這兩種演算法也由對應的多核並行版本BLAKE2bp（4路並行）和BLAKE2sp（8路並行）。除了以上幾種演算法變種，BLAKE2還有一種BLAKE2x的變種，這種演算法可以產生任意長度的消息摘要，詳情請參考相應文檔。除了安全性方面的優勢，據稱BLAKE2演算法在Intel CPU第六代微處理架構（Skylake）中的處理速度要優於MD5，SHA-1，SHA-2和SHA-3等演算法，如圖所示：
BLAKE2源碼可以參考：https://github.com/BLAKE2/BLAKE2，類似的，BLAKE2對空字元串的哈希結果如下：
BLAKE2s-224("") = 1fa1291e65248b37b3433475b2a0dd63d54a11ecc4e3e034e7bc1ef4 BLAKE2s-256("") = 69217a3079908094e11121d042354a7c1f55b6482ca1a51e1b250dfd1ed0eef9 BLAKE2b-384("") = b32811423377f52d7862286ee1a72ee540524380fda1724a6f25d7978c6fd3244a6caf0498812673c5e05ef583825100 BLAKE2b-512("") = 786a02f742015903c6c6fd852552d272912f4740e15847618a86e217f71f5419d25e1031afee585313896444934eb04b903a685b1448b755d56f701afe9be2ce
4 應用
BLAKE系列演算法被廣泛應用於區塊鏈數字貨幣領域，下面介紹3中典型數字貨幣：
1 decred
以blake256為核心哈希演算法，其主頁為：https://decred.org/
2 sia
以blake2b為核心哈希演算法，其主頁為：https://sia.tech/
3 verge
以blake2s為核心哈希演算法，其主頁為：https://vergecurrency.com/
至於具體哈希演算法在各個幣種應用細節，請參考相關錢包的源程式碼。
參考：
1 https://en.wikipedia.org/wiki/BLAKE_(hash_function)
