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)

Leave a Reply

Your email address will not be published.

Warning: This site uses Akismet to filter spam. Until or unless I can find a suitable replacement anti-spam solution, this means that (per their indemnification document) all commenters' IP addresses will be sent to Automattic, Inc., who may choose to share such with 3rd parties.
If this is unacceptable to you, I highly recommend using an anonymous proxy or public Wi-Fi connection when commenting.