Crypto assignment 2 Solutions

assignment-solutions-16-to-21.md

16 Birthday Paradox

The Birthday Paradox question is stated as follows:

Given that there are $k$ people in a room, what is the minimum value of $k$ that the probability that any two people in the room share a birthday is at least $\frac{1}{2}$

We can note the following events:

• A = nobody shares a birthday
• B = At least two people share a birthday

$$ P(B) = 1 - P(A) $$

$$ P(A) = \frac{\text{Number of cases where each person has a uniquely assigned birthday}}{\text{Total number of assignments of birthdays}} $$

The number of unique assignments can be determined by the following method:

• Label each person with a number i=1 to k
• Assign one day to person 1 = 365
• Choose one day out of the remaining (365 - 1) = 364 days to person 2
• Repeat the above process until each person k is assigned a day

Therefore, number of unique assignments of birthdays = $365364363*\cdots*(365 - (k - 1))$

Total number of assignments = $365^k$

Therefore the probability that nobody shares a birthday is

$$ \frac{\prod_{i=0}^{k - 1}(365 - i)}{365^k} = \prod_{i=0}^{k - 1}(1 - \frac{i}{365}) $$

Therefore the probability that at least two people share a birthday is then

$$ 1- \frac{\prod_{i=0}^{k - 1}(365 - i)}{365^k} = \prod_{i=0}^{k - 1}(1 - \frac{i}{365}) $$

We can calculate this value emprirically until we exceed $\frac{1}{2}$ or use the following first order approximation:

$$ e^x = 1 + x + \frac{x^2}{2!} + \cdots \approx 1 + x $$

$$ e^{-\frac{i}{365}} \approx 1 - \frac{i}{365} $$

This yields our required probability

$$ P(B) = 1 - \prod_{i=0}^{k-1}exp{-\frac{i}{365}} = 1 - exp{-\sum_{i=0}^{k-1}\frac{i}{365}} = 1 - exp{-\frac{k*(k-1)}{2*365}} $$

For our birthday problem

$$ P(B) > \frac{1}{2} $$

$$ 1 - exp{-\frac{k*(k-1)}{2*365}} > \frac{1}{2} $$

$$ exp{-\frac{k*(k-1)}{2*365}} < \frac{1}{2} $$

Taking log and negating

$$ \frac{k*(k-1)}{2*365} > ln2 $$

Therefore, we can see that

$$ k \approx \sqrt{365} \approx 23 $$

In general, for any event space size $d$, the population size $k$ required to execute a birthday attack would be $k=\sqrt{d}$.

For the hash collision problem, a n-bit hash will have $2^n$ possible hashes. The number of hashes required to be computed for a birthday attack would be $\sqrt{2^n} = 2^{\frac{n}{2}}$.

For a 64-bit key, this would require computation of $2^{32} = 4294967296$ hashes. Thus, the computational cost to obtain a collision with reasonable probability reduces by a factor of 4 billion.

17 Non-repudiation of Origin using Symmetric Cryptography

Alice and Bob are two individuals who share a secret key for encrypting their communication using a symmetric cryptographic scheme.

Assuming that no one else has the secret key, it holds that Alice and Bob have the same key. In this situation, it is possible for Bob to create a message, encrypt it using the secret key to generate a ciphertext and claim that Alice had sent it.

Therefore, Alice can, under this possibility, deny sending the message to Bob. Thus, non-repudation of origin is not satisfied by a symmetric cryptographic scheme.

18 Message Digest Collision Resistance

If the length of the message digest is $64$ bits, this implies that there are $2^{64}$ possible values for the message digest. Therefore, to find a collision in a hashing scheme, the adversary needs to try at least $2^{63}$ and at most $2^{64}$ tests.

Assuming that the adversary can perform $2^{20}$ tests per second, the time taken to brute force is:

$$ \frac{2^{64}}{2^{20}} = 2^{44} seconds \approx 27 days $$

However, according to the birthday paradox, a collision is very likely to be found after evaluating $\sqrt{H}$ tries, where $H$ is the total possible number of values the hash can take.

$$ \sqrt{H} = \sqrt{2^{64}} = 2^{32} tries $$

Therefore, if $2^{20}$ tests can be performed in $1s$, the time required to perform a birthday attack will be:

$$ \frac{2^{32}}{2^{20}} s = 2^{12} s \approx 85 mins $$

Since this time frame is very small, it is quite evident that $64$ bit message digests are insecure.

19 Forgery of MAC under CMA

Let $E: {0,1}^k \times B^n \rightarrow B^n$ be a block cipher where $B = {0, 1}^n$. View a message $M \in B^* $ as a sequence of $l$ bit blocks,

$M = M[1] \dots M[m]$

####19.1 $ MAC_k(M[1] \dots M[m] = E_k[M[1]] \oplus E_k[M[2]] \oplus \dots \oplus E_k[M[m]] $

Let $ m_1 = 01 $ and $ m_2 = 10 $ where $l = 1$:

$ MAC_k(m_1) = E_k[0] \oplus E_k[1] $

$ MAC_k(m_2) = E_k[1] \oplus E_k[0]$

Since $\oplus$ (XOR) is commutative, both yield the same MAC tag, resulting in a forgery

19.2

Let $l = n - 32$. Function MAC is defined by $ MAC_k(M[1] \dots M[m]) = E_k[<1>||M[1]] \oplus E_k[<2>||M[2]] \oplus \dots \oplus E_k[||M[m]]$ and $$ is the 32-bit binary representation of block index $i$

Consider the following messages where $X$ and $Y$ are $l$ bit blocks: $m_1 = X||X$ $m_2 = X||Y$ $m_3 = Y||Y$ $m_4 = Y||X$

Computing the MAC of the above messages: $ MAC_k(m_1) = E[<1>||X] \oplus E[<2>||X] $ $ MAC_k(m_2) = E[<1>||X] \oplus E[<2>||Y] $ $ MAC_k(m_3) = E[<1>||Y] \oplus E[<2>||Y] $ $ MAC_k(m_4) = E[<1>||Y] \oplus E[<2>||X] $

Performing $ MAC_k(m_1) \oplus MAC_k(m_2) \oplus MAC_k(m_3)$: $ = E[<1>||X] \oplus E[<2>||X] \oplus E[<1>||X] \oplus E[<2>||Y] \oplus E[<1>||Y] \oplus E[<2>||Y]$ $ = E[<1>||Y] \oplus E[<2>||X] = MAC_k(m_4) $ $ \implies MAC_k(m_1) \oplus MAC_k(m_2) \oplus MAC_k(m_3) = MAC_k(m_4)$

Therefore, the above MAC scheme is susceptible to forgery attacks.

20 Padding of message

To make a message a multiple of block length $ n $, padding is required. If a string of $0$s is used to pad the message, then it may lead of a vulnerability under CMA as follows: Let $ m $ be a message of length $|m| &lt; n $ Let $ m^\prime = m || 0$

The corresponding MACs produced are: $ MAC_k(m) = E_k[m||\underbrace{0 \dots 0}{n - |m| }]$ $ MAC_k(m^\prime) = E_k[m||0||\underbrace{0 \dots 0}{n - |m| - 1}] = E_k[m||\underbrace{0 \dots 0}_{n - |m|}]$ $ \implies MAC_k(m) = MAC_k(m^\prime)$

Therefore, the above scheme is vulnerable under CMA

21 CBC-MAC for variable block size

CBC-MAC is semantically secure for a fixed number of blocks, given that $ E $ is semantically secure.

If a variable number of blocks are allowed, the scheme can be broken as follows: Let $ m_1 $ and $ m_2 $ be two messages who size equals the block size. Compute the tags for the two message as follows: $MAC_1 = MAC_k(m_1) = E_k[m_1] - (1)$ $MAC_2 = MAC_k(m_2) = E_k[m_2] - (2)$

Consider the messsage $ m^\prime = m1 || m2 $. According to the CBC-MAC scheme: $MAC^\prime = MAC_k(m^\prime) = E_k[m_2 \oplus E_k[m_1]] $

We can observe that the above expression can be written as: $MAC^\prime = MAC_k(m^\prime) = E_k[m_2 \oplus MAC_1]$ from $(1)$

Therefore, we can perform the following forgery: $ m^{\prime\prime} = m_2 \oplus MAC_1 $ $ \implies MAC^{\prime\prime} = MAC_k(m^{\prime\prime}) = E_k[m^{\prime\prime}] = E_k[m_2 \oplus MAC_1] = MAC^{\prime}$

Therefore, the CBC-MAC under variable block size is susceptible to forgery under CMA.