CSAW CTF rev300 writeup
希望があったので、rev300のWriteupを書きます。
結局、やっていることは
という感じで、単純なパスワード比較系の問題だと思っていいと思います(読むだけ)。
問題は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が得られます。
(注釈)検証用にバイナリをローカルで実行できればよかったんですが、アカウントのセッティングがめんどくさかったのでしません。