[ksnctf] Are you ESPer?

[ksnctf] Are you ESPer?

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

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

(Take36の掲載忘れてました…)

Are you ESPer?

この問題は、本質部分は簡単なのに 仕上げるのにちょっと戸惑う部分があります。

esp というプログラムは 1~9 の数字から正解のものを あてるゲームプログラムで 最初のうちは複数回チャレンジしてもよいので 手動二分検索っぽく入力していけば大丈夫ですが 4,5問目になるとミスが許されなくなっていき 最終的にノーミスで20問連続正解しないといけません。 エスパーの方以外はクリア不能ですね。

ですが、espプログラムを覗くと実は正解の 数字がわかってしまうよ　という問題です。

逆アセンブルした結果から 大まかにespの内容をC言語に起こすと

void main()
{
    int i,n　…ループ数など… ;
    int var1, var2;
    int flag;

    srandom(time(NULL));
    for(i=0; i<20; i++)
    {
        var1 = rand()%10;
       for(;;)
        {
            printf("Level %d/20　…\n",i, …);
            scanf("%d", var2);
            if( var1 > var2 ){
                puts("Too small\n");
                flag = 1;
            }else{
                if(var1 < var2){
                    puts("Too large\n");
                    flag = 1;
                }else{
                    puts("Correct!\n");
                    flag = 0;
                }
            }

            ~~ チャレンジ回数チェック ~~
            if(flag) continue;
        }
    }
}

まぁここまで書きおこす必要はありません ようは先頭で 　srandom(time(NULL)); が使われていることさえ確認できれば終了です。

C言語の rand() は　線形合同法を用いた擬似乱数なので 本来出力するのは乱数っぽい数列です。 よって"同じ条件"では同じ数値を返してきます。

その条件と言うのが seed値 でsrand() で seed値を設定します。

今回は現在時刻 time(NULL) をseed値として利用しているわけです。 プログラムの実行時間は実行するたびに異なるので 毎回違う乱数っぽい数列が得られるっという寸法です。

ということは

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void main()
{
    int i;

    srandom(time(NULL));
    for(i=0; i<20; i++) printf("%d\n",rand()%10);

    return;
}

こんなテストプログラム take36.cを組んで

$ gcc take36.c
$ ./a.out | ./esp

と実行すると、 a.out と esp はほぼ同時刻に実行されるので

この通り ./a.out と ./esp で同じ乱数が生成されて 一瞬でオールコレクト　になります。

ということで完成しましたので

$ gcc take36.c
$ ./a.out |  nc ctfq.sweetduet.info 10777

これでクリア！…あれ？

全然合いません。

仕組み上違ってはいけないので違うとしたら　時刻です。 どういうことかというと

$ ./a.out |  nc ctfq.sweetduet.info 10777

これが実行されるとき a.out の time(NULL) は手元のコンピュータに設定された現在時刻 esp の time(NULL) はksnctfのサーバーに設定された現在時刻 です。

これが何秒かズレているのでseed値が違ってしまっているのでしょう。

take36.c のsrand()に

srandom(time(NULL)+X);

Xに±1〜10秒程度のズレ調整分を設けてやってみました…が失敗。

どうしようか暫く悩んだのですが 結局のところksnctfのサーバーの設定時間が分かればいいので Take13 Proverb を利用することにしました。

sshでQ13にログインして 現在時刻をUNIX時間で取得します。

$ date +'%s'

これを実行。 素早く自分のマシンでも同じコマンドを実行して 両者の時計のズレを計算したところ 　なんと 1183秒 もズレていました。 いやーなズレ具合ですね…。

何はともあれ時計のズレがわかったので　take36 を修正して

srandom(time(NULL)+1183);

こうすると

無事通りました。

このズレはわざとなのでしょうか？ しかし回線状況や手元のPCの時間のズレもあるので どちらにせよ時計の調整は必須かもしれません。

Write up はかなり書きにくそうです。