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.

Type aliases and parameters

There are a number of types, type aliases [#alias[_, and type parameters defined in this module. Some are used to describe the functions that are passed to the various game classes. Others are used for what passes for the state management within the games.

Types for setup functions

class toy_crypto.sec_games.K

Unbounded type variable intended for any type of key.

alias of TypeVar(‘K’)

toy_crypto.sec_games.KeyGenerator

A parameterized type alias to describe the key generator functions. defined as Callable[[], K]

toy_crypto.sec_games.Cryptor

A parameterized type alias to describe the encryptor/decrptor functions. defined as Callable[[K, bytes], bytes]

Types for state management

class toy_crypto.sec_games.State(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)

The state a game.

CHALLENGED = 'C'

Challenge text created.

INITIALIZED = 'I'

Game is initialized

STARTED = 'S'

Game has not been initialized.

class toy_crypto.sec_games.Action(value, names=<not given>, *values, module=None, qualname=None, type=None, start=1, boundary=None)

Adversary actions (Methods called by A).

DECRYPT = 'decrypt'

decrypt() called

ENCRYPT = 'encrypt'

encrypt() called.

ENCRYPT_ONE = 'encrypt_one'

encrypt_one() called.

FINALIZE = 'finalize'

finalize() called.

INITIALIZE = 'initialize'

initialize() called.

toy_crypto.sec_games.TransitionTable

Defined as Mapping[State, Mapping[Action, State]]

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)

A super class for symmetric Indistinguishability games.

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

Parameters:

• key_gen (KeyGenerator[K])

• encryptor (Cryptor[K])

• decryptor (Cryptor[K] | None)

• transition_table (TransitionTable | None)

The classes only [3] 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.

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.

Also resets the challenger, as for this game you cannot call with same key, b pair more than once.

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])

IND-EAV game.

Parameters:

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

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

Raises:

StateError – if methods called in disallowed order.

IND-EAV game states and transitions

T_TABLE: TransitionTable = {State.CHALLENGED: {Action.FINALIZE: State.STARTED}, State.INITIALIZED: {Action.ENCRYPT_ONE: State.CHALLENGED}, State.STARTED: {Action.INITIALIZE: State.INITIALIZED}}

Transition table for EAV game

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

IND-CPA game.

Parameters:

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

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

IND-CPA game states and transitions

T_TABLE: TransitionTable = {State.CHALLENGED: {Action.ENCRYPT_ONE: State.CHALLENGED, Action.FINALIZE: State.STARTED}, State.INITIALIZED: {Action.ENCRYPT_ONE: State.CHALLENGED}, State.STARTED: {Action.INITIALIZE: State.INITIALIZED}}

Transition table for CPA game.

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])

IND-CCA game.

Parameters:

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

• encryptor (Cryptor[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 (Cryptor[K])

Raises:

StateError – if methods called in disallowed order.

IND-CCA1 game states and transitions

T_TABLE: TransitionTable = {State.CHALLENGED: {Action.ENCRYPT: State.CHALLENGED, Action.FINALIZE: State.STARTED}, State.INITIALIZED: {Action.DECRYPT: State.INITIALIZED, Action.ENCRYPT: State.INITIALIZED, Action.ENCRYPT_ONE: State.CHALLENGED}, State.STARTED: {Action.INITIALIZE: State.INITIALIZED}}

Transition table for IND-CCA1 game

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

IND-CCA game.

Parameters:

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

• encryptor (Cryptor[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 (Cryptor[K])

Raises:

StateError – if methods called in disallowed order.

IND-CCA1 game states and transitions

T_TABLE: TransitionTable = {State.CHALLENGED: {Action.DECRYPT: State.CHALLENGED, Action.ENCRYPT: State.CHALLENGED, Action.FINALIZE: State.STARTED}, State.INITIALIZED: {Action.DECRYPT: State.INITIALIZED, Action.ENCRYPT: State.INITIALIZED, Action.ENCRYPT_ONE: State.CHALLENGED}, State.STARTED: {Action.INITIALIZE: State.INITIALIZED}}

Transition table for IND-CCA2 game

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.

[2]

I am open to recommendations on how to document type aliases with Sphinx.

[3]

Well, almost only. Specific games may introduce specifc checks on input, and so will wrap the Ind class methods.