# DDT 구하기
가장 먼저, Sbox가 어떤 형태로 구성되어 있는지 확인시켜주고 있다.
Sbox는 위와 같이 구성되어 있다. 이를 바탕으로 DDT(Differential Distribution Table)를 만들고 출력해주는 함수 createDDT 를 만들었다.
DDT는 다음과 같다.
# 차분특성식 구하기
차분 특성식을 구할 때 고려해야 하는 것은 최종 확률이 최대한 커야한다는 것이다. 그러기 위해서는 입력 차분에서 차이가 있는 bit가 sbox를 지나면서 많이 퍼지지 않도록, 그리고 최대한 높은 확률의 sbox 출력이 나오도록 해야한다.
그리고 filtering 과정을 위해서는 최종 라운드 이전에 출력 차분이 하나의 sbox 출력값에서만 발생하도록 한다. 왜냐하면 키를 유추하고 복호화하는 과정에서 차분이 발생하는 sbox가 많아질수록 예측해야 하는 키가 2^4만큼 늘어나기 때문이다. (2^4 → 2^8 → 2^12 → 2^16)
차분 특성식이 위의 조건을 만족하도록 하기 위해서 나는 경로를 밑에서부터 위로 올라가는 방법으로 구했다.
이렇게 구한 차분특성식의 확률은 p=2^(-15)이었고, 필요한 input의 쌍은 8/p=2^18개만큼 구하였다.
# plain(입력) pair
랜덤한 입력 쌍을 만드는 함수 plaintextPairGen 를 구성했다.
# cipher(출력) pair
위에서 구성한 입력 쌍에 대한 출력 쌍을 구하는 함수 ciphertextPairGen 를 구성했다.
# filtering
위에서 입력 쌍에 대한 출력 쌍을 구했다. 출력 쌍의 차분을 구하고, 차분이 0?00 모습인지 확인하는 cipherFiltering 함수를 구했다.(마지막 이전 라운드에서 중간 차분이 0400이었으므로) filtering을 통과한 암호문 쌍에 대해서는 filter 배열의 원소를 1로 설정해주었다.
# key 추측
키(의 일부)를 추측하는 guessKey 함수이다. 아까 설정한 filter 배열에서 값이 1이 아니면 무시한다. (filtering에서 걸러진 것임) 값이 1이라면 차분이 발생하는 4bit를 key와 xor하고, sbox를 거꾸로 진행한다. inv_sbox의 출력으로 나온 쌍의 차분이 우리가 설정한 차분이 맞다면 check_key 배열의 원소를 1로 설정해준다.
마지막에 check_key 배열에 설정된 것을 다 합해서 key 배열을 설정해준다.
printGuessedKey 함수이다. 위에서 key 배열을 업데이트한 결과에 따라, 가장 큰 값을 가지고 있는 원소를 올바른 key 라고 추측한다! 그리고 추가 결과를 확인하기 위해 key 배열의 값들을 출력해주고 있다.
# 정리
위의 함수들을 통해 main 함수는 다음과 같이 구성했다.
함수의 실행결과는 다음과 같다.
마지막 라운드의 키인 rk5의 일부가 A(rk5 = xAxx)임을 알아냈다.
전체 코드는 다음과 같다.
#include "caltoy.h"
#include <stdlib.h>
#include <time.h>
#define M 16 // size of S-box
#define PR 262144 // 2^18
wd_t ddt[M][M]; // Differential Distribution Table
char check_key[16][PR];
char filter[PR];
int key[16];
typedef struct _plaintext {
pt_t p1;
pt_t p2;
} Plain_pair;
typedef struct _ciphertext {
ct_t c1;
ct_t c2;
} Cipher_pair;
Plain_pair plain[PR];
Cipher_pair cipher[PR];
void createDDT();
void clear();
void plaintextPairGen(int inputDiff);
void ciphertextPairGen();
void cipherFiltering();
void guessKey(int interDiff);
void printGuessedKey();
int main(void)
{
int i;
for (i = 0; i < 16; i++)
{
printf("%01X, ", caltoy_sbox[i]);
}
printf("n");
int inputDiff = 0x1000;
int interDiff = 4;
srand(time(NULL));
createDDT();
clear();
plaintextPairGen(inputDiff);
ciphertextPairGen();
cipherFiltering();
guessKey(interDiff);
printGuessedKey();
return 0;
}
void createDDT() {
wd_t i, j; for (i = 0; i < 16; i++) {
for (j = 0; j < 16; j++) {
wd_t input_diff = i ^ j;
wd_t output_diff = caltoy_sbox[i] ^ caltoy_sbox[j];
ddt[input_diff][output_diff]++;
}
}
for (i = 0; i < 16; i++)
{
for (j = 0; j < 16; j++)
{
printf("%2d", ddt[i][j]);
} printf("n");
}
}
void clear() {
int i, j;
for (i = 0;i < 16;i++) {
for (j = 0;j < PR;j++) {
check_key[i][j] = 0;
}
}
for (i = 0;i < PR;i++) {
filter[i] = 0;
plain[i].p1 = 0;
plain[i].p2 = 0;
cipher[i].c1 = 0;
cipher[i].c2 = 0;
}
}
void plaintextPairGen(int diff) {
int i;
const int fourBits = 0x10;
for (i = 0;i < PR;i++) {
unsigned char n1 = rand() % fourBits;
unsigned char n2 = rand() % fourBits;
unsigned char n3 = rand() % fourBits;
unsigned char n4 = rand() % fourBits;
plain[i].p1 = (n1 << 12) | (n2 << 8) | (n3 << 4) | (n4);
plain[i].p2 = plain[i].p1 ^ diff;
if(i < 100)
printf("plain pair is %X %Xn", plain[i].p1, plain[i].p2);
}
}
void ciphertextPairGen() {
int i;
for (i = 0;i < PR;i++) {
caltoy_enc(&(cipher[i].c1), plain[i].p1);
caltoy_enc(&(cipher[i].c2), plain[i].p2);
if (i < 100)
printf("cipher pair is %X %Xn", cipher[i].c1, cipher[i].c2);
}
}
void cipherFiltering() {
int i;
for (i = 0;i < PR;i++) {
int cipher_diff = (cipher[i].c1 ^ cipher[i].c2);
if ((((cipher_diff >> 12) & 0xf) == 0) && (((cipher_diff >> 4) & 0xf) == 0) && ((cipher_diff & 0xf) == 0)) {
filter[i] = 1;
printf("cipher diff is %X", cipher_diff);
printf(" filtering success! (%d)n", i);
}
}
}
void guessKey(int interDiff) {
int i, j;
int count[16] = { 0, };
for (i = 0;i < 16;i++) {
for (j = 0;j < PR;j++) {
if (filter[j] != 1) check_key[i][j] = -1;
else {
ct_t c1 = (((cipher[j].c1 & 0x0f00) >> 8) ^ i);
ct_t c2 = (((cipher[j].c2 & 0x0f00) >> 8) ^ i);
ct_t i1 = caltoy_inv_sbox[c1];
ct_t i2 = caltoy_inv_sbox[c2];
if ((ct_t)(i1 ^ i2) == interDiff) {
check_key[i][j] = 1;
printf("checking key (%d) success!n", i);
}
}
}
}
for (i = 0;i < 16;i++) {
for (j = 0;j < PR;j++) {
if (check_key[i][j] == 1) key[i]++;
}
}
}
void printGuessedKey() {
int i, Max = -1;
for (i = 0;i < 16;i++) {
if (Max < key[i]) Max = key[i];
}
printf("nPartial keyn");
printf("Max value is %dn", Max);
for (i = 0;i < 16;i++) {
if (Max == key[i]) printf("%01Xn", i);
}
for (i = 0;i < 16;i++) {
printf("nkey[%d] : %d", i, key[i]);
}
}