ksnctf write up ~ 36 Are you ESPer? ~

解けそうで解けない、がずっと続いていたがようやく解けた。

問題

nc ctfq.sweetduet.info 10777
http://ksnctf.sweetduet.info/q/36/esp

ハマりどころ

• MACでrand() を使うと、ubuntuのrand()とは違う値を吐き出すので、ubuntu上でコードを実行する必要あり。
• 問題サーバの時刻がずれているので、srand(time(NULL))をsrand(time(NULL) + （誤差）)としなければならない。

解法

nc ctfq.sweetduet.info 10777 すると、以下のような数当てゲームが始まる。

Level 1/20, Challenge 1/10
? 5
Too large

Level 1/20, Challenge 2/10
? 3
Too large

Level 1/20, Challenge 3/10
? 2
Correct!

初めはChallenge数が多いので正解できるが、途中からChallenge数が1とかになって来るので、一発で当てる必要がある。

ここからバイナリ解析。

   0x0804837c <+188>:	lea    eax,[esp+0x3c]
   0x08048380 <+192>:	mov    DWORD PTR [esp+0x4],eax
   0x08048384 <+196>:	mov    DWORD PTR [esp],0x80cc649
   0x0804838b <+203>:	call   0x8055500 <scanf>
   0x08048390 <+208>:	mov    edx,DWORD PTR [esp+0x18]
   0x08048394 <+212>:	cmp    edx,DWORD PTR [esp+0x3c]
   0x08048398 <+216>:	jg     0x8048478 <main+440>
   0x0804839e <+222>:	jge    0x8048460 <main+416>

ここら辺で、ユーザの入力した値は[esp+0x3c]に格納され、[esp+0x18]の値と比較されていることが分かる。

---

   0x080482cc <+12>:	mov    DWORD PTR [esp],0x0
   0x080482d3 <+19>:	call   0x806b880 <time>
   0x080482d8 <+24>:	mov    DWORD PTR [esp],eax
   0x080482db <+27>:	call   0x8054ec0 <srandom>
   0x080482e0 <+32>:	mov    DWORD PTR [esp+0x1c],0x0
   0x080482e8 <+40>:	call   0x8055490 <rand>
   0x080482ed <+45>:	mov    ecx,eax
   0x080482ef <+47>:	mov    eax,0x66666667
   0x080482f4 <+52>:	imul   ecx
   0x080482f6 <+54>:	mov    eax,ecx
   0x080482f8 <+56>:	sar    eax,0x1f
   0x080482fb <+59>:	mov    edi,edx
   0x080482fd <+61>:	mov    edx,DWORD PTR [esp+0x1c]
   0x08048301 <+65>:	sar    edi,0x2
   0x08048304 <+68>:	sub    edi,eax
   0x08048306 <+70>:	lea    edi,[edi+edi*4]
   0x08048309 <+73>:	mov    eax,DWORD PTR [edx*4+0x80bb260]
   0x08048310 <+80>:	add    edi,edi
   0x08048312 <+82>:	sub    ecx,edi
   0x08048314 <+84>:	test   eax,eax
   0x08048316 <+86>:	jg     0x8048340 <main+128>
.
.
.
   0x08048340 <+128>:	add    edx,0x1
   0x08048343 <+131>:	xor    ebx,ebx
   0x08048345 <+133>:	mov    DWORD PTR [esp+0x1c],edx
   0x08048349 <+137>:	mov    edi,eax
   0x0804834b <+139>:	mov    DWORD PTR [esp+0x18],ecx

ここら辺で、time()をシードとして初期化された乱数rを用いて以下のように[esp+0x18]の計算が行われている。

ecx = r
eax = 0x66666667
edx:eax = ecx * eax (= r * 0x66666667)
eax = ecx (= r)
eax >>= 0x1f
edi = edx (= r * 0x66666667 >> 32)
edi >>= 2
edi = edi - eax (= edi - r >> 0x1f)
edi *= 5
edi += edi
ecx = ecx - edi (= r - edi)
[esp+0x18] = ecx

まとめると、以下。

[esp+0x18] = r - (((r * 0x66666667 >> 32) >> 2) - (r >> 0x1f)) * 10)

これを実装すればよいので、以下のようなCスクリプトを作成。

miss.c

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

int main(int argc, char *argv[]){
  srand(time(NULL));
  for (int i = 0; i < 20 ; i++){
    long long r = rand();
    printf("%lld\n", r - (((r * 0x66666667 >> 32) >> 2) - (r >> 0x1f)) * 10);
    fflush(stdout);
  }
}

これで以下のコマンドでいけるはず、、！

gcc miss.c
a.out | nc ctfq.sweetduet.info 10777

しかし、ローカルではうまくいくが、リモートサーバで上手くいかない。
これは、サーバの時刻がずれているためらしい。
他の問題(4 Villager A など)で、問題サーバにsshできるので、date コマンドで時刻を確認。
すると、時刻が1分ほどずれていることがわかった。

そこで、srand(time(NULL)) を srand(time(NULL) + （誤差）) とした。

solve.c

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

int main(int argc, char *argv[]){
  srand((time(NULL))+atoi(argv[1]));
  for (int i = 0; i < 20 ; i++){
    long long r = rand();
    printf("%lld\n", r - (((r * 0x66666667 >> 32) >> 2) - (r >> 0x1f)) * 10);
    fflush(stdout);
  }
}

solve.sh

#!/usr/bin/bash
for ((i = 40; i < 80; i++)) do
./a.out $i | nc ctfq.sweetduet.info 10777
echo $i
done

シェルスクリプトで誤差の値を1秒ずつ変えて送ったら、誤差65秒で無事Flagゲット。