はじめに

Differential Cryptanalysis(差分解読法)を説明します。[1]を解説します。
The Basic SPN Cipherおよび記号については[2]を参照ください。

S-Box に対する Differential Characteristics

S-Box への入力差分 $\Delta X = X' \oplus X''$ と出力差分 $\Delta Y = Y' \oplus Y''$の関係を考えます。
例としてΔX = 1011 における ΔYの対応を次に示します。ΔY = 0010b の出現回数が多いことが分かります。

すべての$\Delta X$に対して$\Delta Y$が出現する回数を表にします。Difference Distribution Tableといいます。

(ΔX, ΔY)をDifferentialといいます。(ΔX, ΔY, pd)をDifferential Characteristicといいます。
pdは出現回数を16で割ったものです。

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

The Basic SPN Cipher に対する Differential Characteristics

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

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

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

ΔP = [0000 1011 000 0000]の時にΔU4 = [0000 0110 0000 0110]となる確率は
S-BoxのDifferential Characteristicsを用いて次のように計算できます。

\frac{8}{16} (\frac{6}{16})^3 = \frac{27}{1024}

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

具体的な実装例はCode Example [C2] を参照ください。
正しい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] Difference Distribution Table

test.c

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

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

static void difference_distribution(uint8_t dx, uint8_t* dy /*[16]*/)
{
  uint8_t X;

  for (X=0; X<0x10; X++) {
    dy[Sbox[X^dx] ^ Sbox[X]]++;
  }
}

int main(int argc, char* argv[])
{
  uint8_t dx, dy[16], i;
  printf("  ");
  for (i=0; i<0x10; i++) {
    printf("%2X ", i);
  }
  printf("\n");
  for (dx=0; dx<0x10; dx++) {
    printf("%01X ", dx);
    memset(dy, 0, 16);
    difference_distribution(dx, dy);
    for (i=0; i<0x10; i++) {
      printf("%2d ", dy[i]);
    }
    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 16  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
1  0  0  0  2  0  0  0  2  0  2  4  0  4  2  0  0
2  0  0  0  2  0  6  2  2  0  2  0  0  0  0  2  0
3  0  0  2  0  2  0  0  0  0  4  2  0  2  0  0  4
4  0  0  0  2  0  0  6  0  0  2  0  4  2  0  0  0
5  0  4  0  0  0  2  2  0  0  0  4  0  2  0  0  2
6  0  0  0  4  0  4  0  0  0  0  0  0  2  2  2  2
7  0  0  2  2  2  0  2  0  0  2  2  0  0  0  0  4
8  0  0  0  0  0  0  2  2  0  0  0  4  0  4  2  2
9  0  2  0  0  2  0  0  4  2  0  2  2  2  0  0  0
A  0  2  2  0  0  0  0  0  6  0  0  2  0  0  4  0
B  0  0  8  0  0  2  0  2  0  0  0  0  0  2  0  2
C  0  2  0  0  2  2  2  0  0  0  0  2  0  6  0  0
D  0  4  0  0  0  0  0  4  2  0  2  0  2  0  2  0
E  0  0  2  4  2  0  0  0  6  0  0  0  0  0  2  0
F  0  2  0  0  6  0  0  0  0  4  0  2  0  0  2  0

[C2] Differential Cryptanalysis