bpo-29410: Change the default hash algorithm to SipHash13. (GH-28752)

Co-authored-by: Erlend Egeberg Aasland <erlend.aasland@innova.no>
Co-authored-by: Christian Heimes <christian@python.org>

1 files changed, 72 insertions, 7 deletions

diff --git a/Python/pyhash.c b/Python/pyhash.c
index f0c82356f1..d5ac9f83be 100644
--- a/Python/pyhash.c
+++ b/Python/pyhash.c
@@ -358,20 +358,73 @@ static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * SIZEOF_PY_HASH_T,
 #  define ROTATE(x, b) (uint64_t)( ((x) << (b)) | ( (x) >> (64 - (b))) )
 #endif
 
-#define HALF_ROUND(a,b,c,d,s,t)         \
-    a += b; c += d;             \
+#define HALF_ROUND(a,b,c,d,s,t)     \
+    a += b; c += d;                 \
     b = ROTATE(b, s) ^ a;           \
     d = ROTATE(d, t) ^ c;           \
     a = ROTATE(a, 32);
 
-#define DOUBLE_ROUND(v0,v1,v2,v3)       \
-    HALF_ROUND(v0,v1,v2,v3,13,16);      \
-    HALF_ROUND(v2,v1,v0,v3,17,21);      \
-    HALF_ROUND(v0,v1,v2,v3,13,16);      \
+#define SINGLE_ROUND(v0,v1,v2,v3)   \
+    HALF_ROUND(v0,v1,v2,v3,13,16);  \
     HALF_ROUND(v2,v1,v0,v3,17,21);
 
+#define DOUBLE_ROUND(v0,v1,v2,v3)   \
+    SINGLE_ROUND(v0,v1,v2,v3);      \
+    SINGLE_ROUND(v0,v1,v2,v3);
+
 
 static uint64_t
+siphash13(uint64_t k0, uint64_t k1, const void *src, Py_ssize_t src_sz) {
+    uint64_t b = (uint64_t)src_sz << 56;
+    const uint8_t *in = (const uint8_t*)src;
+
+    uint64_t v0 = k0 ^ 0x736f6d6570736575ULL;
+    uint64_t v1 = k1 ^ 0x646f72616e646f6dULL;
+    uint64_t v2 = k0 ^ 0x6c7967656e657261ULL;
+    uint64_t v3 = k1 ^ 0x7465646279746573ULL;
+
+    uint64_t t;
+    uint8_t *pt;
+
+    while (src_sz >= 8) {
+        uint64_t mi;
+        memcpy(&mi, in, sizeof(mi));
+        mi = _le64toh(mi);
+        in += sizeof(mi);
+        src_sz -= sizeof(mi);
+        v3 ^= mi;
+        SINGLE_ROUND(v0,v1,v2,v3);
+        v0 ^= mi;
+    }
+
+    t = 0;
+    pt = (uint8_t *)&t;
+    switch (src_sz) {
+        case 7: pt[6] = in[6]; /* fall through */
+        case 6: pt[5] = in[5]; /* fall through */
+        case 5: pt[4] = in[4]; /* fall through */
+        case 4: memcpy(pt, in, sizeof(uint32_t)); break;
+        case 3: pt[2] = in[2]; /* fall through */
+        case 2: pt[1] = in[1]; /* fall through */
+        case 1: pt[0] = in[0]; /* fall through */
+    }
+    b |= _le64toh(t);
+
+    v3 ^= b;
+    SINGLE_ROUND(v0,v1,v2,v3);
+    v0 ^= b;
+    v2 ^= 0xff;
+    SINGLE_ROUND(v0,v1,v2,v3);
+    SINGLE_ROUND(v0,v1,v2,v3);
+    SINGLE_ROUND(v0,v1,v2,v3);
+
+    /* modified */
+    t = (v0 ^ v1) ^ (v2 ^ v3);
+    return t;
+}
+
+#if Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
+static uint64_t
 siphash24(uint64_t k0, uint64_t k1, const void *src, Py_ssize_t src_sz) {
     uint64_t b = (uint64_t)src_sz << 56;
     const uint8_t *in = (const uint8_t*)src;
@@ -419,14 +472,26 @@ siphash24(uint64_t k0, uint64_t k1, const void *src, Py_ssize_t src_sz) {
     t = (v0 ^ v1) ^ (v2 ^ v3);
     return t;
 }
+#endif
 
 uint64_t
 _Py_KeyedHash(uint64_t key, const void *src, Py_ssize_t src_sz)
 {
-    return siphash24(key, 0, src, src_sz);
+    return siphash13(key, 0, src, src_sz);
 }
 
 
+#if Py_HASH_ALGORITHM == Py_HASH_SIPHASH13
+static Py_hash_t
+pysiphash(const void *src, Py_ssize_t src_sz) {
+    return (Py_hash_t)siphash13(
+        _le64toh(_Py_HashSecret.siphash.k0), _le64toh(_Py_HashSecret.siphash.k1),
+        src, src_sz);
+}
+
+static PyHash_FuncDef PyHash_Func = {pysiphash, "siphash13", 64, 128};
+#endif
+
 #if Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
 static Py_hash_t
 pysiphash(const void *src, Py_ssize_t src_sz) {