HITB 2015 Write-up - Crypto 400

Introduction

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
else:
  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$

Implementation

The following script is the implementation of the attack:

#!/usr/bin/python2.7
# -*- coding: utf-8 -*-
import os

S = [
  0xa5,0xc6,0x62,0x01,0x49,0x2a,0x8e,0xed,0x1f,0x7c,0xd8,0xbb,0xf3,0x90,0x34,0x57,
  0xb3,0xd0,0x74,0x17,0x5f,0x3c,0x98,0xfb,0x09,0x6a,0xce,0xad,0xe5,0x86,0x22,0x41,
  0x89,0xea,0x4e,0x2d,0x65,0x06,0xa2,0xc1,0x33,0x50,0xf4,0x97,0xdf,0xbc,0x18,0x7b,
  0x9f,0xfc,0x58,0x3b,0x73,0x10,0xb4,0xd7,0x25,0x46,0xe2,0x81,0xc9,0xaa,0x0e,0x6d,
  0xfd,0x9e,0x3a,0x59,0x11,0x72,0xd6,0xb5,0x47,0x24,0x80,0xe3,0xab,0xc8,0x6c,0x0f,
  0xeb,0x88,0x2c,0x4f,0x07,0x64,0xc0,0xa3,0x51,0x32,0x96,0xf5,0xbd,0xde,0x7a,0x19,
  0xd1,0xb2,0x16,0x75,0x3d,0x5e,0xfa,0x99,0x6b,0x08,0xac,0xcf,0x87,0xe4,0x40,0x23,
  0xc7,0xa4,0x00,0x63,0x2b,0x48,0xec,0x8f,0x7d,0x1e,0xba,0xd9,0x91,0xf2,0x56,0x35,
  0x14,0x77,0xd3,0xb0,0xf8,0x9b,0x3f,0x5c,0xae,0xcd,0x69,0x0a,0x42,0x21,0x85,0xe6,
  0x02,0x61,0xc5,0xa6,0xee,0x8d,0x29,0x4a,0xb8,0xdb,0x7f,0x1c,0x54,0x37,0x93,0xf0,
  0x38,0x5b,0xff,0x9c,0xd4,0xb7,0x13,0x70,0x82,0xe1,0x45,0x26,0x6e,0x0d,0xa9,0xca,
  0x2e,0x4d,0xe9,0x8a,0xc2,0xa1,0x05,0x66,0x94,0xf7,0x53,0x30,0x78,0x1b,0xbf,0xdc,
  0x4c,0x2f,0x8b,0xe8,0xa0,0xc3,0x67,0x04,0xf6,0x95,0x31,0x52,0x1a,0x79,0xdd,0xbe,
  0x5a,0x39,0x9d,0xfe,0xb6,0xd5,0x71,0x12,0xe0,0x83,0x27,0x44,0x0c,0x6f,0xcb,0xa8,
  0x60,0x03,0xa7,0xc4,0x8c,0xef,0x4b,0x28,0xda,0xb9,0x1d,0x7e,0x36,0x55,0xf1,0x92,
  0x76,0x15,0xb1,0xd2,0x9a,0xf9,0x5d,0x3e,0xcc,0xaf,0x0b,0x68,0x20,0x43,0xe7,0x84
]

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)
            dWtemp.append(dW15)

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

if __name__ == '__main__':
    main()

Conclusion

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