Page MenuHomePhabricator
Differential D13888 Diff 40288 test/functional/test_framework/muhash.py

Changeset View

Standalone View

View Options

test/functional/test_framework/muhash.py

#!/usr/bin/env python3 #!/usr/bin/env python3
# Copyright (c) 2020 Pieter Wuille # Copyright (c) 2020 Pieter Wuille
# Distributed under the MIT software license, see the accompanying # Distributed under the MIT software license, see the accompanying
# file COPYING or http://www.opensource.org/licenses/mit-license.php. # file COPYING or http://www.opensource.org/licenses/mit-license.php.
"""Native Python MuHash3072 implementation.""" """Native Python MuHash3072 implementation."""
import hashlib import hashlib
import unittest import unittest
from .util import modinv from .util import modinv
def rot32(v, bits): def rot32(v, bits):
"""Rotate the 32-bit value v left by bits bits.""" """Rotate the 32-bit value v left by bits bits."""
# Make sure the term below does not throw an exception # Make sure the term below does not throw an exception
bits %= 32 bits %= 32
return ((v << bits) & 0xffffffff) | (v >> (32 - bits)) return ((v << bits) & 0xFFFFFFFF) | (v >> (32 - bits))
def chacha20_doubleround(s): def chacha20_doubleround(s):
"""Apply a ChaCha20 double round to 16-element state array s. """Apply a ChaCha20 double round to 16-element state array s.
See https://cr.yp.to/chacha/chacha-20080128.pdf and See https://cr.yp.to/chacha/chacha-20080128.pdf and
https://tools.ietf.org/html/rfc8439 https://tools.ietf.org/html/rfc8439
""" """
QUARTER_ROUNDS = [(0, 4, 8, 12), QUARTER_ROUNDS = [
(0, 4, 8, 12),
(1, 5, 9, 13), (1, 5, 9, 13),
(2, 6, 10, 14), (2, 6, 10, 14),
(3, 7, 11, 15), (3, 7, 11, 15),
(0, 5, 10, 15), (0, 5, 10, 15),
(1, 6, 11, 12), (1, 6, 11, 12),
(2, 7, 8, 13), (2, 7, 8, 13),
(3, 4, 9, 14)] (3, 4, 9, 14),
]
for a, b, c, d in QUARTER_ROUNDS: for a, b, c, d in QUARTER_ROUNDS:
s[a] = (s[a] + s[b]) & 0xffffffff s[a] = (s[a] + s[b]) & 0xFFFFFFFF
s[d] = rot32(s[d] ^ s[a], 16) s[d] = rot32(s[d] ^ s[a], 16)
s[c] = (s[c] + s[d]) & 0xffffffff s[c] = (s[c] + s[d]) & 0xFFFFFFFF
s[b] = rot32(s[b] ^ s[c], 12) s[b] = rot32(s[b] ^ s[c], 12)
s[a] = (s[a] + s[b]) & 0xffffffff s[a] = (s[a] + s[b]) & 0xFFFFFFFF
s[d] = rot32(s[d] ^ s[a], 8) s[d] = rot32(s[d] ^ s[a], 8)
s[c] = (s[c] + s[d]) & 0xffffffff s[c] = (s[c] + s[d]) & 0xFFFFFFFF
s[b] = rot32(s[b] ^ s[c], 7) s[b] = rot32(s[b] ^ s[c], 7)
def chacha20_32_to_384(key32): def chacha20_32_to_384(key32):
"""Specialized ChaCha20 implementation with 32-byte key, 0 IV, """Specialized ChaCha20 implementation with 32-byte key, 0 IV,
384-byte output.""" 384-byte output."""
# See RFC 8439 section 2.3 for chacha20 parameters # See RFC 8439 section 2.3 for chacha20 parameters
CONSTANTS = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574] CONSTANTS = [0x61707865, 0x3320646E, 0x79622D32, 0x6B206574]
key_bytes = [0] * 8 key_bytes = [0] * 8
for i in range(8): for i in range(8):
key_bytes[i] = int.from_bytes(key32[(4 * i):(4 * (i + 1))], 'little') key_bytes[i] = int.from_bytes(key32[(4 * i) : (4 * (i + 1))], "little")
INITIALIZATION_VECTOR = [0] * 4 INITIALIZATION_VECTOR = [0] * 4
init = CONSTANTS + key_bytes + INITIALIZATION_VECTOR init = CONSTANTS + key_bytes + INITIALIZATION_VECTOR
out = bytearray() out = bytearray()
for counter in range(6): for counter in range(6):
init[12] = counter init[12] = counter
s = init.copy() s = init.copy()
for _ in range(10): for _ in range(10):
chacha20_doubleround(s) chacha20_doubleround(s)
for i in range(16): for i in range(16):
out.extend(((s[i] + init[i]) & 0xffffffff).to_bytes(4, 'little')) out.extend(((s[i] + init[i]) & 0xFFFFFFFF).to_bytes(4, "little"))
return bytes(out) return bytes(out)
def data_to_num3072(data): def data_to_num3072(data):
"""Hash a 32-byte array data to a 3072-bit number using 6 Chacha20 """Hash a 32-byte array data to a 3072-bit number using 6 Chacha20
operations.""" operations."""
bytes384 = chacha20_32_to_384(data) bytes384 = chacha20_32_to_384(data)
return int.from_bytes(bytes384, 'little') return int.from_bytes(bytes384, "little")
class MuHash3072: class MuHash3072:
"""Class representing the MuHash3072 computation of a set. """Class representing the MuHash3072 computation of a set.
See https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf and See https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf and
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014337.html
""" """
MODULUS = 2**3072 - 1103717 MODULUS = 2**3072 - 1103717
def __init__(self): def __init__(self):
"""Initialize for an empty set.""" """Initialize for an empty set."""
self.numerator = 1 self.numerator = 1
self.denominator = 1 self.denominator = 1
def insert(self, data): def insert(self, data):
"""Insert a byte array data in the set.""" """Insert a byte array data in the set."""
data_hash = hashlib.sha256(data).digest() data_hash = hashlib.sha256(data).digest()
self.numerator = ( self.numerator = (self.numerator * data_to_num3072(data_hash)) % self.MODULUS
self.numerator * data_to_num3072(data_hash)) % self.MODULUS
def remove(self, data): def remove(self, data):
"""Remove a byte array from the set.""" """Remove a byte array from the set."""
data_hash = hashlib.sha256(data).digest() data_hash = hashlib.sha256(data).digest()
self.denominator = ( self.denominator = (
self.denominator * data_to_num3072(data_hash)) % self.MODULUS self.denominator * data_to_num3072(data_hash)
) % self.MODULUS
def digest(self): def digest(self):
"""Extract the final hash. Does not modify this object.""" """Extract the final hash. Does not modify this object."""
val = (self.numerator * val = (self.numerator * modinv(self.denominator, self.MODULUS)) % self.MODULUS
modinv(self.denominator, self.MODULUS)) % self.MODULUS bytes384 = val.to_bytes(384, "little")
bytes384 = val.to_bytes(384, 'little')
return hashlib.sha256(bytes384).digest() return hashlib.sha256(bytes384).digest()
class TestFrameworkMuhash(unittest.TestCase): class TestFrameworkMuhash(unittest.TestCase):
def test_muhash(self): def test_muhash(self):
muhash = MuHash3072() muhash = MuHash3072()
muhash.insert(b'\x00' * 32) muhash.insert(b"\x00" * 32)
muhash.insert((b'\x01' + b'\x00' * 31)) muhash.insert((b"\x01" + b"\x00" * 31))
muhash.remove((b'\x02' + b'\x00' * 31)) muhash.remove((b"\x02" + b"\x00" * 31))
finalized = muhash.digest() finalized = muhash.digest()
# This mirrors the result in the C++ MuHash3072 unit test # This mirrors the result in the C++ MuHash3072 unit test
self.assertEqual( self.assertEqual(
finalized[::-1].hex(), finalized[::-1].hex(),
"10d312b100cbd32ada024a6646e40d3482fcff103668d2625f10002a607d5863" "10d312b100cbd32ada024a6646e40d3482fcff103668d2625f10002a607d5863",
) )
def test_chacha20(self): def test_chacha20(self):
def chacha_check(key, result): def chacha_check(key, result):
self.assertEqual(chacha20_32_to_384(key)[:64].hex(), result) self.assertEqual(chacha20_32_to_384(key)[:64].hex(), result)
# Test vectors from https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-7 # Test vectors from https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-7
# Since the nonce is hardcoded to 0 in our function we only use those # Since the nonce is hardcoded to 0 in our function we only use those
# vectors. # vectors.
chacha_check( chacha_check(
[0] * 32, [0] * 32,
"76b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8b770dc7da41597c5157488d7724e03fb8d84a376a43b8f41518a11cc387b669b2ee6586") "76b8e0ada0f13d90405d6ae55386bd28bdd219b8a08ded1aa836efcc8b770dc7da41597c5157488d7724e03fb8d84a376a43b8f41518a11cc387b669b2ee6586",
)
chacha_check( chacha_check(
[0] * 31 + [1], [0] * 31 + [1],
"4540f05a9f1fb296d7736e7b208e3c96eb4fe1834688d2604f450952ed432d41bbe2a0b6ea7566d2a5d1e7e20d42af2c53d792b1c43fea817e9ad275ae546963") "4540f05a9f1fb296d7736e7b208e3c96eb4fe1834688d2604f450952ed432d41bbe2a0b6ea7566d2a5d1e7e20d42af2c53d792b1c43fea817e9ad275ae546963",
)