Python: Using XOFs for general-purpose Random

As always, one's own stack overflow answers make the best blog posts.

In this case, we craft a version of random.Random with a few modifications:

• Pulls its data from an arbitrary stream (in our case, a DRBG such as a hash function or deterministic CSPRNG)
• Wastes noticeably fewer bits when generating random integers
• Has fixed code for .shuffle, on the offchance CPython ever changes theirs, and to make it work with other implementations

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


class StreamBasedRandom(Random):
	def __init__(self, stream, blocksize=_getpagesize()):
		self._randbitgen = _ibytestobits(map(stream.read, _repeat(blocksize)))
	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 extremely few bits"""
		a = 0
		b = 1
		while True:
			a = (a * 2) | getrandbits(1)
			b = b * 2
			if b >= n:
				if a < n:
					return a
				a = a - n
				b = b - n
	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)

the example for which this was created:

from Cryptodome.Hash import SHAKE256

def deterministic_shuffle(seq, key, alg=SHAKE256):
	# h/t https://crypto.stackexchange.com/a/90245/8287
	"""Applies a pseudorandom permutation from key to seq"""
	random = StreamBasedRandom(stream=alg.new(key), blocksize=136)
	random.shuffle(seq)

and a more absurd/reductionist example showing that a CSPRNG is a CSPRNG, no matter whether it identifies as a hash function or a stream cipher:

import os
from Cryptodome.Cipher import AES
from types import SimpleNamespace

def aes_random_factory(seed, nonce=b''):
	# CTR is used to allow future implementers to trivially seek without breaking compatibility
	cipher = AES.new(seed, AES.MODE_CTR, nonce=nonce)
	def randbytes(n):
		return cipher.encrypt(b'\x00' * n)
	stream = SimpleNamespace(read=randbytes)
	return StreamBasedRandom(stream=stream, blocksize=cipher.block_size)

seed = os.urandom(32)
random = aes_random_factory(seed)