A Python script to generate permutations of the set of 32-bit strings

README.md

This provides a 32-bit block cipher based on four 16-bit pseudorandom functions, precomputed based on the output of a stream cipher. To compute the F_j(i), the jth PRF evaluated at i, we take the two bytes starting at the (j * 2^16 + i) * 2th byte of the output of the stream cipher. (This particular implementation actually uses four distinct stream cipher output streams, and uses os.urandom() in place of a stream cipher, but you get the idea.) These four PRFs F_0, F_1, F_2, F_3 are used as the F-functions of a four-round Feistel network.

Usage

To do some benchmarks, simply run main.py.

main.py also exposes an API. Simply import main (possibly renaming main.py to something else), and then call main.RandomPRFFeistelCipher.generate(). That will return a RandomPRFFeistelCipher object, which has two methods, encrypt and decrypt; both take two ints between 0 and 65536, left- inclusive, and return a tuple of two ints, again between 0 and 65536.

This certainly isn't the fastest possible implementation; I'd imagine an optimized C implementation could do hundreds of millions of encryptions per second, assuming there are no issues with memory bandwidth. However, you're not going to get significantly faster generating the pseudorandom functions; that appears to mostly be bounded by the speed of the CSPRNG.

main.py

import random
import os
import math

HALF_SIZE = 16
BYTE_SIZE = HALF_SIZE // 8
IS_PY2 = False
USE_STREAM_CIPHER = False

try:
    range = xrange
    IS_PY2 = True
except:
    pass

if IS_PY2:
    import struct
    def from_bytes(bytes_):
        return struct.unpack("<L", bytes_ + b"\0" * (4 - len(bytes_)))[0]
else:
    def from_bytes(bytes_):
        return int.from_bytes(bytes_, "big")

class RandomPRFFeistelCipher:
    def __init__(self, functions):
        self.functions = functions

    def encrypt(self, lhs, rhs=None):
        if rhs is None:
            if type(lhs) is not tuple:
                raise ValueError()
            lhs, rhs = lhs

        lhs ^= self.functions[0][rhs]
        rhs ^= self.functions[1][lhs]
        lhs ^= self.functions[2][rhs]
        rhs ^= self.functions[3][lhs]
        return lhs, rhs

    def decrypt(self, lhs, rhs=None):
        if rhs is None:
            if type(lhs) is not tuple:
                raise ValueError()
            lhs, rhs = lhs

        rhs ^= self.functions[3][lhs]
        lhs ^= self.functions[2][rhs]
        rhs ^= self.functions[1][lhs]
        lhs ^= self.functions[0][rhs]
        return lhs, rhs

    @staticmethod
    def generate():
        return RandomPRFFeistelCipher([
            gen_prf(generate_keystream(2**HALF_SIZE * BYTE_SIZE))
            for i in range(4)
        ])

def generate_keystream(length):
    if USE_STREAM_CIPHER:
        # Instead of using os.urandom directly, we can also use a stream cipher
        # to generate the ~1MB of randomness necessary to generate the PRFs.
        # In this case, we use AES-256-CTR, which is used in various places in Tor.
        from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
        from cryptography.hazmat.backends.openssl import backend
        cipher = Cipher(
            algorithms.AES(os.urandom(32)),
            modes.CTR(os.urandom(16)),
            backend=backend
        ).encryptor()
        ret = cipher.update(b"\0" * length)
        cipher.finalize()
        return ret

    return os.urandom(length)

def gen_prf(keystream):
    if len(keystream) < 2**HALF_SIZE * BYTE_SIZE:
        raise ValueError("Keystream too short.")

    return [from_bytes(keystream[i * BYTE_SIZE:(i + 1) * BYTE_SIZE])
        for i in range(2**HALF_SIZE)]


if __name__ == "__main__":
    import sys
    import time
    sys.stdout.write("Generating permutations... ")
    sys.stdout.flush()
    start = time.time()
    cipher = RandomPRFFeistelCipher.generate()
    print("Done in %0.4f seconds" % (time.time() - start))
    block = (0, 0)
    start = time.time()
    for i in range(1000000):
        block = cipher.encrypt(block) # Try replacing with cipher.decrypt
    print("1 million encryptions took %0.4f seconds." % (time.time() - start))

security.md

This document provides a rough outline of the security reduction from the construction implemented in main.py to the security of the underlying stream cipher.

Bird's-Eye View

This construction produces a 32-bit block cipher using four 16-bit pseudorandom functions in a Feistel network. These four functions are chosen randomly and uniformly from the set of all 16-bit pseudorandom functions as the output of a stream cipher.

Four-Round Feistel Networks

In [1], Luby and Rackoff proved that four-round Feistel networks are indistinguishable from randomly-chosen permutations by a chosen-plaintext adversary, provided that the F-functions are pseudorandom functions.

Security Reduction to a Stream Cipher

This section establishes a security reduction between the generated pseudorandom functions and the underlying stream cipher.

A pseudorandom function is defined by the fact that its outputs, for any set of inputs, must be indistinguishable from random noise (barring the fact that identical inputs will produce identical outputs). In our construction, a set of inputs may be viewed as a set of indices into the output of the stream cipher. If the output of our pseudorandom function for this set of inputs could be distinguished from random noise, then an adversary could use this as a distinguishing attack against the underlying stream cipher, by looking at the same indices and in the same order, and performing the same attack thet used against the pseudorandom function.

Footnotes

1. "How to Construct Pseudorandom Permutations from Pseudorandom Functions". Luby and Rackoff, 1988, SIAM Journal on Computing.