我在Python 3.3中实现了一个BloomFilter,但每次运行时都会得到不同的结果。经过分析,我发现问题出在内部的hash()函数上 - 它会在每次会话中为相同的字符串返回不同的哈希值。
例如:
>>> hash("235")
-310569535015251310
----- 打开一个新的Python控制台 -----
>>> hash("235")
-1900164331622581997
为什么会发生这种情况? 这有什么用处?
我在Python 3.3中实现了一个BloomFilter,但每次运行时都会得到不同的结果。经过分析,我发现问题出在内部的hash()函数上 - 它会在每次会话中为相同的字符串返回不同的哈希值。
例如:
>>> hash("235")
-310569535015251310
----- 打开一个新的Python控制台 -----
>>> hash("235")
-1900164331622581997
为什么会发生这种情况? 这有什么用处?
Python使用随机哈希种子来防止攻击者通过发送被设计为发生冲突的键来使您的应用程序陷入困境。请参见原漏洞披露。通过使用随机种子(在启动时设置一次)偏移哈希,攻击者将无法预测哪些键会发生冲突。
您可以设置固定的种子或通过设置PYTHONHASHSEED
环境变量禁用此功能;默认值为random
,但是您可以将其设置为固定的正整数值,使用0
可以完全禁用该功能。
Python 2.7和3.2版本默认禁用此功能(使用-R
开关或设置PYTHONHASHSEED=random
以启用),在Python 3.3及更高版本中默认启用。
如果您依赖于Python集合中键的顺序,请注意Python使用哈希表实现这些类型及其顺序取决于插入和删除历史记录以及随机哈希种子。请注意,在Python 3.5及更早版本中,这同样适用于字典。
注意:默认情况下,str,bytes和datetime对象的
__hash__()
值将与不可预测的随机值“混淆”。虽然它们在单个Python进程中保持恒定,但在重复调用Python时它们是不可预测的。
这旨在提供保护,防范由精心选择的输入引起的拒绝服务攻击,该攻击利用字典插入的最坏情况性能(O(n^2) 复杂度)。详情请参见http://www.ocert.org/advisories/ocert-2011-003.html。
改变哈希值会影响字典、集合和其他映射的迭代顺序。Python从未对这种排序方式做出过保证(并且通常在32位和64位版本之间有所不同)。
还请参见PYTHONHASHSEED
。
如果您需要稳定的哈希实现,可能需要查看hashlib
模块;这个模块实现了加密哈希功能。 pybloom 项目使用了这种方法。
由于偏移量由前缀和后缀(即起始值和最终XORed值)组成,你不能只存储偏移量。不幸的是。但好的一面是,这意味着攻击者也无法通过时间攻击轻松确定偏移量。
hash()
的这种行为使我在尝试在会话之间比较保存在数据库中的记录时遇到了问题。
PYTHONHASHSEED
的解决方案太复杂了,因为我需要让程序可靠地工作,独立于环境变量设置。
所以我创建了一个简单的哈希函数来哈希字符串(将任何东西转换为字符串很容易),并生成一个32位正整数作为哈希值。虽然它不是一个加密安全的哈希算法,但已经足够快速进行比较。
def myHash(text:str):
hash=0
for ch in text:
hash = ( hash*281 ^ ord(ch)*997) & 0xFFFFFFFF
return hash
在这个乘法中使用的数字仅仅是任意选择的质数,以便混淆位。
如果你想要哈希为十六进制字符串,可以将最后一行替换为:
return hex(hash)[2:].upper().zfill(8)
哈希随机化在Python 3中默认开启。这是一个安全功能:
哈希随机化旨在提供保护,防止因利用字典构造的最坏情况性能而导致的拒绝服务攻击。
在2.6.8之前的版本中,您可以使用命令行选项-R或PYTHONHASHSEED环境选项来开启它。
您可以通过将PYTHONHASHSEED
设置为零来关闭它。