はじめに

こんにちは、大阪大学CTFサークルWani Hakcaseのぐれいしゃといいます。
普段は週末にCTFに参加して、cryptやmisc、revなどの問題を解いています。
先日、近畿総合通信局が開催していた大学対抗CTFに作問者としていくつか問題を提供していたので、それらの作問者Writeupを投稿しようと思います。
作問者は自分の出題した問題が含まれない問題セットで解くことになるため、実際の出題形式と異なる場合があります。ご容赦ください。

目次

forest [初級者：misc]
see_that_and_go [上級者：crypt]
Randomize [上級者：rev]

forest [misc]

問題文

木を隠すなら森の中ってね！

概要

以下のような2つのファイルが配布されます。

output.txt

~ dummy flags ~

FLAG{250}
FLAG{251}
FLAG{252}
FLAG{253}
FLAG{254}
FLAG{255}
FLAG{256}
FLAG{257}
FLAG{258}
FLAG{259}
FLAG{260}

~ dummy flags ~

chall.py

import random

FLAG = 'FLAG{FAKE_FLAG}'
FLAGFORMAT = 'FLAG{%s}'
n_line = 100000
rdint = random.randint(n_line//4, n_line*3//4)

f = open('out.txt', 'w')

for i in range(n_line):
    if i == rdint:
        f.write(FLAG + '\n')
    else:
        f.write(FLAGFORMAT % (str(i)) + '\n')

f.close()

解説

chall.pyを読むと、FLAGは100000行あるダミーフラグの内、25000行目から75000行目のどこかにあるようです。
流石にこの量を目で追うのは大変なので、楽に調べる方法を利用します。
例えば、grepというコマンドは正規表現を用いて条件を満たすような文字列だけを検索することが出来ます。
実際のコマンド例は次のようになります。

$ grep -v -E "FLAG\{[0-9]+\}" output.txt

実行してみると、ターミナルに以下の文字列が出力されます。

FLAG{d1d_y0u_d0_3y3_gr3p?}

ということでFLAGを得ることが出来ました。
ちなみに、VSCodeというエディターでも正規表現を用いた検索をすることが出来ます。

see_that_and_go [cry]

問題文

あれだ！あれこそが古代に存在した超文明の宝だ！！
しかし、透明の障壁に阻まれて近づけん・・・
どうやら暗号を解いて解除しないといけないみたいだ

DJYE{0ol_x0qhzY11_q4m_q34e_3Lwlsjn10h}

概要

以下のchall.pyが配布されます。

chall.py

import random

FLAG = 'FLAG{FAKE_FLAG}'

def encrypt(s):
    randint1 = random.randint(1, 25)
    randint2 = random.randint(1, 25)
    while randint1 == randint2:
        randint2 = random.randint(1, 25)
    ret = ''
    for c in s:
        if c.isalpha():
            if c.islower():
                ret += chr((ord(c) - ord('a') + randint1) % 26 + ord('a'))
            else:
                ret += chr((ord(c) - ord('A') + randint2) % 26 + ord('A'))
        else:
            ret += c
    return ret


def main():
    enc = encrypt(FLAG)
    print(enc)

if __name__ == '__main__':
    main()

解説

chall.pyを見ると大文字と小文字で異なるkeyを使ったシーザー暗号で暗号化されていることが分かります。

シーザー暗号はアルファベットからなる文章に対して、各文字をx文字後ろの文字にするという暗号化です。

（key=0）：crypt → crypt
（key=1）：abcde → bcdef
（key=13）：FLAG → SYNT
（key=25）：qiita → phhsz

ここで、zの1文字後ろはaというように、循環するように暗号化されることに注意してください。

さて、暗号化されたFLAGの最初の4文字は"FLAG"なので大文字の鍵はそこから推測できます。
大文字を暗号化前の状態に戻したら、小文字のkeyを総当たりすることで残りも復号できます。
ということで、solverは以下のようになります。

solve.py

def caesar(s, k, mode):
    r = ''
    if mode == 0:
        for i in s:
            if i.islower():
                r += chr((ord(i) - 97 + k) % 26 + 97)
            elif i.isupper():
                r += chr((ord(i) - 65 + k) % 26 + 65)
            else:
                r += i
    elif mode == 1:
        for i in s:
            if i.islower():
                r += chr((ord(i) - 97 - k) % 26 + 97)
            else:
                r += i
    elif mode == 2:
        for i in s:
            if i.isupper():
                r += chr((ord(i) - 65 - k) % 26 + 65)
            else:
                r += i
    else:
        print('mode error')
    return r

def decrypt(s):
    key_upper = 0
    key_lower = 0
    ret = []
    for i in range(26):
        if caesar(s, i, 2).find('FLAG') != -1:
            key_upper = i
            break
    tmp = caesar(s, key_upper, 2)
    for i in range(26):
        ret.append(caesar(tmp, i, 1))
    return ret

def main():
    c = 'DJYE{0ol_x0qhzY11_q4m_q34e_3Lwlsjn10h}'
    FLAG_list = decrypt(c)
    for i in FLAG_list:
        print(i)

if __name__ == '__main__':
    main()

solverを利用すると出力は以下のようになります。

FLAG{0ur_d0wnfA11_w4s_w34k_3Ncrypt10n}

上級者コースで出題されましたが、他のcryptに比べると結構簡単だったのではないかなと思います。

Randomize [rev]

問題文

Flagを暗号化するプログラムを作成しました！
誰にも解読できないよね・・・？

概要

以下のoutput.txtと実行ファイルであるrandomizeが配布されます。

output.txt

20 25 89 92 37 80 71 64 53 92 5 108 24 73 11 96 55 54 43 62 124 34 41

randomizeは実際には以下のCファイルをコンパイルしたものです。

randomize.c

#include <stdio.h>
#include <stdbool.h>

int state, A, B, M;
char buf[50];
int cipher[50];
int randoms[50];

void init(){
    printf("Enter the seed: ");
    scanf("%d", &state);
    printf("Enter A: ");
    scanf("%d", &A);
    printf("Enter B: ");
    scanf("%d", &B);
    M = 128;
    printf("Enter the flag: ");
    scanf("%s", buf);
}

int nextInt(){
    state = (state * A + B) % M;
    return state;
}

void encrypt(char *buf){
    for(int i = 0; buf[i] != '\0'; i++){
        randoms[i] = nextInt();
        cipher[i] = buf[i] ^ randoms[i];
    }
}

int main(){
    init();
    encrypt(buf);
    FILE *fp;
    fp = fopen("out.txt", "w");
    for(int i = 0; buf[i] != '\0'; i++){
        fprintf(fp, "%d ", cipher[i]);
    }
    fclose(fp);
    printf("Done!\n");
    return 0;
}

$ gcc -o randomize randomize.c

解説

実行ファイルが配布されているためghidraなどを用いてデコンパイルします。
ghidraについて詳しくない方は、以前ghidraについての記事を投稿したのでそちらを参考にしていただけたらと思います。(CTFとは？Ghidraを使ったreversing入門)
デコンパイルしたソースコードは次のようになります。

main

undefined8 main(EVP_PKEY_CTX *param_1,int param_2)

{
  FILE *__stream;
  int local_14;
  
  init(param_1);
  encrypt(buf,param_2);
  __stream = fopen("out.txt","w");
  for (local_14 = 0; buf[local_14] != '\0'; local_14 = local_14 + 1) {
    fprintf(__stream,"%d ",(ulong)*(uint *)(cipher + (long)local_14 * 4));
  }
  fclose(__stream);
  puts("Done!");
  return 0;
}

init

int init(EVP_PKEY_CTX *ctx)

{
  int iVar1;
  
  printf("Enter the seed: ");
  __isoc99_scanf(&DAT_00102015,&state);
  printf("Enter A: ");
  __isoc99_scanf(&DAT_00102015,&A);
  printf("Enter B: ");
  __isoc99_scanf(&DAT_00102015,&B);
  M = 0x80;
  printf("Enter the flag: ");
  iVar1 = __isoc99_scanf(&DAT_0010203d,buf);
  return iVar1;
}

encrypt

void encrypt(char *__block,int __edflag)

{
  undefined4 uVar1;
  int local_c;
  
  for (local_c = 0; __block[local_c] != '\0'; local_c = local_c + 1) {
    uVar1 = nextInt();
    *(undefined4 *)(randoms + (long)local_c * 4) = uVar1;
    *(uint *)(cipher + (long)local_c * 4) =
         (int)__block[local_c] ^ *(uint *)(randoms + (long)local_c * 4);
  }
  return;
}

nextInt

int nextInt(void)

{
  state = (B + state * A) % M;
  return state;
}

まず、main関数の処理を見ると、init関数を呼んでstate, A, B, M, FLAGを初期化しています。
その後、encrypt関数でFLAGとランダムな数とのxorを取って暗号化しているのですが、ランダムな数はnextInt関数で計算されており、その内部のアルゴリズムは線形合同法となっています。
線形合同法は以下のようなアルゴリズムとなっています。
$$
X_{i+1} = (X_i * A+B)\ mod\ M
$$

$X_i$：作成される疑似乱数列のi番目
$A$：線形合同法のパラメータ１
$B$：線形合同法のパラメータ２
$M$：線形合同法のパラメータ３

線形合同法はいずれかのパラメータと連続するいくつかの疑似乱数が判明している場合、i番目の疑似乱数($\forall i\in \mathrm{N}$)を求めることが出来ます。（パラメータが何も判明していない場合でも可能です）
詳しくは以下の記事を参照してください。
線形合同法 (Linear Congruential Generators) によって生成される擬似乱数を予測する

この問題では疑似乱数が何も判明していないように見えますが、FLAGが FLAG{ から始まるため ord('F') xor output[0] のようにして連続する5つの疑似乱数が計算できます。
また、init関数を見ると M=0x80 とあり、Mの値が判明しています。（0x80は16進数表記であり、10進数表記に直すと128になります）

線形合同法の式から、$X_0,A,B$はM以上の値を取っても$X_0\ mod\ M$や$A\ mod\ M$, $B\ mod\ M$に変換されて意味がないため、$0\leq X_0,A,B < M=128$ を考えます。

例）$X_0 = X_0'+M*k$の時

\begin{align}
X_{1} &= (X_0*A+B)\ mod\ M \\ 
        &= ((X_0'+M*k)*A+B)\ mod\ M \\
        &= (X_0'*A+M*k*A+B)\ mod\ M \\
        &= (X_0'*A+B)\ mod\ M
\end{align}

例）$A = A'+M*k$の時

\begin{align}
X_{i+1} &= (X_i*A+B)\ mod\ M \\ 
        &= (X_i*(A'+M*k)+B)\ mod\ M \\
        &= (X_i*A'+X_i*M*k+B)\ mod\ M \\
        &= (X_i*A'+B)\ mod\ M
\end{align}

例）$B = B'+M*k$の時

\begin{align}
X_{i+1} &= (X_i*A+B)\ mod\ M \\ 
        &= (X_i*A+B'+M*k)\ mod\ M \\
        &= (X_i*A+B')\ mod\ M
\end{align}

ということで、$X_0, A, B$について0以上128未満の整数を全探索して、生成された疑似乱数列の初めの5項が既に判明している5つの疑似乱数と一致するものを探します。

以下が実装したsolverになります。

solve.c

#include <stdio.h>
#include <stdbool.h>

int state, A, B, M;
char FLAG[50] = "FLAG{";
char buf[50];
int cipher[50];
int randoms[50];

int nextInt(){
    state = (state * A + B) % M;
    return state;
}

int main(){
    FILE *fp;
    fp = fopen("out.txt", "r");
    for(int i = 0; i < 50; i++){
        fscanf(fp, "%d", &cipher[i]);
    }
    fclose(fp);
    M = 128;
    for(int i = 0; i < 5; i++){
        randoms[i] = cipher[i] ^ FLAG[i];
    }
    for(int a=0;a<128;a++){
        A = a;
        for(int b=0;b<128;b++){
            B = b;
            for(int s=0;s<128;s++){
                state = s;
                bool flag = true;
                for(int i = 0; i < 5; i++){
                    if(randoms[i] != nextInt()){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    for(int i=0;i<5;i++){
                        printf("%c", FLAG[i]);
                    }
                    for(int i=5;i<50;i++){
                        printf("%c", cipher[i] ^ nextInt());
                    }
                }
            }
        }
    }
    return 0;
}

上記のコードを実行すると以下の出力を得ます。

FLAG{1cg_15_n07_53cur3}W`c&)lo25x{>AJMVYbe

FLAGの後ろについている文字列はご愛敬です。

おわりに

今回のCTFでは私も現地に赴き、競技者として参加していましたが、多くの方に楽しんでもらえたようで良かったです。もし、このイベントでCTFに興味を持たれた方がいらっしゃれば、Wani Hackaseでは毎年（？）Wani CTFを開催しておりますので、そちらにもご参加いただければ嬉しいです。
最後に、ご参加くださった皆様、NTTの粕淵様、各大学の先生方に心から感謝申し上げます。ありがとうございました。