# Expandable hash function

I have been studying a cryptosystem using Mersenne primes. More specifically, this paper.

I have implemented this cryptosystem in Python, but I am missing the key encapsulation system.

On page 12, they refer to something known as an "expandable hash function". It should take as input a $$\lambda$$-bit string and output a uniformly random $$n$$-bit string ($$\lambda<) of Hamming weight $$h$$. This weight $$h$$ is already determined (actually $$h=\lambda$$).

I am kind of new to this stuff. Is there a way to implement this hash function in Python?

• @kelalaka but what about the Hamming weight? May 24, 2021 at 20:29
• Hmm, would this just be $H'(m)\leftarrow_\$ S(\text{1}^h\parallel\text{0}^\left(n-h\right))$? All you gotta do is find a way to use$H\$ to uniformly randomly select a permutation of '1' * h + '0' * (n-h). Have you got any candidates for expandable hash functions currently? (This question may prove informative or helpful) May 25, 2021 at 17:31
• @JamesTheAwesomeDude no, I have not. How would you implement it in python? May 25, 2021 at 18:32
• I was too dumb to properly understand or implement it, but it appears that this paper provides a general method for doing so (or, at least, constructing a function that constructs functions that do so) May 26, 2021 at 15:13
• While I haven't yet figured out the permutation generator, It looks like pycryptodome includes a reputable expandable-output hash function: “Are there any variable length hash functions available for Python? May 27, 2021 at 4:27

Remember: a random permutation (or, when taken bitwise, "a hamming-weight-preserving one-way function") is known in layman's terms as a shuffle.

There are well-known correct algorithms to do this — Python itself, for example, makes it quite convenient to just leverage its shuffle implementation by subclassing Random with your choice of DRBG:

from random import Random
from resource import getpagesize as _getpagesize
from functools import reduce as _reduce
from itertools import islice as _islice, repeat as _repeat

from Cryptodome.Hash import SHAKE256

def deterministic_shuffle(seq, seed, sponge=SHAKE256):
"""Applies a pseudorandom permutation from arbitrary bytestring seed to mutable sequence seq, using SHAKE256 as the DRBG."""
stream = sponge.new(data=seed)
random = StreamBasedRandom(stream=stream, blocksize=136)
random.shuffle(seq)

class StreamBasedRandom(Random):
def __init__(self, stream, blocksize=_getpagesize()):
def getrandbits(self, k):
return _concatbits(_islice(self._randbitgen, k))
# Fix the following functions to prevent implementation-dependency
def randbytes(self, n):
return self.getrandbits(n * 8).to_bytes(n, 'big')
def _randbelow(self, n):
"""Replacement for CPython's Random._randbelow that wastes very few bits"""
if n <= 1:
return 0
getrandbits = self.getrandbits
k = (n - 1).bit_length()
a = getrandbits(k)
b = 2 ** k
if n == b:
return a
while (n * a // b) != (n * (a + 1) // b):
a = a * 2 | getrandbits(1)
b *= 2
return n * a // b
def shuffle(self, x):
"""Modern Fisher-Yates shuffle"""
randbelow = self._randbelow
for i in reversed(range(1, len(x))):
j = randbelow(i + 1)
x[i], x[j] = x[j], x[i]

def _ibytestobits(ibytes):
"""Turns an iterator of bytes into an iterator of its component bits, big-endian"""
yield from ((i >> k) & 0b1 for b in ibytes for i in b for k in reversed(range(8)))

def _concatbits(bits):
"""Takes a finite iterator of bits and returns their big-endian concatenation as an integer"""
return _reduce((lambda acc, cur: ((acc << 1) | cur)), bits, 0)


(SHAKE256 was used in this example code; it should be easily repurposeable to any bit generator. See this answer for some other ideas, and the appendix to this answer for a concrete example of how that might be done.)

To use this in your code would be something like this:

k = b'Hyper Secret Input Key'
h = len(k) * 8
n = 4096
assert n > (8 * h)

# An n-element bit sequence of hamming weight h
bitstream = ([1] * h) + ([0] * (n - h))
deterministic_shuffle(bitstream, k)

print("Shuffled bitstream:", _concatbits(bitstream).to_bytes(n // 8, 'big').hex())


Appendix: example usage of another DRBG

# this block of code depends on StreamBasedRandom, defined above
from types import SimpleNamespace as _SimpleNamespace

from Cryptodome.Cipher import AES
from Cryptodome.Hash import SHA256

def deterministic_shuffle(seq, seed, nonce=b''):
"""Applies a pseudorandom permutation from 256-bit (32-byte) seed to mutable sequence seq, using AES-256-CTR as the DRBG."""
assert len(seed) == 32, "seed must be 256 bits (32 bytes) long for AES-256."
cipher = AES.new(key=seed, mode=AES.MODE_CTR, nonce=nonce)
def randbytes(n):
return cipher.encrypt(b'\x00' * n)
random = StreamBasedRandom(stream=stream, blocksize=cipher.block_size)
random.shuffle(seq)

def _normalize(data):
return SHA256.new(data).digest()

k = b'Hyper Secret Input Key'
h = len(k) * 8
n = 4096
assert n > (8 * h)

bitstream = ([1] * h) + ([0] * (n - h))
deterministic_shuffle(bitstream, _normalize(k))

print("AES-shuffled bitstream:", _concatbits(bitstream).to_bytes(n // 8, 'big').hex())

• Interestingly, according to some dude on Quora, Fisher-Yates (which Python uses) is "optimal" -- his description of why seems underwhelming, but I don't doubt it per se... Jun 16, 2021 at 15:12
• (Admittedly, with the key functions fixed thus, I suppose it doesn't actually need to subclass Random…) Jun 16, 2021 at 20:16