首页>编程相关>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测试NO​​P
坏哈希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，！msvc
海哈希32low 8266.17 58.90 290.21 (16)第871章PerlinNoise 32，！msvc
冲突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（索尼 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 月。可用：http://csrc.nist.gov/groups/STM/cavp（未提供测试源代码，仅提供高级描述）

另外两个独立的第三方测试套件发现 SHA3 候选者中存在大量错误和弱点。 “查找加密哈希函数实现中的错误”，Nicky Mouha、Mohammad S Raunak、D. Richard Kuhn 和 Raghu Kacker，2017 年。https://eprint.iacr.org/2017/891.pdf

也许独立研究人员应该齐心协力，基于更好、更多的测试方法、测试的开源代码以及使用标准行业实践（例如 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_皮皮普_尤里， 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”来说太大

展开
附加信息
相关应用
为您推荐
相关资讯 全部