CSAW CTF rev300 writeup

希望があったので、rev300のWriteupを書きます。

結局、やっていることは

  1. 256バイト以下の文字列をrecvする。
  2. recvした文字列に対してハッシュ関数を使ってハッシュを計算する。
  3. 計算したハッシュ値と、期待しているハッシュ値を比較する。

という感じで、単純なパスワード比較系の問題だと思っていいと思います(読むだけ)。

 

問題は2のハッシュ関数です(かなり意訳してますが)。

unsigned int hash(char *input) {
    int value = 0x539;

    for (int i=0;i<strlen(input);i++) {
        value += (value << 5) + input[i];
    }

    return value;
}

この関数の戻り値が0x0EF2E3558となるようにしなければなりません。

 

まず、value << 5というのは、value * 32と同値です。

従って、

  value += (value << 5) + input[i]

⇔ value = value * (32 + 1) + input[i]

と言えます。

 つまり、このvalueを33進法として見る事ができます。

要は、inputの長さをnとすれば、

value = input[0] * (33 ** n-1)

          + input[1] * (33 ** n-2)

          + input[2] * (33 ** n-3)

          +             ・

                         ・

          + input[n-1] * (33 ** 0)

と表すことが出来ます。

 

次に、valueはunsigned int型なので、0xffffffffを超えた時のオーバーフローを考えます。

しかし、オーバーフローは0x100000000の剰余を取ることと同じ意味を持つので、

演算を0x100000000を法として考えればいいということになります。

この時、行われる計算は全て閉じているので、

(計算のたびに剰余を取った値) ⇔ (最終的な値に対して剰余取った値)

が言えます。

 

これらより、

value ≡ 0x0EF2E3558 (mod 0x100000000)を33進数とした時の桁の列

を求めてやればいいのです。

 

ここで制約として重要なのは、valueの各位の桁に0が含まれてはならないことです。

0が含まれていた場合、strlenによってそれより後の桁の計算が行われません。

従って、全ての桁が0にならないようにこの桁の列を求めます。

 

求めるvalueの上位3桁は[1, 7, 17]で固定です [∵ valueを0x539で初期化]。

従って、予め求めるvalueの桁数をnとし、0x100000000を法として

0x0EF2E3558 - (33 ** n-1) - 7 * (33 ** n-2) - 17 * (33 ** n-3)

と合同になるような数tを見つけます(ただし、n-3桁の内に0を含まない)。

 

書いたスクリプト

 mod = 0x100000000

def convert(x, digit):
    l = []
    while x >= 33:
        t = divmod(x, 33)
        l.append(t[1])
        x = t[0]

    l.append(x)
    return [0] * (digit - len(l)) + l[::-1]

def calc(digit):
    p = 0x0EF2E3558 -  0x539 * pow(33, digit, mod)

    while p < 0:
        p += mod

    while True:
        l = convert(p, digit)
        if len(l) > digit:
            return None
        if not 0 in l:
            return l
        p += mod

def check(l):
    value = 0x539;
    for i in l:
        value += (((value << 5) + i)%mod)
    return value%mod;

def main():
    for i in range(4, 256):
        ret = calc(i)
        if ret:
            print ret
            print hex(check(ret))
            return

if __name__ == "__main__":
    main()

 

実行すると、[3, 15, 20, 13, 16, 27, 1]が得られるので、こいつをcharに直して、送ってやればFLAGが得られます。

f:id:potetisensei:20130929002857p:plain

 

 

(注釈)検証用にバイナリをローカルで実行できればよかったんですが、アカウントのセッティングがめんどくさかったのでしません。