HITB 2015 Write-up - Crypto 400


The crypto 400 challenge deals with the Even Mansour cryptosystem. To validate this challenge we have to send the flag to a server. The server checks if the answer matches the flag by encrypting the flag and the given message with a random key. If both are equal the flag is correct otherwise it fails and the encrypted message is printed.

key = os.urandom(32)
enc_flag = encrypt(flag, key)
enc = encrypt(answer, key)

if enc == enc_flag:
  response = "You lucky bastard, %s is indeed the correct flag!\n" % flag
  response = "Unfortunately that is not our flag :(\n"
  response += "Your guess encrypts as\n%s" % enc
  response += "whereas our flag encrypts as\n%s" % enc_flag

Even Mansour scheme

In this Even-Masour scheme the size of a block is 16-bytes and the key — on 32-bytes — is split in two: $k_1$ and $k_2$ each one on 16-bytes. At first, the message $M$ is xor-ed with $k_1$ then $M \oplus k_1$ is going through a $F$ function which will be discussed later. Finally the output is xor-ed with $k_2$.

So we have:

$$C = F(M \oplus k_1) \oplus k_2$$

def EvenMansour(block, key):
  block = xor(block, key[:16])
  block = F(block)
  block = xor(block, key[16:])
  return block

In this challenge, the weakness comes from the $F$ function.

$F$ function

The $F$ function is composed of 64-rounds that perform the step(...) transformation:

def F(block):
  for i in range(64):
    block = step(block)
  return block

step uses a S-Box to transform the block in this way:

$\begin{cases} \text{block}^{n+1}_0 = \text{SBox}(\text{block}^{n}_{10} \oplus \text{block}^{n}_{12} \oplus \text{block}^{n}_{13} \oplus \text{block}^{n+1}_{15}) & k = 0 \\\ \text{block}^{n+1}_k = \text{block}^{n}_{k - 1} & k > 0 \end{cases}$

$\text{block}^{n}_k$ is the byte $k$ of the block at round $n$ ($0 \leq k < 16$ and $0 \leq n < 64$)

def step(block):
  return chr( S[ ord(block[10]) ^ ord(block[12]) ^ ord(block[13]) ^ ord(block[15]) ] ) + block[:15]

By ploting $y = \text{S-Box}(x)$ we can notice that the S-Box has a special construction:

I thought about computing the differential characteristics which is the probability that given the input difference $\Delta = x \oplus y$ we get the output delta: $\delta = S(x) \oplus S(y)$. We will call this probability $P(\Delta | \delta)$ and with following function, we can compute this probability:

def P(dx ,dy):
    count = 0;
    for x in range(len(SBox)):
        dY = SBox[x] ^ SBox[x ^ dx]
        if dY == dy:
            count += 1;
    return float(count) / float(256)

For all $\Delta$ and $\delta$, we notice that this probability is either 0 or 1. Consequently if we know $\delta$ we are sure to find $\Delta$. This will be useful for the differential attack.

Differential Attack

To find the flag, we will perform a differential attack. We have a message $M_1$ that we know and we have an unknown second message $M_2$ that is the flag. We also know $C_1$ and $C_2$ such as:

$$\begin{eqnarray} C_1 & = & F(M_1 \oplus k_1) \oplus k_2 \\\ C_2 & = & F(M_2 \oplus k_1) \oplus k_2 \end{eqnarray}$$

By xor-ing $C_1$ and $C_2$ we can get $\Delta W = W_1 \oplus W_2 = C_1 \oplus C_2$. If somehow we can resolve $\Delta V$:

$$\begin{eqnarray} \Delta V & = & V_1 \oplus V_2 \\\ & = & M_1 \oplus k_1 \oplus M_2 \oplus k_1\\\ & = & M_1 \oplus M_2. \end{eqnarray}$$

We can extract $M_2$ with:

$$M_2 = \Delta V \oplus M_1$$

Recovering $\Delta V$

Now, let’s see how to resolve $\Delta V$ from $\Delta W$.

From the step function, we know that $\text{block}^{n+1}_k = \text{block}^{n}_{k - 1}$ therefore:

$$\Delta W^{n-1}_k = \Delta W^{n}_{k + 1} \forall k < 15$$

We know also $\Delta W^{n-1}_{0,1,2 \ldots 14}$ but not $\Delta W^{n-1}_{15}$

To find $\Delta W^{n-1}_{15}$ we will use the fact that $P(\Delta X | \Delta W^{n-1}_{15}) = 1$ for a given $\Delta X$. Concretely, I built a table diffTable which maps $\delta$ to $\Delta$.

$\begin{eqnarray} \text{diffTable}(\Delta W^{n}_{0}) & = & \Delta W^{n-1}_{10} \oplus \Delta W^{n-1}_{12} \oplus \Delta W^{n-1}_{13} \oplus \Delta W^{n-1}_{15} \\\ & = & \Delta W^{n}_{11} \oplus \Delta W^{n}_{13} \oplus \Delta W^{n}_{14} \oplus \Delta W^{n-1}_{15}\\\ \Delta W^{n-1}_{15} & = & \text{diffTable}(\Delta W^{n}_{0}) \oplus \Delta W^{n}_{11} \oplus \Delta W^{n}_{13} \oplus \Delta W^{n}_{14} \end{eqnarray}$

Which enables to recover $\Delta W^{n - 1}$ from $\Delta W^{n}$. Then, with recursion we can compute $\Delta W^{0} = \Delta V$


The following script is the implementation of the attack:

# -*- coding: utf-8 -*-
import os

S = [

def xor(block1, block2):
  return "".join( chr(ord(a) ^ ord(b)) for (a,b) in zip(block1, block2))

def step(block):
  return chr(S[ord(block[10]) ^ ord(block[12]) ^ ord(block[13]) ^ ord(block[15])]) + block[:15]

def F(block):
  for i in xrange(64):
    block = step(block)
  return block

def EvenMansour(block, key):
  block = xor(block, key[:16])
  block = F(block)
  block = xor(block, key[16:])
  return block

def encrypt(data, key):
  data, num_blocks = pad(data)
  res = ""
  for i in xrange(num_blocks):
            block = EvenMansour(data[16*i:16*i+16], key)
      res += block
        return res

def pad(data):
    while True:
        data += '\x00'
    if len(data) % 16 == 0:
      return data, len(data) / 16

# Table T[a] = b such as
# S[x] ^ S[y] = a and b = x ^ y
def DiffTable(S):
    table = [0 for i in range(len(S))]
    for delta in range(len(S)):
        for x in range(len(S)):
            dY = S[x] ^ S[x ^ delta]
            table[dY] = delta
    return table

def main():
    key = os.urandom(32)
    M1 = "hitb{0123456789abcdef}"
    M2 = "aaaaaaaaaaaaaaaaaaaaaa"

    C1 = encrypt(M1, key)
    C2 = encrypt(M2, key)

    numberOfBlocks = len(C2) / 16
    diffTable = DiffTable(S)
    clearText = ""

    for block in range(numberOfBlocks):
        dW = xor(C1,C2)[16 * block : 16 * (block + 1)]
        for i in range(64):
            dWtemp = [dW[i + 1] for i in range(15)]

            delta = diffTable[ord(dW[0])]
            dW15 = chr(ord(dW[11]) ^ ord(dW[13]) ^ ord(dW[14]) ^ delta)

            dW = "".join(dWtemp)
        M = xor(dW, M2[16 * block : 16 * (block + 1)])
        clearText += M
    print clearText

if __name__ == '__main__':


In fact by noticing that

$$F(x \oplus y) = F(x) \oplus F(y) \oplus C^{te}$$

for b in xrange(10):
        u = os.urandom(16);
        v = os.urandom(16);
        d = xor(F(xor(u,v)), xor(F(u), F(v)))
        print d.encode("hex")

We have:

\begin{eqnarray} F(M_1 \oplus k_1) \oplus F(M_2 \oplus k_1) & = & F(M_1) \oplus F(M_2)\ M_2 & = & F^{-1}(F(M_1) \oplus C_1 \oplus C_2) \end{eqnarray}

Which is far more easier to resolve.

Thanks to jb^ who help me and who find the previous technique.

Sources are available here