Danger

Nothing here should be used for any security purposes.

• If you need cryptographic tools in a Python environment use pyca.

• If you need efficient and reliable abstract math utilities in a Python-like environment consider using SageMath.

Security games

Imported with:

import toy_crypto.sec_games

The module includes a classes for running the several ciphertext indistisguishability games for symmetric encryption game.

General Structure

Indisitinguisibility games are set up as an adversary playing against a game (or Challenger). The game is given an encryption scheme and a key generation function. So creating a game will often look like

def keygen() -> bytes:
    ...

def encrypt(key: by, m: bytes) -> bytes:
    ...

game = IndCpa(keygen, encrypt)

Once that is done, the adversary can interact with the game according to the rules of the particular game.

The first thing (in how I’ve coding things here) is that the adversary will tell the game to initialize itself.

game.initialize()
...

During that initialization the game will generate a key and randomly select 0 or 1 as the value of the bit b. The adversary’s task durig the course of the game is to figure out the value of b. At the end of a round, the adversary will finalize the game by submitting its guess.

...
if game.finalize(guess):
    # Yay! Guessed correctly
    adv_score += 1

The only thing the adversary can do with the game after finalizing is to tell it to re-initialize [1] , which will generate a fresh key and value for the bit, b.

Between initialization and finalization the adversary can ask the game to to perform certain computions, which may include encrypting or decrypting data of the adversaries chosing. Which are available and in what sequences depends on the specific game.

The computation that is essential to all of these games is to encrypt one of two messages provided by the adversary. The game returns a challenge ciphertext that is the encryption of one of the messages depending on its value of b. So the adversary is really trying to figure out if whether it is the left or right message that gets encrypted.

game.initialize()
...
challenge_ctext = game.encrypt_one(m0, m1)
...
if game.finalize(guess):
    ...

To save having to create many instances of a game with the same encryption scheme, py:func:Ind.initialize can be called after a game is finalized to start over with a fresh key and b while using the same encryption scheme. [1]

Examples

For testing, it is useful to have a challenge that the adversary can always win, so we will use a shift ciper for testing IND-EAV and a reused pad (N-time-pad) for testing IND-CPA.

import secrets
from toy_crypto.sec_games import IndEav, IndCpa

def shift_encrypt(key: int, m: bytes) -> bytes:
    encrypted: bytes = bytes([(b + key) % 256 for b in m])
    return encrypted

def shift_keygen() -> int:
    return secrets.randbelow(256)

The shift-cipher IND-EAV condition (and thus does not provide semantic security). The adversary will set m0 = "AA" and m1 = AB. If m0 is encrypted then the two bytes of the challenge ciphertext will be the same as each other. If they differ, then m1 was encrypted.

game = IndEav(shift_keygen, shift_encrypt)
game.initialize()

m0 = b"AA"
m1 = b"AB"
ctext = game.encrypt_one(m0, m1)

guess: bool = ctext[0] != ctext[1]

assert game.finalize(guess)  # passes if guess is correct

Let’s use a stronger cipher, the N-Time-Pad for our IND-CPA example.

# import secrets  # already imported
from toy_crypto.utils import xor

def ntp_keygen() -> bytes:
    return secrets.token_bytes(16)

def ntp_encrypt(key: bytes, m: bytes) -> bytes:
    if len(m) > len(key):
        raise ValueError("message too long")
    return xor(key, m)

The N-Time-Pad (up to limited message length) is semantically secure. One can prove that any adversary that can reliability win the IND-EAV game can reliabily predict bits from the presumed security random number generator. Thus the NTP is at least as secure as the random number generator.

But because the NTP is deterministic it will fail IND-CPA security.

game = IndCpa(ntp_keygen, ntp_encrypt)
game.initialize()

m0 = b"Attack at dawn!"
m1 = b"Attack at dusk!"
ctext1 = game.encrypt_one(m0, m1)
ctext2 = game.encrypt_one(m1, m1)

guess: bool = ctext1 == ctext2

assert game.finalize(guess)  # passes if guess is correct

Exceptions

class toy_crypto.sec_games.StateError

When something attempted in an inappropriate state.

Types for encryption scheme

When a game is set up, it must be given an encryption scheme, which will include a key generation function, an encryption function, and optionally a decryption function.

Spinx doesn’t seem to have good ways of documenting these, but hopefully what I list here makes some sense.

type toy_crypto.sec_games.KeyGenerator = Callable[[], K]

A parameterized type alias for the key generation function.

type toy_crypto.sec_games.Cryptor = Callable[[K, bytes], bytes]

A parameterized type alias to describe the encryptor/decrptor functions.

The class and method organization

All of the specific game classes are subclasses of the Ind class.

class toy_crypto.sec_games.Ind(key_gen: KeyGenerator[K], encryptor: Cryptor[K], decryptor: Cryptor[K] | None = None, transition_table: TransitionTable | None = None) → None

A super class for symmetric Indistinguishability games.

Unless the user provides an appropriate transition table, no methods will be allowed.

Parameters:

• key_gen (GenericAlias[TypeVar(K)])

• encryptor (GenericAlias[TypeVar(K)])

• decryptor (Optional[GenericAlias[TypeVar(K)]], default: None)

• transition_table (Optional[TransitionTable], default: None)

TRACK_CHALLENGE_CTEXTS: bool

Game does not track which challenge texts have been created

The classes optionally differ in which methods they offer and the sequence in which they are called. That ordiering defined by the transition tables in T_TABLE with the initial stated being State.STARTED.

All games allow the initialize(), encrypt_one() and finalize(), methods.

Ind.initialize() → None

Initializes self by creating key and selecting b.

Also clears an saved challenge ciphertexts.

Raises:

StateError – if method called when disallowed.

Return type:

None

Ind.encrypt_one(m0: bytes, m1: bytes) → bytes

Left-Right encryption oracle.

Challenger encrypts m0 if b is False, else encrypts m1.

Parameters:

• m0 (bytes) – Left message

• m1 (bytes) – Right message

Raises:

• ValueError – if lengths of m0 and m1 are not equal.

• StateError – if method called when disallowed.

Return type:

bytes

Ind.finalize(guess: SupportsBool) → bool

True iff guess is the same as b of previously created challenger.

Raises:

StateError – if method called when disallowed.

Parameters:

guess (SupportsBool)

Return type:

bool

Some of the games allow the encrypt() and decrypt(), methods.

Ind.encrypt(ptext: bytes) → bytes

Encryption oracle.

Parameters:

ptext (bytes) – Message to be encrypted

Raises:

StateError – if method called when disallowed.

Return type:

bytes

Ind.decrypt(ctext: bytes) → bytes

Decryption oracle.

Parameters:

ctext (bytes) – Ciphertext to be decrypted

Raises:

StateError – if method called when disallowed.

Return type:

bytes

The only difference between IndEav and IndCpa is that the latter allows multiple calls to encrypt_one().

class toy_crypto.sec_games.IndEav(key_gen: KeyGenerator[K], encryptor: Cryptor[K]) → None

IND-EAV game.

Parameters:

• key_gen (GenericAlias[TypeVar(K)]) – A key generation function appropriate for encryptor

• encryptor (GenericAlias[TypeVar(K)]) – A function that takes a key and message and outputs ctext

Raises:

StateError – if methods called in disallowed order.

T_TABLE

Transition Table to manage state of a game.

It can be treated like a mapping.

TransitionTable(table={ <State.STARTED: 'S'>: { <Action.INITIALIZE: 'initialize'>: <State.INITIALIZED: 'I'>},
                        <State.INITIALIZED: 'I'>: { <Action.ENCRYPT_ONE: 'encrypt_one'>: <State.CHALLENGED: 'C'>},
                        <State.CHALLENGED: 'C'>: { <Action.FINALIZE: 'finalize'>: <State.STARTED: 'S'>}})

IND-EAV game states and transitions

TRACK_CHALLENGE_CTEXTS: bool = False

This game does not need to record challenge ctexts.

class toy_crypto.sec_games.IndCpa(key_gen: KeyGenerator[K], encryptor: Cryptor[K]) → None

IND-CPA game.

Parameters:

• key_gen (GenericAlias[TypeVar(K)]) – A key generation function appropriate for encryptor

• encryptor (GenericAlias[TypeVar(K)]) – A function that takes a key and message and outputs ctext

T_TABLE

Transition Table to manage state of a game.

It can be treated like a mapping.

TransitionTable(table={ <State.STARTED: 'S'>: { <Action.INITIALIZE: 'initialize'>: <State.INITIALIZED: 'I'>},
                        <State.INITIALIZED: 'I'>: { <Action.ENCRYPT_ONE: 'encrypt_one'>: <State.CHALLENGED: 'C'>},
                        <State.CHALLENGED: 'C'>: { <Action.ENCRYPT_ONE: 'encrypt_one'>: <State.CHALLENGED: 'C'>,
                                                   <Action.FINALIZE: 'finalize'>: <State.STARTED: 'S'>}})

IND-CPA game states and transitions

TRACK_CHALLENGE_CTEXTS: bool = False

This game does not need to record challenge ctexts.

The only difference between IndCca1 and IndCca2 is the latter allows calls to decrypt() the challenge ciphertext has been provided by encrypt_one(). The challenge ciphertext cannot be given to decrypt().

class toy_crypto.sec_games.IndCca1(key_gen: KeyGenerator[K], encryptor: Cryptor[K], decrytpor: Cryptor[K]) → None

IND-CCA1 game.

Parameters:

• key_gen (GenericAlias[TypeVar(K)]) – A key generation function appropriate for encryptor

• encryptor (GenericAlias[TypeVar(K)]) – A function that takes a key and message and outputs ctext

• decryptor – A function that takes a key and ciphertext and outputs plaintext

• decrytpor ()

Raises:

StateError – if methods called in disallowed order.

TransitionTable(table={ <State.STARTED: 'S'>: { <Action.INITIALIZE: 'initialize'>: <State.INITIALIZED: 'I'>},
                        <State.INITIALIZED: 'I'>: { <Action.ENCRYPT_ONE: 'encrypt_one'>: <State.CHALLENGED: 'C'>,
                                                    <Action.ENCRYPT: 'encrypt'>: <State.INITIALIZED: 'I'>,
                                                    <Action.DECRYPT: 'decrypt'>: <State.INITIALIZED: 'I'>},
                        <State.CHALLENGED: 'C'>: { <Action.FINALIZE: 'finalize'>: <State.STARTED: 'S'>,
                                                   <Action.ENCRYPT: 'encrypt'>: <State.CHALLENGED: 'C'>}})

IND-CCA1 game states and transitions

TRACK_CHALLENGE_CTEXTS: bool = False

This game does not need to record challenge ctexts.

class toy_crypto.sec_games.IndCca2(key_gen: KeyGenerator[K], encryptor: Cryptor[K], decrytpor: Cryptor[K]) → None

IND-CCA2 game.

Parameters:

• key_gen (GenericAlias[TypeVar(K)]) – A key generation function appropriate for encryptor

• encryptor (GenericAlias[TypeVar(K)]) – A function that takes a key and message and outputs ctext

• decryptor – A function that takes a key and ciphertext and outputs plaintext

• decrytpor (GenericAlias[TypeVar(K)])

Raises:

StateError – if methods called in disallowed order.

T_TABLE

Transition Table to manage state of a game.

It can be treated like a mapping.

TransitionTable(table={ <State.STARTED: 'S'>: { <Action.INITIALIZE: 'initialize'>: <State.INITIALIZED: 'I'>},
                        <State.INITIALIZED: 'I'>: { <Action.ENCRYPT_ONE: 'encrypt_one'>: <State.CHALLENGED: 'C'>,
                                                    <Action.ENCRYPT: 'encrypt'>: <State.INITIALIZED: 'I'>,
                                                    <Action.DECRYPT: 'decrypt'>: <State.INITIALIZED: 'I'>},
                        <State.CHALLENGED: 'C'>: { <Action.FINALIZE: 'finalize'>: <State.STARTED: 'S'>,
                                                   <Action.ENCRYPT: 'encrypt'>: <State.CHALLENGED: 'C'>,
                                                   <Action.DECRYPT: 'decrypt'>: <State.CHALLENGED: 'C'>}})

IND-CCA2 game states and transitions

TRACK_CHALLENGE_CTEXTS: bool = True

CCA2 needs to prevent decrypt() from decrypting challenge ctexts.

State management tools

As described above, the difference between the particular gaves is defined by what action the adversary can take when. This is specified within the TransitionTable for each.

enum toy_crypto.sec_games.State(value)

The state a game.

Member Type:

str

Valid values are as follows:

STARTED = <State.STARTED: 'S'>

INITIALIZED = <State.INITIALIZED: 'I'>

CHALLENGED = <State.CHALLENGED: 'C'>

enum toy_crypto.sec_games.Action(value)

Adversary actions (Methods called).

Member Type:

str

Valid values are as follows:

INITIALIZE = <Action.INITIALIZE: 'initialize'>

ENCRYPT_ONE = <Action.ENCRYPT_ONE: 'encrypt_one'>

ENCRYPT = <Action.ENCRYPT: 'encrypt'>

DECRYPT = <Action.DECRYPT: 'decrypt'>

FINALIZE = <Action.FINALIZE: 'finalize'>

class toy_crypto.sec_games.TransitionTable(table: Mapping[State, Mapping[Action, State]]) → None

Transition Table to manage state of a game.

It can be treated like a mapping.

Parameters:

table (Mapping[State, Mapping[Action, State]])

__getitem__(item: State) → Mapping[Action, State]

So that items can be looked up with [key] as in a real dict.

Parameters:

item (State)

Return type:

Mapping[Action, State]

keys() → KeysView[State]

Just like keys for a real dict.

Return type:

KeysView[State]

protocol toy_crypto.sec_games.SupportsTTable

Has what it takes to be decorated by manage_state().

This protocol also depends on a private member. See source if you need to make this work for something other than an Ind. Classes that implement this protocol must have the following methods / attributes:

current_state: State

t_table: TransitionTable

Each method that the adversary can call is wrapped by the @manage_state decorator

@toy_crypto.sec_games.manage_state(fn: F) → F

Decorator to check/transition state for Ind method calls.

Parameters:

fn (TypeVar(F, bound= Callable[..., Any]))

Return type:

TypeVar(F, bound= Callable[..., Any])

Footnotes

[1] (1,2)

The reason I separated game initialization from game creation is because the user may wish to rerun a game many times. After all, the adversary doesn’t need to win every time to win overall. It only needs to win meaningfully more than half the time. And so I didn’t want to user to have to create a large number of instances of a game class and have to rely on the Python garbage collector to free up memory.