标题: Python3中SipHash算法简介

创建: 2023-03-06 15:00
更新: 2023-04-27 13:22
链接: https://scz.617.cn/python/202303061500.txt

参看

https://peps.python.org/pep-0456/
https://en.wikipedia.org/wiki/SipHash

SipHash是2012年出场的，对任意长度明文求8字节hash，需要提供16字节key。该算
法属于密码学意义上的安全哈希算法，与之相比，MurmurHash、FNV等算法不是。
SipHash-c-d表示SipHash家族的算法，推荐SipHash-2-4，有更高安全追究时或可采
用SipHash-4-8，而Siphash-1-3靠降低安全性来提升效率，不推荐。

2023.4.26，flier对此算法有重要反馈。这个算法真不行，又慢又不够安全还没法定
制，被大量使用是因为一个HASH攻击论文里刚好拿它举例，然后一群人就以为这个靠
谱，具体可以参考大佬的点评

https://rurban.github.io/smhasher/#security

The usage of SipHash for their hash table in Python 3.4, ruby, rust,
systemd, OpenDNS, Haskell and OpenBSD is pure security theatre. SipHash is
not secure enough for security purposes and not fast enough for general
usage. All hash functions with less than 160 bits tested here cannot be
considered "secure" at all.

再次表明，非密码学相关细分领域专业人士，不要在密码学问题上想当然，我也是受
害者。

2013年从Python 3.4开始，其内置hash()函数默认采用SipHash24算法，过去是FNV算
法。SipHash24算法需要16字节key，对应全局变量_Py_HashSecret.siphash，默认情
况下由pyurandom()产生的随机数充当key。

$ python3 -c "import sys;print(sys.hash_info)"
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)

hashlib模块未提供SipHash算法

>>> import hashlib
>>> print(hashlib.algorithms_available)
{'mdc2', 'md5-sha1', 'ripemd160', 'sha384', 'sha3_256', 'sha3_384', 'shake_128', 'sha512_224', 'whirlpool', 'sha512_256', 'sha224', 'blake2s', 'md5', 'sha3_224', 'sha1', 'sm3', 'blake2b', 'md4', 'sha512', 'sha256', 'sha3_512', 'shake_256'}

有现成的siphash24模块支持SipHash13、SipHash24

--------------------------------------------------------------------------
#
# python3 -m pip install siphash24
# python3 SipHash24.py "some key" "scz is here"
#
# da6ef3d8451eb29a
#
import sys, siphash24

def s2b ( s, e="utf-8" ) :
    return( s.encode( encoding=e ) )

def decode_escaped_string ( s:str ) -> bytes :
    return bytes( s.encode( 'utf-8' ).decode( 'unicode_escape' ), 'utf-8' )

def SipHash24 ( key, data ) :
    return siphash24.siphash24( data, key=key ).digest()

key     = decode_escaped_string( sys.argv[1] )
data    = decode_escaped_string( sys.argv[2] )
print( SipHash24( key, data ).hex() )
--------------------------------------------------------------------------

接受转义序列指定的key、data

$ python3 SipHash24.py "a\r\r\n" "0123456789abcdef"
6d59d0bd7d803df0

有现成的SipHash C实现，非OS相关的实现

git clone git@github.com:veorq/SipHash.git
cd SipHash
make
./test

有在线SipHash24

https://duzun.me/playground/hash

选中SipHash-2-4，第一行输入data，第二行输入key，最下面显示hash

scz is here
some key
9ab21e45d8f36eda

它这个显示是按little-endian序显示64位整数

从Python 3.4开始，其内置hash()函数默认采用SipHash24算法。基本上无法给内置
hash()函数指定key，默认key是随机生成的；环境变量PYTHONHASHSEED非0时，其值
作为种子转给某固定的线性同余发生器(LCG)再生成key；环境变量PYTHONHASHSEED为
0时，key为0，这是唯一指定key的方式。下例演示key为0对"scz"求SipHash24

$ PYTHONHASHSEED=0 python3 -c 'print(hash("scz").to_bytes(8,byteorder="little",signed=True).hex())'
771a041320f7d834

对比

$ python3 SipHash24.py "" "scz"
771a041320f7d834

Python 3.3之前pyc首部占8字节

--------------------------------------------------------------------------
magic number        // +0x0 随版本不同而不同
source timestamp    // +0x4 .py的mtime
                    // +0x8
--------------------------------------------------------------------------

Python 3.3到3.6时，pyc首部占12字节。2017年从Python 3.7开始新增了一种HASH机
制，pyc首部出现相应变化。

使用HASH时，pyc首部如下

--------------------------------------------------------------------------
magic number        // +0x0 随版本不同而不同
flags               // +0x4 little-endian序
                    //      bit-0置位，表示启用HASH机制，否则启用时间戳
                    //      bit-1置位，表示必须检查HASH，否则不检查HASH
                    //      bit-1也叫"check_source flag"
hash                // +0x8 对.py求SipHash24，"magic number"做key
                    // +0x10
--------------------------------------------------------------------------

有多种办法强制生成"hash-based pyc"，试举一例

python3 -c "import sys,py_compile;py_compile.compile(sys.argv[1],doraise=True,optimize=2,invalidation_mode=py_compile.PycInvalidationMode.CHECKED_HASH)" is_prime_pub.py

上述命令生成

__pycache__\is_prime_pub.cpython-39.opt-2.pyc

$ xxd -g 1 -l 0x10 is_prime_pub.cpython-39.opt-2.pyc
00000000: 61 0d 0d 0a 03 00 00 00 85 81 b5 18 2f 7d fa 2c  a.........../}.,

--------------------------------------------------------------------------
61 0d 0d 0a             // +0x0 magic number
03 00 00 00             // +0x4 flags，little-endian序，启用HASH、检查HASH
85 81 b5 18 2f 7d fa 2c // +0x8 对.py求SipHash24，"magic number"做key
                        // +0x10
--------------------------------------------------------------------------

可以自己计算hash

--------------------------------------------------------------------------
#
# python3 source_hash.py is_prime_pub.py
#
import sys
import importlib.util

def get_hash ( filename ) :
    with open( filename, 'rb' ) as f :
        data    = f.read()
        hash    = importlib.util.source_hash( data )
        return hash

print( get_hash( sys.argv[1] ).hex() )
--------------------------------------------------------------------------

这个版本用了Python3自带的"importlib.util.source_hash"