Linear Cryptanalysisを理解する

はじめに

Linear Cryptanalysis(線形解読法)を説明します。[1]を解説します。

The Basic SPN Cipher

例として使用する Substitution-Permutation Network (SPN) Cipher の図を示します。
plaintext / ciphertext の bit length は 16bitです。roundは4です。

plaintextをP1,...,P16と表記します。ciphertextをC1,...,C16と表記します。
round i に対する key を Ki,1 ... Ki,16 と表記します。
Substitutionは4bit 符号なし整数の置換です。置換表をS-Boxといいます。
round i に対する S-Box を $S_{i1},S_{i2},S_{i3},S_{i4}$ と表します。すべて同じS-Boxです。
Permutation は 16bit をまとまりとした bit の並び替えです。それぞれ、具体的には以下の通りです。

具体的な実装例はCode Example [C1] を参照ください。

S-Box に対する Linear Approximation

S-Box に対する Linear Approximationを考えます。
S-Box のinput / output は4bitです。X1, Y1がMSBです。

次の式が成り立つ確率を考えます。
$\oplus$は排他的論理和(XOR)です。$\bullet$は論理積(AND)です。式1とします。

a_1 \bullet X_1 \oplus a_2 \bullet X_2 \oplus a_3 \bullet X_3 \oplus a_4 \bullet X_4 = b_1 \bullet Y_1 \oplus b_2 \bullet Y_2 \oplus b_3 \bullet Y_3 \oplus b_4 \bullet Y_4 \\
X_i, Y_i, a_i, b_i \in \{0, 1\} \\

a, bの例として a1a2a3a4 = 0110b = 0x6, b1b2b3b4 = 1011b = 0xB を考えます。
式1は次のようになります。

X_2 \oplus X_3 = Y_1 \oplus Y_3 \oplus Y_4

すべての input / output に対して式が成立する回数をカウントします。
次に示す通り12通りとなります。

すべての a, b に対して上記を実行した結果を次に示します。
理想的な式1の成立回数は8です。
8からの偏りを明確にするため、式1の成立回数を"-8"した回数をセルの値とします。
したがって、[セルの値] / 16 が 頻度の偏り(以降、biasといいます)になります。

具体的な実装例はCode Example [C2] を参照ください。

The Basic SPN Cipher に対する Linear Approximation

S-Box に対する Linear Approximationを使って
The Basic SPN Cipher に対する Linear Approximationを構成します。

構成方法はさまざま考えられますが、
ここでは例として、各S-Boxに対して、次のLinear Approximationを考えます。

上記をCipher全体に適用します。注目しているbitのデータフローを太線で示します。

round i に対する S-Box の 入力をUi,1 ... Ui,16と表記します。出力をVi,1 ... Vi,16と表記します。

S12について以下を考えます。

U_{1,5} \oplus U_{1,7} \oplus U_{1,8} = V_{1,6} \\

上記はplaintextとkeyを使って次のように表せます。式2とします。

P_5 \oplus K_{1,5} \oplus P_7 \oplus K_{1,7} \oplus P_8 \oplus K_{1,8} = V_{1,6} \\

S22について以下を考えます。

U_{2,6} = V_{2,6}  \oplus V_{2,8} \\

上記は式2とkeyを使って次のように表せます。式3とします。

V_{1,6} \oplus K_{2,6} = V_{2,6} \oplus V_{2,8} \\
P_5 \oplus K_{1,5} \oplus P_7 \oplus K_{1,7} \oplus P_8 \oplus K_{1,8} \oplus K_{2,6} = V_{2,6} \oplus V_{2,8} \\

S32,S34について以下を考えます。

U_{3,6} = V_{3,6} \oplus V_{3,8} \\
U_{3,14} = V_{3,14} \oplus V_{3,16} \\

上記から以下が成り立ちます。

U_{3,6} \oplus U_{3,14} = V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \\

上記は式3とkeyを使って次のように表せます。式4とします。

P_5 \oplus K_{1,5} \oplus P_7 \oplus K_{1,7} \oplus P_8 \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6} \oplus K_{3,16} = V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \\
P_5 \oplus P_7 \oplus P_8 \oplus K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6} \oplus K_{3,16} = V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \\

S42,S44の入力について式4とkeyを使って次のように表せます。式5とします。

U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} = V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \oplus K_{4,6} \oplus K_{4,8} \oplus K_{4,14} \oplus K_{4,16} \\
U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} = P_5 \oplus P_7 \oplus P_8 \oplus K \\
U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} \oplus P_5 \oplus P_7 \oplus P_8 =  K \\

Kは次の通りです。Kは暗号化を通じて変化しないため 0 or 1 固定となります。

K = K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6} \oplus K_{3,16} \oplus K_{4,6} \oplus K_{4,8} \oplus K_{4,14} \oplus K_{4,16} \\ 

次に式5が成立する確率を計算します。次の式で計算できます。Piling-Up Lemmaといいます。

\frac{1}{2} + 2^{n-1} ( \varepsilon_1 + ... + \varepsilon_n ) \\

$\varepsilon_n$ は S-Box に対する Linear Approximation によって得られるbiasです。

式5が (成立する or 成立しない) 確率は次の通り計算できます。S12,S22,S32,S34のbiasを使います。
成立するかどうかはKに依存します。Kは未知であるため決定できません。

\frac{1}{2} + 2^3 (\frac{1}{4})(- \frac{1}{4})(- \frac{1}{4})(- \frac{1}{4}) = \frac{1}{2} - \frac{1}{32} = \frac{15}{32}

したがって式5が成立する , 成立しない確率は それぞれ $\frac{15}{32}$ , $\frac{17}{32}$ になります。
いずれもbiasは $\frac{1}{32}$となります。

Keyの導出

いままでの結果をまとめます。
次の式が成立するbiasは$\frac{1}{32}$です。式6とします。

U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} \oplus P_5 \oplus P_7 \oplus P_8 =  0 \\

上記を計算するには U4,6 U4,8 U4,14 U4,16 が未知です。
これは既知である C5~C8,C13~C16 に対して
K5,5~K5,8 K5,13~K5,16 (16bit) すべてのパターンで CとのXORとS-Boxの逆対応をすることで得られます。

多数の plaintext / ciphertext に対して 式6の成立確率を計算します。
biasが$\frac{1}{32}$に近くなるKeyが正しいKeyであると判断できます。

具体的な実装例はCode Example [C3] を参照ください。
正しいKey 0x9A の成立回数が一番多くなっています。

Code Example

Code Exampleを記載します。

makefile

CFLAGS=-I. -Wall -Werror -O2
INCS=
OBJS=test.o
LIBS=
TARGET=test

%.o: %.c $(INCS)
    $(CC) $(CFLAGS) -c -o $@ $<

$(TARGET): $(OBJS)
    $(CC) $(CFLAGS) -o $@ $^ $(LIBS)

clean:
    rm -rf $(TARGET) *.o

[C1] Basic SPN Cipher

test.c

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
                                 //0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0xA, 0xB, 0xC, 0xD, 0xE, 0xF, 
static const uint8_t Sbox[]    = { 0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7, };
static const uint8_t InvSbox[] = { 0xE, 0x3, 0x4, 0x8, 0x1, 0xC, 0xA, 0xF, 0x7, 0xD, 0x9, 0x6, 0xB, 0x2, 0x0, 0x5, };
static const uint8_t Key[] = { 0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, }; // 5 x 16bit = 5 x 2byte = 10byte
static const int round = 4;

static void print(const char* header, const char* footer, uint8_t* buf, int size)
{
  int i;
  printf("%s", header);
  for (i=0; i<size; i++) {
    printf("%02X ", buf[i]);
  }
  printf("%s", footer);
}

static void Substitution(uint8_t* S, bool is_inv)
{
  uint8_t* box, _S[2];

  if (is_inv) {
    box = (uint8_t*)InvSbox;
  } else {
    box = (uint8_t*)Sbox;
  }

  _S[0]  = box[S[0]&0x0F];
  _S[0] |= (box[S[0]>>4]<<4);
  _S[1]  = box[S[1]&0x0F];
  _S[1] |= (box[S[1]>>4]<<4);
  memcpy(S, _S, 2);
}

static void Permutation(uint8_t* S)
{
  uint8_t tmp[2];
  /* bit0 */
  tmp[0]  = (S[0] & 0x80);
  tmp[0] |= (S[0] & 0x08)<<3;
  tmp[0] |= (S[1] & 0x80)>>2;
  tmp[0] |= (S[1] & 0x08)<<1;
  /* bit1 */
  tmp[0] |= (S[0] & 0x40)>>3;
  tmp[0] |= (S[0] & 0x04);
  tmp[0] |= (S[1] & 0x40)>>5;
  tmp[0] |= (S[1] & 0x04)>>2;
  /* bit2 */
  tmp[1]  = (S[0] & 0x20)<<2;
  tmp[1] |= (S[0] & 0x02)<<5;
  tmp[1] |= (S[1] & 0x20);
  tmp[1] |= (S[1] & 0x02)<<3;
  /* bit3 */
  tmp[1] |= (S[0] & 0x10)>>1;
  tmp[1] |= (S[0] & 0x01)<<2;
  tmp[1] |= (S[1] & 0x10)>>3;
  tmp[1] |= (S[1] & 0x01);

  memcpy(S, tmp, 2);
}

static void cipher(const uint8_t* P, uint8_t* C)
{
  int i; bool inv = false;
  uint8_t S[2];

  memcpy(S, P, 2);

  for (i=0; i<round-1; i++) {
    S[0] ^= Key[i*2+0]; S[1] ^= Key[i*2+1];
    Substitution(S, inv);
    Permutation(S);
  }
  S[0] ^= Key[6]; S[1] ^= Key[7];
  Substitution(S, inv);
  S[0] ^= Key[8]; S[1] ^= Key[9];

  memcpy(C, S, 2);
}

static void inv_cipher(const uint8_t* C, uint8_t* P)
{
  int i; bool inv = true;
  uint8_t S[2];

  memcpy(S, C, 2);

  S[0] ^= Key[8]; S[1] ^= Key[9];
  Substitution(S, inv);
  S[0] ^= Key[6]; S[1] ^= Key[7];
  for (i=0; i<round-1; i++) {
    Permutation(S);
    Substitution(S, inv);
    S[0] ^= Key[(round/2-i)*2+0]; S[1] ^= Key[(round/2-i)*2+1];
  }

  memcpy(P, S, 2);
}

int main(int argc, char* argv[])
{
  uint8_t C[2], P[2] = {0x11, 0x22}, D[2];

  print("Key ", "\n", (uint8_t*)Key, 10);
  print("P ", "\n", P, 2);
  cipher(P, C);
  print("C ", "\n", C, 2);
  inv_cipher(C, D);
  print("P ", "\n", D, 2);

  return 0;
}

console

$ gcc --version && make clean && make && ./test.exe
gcc.exe (Rev2, Built by MSYS2 project) 6.2.0
Copyright (C) 2016 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rm -rf test *.o
cc -I. -Wall -Werror -O2 -c -o test.o test.c
cc -I. -Wall -Werror -O2 -o test test.o
Key 00 01 02 03 04 05 06 07 08 09
P 11 22
C 9E 46
P 11 22

[C2] Linear Approximation Table

test.c

#include <stdio.h>
#include <stdint.h>

static uint8_t Sbox[] = { 0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7, };

static int8_t linear_approximation(uint8_t a, uint8_t b)
{
  uint8_t X, Y; int8_t cnt= -8;

  for (X=0; X<0x10; X++) {
    uint8_t i, _X, _Y, xsum=0, ysum=0;
    Y = Sbox[X];
    _X = X & a;
    _Y = Y & b;
    for (i=0; i<4; i++) {
      xsum ^= ((_X>>i) & 1);
      ysum ^= ((_Y>>i) & 1);
    }
    if (xsum == ysum)
      cnt++;
  }

  return cnt;
}

int main(int argc, char* argv[])
{
  uint8_t a, b; // a1a2a3a4, b1b2b3b4

  printf("  ");
  for (b=0; b<0x10; b++) {
    printf("%2X ", b);
  }
  printf("\n");
  for (a=0; a<0x10; a++) {
    printf("%01X ", a);
    for (b=0; b<0x10; b++) {
      printf("%+1d ", linear_approximation(a, b));
    }
    printf("\n");
  }

  return 0;
}

console

$ gcc --version && make clean && make && ./test.exe
gcc.exe (Rev2, Built by MSYS2 project) 6.2.0
Copyright (C) 2016 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rm -rf test *.o
cc -I. -Wall -Werror -O2 -c -o test.o test.c
cc -I. -Wall -Werror -O2 -o test test.o
   0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
0 +8 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0
1 +0 +0 -2 -2 +0 +0 -2 +6 +2 +2 +0 +0 +2 +2 +0 +0
2 +0 +0 -2 -2 +0 +0 -2 -2 +0 +0 +2 +2 +0 +0 -6 +2
3 +0 +0 +0 +0 +0 +0 +0 +0 +2 -6 -2 -2 +2 +2 -2 -2
4 +0 +2 +0 -2 -2 -4 -2 +0 +0 -2 +0 +2 +2 -4 +2 +0
5 +0 -2 -2 +0 -2 +0 +4 +2 -2 +0 -4 +2 +0 -2 -2 +0
6 +0 +2 -2 +4 +2 +0 +0 +2 +0 -2 +2 +4 -2 +0 +0 -2
7 +0 -2 +0 +2 +2 -4 +2 +0 -2 +0 +2 +0 +4 +2 +0 +2
8 +0 +0 +0 +0 +0 +0 +0 +0 -2 +2 +2 -2 +2 -2 -2 -6
9 +0 +0 -2 -2 +0 +0 -2 -2 -4 +0 -2 +2 +0 +4 +2 -2
A +0 +4 -2 +2 -4 +0 +2 -2 +2 +2 +0 +0 +2 +2 +0 +0
B +0 +4 +0 -4 +4 +0 +4 +0 +0 +0 +0 +0 +0 +0 +0 +0
C +0 -2 +4 -2 -2 +0 +2 +0 +2 +0 +2 +4 +0 +2 +0 -2
D +0 +2 +2 +0 -2 +4 +0 +2 -4 -2 +2 +0 +2 +0 +0 +2
E +0 +2 +2 +0 -2 -4 +0 +2 -2 +0 +0 -2 -4 +2 -2 +0
F +0 -2 -4 -2 -2 +0 +2 +0 +0 -2 +4 -2 -2 +0 +2 +0

[C3] Linear Cryptanalysis

test.c

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

#define COUNT (10000)
#define COUNTER_MAX (256)
                                 //0x0, 0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8, 0x9, 0xA, 0xB, 0xC, 0xD, 0xE, 0xF, 
static const uint8_t Sbox[]    = { 0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7, };
static const uint8_t InvSbox[] = { 0xE, 0x3, 0x4, 0x8, 0x1, 0xC, 0xA, 0xF, 0x7, 0xD, 0x9, 0x6, 0xB, 0x2, 0x0, 0x5, };
static const uint8_t Key[] = { 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, 0xAA, }; // 5 x 16bit = 5 x 2byte = 10byte
static const int round = 4;
static uint16_t counter[COUNTER_MAX];

static void Substitution(uint8_t* S, bool is_inv)
{
  uint8_t* box, _S[2];

  if (is_inv) {
    box = (uint8_t*)InvSbox;
  } else {
    box = (uint8_t*)Sbox;
  }

  _S[0]  = box[S[0]&0x0F];
  _S[0] |= (box[S[0]>>4]<<4);
  _S[1]  = box[S[1]&0x0F];
  _S[1] |= (box[S[1]>>4]<<4);
  memcpy(S, _S, 2);
}

static void Permutation(uint8_t* S)
{
  uint8_t tmp[2];

  /* bit0 */
  tmp[0]  = (S[0] & 0x80);
  tmp[0] |= (S[0] & 0x08)<<3;
  tmp[0] |= (S[1] & 0x80)>>2;
  tmp[0] |= (S[1] & 0x08)<<1;
  /* bit1 */
  tmp[0] |= (S[0] & 0x40)>>3;
  tmp[0] |= (S[0] & 0x04);
  tmp[0] |= (S[1] & 0x40)>>5;
  tmp[0] |= (S[1] & 0x04)>>2;
  /* bit2 */
  tmp[1]  = (S[0] & 0x20)<<2;
  tmp[1] |= (S[0] & 0x02)<<5;
  tmp[1] |= (S[1] & 0x20);
  tmp[1] |= (S[1] & 0x02)<<3;
  /* bit3 */
  tmp[1] |= (S[0] & 0x10)>>1;
  tmp[1] |= (S[0] & 0x01)<<2;
  tmp[1] |= (S[1] & 0x10)>>3;
  tmp[1] |= (S[1] & 0x01);

  memcpy(S, tmp, 2);
}

static void cipher(const uint8_t* P, uint8_t* C)
{
  int i; bool inv = false;
  uint8_t S[2];

  memcpy(S, P, 2);

  for (i=0; i<round-1; i++) {
    S[0] ^= Key[i*2+0]; S[1] ^= Key[i*2+1];
    Substitution(S, inv);
    Permutation(S);
  }
  S[0] ^= Key[6]; S[1] ^= Key[7];
  Substitution(S, inv);
  S[0] ^= Key[8]; S[1] ^= Key[9];

  memcpy(C, S, 2);
}

static void part_inv_cipher(uint8_t K, const uint8_t* C, uint8_t* U)
{
  // K = K5-K8, K13-K16
  U[0] = C[0] ^ (K>>4);
  U[1] = C[1] ^  K;
  Substitution(U, true /*inv*/);
}

static uint8_t sum(const uint8_t* P, const uint8_t* U)
{
  uint8_t s = 0;

  s ^= ((U[0]&0x4)>>2) ^ (U[0]&0x1) ^ ((U[1]&0x4)>>2) ^ (U[1]&0x1);
  s ^= ((P[0]&0x8)>>3) ^ ((P[0]&0x2)>>1) ^ (P[0]&0x1);
  return s;
}

static void count(const uint8_t* P, const uint8_t* C)
{
  uint16_t K;

  for (K=0; K<COUNTER_MAX; K++) {
    uint8_t U[2];
    part_inv_cipher(K, C, U);
    counter[K] += sum(P, U);
  }
}

int main(int argc, char* argv[])
{
  uint16_t P, C, _P;
  int i;

  for (P=0; P<COUNT; P++) {
    _P = P<<8 | P>>8;
    cipher((uint8_t*)&_P, (uint8_t*)&C);
    count((uint8_t*)&_P, (uint8_t*)&C);
  }

  for (i=0; i<COUNTER_MAX; i++) {
    printf("%03d %02X\n", abs(counter[i] - COUNT/2), i);
  }

  return 0;
}

console

$ make clean && make && ./test.exe | sort -r | head
rm -rf test *.o
cc -I. -Wall -Werror -O2 -c -o test.o test.c
cc -I. -Wall -Werror -O2 -o test test.o
356 9A
262 5A
259 64
...

references

• [1] A Tutorial on Linear and Differential Cryptanalysis Howard M. Heys