ksnctf 21 Perfect Cipher

ksnctfの21問目を解いていきます。メルセンヌツイスタの問題です。 ksnctf.sweetduet.info

大まかな解法

1. encrypt.keyを復元する
2.encrypt.keyからメルセンヌツイスタの乱数を予測し、flag.keyを生成する
3.flag.keyとflag.encからflag_dec.jpgを復元する

1. encrypt.keyを復元する

encrypt.zipには以下のファイルがあります。

↓encrypt.cpp

//  g++ -O2 -o encrypt.exe encrypt.cpp mt19937ar.cpp

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

typedef unsigned long dword;

void initialize(const char *seed);
void encrypt(const char *plain, const char *crypt, const char *key);
void decrypt(const char *plain, const char *crypt, const char *key);
int min(int a, int b) { return a<b ? a : b; }

int main()
{
    initialize("seed");
    
    encrypt("encrypt.cpp", "encrypt.enc", "encrypt.key");
    encrypt("flag.jpg", "flag.enc", "flag.key");
    
    //  decrypt("encrypt_dec.cpp", "encrypt.enc", "encrypt.key");
    //  decrypt("flag_dec.jpg", "flag.enc", "flag.key");
}

void initialize(const char *seed)
{
    const int N = 1024;
    
    FILE *f = fopen(seed, "rb");
    if (f==NULL)
    {
        printf("Failed to open %s\n", seed);
        exit(-1);
    }
    
    dword buf[N];
    fread(buf, sizeof (dword), N, f);
    
    fclose(f);
    
    init_by_array(buf, N);
}

void encrypt(const char *plain, const char *crypt, const char *key)
{
    FILE *fp = fopen(plain, "rb");
    if (fp==NULL)
    {
        printf("Failed to open %s\n", plain);
        exit(-1);
    }
    FILE *fc = fopen(crypt, "wb");
    if (fc==NULL)
    {
        printf("Failed to open %s\n", crypt);
        exit(-1);
    }
    FILE *fk = fopen(key, "wb");
    if (fk==NULL)
    {
        printf("Failed to open %s\n", key);
        exit(-1);
    }
    
    fseek(fp, 0, SEEK_END);
    dword length = (dword)ftell(fp);
    fseek(fp, 0, SEEK_SET);
    
    fwrite(&length, 4, 1, fc);
    
    for (int i=0; i<length; i+=4)
    {
        dword p;
        fread(&p, 4, 1, fp);
        dword k = genrand_int32();
        dword 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");
    if (fp==NULL)
    {
        printf("Failed to open %s\n", plain);
        exit(-1);
    }
    FILE *fc = fopen(crypt, "rb");
    if (fc==NULL)
    {
        printf("Failed to open %s\n", crypt);
        exit(-1);
    }
    FILE *fk = fopen(key, "rb");
    if (fk==NULL)
    {
        printf("Failed to open %s\n", key);
        exit(-1);
    }
    
    dword length;
    fread(&length, 4, 1, fc);
    
    for (int i=0; i<length; i+=4)
    {
        dword c;
        fread(&c, 4, 1, fc);
        dword k;
        fread(&k, 4, 1, fk);
        dword p = c^k;
        
        fwrite(&p, min(4,length-i), 1, fp);
    }
    
    fclose(fp);
    fclose(fc);
    fclose(fk);
}

encrypt関数において、
①引数で指定したファイルを開く
②第一引数で指定したファイル(fp)のサイズを取得して.encファイルの先頭4バイトに書き込む ③genrand_int32関数でメルセンヌツイスタの疑似乱数を生成
④fpと生成した疑似乱数を4バイト単位でXORしたものを.encファイルに出力(生成した乱数は.keyファイルに記録する)
というような操作が行われています。

暗号化と言っても単にXORしているだけなのでXORの性質を利用すればencrypt.keyファイルの復元が可能です。
いま、encrypt関数で
encrypt .cpp (XOR) encrypt.key = encrypt.enc
が計算されているので、
encrypt.cpp (XOR) encrypt.enc(先頭4バイト除く) = encrypt.key
となり、生成された乱数を得ることができます。

2.encrypt.keyからメルセンヌツイスタの乱数を予測し、flag.keyを生成する

メルセンヌ・ツイスタをわかった気になる | 成瀬順のメモ帳
(メルセンヌツイスタのしくみについて書かれています)

メルセンヌツイスタは連続した624個の乱数があれば次に生成される乱数の予測が可能になります。先ほど復元したencrypt.keyは2600バイト(=650個の乱数)なので次に生成されたflag.keyを予測できます。これを一から実装するのは大変なので、

Mersenne Twisterの出力を推測してみる - ももいろテクノロジー
こちらのpredict_mt.pyをお借りして、改造します。

import random
from struct import *

def untemper(x):
    x = unBitshiftRightXor(x, 18)
    x = unBitshiftLeftXor(x, 15, 0xefc60000)
    x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
    x = unBitshiftRightXor(x, 11)
    return x

def unBitshiftRightXor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^ z
        i += 1
    return y

def unBitshiftLeftXor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^ (z & mask)
        i += 1
    return y


#encrypt.keyから乱数を624読み込みメルセンヌツイスタの内部状態を復元
with open("encrypt.key", "rb") as f:
    values1 = [int.from_bytes(f.read(4), 'little') for i in range(624)]
    mt_state = tuple([untemper(x) for x in values1] + [624])
    random.setstate((3, mt_state, None))

#650個まで分かってるのでいらない
waste=[random.getrandbits(32) for i in range(26)]

#バイト数が78556 → 19639個の乱数が復元に必要
pre = [random.getrandbits(32) for i in range(19639)]


#生成された乱数を4バイト単位でflag.keyに書き込み
with open("flag.key", "wb") as f:
    for x in pre:
        f.write(pack('<L', x))

3.flag.keyとflag.encからflag_dec.jpgを復元する

flag.keyが分かったのであとはdecrypt関数にかければflag_dec.jpgが復元されます。flag_dec.jpgをバイナリエディタで開くとちょっと下にフラグが出てきます。