首頁>編程相關>C#源碼
下載

哈希器

哈希函數MiB/秒循環/哈希循環/地圖尺寸品質問題
什麼也不做32 11149460.06 4.00 - 13壞種子 0，測試 NOP
什麼也不做64 11787676.42 4.00 - 13壞種子 0，測試 NOP
什麼也不做128 11745060.76 4.06 - 13壞種子 0，測試 NOP
NOP_OAAT_read64 11372846.37 14:00 - 47測試NOP
壞哈希769.94 73.97 - 47壞種子 0，測試失敗
總哈希值10699.57 29.53 -第363章壞種子 0，測試失敗
總哈希32 42877.79 23.12 -第863章UB，測試失敗
乘法移位8026.77 26.05 226.80 (8)第345章壞種子 & 0xffffffff0，大多數測試失敗
配對乘法移位3716.95 40.22 186.34 (3) 609大多數測試失敗
--------------------------




CRC32 383.12 134.21 257.50 (11)第422章不安全、8590x 碰撞、distrib、PerlinNoise
md5_32 350.53 644.31 894.12 (10) 4419
md5_64 351.01 656.67 897.43 (12) 4419
MD5-128 350.89 681.88 894.03 (13) 4419
sha1_32 353.03 1385.80 1759.94 (5) 5126理智，循環低 32，分佈 36.6%
sha1_64 353.03 1385.80 1759.94 (5) 5126理智，循環低 32，分佈 36.6%
sha1-160 364.95 1470.55 1794.16 (13) 5126梳狀/循環 low32
sha2-224 147.13 1354.81 1589.92 (12)
梳低32
sha2-224_64 147.60 1360.10 1620.93 (13)
循環低32
sha2-256 147.80 1374.90 1606.06 (16)

sha2-256_64 148.01 1376.34 1624.71 (16)

沙尼1601.21 174.16 397.28 (6) 989不安全、理智、排列、零、特定於機器
sha1ni_32 1576.17 174.04 405.56 (6) 989機器特定的
sha2ni-256 1527.38 184.35 404.40 (4) 4241不安全、理智、排列、零、特定於機器
sha2ni-256_64 1501.85 186.20 407.96 (5) 4241零點，特定於機器
布萊克3_c 1288.84 357.69 582.89 (6)
沒有 32 位元可移植性
128元290.90 710.49 965.55 (6)

RM160 202.16 1045.79 1287.74 (16)
循環hi32
RM256 364.81 584.86 835.02 (11)

edonr224 864.69 303.42 526.94 (6)

edonr256 847.85 305.79 510.01 (4)

布萊克2S-128 295.30 698.09 1059.24 (51)

布萊克2S-160 215.01 1026.74 1239.54 (11)

布萊克2S-224 207.06 1063.86 1236.50 (20)

布萊克2S-256 215.28 1014.88 1230.38 (28)

blake2s-256_64 211.52 1044.22 1228.43 (8)

布萊克2b-160 356.08 1236.84 1458.15 (12)

布萊克2b-224 356.59 1228.50 1425.87 (16)

布萊克2b-256 355.97 1232.22 1443.31 (19)

布萊克2b-256_64 356.97 1222.76 1435.03 (9)

asconhashv12 144.98 885.02 1324.23 (38) 4341
asconhashv12_64 159.68 386.90 480.86 (4) 6490
sha3-256 100.58 3877.18 4159.79 (37)
柏林噪音
sha3-256_64 100.57 3909.00 4174.63 (16)
柏林噪音
哈斯謝2 2773.89 64.35 282.30 (3)第445章排列、雙字節、零、種子
聚_1_梅森1369.21 61.59 248.86 (4)第479章大多數測試失敗
聚_2_梅森1364.03 70.30 261.00 (6)第479章
聚_3_梅森1342.82 80.22 268.79 (2)第479章
聚_4_梅森1343.19 89.13 277.52 (3)第479章
製表32 5781.16 40:00 241.79 (10)第848章碰撞
製表7875.01 39.95 249.49 (3)第554章
crc32_hw 6244.38 41.23 226.80 (2)第653章不安全、100% 偏差、衝突、分佈、BIC、機器特定 (SSE4.2/NEON)
crc32_hw1 7569.29 49.07 233.75 (3)第671章不安全、100% 偏差、衝突、distrib、BIC、機器特定 (x86 SSE4.2)
crc64_hw 6143.62 40.48 223.13 (2)第652章不安全、100% 偏差、衝突、分佈、BIC、機器特定 (SSE4.2/NEON)
crc32_pclmul - - -
不安全、100% 偏差、衝突、distrib、BIC、機器特定 (x86 SSE4.2+PCLMUL)
o1hash 11629440.57 18.15 199.35 (2) 101不安全，沒有種子，零，所有測試都失敗
斐波那契16878.32 22.94 803.18 (15)第1692章UB，零，所有測試均未通過
FNV1a 760.52 73.83 254.29 (5) 204壞種子，零，所有測試都失敗
FNV1A_托滕希夫6274.78 26.23 251.13 (2) 270 UB，零，所有測試均未通過
FNV1A_皮皮_尤里6172.14 27.55 244.80 (2) 147 UB，理智，未通過所有測試
FNV1a_YT 13486.49 30.50 237.43 (4) 321壞種子，UB，未通過所有測試
FNV2 6171.60 32.20 208.59 (4) 278所有測試均未通過
FNV64 774.37 72.43 201.15 (2) 79所有測試均未通過
FNV128 390.14 136.42 289.00 (3) 171所有測試均未通過
k-hash32 2230.42 53.05 264.64 (3) 808不安全、零、UB、壞種子、所有測試都失敗
k-hash64 2451.88 48.66 249.44 (2) 609不安全、零、UB、壞種子、所有測試都失敗
弗萊契2 15552.61 20.61 335.31 (3) 248壞種子 0，UB，所有測試失敗
弗萊契4 15556.93 20.60 358.60 (3)第371章壞種子 0，UB，所有測試失敗
伯恩斯坦1045.97 58.31 225.78 (3) 41壞種子 0，所有測試失敗
南德邦784.83 68.57 222.68 (5) 41壞種子 0，所有測試失敗
x17 748.75 74.13 236.00 (10) 79 99.98% 偏差，未通過所有測試
自由628.66 84.95 225.07 (4) 37不安全、100% 偏見、未通過所有測試、不良種子
海灣合作委員會611.69 86.47 231.51 (5) 39不安全、100% 偏見、未通過所有測試、不良種子
詹金斯OOAT 627.64 107.04 252.79 (3) 153壞種子 0，偏差 53.5%，所有測試均失敗
JenkinsOOAT_perl 608.10 94.17 254.09 (4) 65壞種子 0、1.5-11.5% 偏差、7.2x 衝突、BIC、LongNeighbors
微OAAT 701.35 76.68 251.01 (3) 68 100% 偏差、分佈、BIC
皮爾遜哈希64 434.17 124.14 230.79 (4)
僅限雪崩、種子、SSSE3。損壞的MSVC
皮爾遜哈希128 434.23 121.34 221.03 (7)
僅限雪崩、種子、SSSE3。損壞的MSVC
皮爾遜哈希256 444.08 119.11 229.75 (4)
僅限雪崩、種子、SSSE3。損壞的MSVC
VHASH_32 13053.40 65.84 289.86 (3) 1231理智, 種子, MomentChi2
VHASH_64 13465.50 63.88 286.38 (5) 1231理智、種子、稀疏
法什32 27038.23 66.88 278.89 (5)第944章不安全：AppdedZeroes、碰撞+偏差、MomentChi2、LongNeighbors
法什64 13829.32 112.46 332.59 (3)第944章不安全：AppdedZeroes、碰撞+偏差、MomentChi2、LongNeighbors
法什128 6878.88 233.35 384.85 (3)第944章不安全：附加零、碰撞+偏差、排列、組合、2位元組、零、PerlinNoise
法什256 3467.37 440.40 593.57 (5)第944章不安全：附加零、碰撞+偏差、排列、組合、2位元組、零、PerlinNoise
喬迪哈希32 1794.34 41.12 235.12 (4) 102偏差、碰撞、分佈、BIC LongNeighbors
喬迪哈希64 4813.10 40.72 239.22 (6) 118偏差、碰撞、分佈、BIC、LongNeighbors
找3 2475.35 39.65 240.10 (3)第341章UB、28% 偏差、碰撞、30% 分佈、BIC
超快2058.22 49.56 254.12 (3) 210 UB，壞種子 0，91% 偏差，5273.01x 衝突，37% 分佈，BIC
雜音OAAT 506.66 103.33 236.89 (3) 47壞種子 0、衝突、99.998% 分佈、BIC、LongNeighbors
廢話8 3041.14 37.25 247.87 (4)第342章UB，2.42% 偏差，碰撞，2% 分佈
雜音1 2027.85 48.51 253.34 (3)第358章UB、1 壞種子、511x 衝突、Diff、BIC
雜音2 3089.18 41.22 238.42 (4)第358章UB，1 個壞種子，1.7% 偏差，81x coll，1.7% distrib，BIC
雜音2A 3087.98 45.90 238.54 (4) 407 UB，1 個壞種子，12.7% 偏差，LongNeighbors
雜音2B 5919.38 38.18 215.96 (3)第433章UB、1.8% 偏差、碰撞、3.4% 分佈、BIC
雜音2C 3810.98 49.09 218.51 (3)第444章UB、2^32 壞種子、91% 偏差、碰撞、distr、BIC、LongNeighbors
雜音3A 2982.67 49.08 245.78 (4)第351章UB，1 顆壞種子，Moment Chi2 69
PMurHash32 3005.85 48.88 242.38 (3) 1862年1 顆壞種子，Moment Chi2 69
雜音3C 4833.18 56.87 250.47 (6)第859章UB、LongNeighbors、文字、DiffDist
mirhash32low 6145.39 36.95 235.09 (4) 1112 UB、4 個壞種子、循環、LongNeighbors、機器特定（32/64 不同）
PMPML_32 6639.68 45.33 257.45 (3) 1084 Avalanche >512，非種子：Seed、BIC、MomentChi2、PerlinNoise
PMPML_64 9833.77 50.00 251.64 (6) 1305非種子：Seed、MomentChi2、BIC
xxHash32 5865.17 49.20 242.74 (3)第738章LongNeighbors，與 4 位元 diff 的碰撞，MomentChi2 220
地鐵哈希64 14741.56 39.44 215.76 (2) 624 UB、長鄰居、BIC
Metrohash64_1 14298.77 40.31 223.25 (4) 624 UB、LongNeighbors、BIC、MomentChi2
Metrohash64crc_1 6929.69 44.65 223.68 (3)第632章UB、循環 8/8 位元組、DiffDist、BIC、MomentChi2、機器特定 (SSE4.2/NEON)
Metrohash64crc_2 8150.65 43.72 219.45 (5)第632章UB、循環 8/8 位元組、DiffDist、BIC、機器特定 (SSE4.2/NEON)
cmetrohash64_1o 14921.73 38.95 213.25 (2) 3506 UB、LongNeighbors、BIC、MomentChi2
cmetrohash64_1 14151.73 40.90 211.89 (2)第652章UB、LongNeighbors、BIC、MomentChi2
城市64無種子14209.19 31.80 225.90 (5) 1038 Avalanche、稀疏、TwoBytes、MomentChi2、種子
城市64 13887.84 46.32 239.77 (3) 1120稀疏，兩個位元組
t1ha1_64le 13442.64 31.41 219.58 (3)第517章雪崩
t1ha1_64be 11586.02 32.74 232.55 (3)第555章雪崩
t1ha0_32le 7401.21 48.27 238.99 (3) 509鄰居稀少，鄰居長
t1ha0_32be 6217.37 50.66 244.51 (3)第533章鄰居稀少，鄰居長
t1ha2_stream 14011.63 80.72 275.17 (3) 1665稀疏、排列、長鄰居
t1ha2_stream128 13136.06 97.80 306.11 (7) 1665稀疏、排列、長鄰居
埃斯尼哈希5579.32 56.83 258.71 (5) 1209未通過許多特定於機器的測試 (x64 AES-NI)
法爾哈什50631.69 123.02 322.14 (7) 264稀疏、LongNeighbors、機器特定 (x64 AES-NI)
喵哈什29969.40 64.96 274.29 (4) 1764稀疏、可逆、機器特定 (x64 AES-NI)
喵哈斯64low 29485.59 65.98 278.05 (3) 1764稀疏、可逆、機器特定 (x64 AES-NI)
喵哈希32low 26944.58 65.95 292.79 (9) 1764稀疏、可逆、機器特定 (x64 AES-NI)
--------------------------------------




tifuhash_64 35.60 1679.52 1212.75 (15) 276循環低32
軟碟哈希值35.72 1868.92 1411.07 (7) 623
分束器789.22 682.45 1150.33 (26) 4203 UB
迪斯可哈希1 4131.12 199.00 398.35 (5) 1294
discoash1-128 4072.95 234.17 438.43 (5) 1294
迪斯可哈希2 3986.52 207.52 421.99 (2) 1294
discoash2-128 4094.73 236.61 433.35 (4) 1294
迪斯可農3698.45 399.67 597.78 (9)
壞種子
查斯基1143.05 113.70 294.43 (4) 1609柏林噪音
西普哈希943.53 147.15 338.74 (4) 1071
半吸哈希1141.57 79.65 263.96 (3) 700零點
好OAAT 743.81 85.62 231.22 (3)第237章
皮爾森巴什64 1794.83 97.80 268.90 (8)第683章
皮爾遜巴什128 1691.62 104.57 272.38 (4) 1134
皮爾森巴什256 1442.59 126.04 309.34 (4)第844章
prvhash64_64m 3077.18 47.31 241.92 (3)第349章
prvhash64_64 3015.08 48.03 240.64 (3)第384章
prvhash64_128 3353.81 67.64 266.32 (2) 718
prvhash64s_64 6591.34 273.50 464.65 (3) 2640
prvhash64s_128 6581.40 333.83 528.07 (5) 2799
SipHash13 1812.75 106.56 310.76 (5)第778章0.9% 偏差
TSip 4233.17 53.31 249.19 (3​​) 519 !msvc
海哈希8261.80 58.94 256.08 (4)第871章PerlinNoise，！
海哈希32low 8266.17 58.90 290.21 (16)第871章PerlinNoise 32，！
衝突18703.04 70.19 282.12 (6) 1809年PerlinNoise，特定於機器 (x64 SSE4.2)
高速公路哈希64 6242.58 99.55 248.41 (3) 2546
雜音3F 7623.44 52.69 221.87 (3) 699 UB
媽媽9563.99 34.99 228.55 (5) 1912年UB，壞種子太多，特定於機器（32/64 不同）
穆爾低9261.89 36.17 247.66 (4) 1912年UB，5顆壞種子
xmsx32 2039.10 46.39 249.30 (7) 192 2顆壞種子
米爾哈什6139.07 37.02 209.47 (3) 1112 UB、2^36 壞種子、LongNeighbors、機器特定（32/64 不同）
米爾哈什嚴格3549.01 49.99 224.91 (2) 1112
mirhashstrict32low 3441.35 50.60 247.19 (3​​) 1112 1 顆壞種子，MomentChi2 9
快散列32 6128.28 40.30 241.64 (4)第566章UB
快哈希64 5818.92 38.70 220.74 (2) 509 UB
埃斯尼31232.34 29.21 230.14 (4) 519機器特定 (x64 AES-NI)
埃斯尼洛31221.14 29.64 226.18 (3) 519機器特定 (x64 AES-NI)
MX3 9034.90 48.71 227.89 (2)第734章UB
彭吉哈希13428.80 74.24 275.42 (5)第421章
城市32 5551.28 54.40 261.64 (2) 1319
城市64低13904.10 46.24 260.08 (3) 1120
城市128 14031.96 89.09 290.05 (10) 1841年
城市CRC128 7916.44 55.50 240.79 (2) 295
FarmHash32 21755.58 47.54 258.35 (3) 11489機器特定（x64 SSE4/AVX）
農場哈希64 12845.53 47.11 251.58 (3) 3758
農場哈希128 13913.65 70.25 263.06 (3) 163
farmhash32_c 21601.86 47.38 273.00 (3)第762章機器特定（x64 SSE4/AVX）
farmhash64_c 12834.10 47.23 246.20 (2) 3688
farmhash128_c 13753.24 68.96 263.76 (3) 1890年
Metrohash64_2 14316.37 40.23 218.28 (3) 627 UB，長鄰居
cmetrohash64_2 14294.26 40.76 221.40 (4)第655章長鄰居
地鐵哈希128 15634.66 73.28 261.23 (4)第773章UB，長鄰居
Metrohash128_1 15806.97 72.30 260.90 (4)第773章UB，長鄰居
Metrohash128_2 15822.60 72.30 255.34 (3)第773章UB，長鄰居
Metrohash128crc_1 8009.23 78.72 281.55 (13)第723章UB，機器特定（SSE4.2/NEON）
Metrohash128crc_2 7878.22 79.90 275.22 (4)第723章UB，機器特定（SSE4.2/NEON）
xxHash64 12108.87 49.78 228.83 (2) 1999年
幽靈32 13108.95 56.27 255.36 (3) 2221 UB
幽靈64 13529.36 58.76 236.31 (3) 2221 UB
幽靈128 11781.35 58.91 242.91 (3) 2221 UB
幽靈V2_32 13529.16 55.55 248.37 (4) 2069
幽靈V2_64 12678.82 56.71 243.21 (4) 2069
幽靈V2_128 13512.82 58.33 244.56 (5) 2069
ahash64 9862.62 27.32 181.68 (1)第412章鏽
xxh3 21033.55 29.48 226.77 (4)第744章DiffDist 位元 7 w. 36位，BIC
xxh3低17093.19 30.57 242.07 (7)第756章
xxh128 18802.16 32.37 234.30 (4) 1012
xxh128低18833.05 32.30 234.68 (3) 1012
t1ha2_atonce 13854.44 37.92 233.54 (2)第541章零低3
t1ha2_atonce128 14148.42 55.70 253.74 (6) 613長鄰居
t1ha0_aes_noavx 27231.59 37.70 236.10 (3) 925 LongNeighbors，特定於機器 (x86 AES-NI)
t1ha0_aes_avx1 22714.85 48.12 226.52 (16)第843章LongNeighbors，特定於機器的 (x64 AVX.txt)
t1ha0_aes_avx2 56919.46 36.70 233.14 (2)第792章LongNeighbors，特定於機器 (x64 AVX2)
wyhash32 2532.89 48.40 484.57 (1)第426章4 個壞的和損壞的種子，32 位
wyhash32low 22393.77 29.04 243.40 (3)第474章5顆壞種子
威哈什22540.23 28.87 236.16 (8)第474章
快速哈希23789.79 22.80 138.71 (7)第574章
rapidhash_展開23892.88 23.41 139.47 (12)第782章
烏馬什32 21427.57 42.12 255.55 (5) 1530
umash32_hi 21483.12 42.65 251.09 (4) 1530
烏馬什64 21690.08 41.67 238.01 (4) 1530
烏馬什128 13211.88 43.37 237.40 (3) 1530
halftime_hash64 4735.63 99.90 315.34 (3) 2911
halftime_hash128 17534.53 97.97 311.10 (4) 2462
halftime_hash256 18003.39 99.46 315.09 (3) 2622
halftime_hash512 10890.15 118.05 333.45 (3) 3550
nmhash32 12969.62 55.88 265.69 (4) 2445
nmhash32x 12775.08 42.66 246.05 (3)第1494章
k-hashv32 9181.87 52.76 245.14 (3) 1280
k-hashv64 7850.92 46.94 193.94 (1)第1279章
科米哈希12242.78 33.02 236.07 (2) 1323
波利穆爾9676.33 42.70 246.53 (3) 1128

可排序表變體：

  • 預設AMD Ryzen 5 3350G 3.6GHz

  • 英特爾 i5-2300 2.8GHz

  • 英特爾 i5-2300 2.8GHz 32 位

  • AMD 銳龍 3 3200U 3.5GHz

  • Mac Air i7-4650

  • Cortex-A53 2GHz（Sony XPeria L4）

概括

我添加了一些 SSE 輔助哈希值和快速 intel/arm CRC32-C、AES 和 SHA 硬體變體。另請參閱舊的 https://github.com/aappleby/smhasher/wiki、改進但未維護的分支 https://github.com/demerphq/smhasher 以及新的改進版本 SMHasher3 https://gitlab.com/ fwojcik/smhasher3。

所以x86_64上最快且沒有品質問題的雜湊函數是：

  • rapidhash（改進的 wyhash）

  • xxh3低

  • 威哈什

  • umash（甚至是通用的！）

  • ahash64

  • t1ha2_atonce

  • 科米哈希

  • FarmHash（不可移植，太特定於機器：64 與 32 位，舊的 gcc，... ）

  • halftime_hash128

  • 幽靈32

  • 彭吉哈希

  • nmhash32

  • MX3

  • MUM/mir（ 32/64 位元架構上的不同結果，需要過濾掉大量不良種子）

  • 快散列32

符號表或哈希表的雜湊函數通常使用 32 位元哈希，資料庫、檔案系統和檔案校驗和通常使用 64 或 128 位，加密現在從 256 位元開始。

perl5 中鍵大小的典型中位數是 20，最常見的是 4。請參閱 github.com/rurban/perl-hash-stats

當在哈希表中使用時，指令快取通常會擊敗此處測量的 CPU 和吞吐量。在我的測試中，最小的FNV1A擊敗了帶有 Perl 5 哈希表的最快的crc32_hw1 。即使那些較差的雜湊函數會導致更多的衝突，但整體速度優勢和內聯能力勝過品質稍差的雜湊函數。請參閱哈希方法的七維分析及其對查詢處理的影響，以簡要概述最佳哈希表策略，確認最簡單的Mult 哈希（bernstein、FNV*、x17、sdbm）始終擊敗“更好”的哈希函數（製表、雜音、農場…）在哈希表中使用時。

此處測試的快速雜湊函數對於文件摘要和可能更大的資料庫來說是建議的，但對於 32 位元雜湊表來說則不然。 「品質問題」導致分佈不均勻，即更多的衝突和更差的性能，但很少與真正的安全攻擊相關，只有針對 � 第二個理智 AppendZeroes 測試與安全相關。

專欄

MiB/秒：使用 262144 位元組密鑰進行對齊 0-7 的批次密鑰速度測試的平均值。越高越好。

循環/散列：1-31 位元組密鑰的小密鑰速度測試的平均值。越小越好。

cycl./map：使用快速 C++ hashmap get 查詢對 /usr/dict/words 進行 Hashmap 測試的結果，括號中為標準差。這在實踐中測試了雜湊函數的不可連結性（參見 size）。越小越好。

size：AMD64 上的物件大小（以位元組為單位）。這會影響哈希表等的不可連結性。越小越好。

品質問題：請參閱連結文件中的故障。越少越好。

其他

  • https://github.com/martinus/better-faster-stronger-mixer 混音器。在他的部落格中提供了最好的 C++ hashmap 基準測試。

  • http://nohatcoder.dk/2019-05-19-1.html 給了一個新的、有用的哈希級別分類 1-5。

  • http://www.strchr.com/hash_functions 列出了最簡單和快速雜湊函數的其他基準和品質。

  • http://bench.cr.yp.to/primitives-hash.html 列出了所有目前測試的安全雜湊的基準。

  • http://valerieaurora.org/hash.html 加密雜湊函數的生命週期

安全

這裡不包括 SipHash 中針對 City、Murmur 或 Perl JenkinsOAAT 或 Hash Function Lounge 的哈希表攻擊。我們在 GH #186 中列出了一些已知的攻擊。

這樣的攻擊避免不可能是雜湊函數的問題，而只是哈希表衝突解決方案的問題。 您可以攻擊每個雜湊函數，即使是最好和最安全的雜湊函數，如果您偵測到種子，例如來自語言（錯誤）特徵、旁道攻擊、衝突計時和獨立的排序順序，因此您需要保護您的衝突最壞情況 O(n) 的處理方案，即使用鍊錶進行單獨連結。鍊錶連結允許高負載因子，但對快取非常不友善。 唯一值得推薦的鍊錶方案是將鍵或雜湊內聯到陣列中。現在每個人都使用快速開放尋址，即使負載因子需要 ~50%，除非您使用 Cuckoo Hashing。

即，Python 3.4、ruby、rust、systemd、OpenDNS、Haskell 和 OpenBSD 中使用 SipHash 作為雜湊表是純粹的安全劇場。 SipHash 對於安全目的來說不夠安全，對於一般用途來說也不夠快。對於所有這些哈希，暴力生成約 32k 衝突需要 2-4m。 siphash 是最慢的，最多需要 4m，其他通常最多 2m30s，對於所有雜湊函數的實際 16k 衝突攻擊，<10s。 即使在最壞的情況下，使用 Murmur 通常比簡單的 Mult 慢。 可以證明安全的只是統一雜湊，即2-5個獨立的Mult或Tabulation，或使用有保證的對數碰撞方案（樹）或線性碰撞方案，例如帶有碰撞計數的swisstable/folly-F14、Robin Hood或Cuckoo散列。

關於安全性的另一點注意事項：如今，甚至 SHA1 也可以在解算器中求解，例如用於實際雜湊表衝突攻擊（即 14-20 位元）的 Z3（或更快的解算器）。此處測試的所有少於 160 位元的雜湊函數根本不能被視為「安全」。

使用二進制密鑰的“�”漏洞攻擊在第二次理智零測試中進行了測試。

加密貨幣

我們的加密雜湊透過添加 size_t 種子進行強化，混合到初始狀態中，需要零填充的版本也透過添加 len 進行強化，以防止與填充的 AppishedZeroes 發生衝突。 libtomcrypt 實作已經提供了這一點，但其他實作可能沒有。如果沒有，這樣的加密雜湊函數不適合正常任務，因為透過填充或壞種子創建衝突是微不足道的。

官方 NIST 雜湊函數測試套件不會進行如此廣泛的統計測試來搜尋位元中的弱範圍。此外，加密不會改變初始狀態，我們在這裡為隨機 32 位元種子執行此操作。加密主要關心不可逆的金鑰 -> 雜湊函數，而不改變初始固定狀態和計時/側通道攻擊。

NIST「加密演算法驗證計畫」(CAVP) 涉及對 FIPS 批准和 NIST 推薦的加密演算法的實作進行測試。在 NIST SHA-3 競賽期間，測試方法借鑒了“CAVP”，因為 SHA-3 競賽測試套件的 KAT 和 MCT 是基於 SHA-2 的 CAVP 測試。除此之外，SHA-2 的 CAVP 中不存在的「極長訊息測試」要求提交者產生與長度為 1 GiB 的訊息相對應的雜湊值。 “NIST - 加密演算法驗證計劃 (CAVP)”，2017 年 6 月。

另外兩個獨立的第三方測試套件發現 SHA3 候選者中存在大量錯誤和弱點。 “尋找加密雜湊函數實作中的錯誤”，Nicky Mouha、Mohammad S Raunak、D. Richard Kuhn 和 Raghu Kacker，2017 年。

也許獨立研究人員應該齊心協力，基於更好、更多的測試方法、測試的開源程式碼以及使用標準行業實踐（例如valgrind、address-sanitizer 和ubsan）來進行更好的公共SHA-4 輪次來檢測明顯的錯誤。

問題

  • 壞種子

    哈希函數通常使用隨機種子進行初始化。但無論密鑰如何，某些種子值都可能導致錯誤的雜湊函數。在隨機種子的常規情況下，此類不良種子的機率非常低，例如 2^32 或 2^64。實際應用需要知道是否存在壞種子並選擇另一個。請參閱Hashes.h中的mirhash_seed_init()和mirhash_bad_seeds() 。請注意，當您在初始化期間跳過此種子時，壞種子並不是真正的問題。它仍然可以是一個好的或推薦的雜湊函數。但是導致衝突的壞種子0被認為是一個錯誤，一個壞的雜湊函數。

    我們測試內部秘密是否會與 0 相乘。 main.cpp列出了我們測試的每個雜湊函數的一些秘密。函數<hash>_bad_seeds()列出了已確認的壞種子。

    需要特別注意 crc、大多數 FNV1 變體、fletcher、Jenkins。大多數 MUM 變體都具有良好的雜湊值，例如 mirhash、MUM、wyhash。

    除此之外，當攻擊者知道種子時，就會導致 DDOS 攻擊。即使在 power2 哈希表中使用加密哈希。

典型的未定義行為（ UB ）問題：

  • 未對準

    許多逐字雜湊（與安全逐字節處理相反）不會檢查輸入緩衝區是否正確對齊字，這將在 ubsan 或 Sparc 中失敗。單字是int32_t或int64_t甚至更多。 在一些舊的 RISC 硬體上，這將是一個總線錯誤，您甚至可以透過設定一些 CPU 標誌來讓 Intel 硬體產生這樣的匯流排錯誤。但通常使用未對齊的存取就可以了。

    這些是：mx3、Spooky、mirhash（但不嚴格）、MUM、fasthash、Murmur3*、Murmur2*、metrohash*（除cmetro* 之外的所有版本）、Crap8、beamsplitter、lookup3、fletcher4、fletcher2、所有sanmayce FNV1a_變異體（FNV1a_YT、 FNV1A_Pippip_Yurii、FNV1A_Totenschiff、...)、斐波那契。

    通常的緩解措施是在呼叫者中檢查緩衝區對齊情況，為未對齊的前綴提供預處理循環，或將整個緩衝區複製到新的對齊區域。將額外的程式碼放入#ifdef HAVE_ALIGNED_ACCESS_REQUIRED 。

  • oob - 出界

    某些雜湊函數假設有一個填充的輸入緩衝區，可以對其長度進行訪問，直到達到字大小。這允許更快的循環處理，因為不需要第二個循環或其​​餘部分的切換表，但它需要協作調用環境，因此被視為作弊。

  • 有符號整數溢出

    一個簡單的類型錯誤，此哈希需要在內部使用無符號整數類型，以避免未定義和不一致的行為。即 SuperFastHash：有符號整數溢位：-2147483641 + -113 無法用「int」型別表示

  • 移位指數溢出

    使用：FNV1A_Pippip_Yurii、FNV1A_Totenschiff、pair_multiply_shift、sumhash32 移位指數 64 對於 64 位元類型「long unsigned int」來說太大

展開
附加信息
相關應用
爲您推薦
相關資訊 全部