Inside Bitcoin

1#!/usr/bin/env python3
2# Copyright (c) 2016-present The Bitcoin Core developers
3# Distributed under the MIT software license, see the accompanying
4# file COPYING or http://www.opensource.org/licenses/mit-license.php.
5"""SipHash-2-4 implementation.
6
7This implements SipHash-2-4. For convenience, an interface taking 256-bit
8integers is provided in addition to the one accepting generic data.
9"""
10
11import json
12from pathlib import Path
13import unittest
14
15
16def rotl64(n, b):
17    return n >> (64 - b) | (n & ((1 << (64 - b)) - 1)) << b
18
19
20def siphash_round(v0, v1, v2, v3):
21    v0 = (v0 + v1) & ((1 << 64) - 1)
22    v1 = rotl64(v1, 13)
23    v1 ^= v0
24    v0 = rotl64(v0, 32)
25    v2 = (v2 + v3) & ((1 << 64) - 1)
26    v3 = rotl64(v3, 16)
27    v3 ^= v2
28    v0 = (v0 + v3) & ((1 << 64) - 1)
29    v3 = rotl64(v3, 21)
30    v3 ^= v0
31    v2 = (v2 + v1) & ((1 << 64) - 1)
32    v1 = rotl64(v1, 17)
33    v1 ^= v2
34    v2 = rotl64(v2, 32)
35    return (v0, v1, v2, v3)
36
37
38def siphash(k0, k1, data):
39    assert type(data) is bytes
40    v0 = 0x736f6d6570736575 ^ k0
41    v1 = 0x646f72616e646f6d ^ k1
42    v2 = 0x6c7967656e657261 ^ k0
43    v3 = 0x7465646279746573 ^ k1
44    c = 0
45    t = 0
46    for d in data:
47        t |= d << (8 * (c % 8))
48        c = (c + 1) & 0xff
49        if (c & 7) == 0:
50            v3 ^= t
51            v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
52            v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
53            v0 ^= t
54            t = 0
55    t = t | (c << 56)
56    v3 ^= t
57    v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
58    v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
59    v0 ^= t
60    v2 ^= 0xff
61    v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
62    v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
63    v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
64    v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3)
65    return v0 ^ v1 ^ v2 ^ v3
66
67
68def siphash256(k0, k1, num):
69    assert type(num) is int
70    return siphash(k0, k1, num.to_bytes(32, 'little'))
71
72
73class TestFrameworkSipHash(unittest.TestCase):
74    def test_vectors(self):
75        with (Path(__file__).parents[4] / "src/test/data/siphash.json").open() as vectors_file:
76            for test in json.load(vectors_file):
77                k0, k1 = (int(key, 16) for key in test["key"])
78                data = b"".join(bytes.fromhex(block) for block in test["input"])
79                self.assertEqual(siphash(k0, k1, data), int(test["expected"]["siphash24"], 16))
80