[ksnctf] Perfect Cipher

ksnctfにチャレンジ 第21問目です。

※ksnctfは常駐型のCTFサイトです。 ※問題のページはコチラです。

Perfect Cipher

乱数を利用してワンタイムパッドな暗号化が施されているため 元のデータを復元することはできないファイルを復号する問題です。

配布の暗号化ソースコードをみると 　メルセンヌ・ツイスタを用いた乱数生成器 を利用してワンタイムパッド用の乱数表を作成していることが わかります。

メルセンヌ・ツイスタは非常に優秀な乱数生成器ですが、 一定量以上の生成器の出力を集めると暗号生成器の中身が 再現可能になって、以降どんな乱数が出力されるか計算可能に なります。 mt19937.cpp はじめ通常の実装では　連続する624個分の出力が集まればOKです。 mt19937.cpp では乱数を生成するために シード値などから精製した 　テーブル mt[624] と　インデックス mti をもちいて乱数を生成するため、生成された乱数から テーブル mt を復元 すればいいわけです。

genrand_int32() の Tempering という部分が テーブル mt から　乱数を作る計算なので　この逆関数に当たる処理を 書きます。 逆関数は検索すれば　JavaやPythonなどの実装が見つかったので　それを 参考にC用に書きなおせました。

次に、　テーブルmt を復元するための　出力サンプルが必要です。 メルセンヌ・ツイスタで得た乱数を用いて 　(元データ) xor (乱数) = (暗号データ) という計算をしており 乱数は　hoge.key
暗号データは　hoge.enc として保存しているだけなので 　(元データ)　xor (暗号データ) = (乱数) となり encrypt.cpp encrypt.enc のデータを XOR することで encrypt.key を復元することができます。

encrypt.key はまさに メルセンヌ・ツイスタで生成された 乱数表そのものでかつ 624個以上の乱数が記されています。

この乱数表を先術の　Temperingの逆処理にまわして テーブルmt を復元すれば　最初にデータを暗号化したときと 全く同じ乱数表が得られます。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "mt19937ar.h"

extern unsigned long mt[624]; 
extern int mti;

unsigned int store[624];
unsigned int key[624];
int eti;

unsigned int un_bit_shift_left_xor(unsigned int v,int shift, unsigned int mask);
unsigned int un_bit_shift_right_xor(unsigned int v,int  shift);
unsigned int un_tempering(unsigned int k);
unsigned int emu_init();
unsigned int emu_genrand_int32();
void dummy_encrypt(const char *plain, const char *crypt, const char *key);
void decrypt(const char *plain, const char *crypt, const char *key);
void encrypt(const char *plain, const char *crypt, const char *key);
void getflag(const char *file);
void makekey();
int min(int a, int b) { return a<b ? a : b; }

int main()
{
    makekey();
    emu_init();

    encrypt("encrypt.cpp", "encrypt.enc", "encrypt.key");
    dummy_encrypt("flag.jpg", "flag.enc", "flag.key");

    decrypt("encrypt_dec.cpp", "encrypt.enc", "encrypt.key");
    decrypt("flag_dec.jpg", "flag.enc", "flag.key");

    getflag("flag_dec.jpg");
    return 0;
} 

void dummy_encrypt(const char *plain, const char *crypt, const char *key)
{
    FILE *fk = fopen(key, "wb");

    for (int i=0; i<80000; i+=4)
    {
        unsigned long k = emu_genrand_int32();
        fwrite(&k, 4, 1, fk);
    }
    fclose(fk);
}

void encrypt(const char *plain, const char *crypt, const char *key)
{
    FILE *fp = fopen(plain, "rb");
    FILE *fc = fopen(crypt, "wb");
    FILE *fk = fopen(key, "wb");

    fseek(fp, 0, SEEK_END);
    unsigned long length = (unsigned long)ftell(fp);
    fseek(fp, 0, SEEK_SET);

    fwrite(&length, 4, 1, fc);

    for (int i=0; i<length; i+=4)
    {
        unsigned long p;
        fread(&p, 4, 1, fp);
        unsigned long k = emu_genrand_int32();
        unsigned long c = p^k;
        fwrite(&c, 4, 1, fc);
        fwrite(&k, 4, 1, fk);
    }

    fclose(fp);
    fclose(fc);
    fclose(fk);
}

void decrypt(const char *plain, const char *crypt, const char *key)
{
    FILE *fp = fopen(plain, "wb");
    FILE *fc = fopen(crypt, "rb");
    FILE *fk = fopen(key, "rb");

    unsigned long length;
    fread(&length, 4, 1, fc);

    for (int i=0; i<length; i+=4)
    {
        unsigned long c;
        fread(&c, 4, 1, fc);
        unsigned long k;
        fread(&k, 4, 1, fk);
        unsigned long p = c^k;

        fwrite(&p, min(4,length-i), 1, fp);
    }

    fclose(fp);
    fclose(fc);
    fclose(fk);
}

void getflag(const char *file)
{
    int i;
    char c;
    FILE *fp;
    fp = fopen(file, "rb");
    for( i=0; !feof(fp); i++)
     {
        c=fgetc(fp);
         if( isgraph(c) )
         {
            if(i>=4218 && i<=(4218+42)) printf("%c",c);
        }
     }
    fclose(fp);
    printf("\n");
}

void makekey()
{
    int i;
    int blocks;

    unsigned long p,k,e;

    FILE *fp;
    FILE *fe;
    FILE *fk;

    fp = fopen("encrypt.cpp", "rb");
    fe = fopen("encrypt.enc", "rb");
    fk = fopen("sample.key", "wb");

    fread(&blocks, 4, 1, fe);

    for(i=0; i<blocks; i++)
    {
        fread(&p, 4, 1, fp);
        fread(&e, 4, 1, fe);
        k = p^e;
        fwrite(&k, min(4,blocks-i), 1, fk);
    }

    fclose(fp);
    fclose(fe);
    fclose(fk);
    return;
}

unsigned int un_bit_shift_left_xor(unsigned int v,int shift, unsigned int mask)
{
    int i;
    unsigned int r,tmp;

    i = 1;
    r = v;

    while( (i*shift) < 32 )
    {
        tmp = r << shift;
        r   = v ^ (tmp&mask);
        i++;
    }

    return r;
}

unsigned int un_bit_shift_right_xor(unsigned int v,int  shift)
{
    int i;
    unsigned int r,tmp;

    i = 1;
    r = v;

    while( (i*shift) < 32 )
    {
        tmp = r >> shift;
        r   = v ^ tmp;
        i++;
    }

    return r;
}

unsigned int un_tempering(unsigned int k)
{
    unsigned int x;
    x = k;
    x = un_bit_shift_right_xor(x, 18);
    x = un_bit_shift_left_xor(x, 15, 0xefc60000);
    x = un_bit_shift_left_xor(x, 7, 0x9d2c5680);
    x = un_bit_shift_right_xor(x, 11);

    return x;
}

unsigned int emu_init()
{
    FILE  *fk;
    int i;
    unsigned long k;

    fk = fopen("sample.key", "rb");

    for(i=0; i<624; i++)
    {
        fread(&k, 4, 1, fk);
        key[i] = k;
    }

    for(i=0;i<624;i++)  mt[i] = un_tempering(key[i]);
    mti = 624;    
    eti = 0;
}

unsigned int emu_genrand_int32()
{
    unsigned int ret;
    if(eti<624)
    {
        ret = key[eti];
        eti++;
        return ret; 
   }else{
        return genrand_int32();
    }
}

これがソースコードの全体です。 genrand_int32(); の代わりに　画像暗号化時の乱数生成を再現する emu_genrand_int32(); という関数を作って元の encrypt.cppの作業を 再現してみました。

使用する前に　配布されたデータの中の mt19937ar.cpp の 56 57 行目で

unsigned long mt[N]; /* the array for the state vector  */
int mti=N+1; /* mti==N+1 means mt[N] is not initialized */

static を除去します。(解析した値で mt mti を上書きするため)

static 除去が終わったら　take21.cpp という名前で解凍したフォルダに ソースコードを保存して

$ g++ -o take21 take21.cpp mt19937ar.cpp 
$ ./take21

でFLAG取得まで自動でおわります。

ちなみに FLAGなどは正常にとれ、JPEGのヘッダは　FF D8 からはじまり Adobe Exif などの文字も確認できるのですが　画像自体は破損扱いに なっています。 テーブルの生成の一部に不備があるのかもしれません…が とりあえずFLAGが取れたので良しとします。