[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 はかなり書きにくそうです。

コメントする