Python3中SipHash算法简介

创建: 2023-03-06 15:00
更新: 2023-04-23 14:02
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靠降低安全性来提升效率，不推荐。

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 "arrn" "0123456789abcdef"
6d59d0bd7d803df0

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

git clone [email protected]: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"