Notebook

Foundations of Cryptography¶

Modular Arithmetic¶

A number $x \bmod N$ is the equivalent of asking for the remainder of $x$ when divided by $N$ .

Two integers $a$ and $b$ are said to be congruent (or in the same equivalence class) modulo $N$ if they have the same remainder upon division by $N$ . In such a case, we say that

$a \equiv b \pmod N$

Addition in Modular Arithmetic¶

If $a + b = c$ , then $a \pmod N + b \pmod N \equiv c \pmod N$
If $a \equiv b \pmod N$ , then $a + k \equiv b + k \pmod N$ for any integer $k$
If $a \equiv b \pmod N$ and $c \equiv d \pmod N$ , then $a + c \equiv b + d \pmod N$
If $a \equiv b \pmod N$ , then $-a \equiv -b \pmod N$

Multiplication in Modular Arithmetic¶

If $a \cdot b = c$ , then $a \pmod N \cdot b \pmod N \equiv c \pmod N$
If $a \equiv b \pmod N$ , then $k \cdot a \equiv k \cdot b \pmod N$ for any integer $k$
If $a \equiv b \pmod N$ and $c \equiv d \pmod N$ , then $a \cdot c \equiv b \cdot d \pmod N$

Exponentiation in Modular Arithmetic¶

If $a \equiv b \pmod N$ , then $a^k \equiv b^k \pmod N$ for any integer $k$

Division in Modular Arithmetic¶

If $\gcd(k, N) = 1$ and $k \cdot a \equiv k \cdot b \pmod N$ , then $a \equiv b \pmod N$

This property is true, because if $k \cdot (a−b)$ is a multiple of $N$ and $\gcd(k, N) = 1$ , then $N$ must divide $a-b$ , or equivalently $a \equiv b \pmod N$ .

Example: Consider $4 \equiv 8 \pmod 4$ . Note that we cannot simply divide both sides of the equation by $2$ , since $2 \not \equiv 4 \pmod 4$ .

Multiplicative Inverse in Modular Arithmetic¶

If $a$ and $N$ are integers such that $\gcd(a, N) = 1$ (coprime or relatively prime), then there exists an integer $b$ such that $a \cdot b \equiv 1 \pmod N$ . $b$ is called the multiplicative inverse of $a \bmod N$ .

Examples:

$2 \cdot 3 \equiv 1 \pmod{5}$
$2 \cdot 6 \equiv 1 \pmod{11}$

In [1]:

# reference: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode
def mod_inv(x, m):
    r0, r1 = x, m
    s0, s1 = 1, 0
    while r1 != 0:
        quotient = r0 // r1
        r0, r1 = r1, r0 - quotient * r1
        s0, s1 = s1, s0 - quotient * s1
    if r0 != 1:
        return None
    return s0 if s0 >= 0 else s0 + m

In [2]:

mod_inv(2, 11)

Out[2]:

The XOR Operation¶

The boolean XOR (exclusive OR) operation form an abelian group $(\,\{T, F\}^N, \,\oplus\,)$ over the set of boolean vectors of length $N$ :

Closure: when you XOR two boolean vectors $A$ and $B$ , the result $C$ is also a boolean vector
Commutative: $A \oplus B = B \oplus A$
Associative: $A \oplus (B \oplus C) = (A \oplus B) \oplus C$
The identity element for the XOR operation is $T^N$ with $A \oplus T^N = T^N \oplus A = A$
Inverse element: each element is its own inverse, i.e. $A \oplus A = T^N$

Isomorphism¶

Two groups are said to be isomorphic if there is a one-to-one mapping between the elements of the sets that preserves the operation.

The group $(\,\{T, F\}^N, \,\oplus\,)$ is isomorphic to the group $(\,\{0, 1\}^N, \, + \,)$ of addition modulo 2 over the set of vectors whose elements are integers mod 2.

→ The isomorphism simply maps $T$ to $1$ and $F$ to $0$ .

In [3]:

print((0 + 0) % 2, 0 ^ 0)
print((1 + 0) % 2, 1 ^ 0)
print((0 + 1) % 2, 0 ^ 1)
print((1 + 1) % 2, 1 ^ 1)

The group $(\,\{T, F\}^N, \,\oplus\,)$ is also isomorphic to the group $(\,\text{S}^N, \, \Delta \;)$ of symmetric difference $\Delta$ over the power set of $N$ elements (set of all possible subsets of $\text{S}$ ).

Symmetric difference is a set operation that gives the set of elements that are in either of the sets but not in their intersection:

$\begin{align} A \, \Delta \, B &= (A / B) \cup (B / A) \qquad \text{or} \\[8pt] A \, \Delta \, B &= (A \cup B) / (B \cap A) \end{align}$

→ The isomorphism maps $T$ to included in the set and $F$ to excluded from the set for each of the $N$ entries of the Boolean vector.

Properties of the XOR Operation¶

Toggling¶

The combined value $A \oplus B$ remembers both states, and one state is the key to getting at the other:

$\begin{align} A \oplus (A \oplus B) &= (A \oplus A) \oplus B \\[6pt] &= 0 \oplus B \\[6pt] &= B \end{align}$

and

$\begin{align} B \oplus (A \oplus B) &= B \oplus (B \oplus A) \\[6pt] &= (B \oplus B) \oplus A \\[6pt] &= 0 \oplus A \\[6pt] &= A \end{align}$

Parity¶

A powerful interpretation of XOR is in terms of parity, i.e. whether something is odd or even.

For any $n$ bits, $A_1 \oplus A_2 \oplus \ldots \oplus A_n = 1$ if and only if the number of $1$ s is odd.

An application of XOR’s parity property is RAID (Redundant Arrays of Inexpensive Disks) which is a way to recover from hard drive corruption.

If we have $n$ hard drives, we can create an additional one $A^*$ which contains the XOR value of all the others:

$A^* = A_1 \oplus A_2 \oplus \ldots \oplus A_n$

This introduces redundancy: if a failure occurs on one drive, say $A_1$ , we can restore it from the others since:

$\begin{align} A_2 \oplus \ldots \oplus A_n \oplus A^* &= A_2 \oplus \ldots \oplus A_n \oplus (A_1 \oplus A_2 \oplus \ldots \oplus A_n) \\[6pt] &= A_1 \oplus (A_2 \oplus A_2) \oplus \ldots \oplus (A_n \oplus A_n) \\[6pt] &= A_1 \oplus 0 \oplus \ldots \oplus 0 \\[6pt] &= A_1 \end{align}$

(this is the same reasoning used to explain toggling earlier, but applied to $n$ inputs rather than just $2$ )

In the (highly unlikely) event that 2 drives fail simultaneously, the above would not be applicable so there would be no way to recover the data.

Cryptography Principles¶

Kerckhoffs's Principle¶

TODO

Key-Space¶

The key space should be large enough to prevent brute-force and exhaustive-search attacks.

Encryption Schemes¶

A private-key encryption scheme $(\textbf{M}, \textbf{K}, \text{Gen}, \text{Enc}_k, \text{Dec}_k)$ is defined by a message space with the algorithms:

Key generation $\text{Gen}$ which generates a key $k \in \textbf{K}$ from the key space,

Encryption $\text{Enc}_k$ which takes key $k$ and message $m \in \textbf{M}$ from the message space as input and outputs a ciphertext $c \in \textbf{C}$ from the ciphertext space

$c \gets \text{Enc}_k (m)$

Decryption $\text{Dec}_k$ which takes key $k$ and ciphertext $c$ as input and outputs message $m$

$m := \text{Dec}_k (c)$

$\text{Dec}_k$ should decrypt correctly:

$\forall k, \forall m: \quad \text{Dec}_k(\text{Enc}_k(m)) = m$

Here

the left arrow $\gets$ notation denotes assignment to the output of an algorithm that might be randomized. Meaning that the output of the algorithm may be different, even when run twice on the same set of inputs,
the colon equals $:=$ denotes an assignment to the output of a deterministic algorithm and
If the key $k$ is the same for encryption and decryption, then we call it a symetrci cipher.

On Probability¶

a random valriable is a variable that takes on (discrete) values with certain probabilities.
a probability distribution of a random variable specifies the probabilities with which the variable taes on each possible value
an event $\text{E}$ is a particular occurence in some experiment with the probability $\text{P}[\,\text{E}\,]$
the probability that one event occurs, assuming some other event occured is called conditional probability ( $\cap$ corresponds to "and")

$\text{P}[\,\text{A}\, | \,\text{B}\,] = \frac{\text{P}[\,\text{A}\, \cap \text{B}\,]}{\text{P}[\,\text{B}\,]}$

two random variables $\text{A}$ and $\text{B}$ are independent if for all $a$ and $b$

$\text{P}[\,\text{A} = a\, | \,\text{B} = b\,] = \text{P}[\,\text{A} = a\,]$

Law of total probability: given that $\text{E}_1, \ldots, \text{E}_n$ are partitions of all possibilities, then for any $\text{A}$

$\begin{align} \text{P}[\,\text{A}\,] &= \sum_i \text{P}[\,\text{A} \cap \text{E}_i\,] \qquad \text{or alternatively} \\[6pt] &= \sum_i \text{P}[\,\text{A}\, | \,\text{E}_i\,] \cdot \text{P}[\,\text{E}_i\,] \end{align}$

Bayes Theorem

$\text{P}[\,\text{A}\, | \,\text{B}\,] = \frac{\text{P}[\,\text{B}\, | \,\text{A}\,] \cdot \text{P}[\,\text{A}\,]}{\text{P}[\,\text{B}\,]}$

Probability Distributions of Encryption Schemes¶

Let $\text{M}$ be a random variable denoting the value of a message from the message space $\textbf{M}$ (set of all possible messages).

This reflects the likelyhood of different messages sent by the parties, given the attackers prior knowledge, e.g.

$\begin{align} &\text{P}[\, \text{M} = \text{attack today}\,] = 0.7 \\ &\text{P}[\, \text{M} = \text{do not attack}\,] = 0.3 \end{align}$

Let $\text{K}$ be a random variable denoting the key from the key space $\textbf{K}$ (set of all possible keys).

Given a encryption scheme $(\text{Gen}, \text{Enc}_k, \text{Dec}_k)$ , then $\text{Gen}$ defines a probability distribution for $\text{K}$ :

$\text{P}[\,\text{K} = k\,] = \text{P}[\,\text{Gen outputs key}\; k\,]$

Example: consider the shift cipher where the key space is $\textbf{K} = (0, \ldots, 25)$ , then $\text{P}[\, \text{K} = 15\,] = 1/26$

Here we make the reasonable assumption, that $\text{M}$ and $\text{K}$ are independent variables, i.e. the message that a party sends does not depend on the key used to encrypt the message.

Given an encryption scheme $(\text{Gen}, \text{Enc}_k, \text{Dec}_k)$ , then a message $m$ according the given distribution $\text{M}$ defines a distribution of the ciphertext.

Let $\text{C}$ be the random variable denoting the value of the ciphertext from the ciphertext space $\textbf{C}$ (set of all possible ciphertexts).

Example 1¶

Given a shift cipher, then for all $k \in \{0, \ldots, 25\}$ we have $\text{P}[\, \text{K} = k\,] = 1/26$ .

Say we have the distribution

$\begin{align} &\text{P}[\,\text{M} = \text{a}\,] = 0.7 \\ &\text{P}[\, \text{M} = \text{z}\,] = 0.3 \end{align}$

then what is $\text{P}[\, \text{C} = \text{b}\,]$ ?

The ciphertext $\text{C}$ can only be $\text{b}$ , if $\text{M} = \text{a}$ and $\text{K} = 1$ or if $\text{M} = \text{z}$ and $\text{K} = 2$ , hence

$\begin{align} \text{P}[\,\text{C} = \text{b}\,] &= \text{P}[\,\text{M} = \text{a}\,] \cdot \text{P}[\,\text{K} = 1\,] + \text{P}[\,\text{M} = \text{z}\,] \cdot \text{P}[\,\text{K} = 2\,] \\[7pt] &= 0.7 \cdot 1/26 + 0.3 \cdot 1/26 \\[7pt] &= 1/26 \\ \end{align}$

Example 2¶

Consider a shift cipher and the message distribution

$\begin{align} &\text{P}[\,\text{M} = \text{one}\,] = 0.5 \\ &\text{P}[\, \text{M} = \text{ten}\,] = 0.5 \end{align}$

What is $\text{P}[\, \text{C} = \text{rqh}\,]$ ?

Due to the law of total probability we calculate

$\begin{align} \text{P}[\,\text{C} = \text{rqh}\,] &= \text{P}[\,\text{C} = \text{rqh}\, | \, \text{M} = \text{one}\,] \cdot \text{P}[\, \text{M} = \text{one}\,] + \text{P}[\,\text{C} = \text{rqh}\, | \, \text{M} = \text{ten}\,] \cdot \text{P}[\, \text{M} = \text{ten}\,] \\[7pt] &= 1/26 \cdot 0.5 + 0 \cdot 0.5 \\[7pt] &= 1/52 \\ \end{align}$

Core Principles of Modern Cryptography¶

Formal Definitions: precise mathematical model and definition of what security means
Assumptions: clearly stated and unambigious
Proofs of Security: move away from design-break-patch

Perfect Secrecy¶

Informal Definition of Perfect Secrecy¶

"Regardless of any prior information the attacker has about the plaintext, the ciphertext should leak no additional information about the plaintext"

We cannot hide what may be a priori known about the message. Prior information about the message might for example be: it is in English, starts with "Hello", contains today's date, etc.

Formal Definition of Perfect Secrecy¶

The following definitions of Shannon secrecy is equivalent to the definition of perfect secrecy.

Shannon Secrecy¶

The probability of seeing a posteriori a message $m$ after the ciphertext $c$ has been observed by an attacker, is the same as the apriori probability of seeing the message $m$ without the ciphertext, i.e. seeing a ciphertext doesn't give the attacker any extra information about the plaintext.

$\text{P}[\, \text{M} = m\, | \, \text{C} = c \,] = \text{P}[\, \text{M} = m \,]$

Let $\text{M}$ be a random variable for sampling the messages $m$ from the message space $\textbf{M}$ . The distribution $\text{M}$ is known to the adversary. This captures a priori information about the messages.

The ciphertext $c \gets \text{Enc}_k (m)$ induces a distribution $\text{C}$ over the ciphertexts $c$ . The attacker obly observes $c$ .

The knowledge of the attacker about $m$ before observing the output of $\text{C}$ is the distribution $\text{P}[\, \text{M} \,]$ (e.g. the knowledge that the message is in english).

The knowledge of the attacker about $m$ after observing the output of $\text{C}$ is the distribution $\text{P}[\, \text{M}\, | \, \text{C} \,]$ .

Shannon Secrecy: distribution $\text{P}[\, \text{M} \,]$ and $\text{P}[\, \text{M}\, | \, \text{C} \,]$ must be identical. Intuitively, this means that $\text{C}$ contains no new information about $m$ .

Perfect Secrecy¶

The probability of ciphertext $c$ is equally likely for each pair of messages $m_0$ and $m_1$ .

$\text{P}[\, \text{C} = c\, | \, \text{M} = m_0 \,] = \text{P}[\, \text{C} = c\, | \, \text{M} = m_1 \,]$

This definition is simpler than Shannon Secrecy, it basically says that

Even if given a choice of two plaintexts for a ciphertext, where one the real one, you cannot distinguish which plaintext is the real one.

Perfect Indistinguishability¶

Let $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$ be an encryption scheme, and let $A$ be an adversary (or Algorithm). Say we have two messages $m_0$ and $m_1$ and one is choosen at random and encrypted (using an uniform $k$ ). If an adversary $A$ given $c$ and tries to determine which message was encrypted, then

$\Pi$ is secure if no adversary $A$ can guess correctly with probability any better than $1/2$

Define a randomized experiment $\text{K}_{A, \Pi}$ which depend on $A$ and $\Pi$ :

$A$ outputs $m_0, m_1 \in \textbf{M}$ (i.e. $A$ knows both messages)
$k \gets Gen$ , $b \gets \{0, 1\}$ and $c \gets \text{Enc}_k(m_b)$ ( $c$ is called the challenge cipertext)
$b' \gets A(c)$
$A$ succeeds if $b = b'$ and the experiment evaluates to $1$ in this case.

This experiment is easy to succeed with probability $1/2$ because if an attacker $A$ outputs a random guess for its bit $b'$ , it will be correct with probability exactly $1/2$ .

The encryption scheme $\Pi$ is perfectly indistinguishable, if for all attackers $A$ it holds that the attacker succeeds with probability exactly $1/2$ :

$\text{P}[\text{K}_{A, \Pi} = 1] = \frac{1}{2}$

That is to say

there's no* possible attacker $A$ that can succeed any better than one-half*.

The scheme $\Pi$ is perfectly indistinguishable if and only if it is perfectly secret.

Constraints¶

The key is as long as the message and a key should be used uniquely with a probability $\frac{1}{|\textbf{K}|}$ , where $|\textbf{K}|$ is the size of the key space $\textbf{K}$ .

Equivalence Theorem¶

A private-key encryption scheme is perfectly secure if and only if it is Shannon secure.

Example 3¶

The shift cipher has a key space of size $|\text{K}| = 26$ . To achieve perfect secrecy, it thus can have at most 26 plaintexts and ciphertexts.

With a message space of one character (and every key only used once), it would fit the definition of perfect secrecy:

For perfect secrecy we must satisfy

$|\text{K}| \geq |\text{C}| \geq |\text{M}|$

For Shannon secrecy let

$|\text{K}| = |\text{C}| = |\text{M}|$

then we have perfect secrecy if and only if:

each key is used with same probability, and
for each $(m,c)$ pair there is unique key.

With these rules, shift cipher has perfect secrecy.

Example 4¶

The shift cipher does not satisfy the perfect secrecy property if $|\text{M}| \geq 2$ .

Proof:

Take $m_1 = \text{ab}$ , $m_2 = \text{ac}$ and $c = \text{bc}$

Then

$\exists k \in \text{K}, \quad \text{Enc}_k(m_1) = c$

namely $k = 1$ .

However

$\forall k \in \text{K}, \quad \text{Enc}_k(m_2) \neq c$

Hence

$\begin{align} \text{P}[\, \text{C} = \text{bc} \, | \, \text{M} = \text{ab} \,] &\neq \text{P}[\, \text{C} = \text{bc} \, | \, \text{M} = \text{ac} \,] \\[6pt] \frac{1}{26} &\neq 0 \end{align}$

So the perfect secrecy requirement is violated, which requires above two probabilities to be equal.

Example 5¶

Consider a shift cipher and the message distribution

$\begin{align} &\text{P}[\,\text{M} = \text{one}\,] = 0.5 \\ &\text{P}[\, \text{M} = \text{ten}\,] = 0.5 \end{align}$

Now, take as one particular message $m = \text{ten}$ and as one particular ciphertext $c = \text{rqh}$ .

What is the probability that the message is equal to $\text{ten}$ conditioned on the fact that we observed a ciphertext $\text{rqh}$ ?

Because there is no key that match the message $m$ to the ciphertext $c$ , that mean that if we observe to ciphertext $c$ it is not possible that the message is equal to $m$ , hence it is not equal to the prior probability that the message is $\text{ten}$ :

$\begin{align} \text{P}[\, \text{M} = \text{ten}\, | \, \text{C} = \text{rqh} \,] &= 0 \\[7pt] &\neq \text{P}[\, \text{M} = \text{ten} \,] \end{align}$

This shows that the shift cipher does not meet the definition of perfect secrecy.

Example 6¶

Consider a shift cipher and the message distribution

$\begin{align} &\text{P}[\,\text{M} = \text{hi}\,] = 0.3 \\ &\text{P}[\,\text{M} = \text{no}\,] = 0.2 \\ &\text{P}[\, \text{M} = \text{in}\,] = 0.5 \end{align}$

What is the probability $\text{P}[\, \text{M} = \text{hi}\, | \, \text{C} = \text{xy} \,]$ that the message is equal to $\text{hi}$ conditioned on the fact that we observed a ciphertext $\text{xy}$ ?

With

$\begin{align} \text{P}[\, \text{C} = \text{xy}\, | \, \text{M} = \text{hi} \,] = 1/26 \end{align}$

and due to the law of total probability

$\begin{align} \text{P}[\,\text{C} = \text{xy} \,] &= \text{P}[\, \text{C} = \text{xy}\, | \, \text{M} = \text{hi} \,] \cdot 0.3 + \text{P}[\,\text{C} = \text{xy}\, | \, \text{M} = \text{no} \,] \cdot 0.2 + \text{P}[\,\text{C} = \text{xy}\, | \, \text{M} = \text{in} \,] \cdot 0.5 \\[7pt] &= 1/26 \cdot 0.3 + 1/26 \cdot 0.2 + 0 \cdot 0.5 \\[7pt] &= 1/52 \end{align}$

we can calculate using the Bayes theorem

$\begin{align} \text{P}[\, \text{M} = \text{hi}\, | \, \text{C} = \text{xy} \,] &= \frac{\text{P}[\, \text{C} = \text{xy}\, | \, \text{M} = \text{hi} \,] \cdot \text{P}[\,\text{M} = \text{hi} \,]}{\text{P}[\,\text{C} = \text{xy} \,]} \\[7pt] &= \frac{1/26 \cdot 0.3}{1/52} \\[7pt] &= 0.6 \\[7pt] &\neq \text{P}[\, \text{M} = \text{hi} \,] \end{align}$

This again shows that the shift cipher is not perfectly secret.

Example 7 (Perfect Indistinguishability)¶

Let $\Pi$ be the shift cipher.

For which of the following attackers (Algorithms) $A$ is $\text{P}[\text{K}_{A, \Pi} = 1] > \frac{1}{2}$ ?

$A$ outputs $m_0 = \text{a}$ and $m_1 = \text{b}$ . Given a one-character ciphertext $c$ , output $0$ if and only if $c = \text{a}$ .
$A$ outputs $m_0 = \text{az}$ and $m_1 = \text{ab}$ . Given a two-character ciphertext $c_1c_2$ , output $0$ if and only if $c_1 \neq c_2$ .
$A$ outputs $m_0 = \text{ab}$ and $m_1 = \text{aa}$ . Given a two-character ciphertext $c_1c_2$ , output $0$ if and only if $c_1 \neq c_2$ .
There is no such attacker, since the shift cipher is perfectly secret

→ The answer is 3., because the attacker can determine which ciphertext $c_1c_2$ determines to $m_0$ and to $m_1$ .

One-Time Pad (OTP)¶

The encryption scheme that achieves perfect secrecy is the one-time pad. It was proven perfectly secret by Shannon in 1949.

If decryption is to be prevented by frequency analysis, a key may only be used for one message and must also be as long as the message. Such a concept already exists, it is called a one-time pad (Einmalblock).

The one-time pad consists of a very long and randomly selected key. The sender of a message encrypts each plaintext character with the key bits on his one-time pad. The recipient has an identical block and decodes the individual bits of the cipher using the key characters on his block. The block are then destroyed. New key bits are used for a new message.

If the key is an equally distributed random sequence of bits and nobody gains access to the one-time pad that was used to encrypt the message, this concept is absolutely secure. This is because there are as many possible keys as there are possible plaintexts, so a particular ciphertext can belong to any of the reconstructable plaintexts of the same length with the same probability.

The One-Time Pad Encryption Scheme¶

The one-time pad encryption scheme is defined as:

Let $\textbf{M} = \{0, 1\}^n$ (the set of all binary strings of length $n$ , i.e. an $n$ -bit string)
$\text{Gen}$ : choose an uniform key $k \in \{0, 1\}^n$ . Each possible $n$ -bit string is chosen with probability $\text{P}[K] = 2^{-n}$ . There are $2^n$ different strings of length $n$ .
$\text{Enc}_k(m) = k \oplus m$ (bit-wise XOR)
$\text{Dec}_k(c) = k \oplus c$

This scheme is correct, as

$\begin{align} \text{Dec}_k(\text{Enc}_k(m)) &= k \oplus (k \oplus m) \\[6pt] &= (k \oplus k) \oplus m \\[6pt] &= 0 \oplus m \\[6pt] &= m \end{align}$

Perfect Secrecy of the One-Time Pad¶

The One Time Pad is perfectly secure.

Prove:

Let's agree on some arbitrary distribution over the message space $\textbf{M} \in \{0, 1\}^N$ , and agree on some arbitrary message $m$ and arbitrary cyphertext $c$ .

Then using the law of total probability we can calculate the probability of the ciphertext $c$ by summation over all possible messages $m'$ :

$\begin{align} \text{P}[\, \text{C} = c \,] &= \sum_{m'} \text{P}[\, \text{C} = c \, | \, \text{M} = m' \,] \cdot \text{P}[\, \text{M} = m' \,] \\[6pt] &= \sum_{m'} \text{P}[\, \text{K} = m' \oplus c \,] \cdot \text{P}[\, \text{M} = m' \,] \\[6pt] &= \sum_{m'} 2^{-n} \cdot \text{P}[\, \text{M} = m' \,] \\[6pt] &= 2^{-n} \end{align}$

We then calculate using Bayes Law

$\begin{align} \text{P}[\, \text{M} = m \, | \, \text{C} = c \,] &= \frac{\text{P}[\, \text{C} = c \, | \, \text{M} = m \,] \cdot \text{P}[\, \text{M} = m\,]}{\text{P}[\text{C} = c \,]} \\[6pt] &= \frac{\text{P}[\, \text{K} = m \oplus c \,] \cdot \text{P}[\, \text{M} = m\,]}{2^{-n}} \\[6pt] &= \frac{2^{-n} \cdot \text{P}[\, \text{M} = m\,]}{2^{-n}} \\[6pt] &= \text{P}[\, \text{M} = m\,] \end{align}$

Here,

$\text{P}[\, \text{C} = c \, | \, \text{M} = m \,]$ represents the probability that ciphertext $c$ is produced given plaintext $m$ .
$\text{P}[\, \text{K} = m \oplus c \,]$ represents the probability that key $k$ is chosen such that XORing it with plaintext $m$ produces ciphertext $c$ .

In a one-time pad, since each key is as likely as any other, the probability of choosing a specific key is the same as the probability of obtaining a specific ciphertext when that key is used. This is because each bit of the ciphertext is completely dependent on the corresponding bit of the key, and there is no bias or pattern introduced in the encryption process.

So, $\text{P}[\, \text{C} = c \, | \, \text{M} = m \,] = \text{P}[\, \text{K} = m \oplus c \,]$ essentially reflects the inherent randomness and uniformity of the key selection process in a one-time pad cipher.

Disadvantages of the One-Time Pad¶

The fact that other ciphertext methods are still being used, even though an absolutely secure method is known, is due to the disadvantages of the one-time pad:

The key must be the same length as the plaintext and must be available to the recipient.
Statistical deviations can lead to the system becoming insecure. The probability distribution on the key space must be the uniform distribution using cryptographically secure random number generators.
Each key is only used once and must be securely destroyed.

The problem is the transmission of such a key and the error-free use of the same key. Therefore, the procedure is generally not suitable for practical use.

Supposed you are using the key twice:

$\begin{align} c_1 &= k \oplus m_1 \\[6pt] c_2 &= k \oplus m_2 \end{align}$

then the attacker can compute

$\begin{align} c_1 \oplus c_2 &= (k \oplus m_1) \oplus (k \oplus m_2) \\[6pt] &= m_1 \oplus m_2 \end{align}$

This leaks information about $m_1$ and $m_2$ makeing OTP no longer perfectly secret, e.g.:

$m_1 \oplus m_2$ revelas exactly where $m_1$ and $m_2$ differ (the XOR is $1$ at diff positions)
even for XOR'd messages, frequency analysis is possible.
it's possible to exploit a specific characteristic of the ASCII representation table (see below).

ASCII-Exploit of the One-Time Pad¶

Inspecting the ASCII table shows that all letters begin with 01 and that the whitespace character 00100000 starts with 00:

In [21]:

! ascii -b

   0000000 NUL    0010000 DLE    0100000      0110000 0    1000000 @    1010000 P    1100000 `    1110000 p 
   0000001 SOH    0010001 DC1    0100001 !    0110001 1    1000001 A    1010001 Q    1100001 a    1110001 q 
   0000010 STX    0010010 DC2    0100010 "    0110010 2    1000010 B    1010010 R    1100010 b    1110010 r 
   0000011 ETX    0010011 DC3    0100011 #    0110011 3    1000011 C    1010011 S    1100011 c    1110011 s 
   0000100 EOT    0010100 DC4    0100100 $    0110100 4    1000100 D    1010100 T    1100100 d    1110100 t 
   0000101 ENQ    0010101 NAK    0100101 %    0110101 5    1000101 E    1010101 U    1100101 e    1110101 u 
   0000110 ACK    0010110 SYN    0100110 &    0110110 6    1000110 F    1010110 V    1100110 f    1110110 v 
   0000111 BEL    0010111 ETB    0100111 '    0110111 7    1000111 G    1010111 W    1100111 g    1110111 w 
   0001000 BS     0011000 CAN    0101000 (    0111000 8    1001000 H    1011000 X    1101000 h    1111000 x 
   0001001 HT     0011001 EM     0101001 )    0111001 9    1001001 I    1011001 Y    1101001 i    1111001 y 
   0001010 LF     0011010 SUB    0101010 *    0111010 :    1001010 J    1011010 Z    1101010 j    1111010 z 
   0001011 VT     0011011 ESC    0101011 +    0111011 ;    1001011 K    1011011 [    1101011 k    1111011 { 
   0001100 FF     0011100 FS     0101100 ,    0111100 <    1001100 L    1011100 \    1101100 l    1111100 | 
   0001101 CR     0011101 GS     0101101 -    0111101 =    1001101 M    1011101 ]    1101101 m    1111101 } 
   0001110 SO     0011110 RS     0101110 .    0111110 >    1001110 N    1011110 ^    1101110 n    1111110 ~ 
   0001111 SI     0011111 US     0101111 /    0111111 ?    1001111 O    1011111 _    1101111 o    1111111 DEL

Given two ciper texts encrypted with the same key, an attacker can XOR both ciphertexts and identify letters and spaces by guessing that

any byte with a prefix of 01 corresponds to the XOR of a letter and a whitespace, and
any byte with a prefix of 00 corresponds to the XOR of two letters.

This is not perfect as it is possible to have two space characters that XOR to a byte with prefix 00. Also it is possible to have punctuation characters as well that might mess this up. Nevertheless, punctuation characters and pairs of spaces are expected to be much less frequent than pairs of two letters and pairs of a letter and a space.

Now, given a byte $b_i$ with prefix 01 at a position $i$ , the attacker knows with high confidence that one of the two messages has a whitespace at this position $i$ .

The attacker can therefore determine the corresponding letter $\text{letter}_i$ by XOR $b_i$ with the whitespace character $\text{00100000}$ :

$\begin{align} 00100000 \oplus \text{letter}_i &= b_i \\ 00100000 \oplus (00100000 \oplus \text{letter}_i) &= 00100000 \oplus b_i \\ \text{letter}_i &= 00100000 \oplus b_i \end{align}$

Example 1¶

In [75]:

import secrets
from textwrap import wrap

def xor(a, b):
    return [format(int(int(a, 2) ^ int(b, 2)), '08b') for a, b in zip(a, b)]
    
def gen(size):
    return [format(int(k, 16), '08b') for k in (wrap(secrets.token_hex(size), 2))]

def enc(key, message):
    message = [format(ord(m), '08b') for m in message]
    return message, xor(key, message)

In [76]:

key = gen(11)
print(f'       key: {key}')

       key: ['11011100', '10111110', '10000001', '00111101', '10001101', '10100001', '00011011', '00111110', '01010010', '10011001', '10100110']

In [77]:

m1, c1 = enc(key, 'Hello World')
print(f'   message: {m1}')
print(f'ciphertext: {c1}')

   message: ['01001000', '01100101', '01101100', '01101100', '01101111', '00100000', '01010111', '01101111', '01110010', '01101100', '01100100']
ciphertext: ['10010100', '11011011', '11101101', '01010001', '11100010', '10000001', '01001100', '01010001', '00100000', '11110101', '11000010']

In [78]:

m2, c2 = enc(key, 'Foo Bar Baz')
print(f'   message: {m2}')
print(f'ciphertext: {c2}')

   message: ['01000110', '01101111', '01101111', '00100000', '01000010', '01100001', '01110010', '00100000', '01000010', '01100001', '01111010']
ciphertext: ['10011010', '11010001', '11101110', '00011101', '11001111', '11000000', '01101001', '00011110', '00010000', '11111000', '11011100']

In [79]:

print(f'c_1 ⨁ c_2: {xor(c1, c2)}')

c_1 ⨁ c_2: ['00001110', '00001010', '00000011', '01001100', '00101101', '01000001', '00100101', '01001111', '00110000', '00001101', '00011110']

In [80]:

from termcolor import colored
print(f'c_1 ⨁ c_2 = {' '.join([colored(x, 'red') if x.startswith('01') else x for x in xor(c1, c2)])}')

c_1 ⨁ c_2 = 00001110 00001010 00000011 01001100 00101101 01000001 00100101 01001111 00110000 00001101 00011110

In [81]:

print(f'{' '.join([colored(chr(int(x, 2) ^ int('00100000', 2)), 'red') if x.startswith('01') else x for x in xor(c1, c2)])}')

00001110 00001010 00000011 l 00101101 a 00100101 o 00110000 00001101 00011110

Example 2¶

Given three ciphertexts from encryption of ASCII plaintexts using the the same key $k_1 = k_2 = k_3$ :

The 10th byte of the first ciphertext is $c_1 = \text{0xA8}$ ,
the 10th byte of the second ciphertext is $c_2 = \text{0xED}$ , and
the 10th byte of the third ciphertext is $c_3 = \text{0xBD}$ .

What is the 10th ASCII character $m_3$ of the third plaintext?

In [5]:

def xor(h1, h2):
    print(f"{format(int(h1, 16), '08b')} ⨁ {format(int(h2, 16), '08b')} = {format(int(int(h1, 16) ^ int(h2, 16)), '08b')}")

In [6]:

xor('A8', 'ED')

10101000 ⨁ 11101101 = 01000101

$m_1$ or $m_2$ is a whitespace as $c_1 \oplus c_2 = m_1 \oplus m_2 = \text{01000101}$

In [7]:

xor('A8', 'BD')

10101000 ⨁ 10111101 = 00010101

$m_1$ and $m_3$ are letters as $c_1 \oplus c_3 = m_1 \oplus m_3 = \text{00010101}$

In [8]:

xor('ED', 'BD')

11101101 ⨁ 10111101 = 01010000

$m_2$ or $m_3$ is a whitespace as $c_2 \oplus c_3 = m_2 \oplus m_3 = \text{01010000}$

→ from this follows that $m_2$ is a whitespace, hence

$\begin{align} m_2 \oplus m_3 &= c_2 \oplus c_3 \\[6pt] 00100000 \oplus m_3 &= 01010000 \\[6pt] m_3 &= 01010000 \oplus 00100000 \\[6pt] m_3 &= 01110000 \end{align}$

In [89]:

chr(int('01010000', 2) ^ int('00100000', 2))

Out[89]:

'p'

The 10th ASCII character $m_3$ is p.

Computational Secrecy¶

Computational Secrecy is about relaxing perfect Indistinguishability.

Concrete Computational Secrecy¶

$\Pi$ is $(t, \epsilon)$ -indistinguishable if for any attackers $A$ running in time at most $t$ , it holds that

$\text{P}[\text{K}_{A, \Pi} = 1] \leq \frac{1}{2} + \epsilon$

So,

Security may fail with probability $\leq \epsilon$
Restriction attention to attackers running in time $\leq t$

Asymptotic Computational Secrecy¶

For asymptotic secrecy

we introdcuce a security parameter n∈Z+ (positive integer) which
- is fixed by honest parties at initialization
- allows users to tailor the security level (for now we consider this as the key length)
- is known be the adversary
and we view the
- running times of all parties as a function of $n$ and
- the success probability of the adversary as a function of $n$

For computational indistinguishability we relax the notions of perfect indistinguishability in the following:

Security may fail with probability negligible in $n$

A function $f: \mathbb{Z}^+ \to \mathbb{R}^{+,0}$ is negligible if for every polynomial $p$
$\exists \, N \; \text{s.t.} \quad f(n) < \frac{1}{p(n)} \quad \forall \, n > N$
A typical example is: $f(n) = \text{poly}(n) \cdot 2^{-cn}$ .

This means that the function $f$ is negligible, if it's asymptotically smaller than any inverse polynomial function.

Restrict attention to attackers running in time polynomial in $n$

A function $f: \mathbb{Z}^+ \to \mathbb{Z}^+$ is polynomial if
$\exists \, c_i \; \text{s.t.} \quad f(n) < \sum_i c_i \, n^i \quad \forall \, n$

This notion of negligibility and polynomiality are choosen due to

being efficient in the sense of probabilistic polynomial time (PPT)
having convinient closure properties:
- $\text{poly} \cdot \text{poly} = \text{poly}$
  
  → poly-many calls to PPT subroutine is poly-time
- $\text{poly} \cdot \text{negligible} = \text{negligible}$
  
  → poly-many calls to subroutine that fails with negligible probability, fails with negligible probability overall

(Re)definition of an encryption scheme¶

A private-key encryption scheme $(\text{Gen}, \text{Enc}_k, \text{Dec}_k)$ is defined by three PPT algorithms:

Key generation takes as input $1^n$ ; outputs $k$ (assumed $|k| \geq n$ )
Encryption takes as input the key $k$ and message $m \in \{0,1\}^*$ ; outputs ciphertext $c$
Decryption takes $k$ and ciphertext $c$ as input; outputs a message $m$

Pseudorandomness¶

Randomness as well as pseudorandomness is not a property of a string, but a property of a distribution.

That means the string 1101010110011111 is uniform and equaly likely as the string 0000000000000000 with a propability of $2^{-16}$ .

A distribution of $n$ -bit strings is a function

$\text{D}: \{0, 1\}^n \to [0, 1] \; s.t. \quad \sum_x \text{D}(x) = 1$

A uniform distribution of $n$ -bit strings is the distribution $\text{U}_n$ where

$\text{U}_n(x) = 2^{-n} \quad \forall x \in \{0, 1\}^n$

Pseudorandom means, that it can not be distiguished from a uniform distribution.

Cryptographic Definitions of Pseudorandomness¶

$\text{D}$ is pseudorandom if it passes every efficient statistical test

Concrete Definitions of Randomness¶

Let $\text{D}$ be a distribution of $n$ -bit strings, then

$\text{D}$ is $(t, \epsilon)$ -pseudorandom, if for all attacker $A$ running in time $\leq t$

$| \, \text{P}_{x \, \gets \text{D}}[\, A(x) = 1 \,] - \text{P}_{x \, \gets \text{U}_n}[\, A(x) = 1 \,] \, | \leq \epsilon$

Here, the notion $x \, \gets \text{D}$ means $x$ is a sample of the distribution $D$ .

Asymptotic Definitions of Randomness¶

Having a security parameter $n$ and a polynomial $p$ , let $\text{D}_n$ be a distribution over $p(n)$ -bit strings.

Here, pseudorandomness is a property of a sequence of distributions $\{\text{D}_n\} = \{\text{D}_1, \text{D}_2, \ldots\}$

Then we say,

$\{\text{D}_n\}$ , where $\text{D}_n$ is a distribution over $p(n)$ -bit strings, is pseudorandom if for all PPT adversaries $A$ , there is a negligible function $\epsilon$ such that

$| \, \text{P}_{x \, \gets \text{D}_n}[\, A(x) = 1 \,] - \text{P}_{x \, \gets \text{U}_{p(n)}}[\, A(x) = 1 \,] \, | \leq \epsilon(n)$

Pseudorandom (Number) Generator (PRG)¶

A pseudorandom generator is an efficient deterministic algorithm that expands a short and uniform seed or input into a longer pseudorandom output.

In [ ]: