"""
generic implementation of a Feistel cipher
"""
from collections.abc import (
ByteString,
Callable,
Generator,
Iterable,
Iterator,
Sequence,
)
import enum
import operator
from typing import (
Any,
cast,
Generic,
Optional,
TypeVar,
Union,
)
Data = TypeVar('Data', bound=Sequence[Any])
Key = TypeVar('Key')
Variadic = TypeVar('Variadic')
Function = Callable[[Data, Key, Optional[int]], Data]
[docs]class Feistel(Generic[Data, Key]):
"""
Didactic implementation of a generalized Feistel Cipher
see https://www.schneier.com/wp-content/uploads/2016/02/paper-unbalanced-feistel.pdf
This class implements a simple Feistel cipher using an arbitrary
round function and number of rounds. **THIS IMPLEMENTATION IS
INEFFICIENT AND INSECURE**. It can be used for simple
experimentation and obfuscation, but **MUST NOT** be used for any
application requiring (or even expecting) actual security.
""" r"""
.. testcode::
import hashlib
import hmac
from fictive.feistel import Feistel
def func(source, key, target_length):
return hmac.new(key, source, hashlib.sha1).digest()[:target_length]
key = [b'secrets', b'protect', b'my data']
.. doctest::
>>> cipher = Feistel(round_func=func, key=key, num_rounds=3)
>>> cipher.encrypt(b'My data is secret')
b"2X\x9a\x9d\x13\x0e\xf0pW\x8c\xa9\x9a'\xd8\x08\xe2\x90"
>>> cipher.decrypt(b"2X\x9a\x9d\x13\x0e\xf0pW\x8c\xa9\x9a'\xd8\x08\xe2\x90")
b'My data is secret'
"""
#: indicates which "half" of the input is the "source" and which
#: is the "target" (the source is passed through the round
#: function and mixed with the target)
ChiralityType = enum.Enum('ChiralityType', 'SOURCE_TARGET TARGET_SOURCE')
@classmethod
def _length_parameters(
cls, input_length: int, *,
source_length: int = None, target_length: int = None) -> tuple[int, int]:
"""
Determine appropriate sizing parameters
If either of `source_length` or `target_length` is `None`, an
appropriate value will be calculated based on values of other
:term:`parameter`\\s, such that
1. :code:`source_length + target_length == input_length`, and
2. `source_length` and `target_length` are approximately equal
:param input_length:
the length of the data provided to encipher
:param source_length:
the length of the "source" portion of the input data
(i.e., the portion that will be input to the round
function)
:param target_length:
the length of the "target" portion of the input data
(i.e., the portion that will be mixed with the output of
the round function)
:returns:
a `tuple` of appropriate :code:`(source_length,
target_length)` values
"""
if source_length is not None and target_length is not None:
return source_length, target_length
if source_length is not None:
target_length = input_length - source_length
elif target_length is not None:
source_length = input_length - target_length
else:
source_length = input_length // 2
target_length = input_length - source_length
return source_length, target_length
@classmethod
def _iterator_wrap(
cls,
target: Union[Iterator[Variadic], Iterable[Variadic], Variadic],
length: int) -> Iterator[Variadic]:
"""
Provide an :term:`iterator` for `target`
If `target` is already an :term:`iterator` (i.e., it supports
the built-in `next` function), it will be returned as-is. If
`target` is an :term:`iterable` (other than a `str` or
`bytes`), it will be wrapped with the built-in `iter`
function. Otherwise, `target` is considered a "scalar" and a
:term:`generator` is constructed that will :code:`yield`
`target` `length` times.
:param target:
The value(s) that the :term:`iterator` will :code:`yield`
:param length:
if `target` is "scalar", a generator is constructed that
will `yield` this many occurrences `target`; otherwise,
this :term:`parameter` is ignored
:returns:
an :term:`iterator` that will yield the value(s) of
`target`
"""
if isinstance(target, ByteString):
pass
elif isinstance(target, str):
pass
elif isinstance(target, Iterator):
return target
elif isinstance(target, Iterable):
return iter(target)
def constant_iterator(
target_: Any) -> Generator[Variadic, None, None]:
for _ in range(length):
yield target_
return constant_iterator(target)
@classmethod
def _default_xor(cls, factory: Callable[..., Data]) -> Callable[[Data, Data], Data]:
"""
provides the default "exclusive or" operator to use for each round
The builtin `operator.xor` will be mapped to each element of
the `Data` sequences, and the result will be run through the
specified `factory`(e.g., a `Data` class constructor)
:param factory:
a factory that accepts a :map: object :term:`positional
argument` and returns a `Data` object
:returns: an "exclusive or" operator suitable for `bytes` and similar types
"""
def xor(left: Data, right: Data) -> Data:
return factory(map(operator.xor, left, right))
return xor
@classmethod
def _split(
cls, data: Data, *,
source_length: int, target_length: int, chirality: ChiralityType) -> tuple[Data, Data]:
"""
extract the `source` and `target` from `data` based on expected lengths and `chirality`
:returns: a :code:`(source, target)` `tuple`
"""
block_length = source_length + target_length
if chirality is cls.ChiralityType.SOURCE_TARGET:
source = cast(Data, data[-block_length:-target_length])
target = cast(Data, data[-target_length:])
elif chirality is cls.ChiralityType.TARGET_SOURCE:
source = cast(Data, data[-source_length:])
target = cast(Data, data[-block_length:-source_length])
else:
raise ValueError('invalid chirality value') # pragma: no cover
return source, target
@classmethod
def _combine(
cls, *, source: Data, target: Data, chirality: ChiralityType) -> Data:
"""
combine the `source` and `target` halves into output data based on `chirality`
"""
if chirality is cls.ChiralityType.SOURCE_TARGET:
return target + source # type: ignore
if chirality is cls.ChiralityType.TARGET_SOURCE:
return source + target # type: ignore
raise ValueError('invalid chirality value') # pragma: no cover
[docs] @classmethod
def encipher(
cls, *,
round_func: Union[Iterator[Function], Iterable[Function], Function],
key: Union[Iterator[Key], Iterable[Key], Key],
num_rounds: int,
data: Data,
source_length: int = None, target_length: int = None,
chirality: ChiralityType = ChiralityType.SOURCE_TARGET,
xor_operation: Callable[[Data, Data], Data] = None) -> Data:
"""
apply a generalized Feistel cipher to `data`
:param round_func:
the round function (or functions) that will accept a
source `Data` sequence, a `Key` key, and a target length
as inputs, and returns a `Data` sequence of the target
length. This can be a single callable, or an iterable
sequence of callables that will be used sequentially as
each round of the Feistel network is calculated
:param key:
A 'Key' object (or objects) that will be used as input to
the round function(s). It can be a single value, or an
iterable sequence of values
:param num_rounds:
the number of Feistel network rounds to use when
generating the enciphered output
:param data:
a `Data` sequence to be enciphered (i.e., the "plaintext")
:param source_length:
the length of the `data` that should be considered the
"source" in each round of the Feistel network (the source
is used as input to the round function)
:param target_length:
the length of the `data` that should be considered the
"target" in each round of the Feistel network (the target
is mixed with the output of the round function)
:param chirality:
determines which portion of the `data` is the "source" and
which is the "target"
:param xor_operation:
the operation that will be used to combine (a) the output
of the round function and (b) the target data. If none is
provided, the default is to `map` `operator.xor` to each
element of the values, and create a new `Data` instance
from that `map` object. I.e.::
combined = type(data)(map(operator.xor, output, target))
This will likely be suitable for most :term:`sequence` types
:returns:
the enciphered data
"""
source_length, target_length = cls._length_parameters(
input_length=len(data), source_length=source_length, target_length=target_length)
if source_length + target_length > len(data):
raise ValueError('insufficient input')
round_func = cls._iterator_wrap(round_func, num_rounds)
key = cls._iterator_wrap(key, num_rounds)
xor_operation = xor_operation or cls._default_xor(type(data))
round_: Optional[int] = None
for round_, (round_func_, key_) in enumerate(zip(round_func, key)):
if round_ >= num_rounds:
break
source, target = cls._split(
data,
source_length=source_length, target_length=target_length, chirality=chirality)
output_ = round_func_(source, key_, target_length)
if len(output_) != target_length:
raise RuntimeError('`round_func` return size did not match `target_length`')
target = xor_operation(output_, target)
data = cls._combine(source=source, target=target, chirality=chirality)
if round_ < num_rounds - 1:
raise ValueError('insufficient `round_func` or `key` for specified `num_rounds`')
return data
[docs] def __init__(
self, *,
round_func: Union[Iterator[Function], Iterable[Function], Function],
key: Union[Iterator[Key], Iterable[Key], Key],
num_rounds: int,
chirality: ChiralityType = ChiralityType.SOURCE_TARGET,
xor_operation: Callable[[Data, Data], Data] = None):
"""
Initialize a re-usable Feistel network
:param round_func:
the round function (or functions) that will accept a
source `Data` sequence, a `Key` key, and a target length
as inputs, and returns a `Data` sequence of the target
length. This can be a single callable, or an iterable
sequence of callables that will be used sequentially as
each round of the Feistel network is calculated
:param key:
A 'Key' object (or objects) that will be used as input to
the round function(s). It can be a single value, or an
iterable sequence of values
:param num_rounds:
the number of Feistel network rounds to use when
generating the enciphered output
:param chirality:
determines which portion of the `data` is the "source" and
which is the "target"
:param xor_operation:
the operation that will be used to combine (a) the output
of the round function and (b) the target data. If none is
provided, the default is to `map` `operator.xor` to each
element of the values, and create a new `Data` instance
from that `map` object. I.e.::
combined = type(data)(map(operator.xor, output, target))
This will likely be suitable for most :term:`sequence` types
:returns:
the enciphered data
"""
self.round_func = round_func
self.key = key
self.num_rounds = num_rounds
self.chirality = chirality
self.xor_operation = xor_operation
@classmethod
def _reversed_chirality(cls, chirality: ChiralityType) -> ChiralityType:
"""
return the opposite chirality
"""
if chirality is cls.ChiralityType.SOURCE_TARGET:
return cls.ChiralityType.TARGET_SOURCE
if chirality is cls.ChiralityType.TARGET_SOURCE:
return cls.ChiralityType.SOURCE_TARGET
raise ValueError('invalid chirality value') # pragma: no cover
[docs] def encrypt(self, data: Data, source_length: int = None, target_length: int = None) -> Data:
"""
encipher `data` using the Feistel network in the "forward" direction
:param data:
the data to be encrypted
:param source_length:
explicitly specify the length of the `data` that should be
considered the "source" in each round of the Feistel
network (the source is used as input to the round
function)
:param target_length:
explicitly specify the length of the `data` that should be
considered the "target" in each round of the Feistel
network (the target is mixed with the output of the round
function)
"""
return self.encipher(
round_func=self.round_func,
key=self.key,
num_rounds=self.num_rounds,
data=data,
source_length=source_length,
target_length=target_length,
chirality=self.chirality,
xor_operation=self.xor_operation)
[docs] def decrypt(self, data: Data, source_length: int = None, target_length: int = None) -> Data:
"""
decipher `data` using the Feistel network in the "reverse" direction
:param data:
the data to be encrypted
:param source_length:
explicitly specify the length of the `data` that should be
considered the "source" in each round of the Feistel
network (the source is used as input to the round
function)
:param target_length:
explicitly specify the length of the `data` that should be
considered the "target" in each round of the Feistel
network (the target is mixed with the output of the round
function)
"""
return self.encipher(
round_func=reversed(tuple(self._iterator_wrap(self.round_func, self.num_rounds))),
key=reversed(tuple(self._iterator_wrap(self.key, self.num_rounds))),
num_rounds=self.num_rounds,
data=data,
source_length=source_length,
target_length=target_length,
chirality=self._reversed_chirality(self.chirality),
xor_operation=self.xor_operation)