SHA-3

维基百科,自由的百科全书
跳转至: 导航搜索
SHA-3(Keccak)
第三代安全散列算法
作者 Guido Bertoni
Joan Daemen
Michaël Peeters
Gilles Van Assche
摘要尺寸 任意
速度 当 r = 1024, c = 576 时
Intel Core 2 上为
12.5 cpb(每位元組周期數)
结构 海绵函数
NIST 推荐的组合 SHA3-224
SHA3-256
SHA3-384
SHA3-512
SHAKE128
SHAKE256
摘要长度() 224(SHA3-224)
256(SHA3-256)
384(SHA3-384)
512(SHA3-512)
可变长(SHAKE128/SHAKE256)
内部状态 使用一个5×5字节长度为64位的二维矩阵共1600位
块长度(位) 1152
1088
832
576
最大摘要信息长度 不存在
重复回数 24
所需位操作 按位与按位异或取反循环移位
碰撞 未发现

SHA-3,之前名為Keccak(唸作[kɛtʃak],像l“ketchak”)演算法,[1]設計者宣稱在 Intel Core 2 的CPU上面,此演算法的效能是12.5cpb(每位元組周期數,cycles per byte)。[2]不過,在硬體實做上面,這個演算法比起其他演算法明顯的快上很多。[3]

SHA-3 在2015年8月5日由 NIST 通过 FIPS 202 正式发表。[4][5]

历史[编辑]

  • 2012年10月2日,Keccak 被選為NIST雜湊函式競賽的勝利者。[6]SHA-3並不是要取代SHA-2,因為SHA-2目前並沒有出現明顯的弱點。由於對MD5出現成功的破解,以及對SHA-0SHA-1出現理論上破解的方法,NIST感覺需要一個與之前演算法不同的,可替換的加密雜湊演算法,也就是現在的 SHA-3。
  • 2014年,NIST 发布了 FIPS 202 的草案 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"。[7]
  • 2015年8月5日,FIPS 202 最终被 NIST 批准。[8]

设计[编辑]

Keccak 使用海綿函數[9][10],此函數會將資料與初始的內部狀態做XOR運算,這是無可避免可置換的(inevitably permuted)。在最大的版本,演算法使用的內存狀態是使用一個5×5的二維陣列,資料型態是64位元的字節,總計1600位元 。縮版的演算法使用比較小的,以2為冪次的字節大小w為1位元,總計使用25位元。除了使用較小的版本來研究加密分析攻擊,比較適中的大小(例如從w=4使用100位元,到w=32使用800位元)則提供了比較實際且輕量的替代方案。

Keccak 的置換[编辑]

置換方法是先定義的長度為二的某次方,w = 2位元。SHA-3的主要應用使用64位元的字長,ℓ = 6。

內存狀態可以被視為5×5×w的三維陣列。令a[i][j][k]代表內存狀態的第(i×5 + jw + k個位元(使用小端序,little-endian,參見位元組序)。

置換函數是五個子段落(sub-round)作12+2ℓ次的迴圈,每一個子段落都相當簡單:

修改[编辑]

在整個 NIST 雜湊函數比賽裡面,參賽者允許稍微修改演算法解決已經出現的問題。Keccak 的修改有:

  • 迴圈的數目從12+ℓ變成12+2ℓ,以增加安全度。
  • 填充函式使用比起上述10*1的方式更加複雜的作法。
  • 吸收比率r增加到安全限制,而非向下捨入到最接近某個2的冪次。

SHA-3 範例[编辑]

  • 空字串的雜湊值:
SHA3-224("")
6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256("")
a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384("")
0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512("")
a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
SHAKE128("", 256)
7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
SHAKE256("", 512)
46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be
  • 由於雪崩效應,即使一個很小的改變都會產出幾乎完全不同的雜湊值。舉例來說,把 dog 改成 dof:
SHAKE128("The quick brown fox jumps over the lazy dog", 256)
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
SHAKE128("The quick brown fox jumps over the lazy dof", 256)
853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

SHA 家族函数的比较[编辑]

在下面的表格中,“内部状态”指的是传递到下一个块的位数。

SHA 家族函数的比较
算法及其变体 输出长度
(位)
内部状态大小
(位)
块大小
(位)
最大消息长度
(位)
循环 操作 安全性
(位)
示例的性能[12]
(MiB/s)
MD5
(作为参考)
128 128
(4 × 32)
512 264 − 1 64 按位与, 按位异或, 循环移位, 填充(求模 232), 按位或 <64
(已发现碰撞)
335
SHA-0 160 160
(5 × 32)
512 264 − 1 80 按位与, 按位异或, 循环移位, 填充(求模 232),按位或 <80
(已发现碰撞)
-
SHA-1 160 160
(5 × 32)
512 264 − 1 80 <80
(出现 261 计算复杂度的理论攻击[13])
192
SHA-2 SHA-224
SHA-256
224
256
256
(8 × 32)
512 264 − 1 64 按位与, 按位异或, 循环移位, 填充(求模 232), 按位或, 移位 1
112/128
139
SHA-384
SHA-512
SHA-512/224
SHA-512/256
384
512
224
256
512
(8 × 64)
1024 2128 − 1 80 按位与, 按位异或, 循环移位, 填充(求模 264), 按位或, 移位 1
192/256/112/128
154
SHA-3 SHA3-224
SHA3-256
SHA3-384
SHA3-512
224
256
384
512
1600
(5 × 5 × 64)
1152
1088
832
576
无限制 24 按位与, 按位异或, 循环移位, 取反 1
112/128/192/256
-
SHAKE128
SHAKE256
d (可变长)
d (可变长)
1344
1088
1
min (d/2, 128)
min (d/2, 256)
-

參考資料[编辑]

  1. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. The Keccak sponge function family: Specifications summary. [2011-05-11]. 
  2. ^ Keccak implementation overview Version 3.2 http://keccak.noekeon.org/Keccak-implementation-3.2.pdf
  3. ^ Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick, Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations, NIST 2nd SHA-3 Candidate Conference, 2010-Aug.: 12 [2011-02-18]  Keccak is second only to Luffa, which did not advance to the final round.
  4. ^ http://www.nist.gov/itl/csd/201508_sha3.cfm
  5. ^ http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061
  6. ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. [2012-10-02]. 
  7. ^ SHA-3 standardization. NIST. [2015-04-16]. 
  8. ^ National Institute of Standards and Technology. Federal Information Processing Standards: Permutation-Based Hash and Extendable-Output Functions, etc.. Aug 5, 2015 [5 Aug 2015]. 
  9. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. Sponge Functions. Ecrypt Hash Workshop 2007. 
  10. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. On the Indifferentiability of the Sponge Construction. EuroCrypt 2008. 
  11. ^ Crypto++ 5.6.0 Benchmarks. [2013-06-13]. 
  12. ^ AMD Opteron 8354 2.2 GHz 处理器上运行64位 Linux[11]
  13. ^ Cryptanalysis of MD5 & SHA-1 (PDF). [2013-04-25]. 

外部連接[编辑]