Hack.lu CTF 2015 - checkcheckcheck writeup

Hack.lu CTF 2015にscryptosで参加しました。

チームで1950pt入れて34位、
私は1問解いて150pt(+bonus)入れました。

バイナリ系が1問も解けなかったくせにcryptoを1問解くという、
思い出深いCTFになりました（白目）

解けた問題のwriteupを置いておきます(`･ω･´)

checkcheckcheck (crypto 150)

使えるコマンドは以下の4つ(Usageから抜粋)

• version - prints the version of the server. very useful for maintenance purposes and stuff.
• getflag - prints the flag. only available after password login in version 2.0 to make hacker attacks harder.
• login <password> - logs you in so you can use "getflag"
• quit - close the connection

試しにloginコマンドを叩いてみると

$ nc school.fluxfingers.net 1513
login test
Whoops, that didn't work out. You probably mistyped your password, so you should
 try again. In case you want to debug the problem, here's the difference between
 the correct hash and the hash of what you entered: 81caa44f6412

という応答が返ってくる。

公開されているソースを見ると、

p = SHA256(real_password + salt)

while true
    args = gets.split

    if args[0] == "login"
        p = p ^ SHA256(args[1] + salt)

        if p[0...6] == [0, 0, 0, 0, 0, 0]
            # login successful
        else
            # login failed
            print hex(p)
        end
    end
end

という感じになっており、ログインを試行する度にpが書き換わってしまう。
なので、ログインを何回か試行することでp[0...6]をすべて0にすることを目指す。

まず、pの初期状態を知る方法だが、これは1回目の入力と2回目の入力を同じにすることで求められる。

p_0 = SHA256(real_password + salt)
p_1 = p_0 ^ SHA256(input_1 + salt)
p_2 = p_1 ^ SHA256(input_1 + salt)
    = (p_0 ^ SHA256(input_1 + salt)) ^ SHA256(input_1 + salt)
    = p_0

また、出力されるp同士をxorすることで任意の文字列のハッシュを求めることも出来る。

p_1 = p_0 ^ SHA256(input_1 + salt)
p_2 = p_1 ^ SHA256(input_2 + salt)

p_1 ^ p_2 = p_1 ^ (p_1 ^ SHA256(input_2 + salt))
          = SHA256(input_2 + salt)

これを利用してハッシュを収集し、集めたハッシュh_0～h_n (h_n = SHA256(input_n + salt))に対して

x_0 * h_0 + x_1 * h_1 + x_2 * h_2 + ... + x_n * h_n == p_0  (+はxor)

が成り立つようなビットベクトルxを求め、xでビットが立っている部分のパスワードを使ってログインを試行すればいいことになる。

例:

解が x = [0, 1, 1, 0] の場合
x_0 * h_0 + x_1 * h_1 + x_2 * h_2 + x_3 * h_3 == p_0
        0 * h_0 + 1 * h_1 + 1 * h_2 + 0 * h_3 == p_0
                                    h_1 + h_2 == p_0
→h_1, h_2を求めたときのパスワードを投げればログインが成功する

今回はpが48bitなので、48元連立方程式を立て、sageに投げて解を求めた。
mod 2な連立方程式も解けちゃうsageすごい。

#coding:ascii-8bit
require "open3"
require_relative "../../pwnlib"

PasswordHash = "785e64baad24".to_i(16)
host = "school.fluxfingers.net"
port = 1513

def get_hash(tube, input)
    tube.send("login #{input}\n")
    s = tube.recv_until(/Login successful|entered: [0-9a-f]{12}/)
    if s =~ /Login successful/
        0
    else
        s.match(/entered: ([0-9a-f]{12})/).captures[0]
    end
end

def solve(list, answer)
    rank = 48
    matrix = list.map{|a| a.to_s(2).rjust(rank, "0").chars.map(&:to_i)}
    vector = answer.to_s(2).rjust(rank, "0").chars.map(&:to_i)

    open("solve.sage", "w"){|io|
        io.puts <<EOS
m = matrix(IntegerModRing(2), #{matrix.inspect}).transpose()
try:
    m.inverse()
except:
    print("No inverse")
    exit()
print(m.solve_right(vector(IntegerModRing(2), #{vector.inspect})))
EOS
    }
    result = Open3.capture2("sage solve.sage")[0]

    if result =~ /No inverse/
        return nil
    end
    eval(result.gsub("(","[").gsub(")","]"))
end

puts "[*] collect hash"
db = {}
PwnTube.open(host, port){|tube|
    tube.wait_time = 0

    prev_hash = get_hash(tube, "a").to_i(16)

    for c in 0x21...0x7e
        print "."
        hash = get_hash(tube, c.chr).to_i(16)
        db[c.chr] = prev_hash ^ hash
        prev_hash = hash
    end
    puts

    tube.send("quit\n")
}

db = db.to_a
key = nil

puts "[*] find solution"
while true
    print "."
    matrix = db.sample(48)
    result = solve(matrix.map{|a| a[1]}, PasswordHash)
    if result
        puts
        key = matrix.zip(result).select{|m, r| r == 1}.map{|m, r| m[0]}
        puts "solution: #{key.inspect}"
        break
    end
end

puts "[*] attack"
PwnTube.open(host, port){|tube|
    tube.wait_time = 0

    key.each{|c| puts get_hash(tube, c)}

    puts "[*] login successful"
    tube.interactive
}

[*] collect hash
[*] connected
.............................................................................................
[*] connection closed
[*] find solution
........
solution: ["3", "y", "(", "`", "<", "9", "m", "'", "S", "/", "E", "4", "2", "1", "{", "f", "|", "=", "z", "N", "7"]
[*] attack
[*] connected
aa098a9c9406
7997f1148f8d
4c604600f0ef
db4d0395f665
f275b2668457
048a95f3cfb6
ef35d8fb9b96
375576aa594b
283e34988340
b768816de9f4
28b9a132e60b
8857fb790491
3105d6648b0e
e5e2fedc5789
c3150564b8aa
818aaaf3ad0e
b69f47f17ab3
a51a2e27df1b
2276ceda771c
6959b15692bc
0
[*] login successful
[*] interactive mode

getflag
Okay, sure! Let me grab that flag for you.
flag{more_MATH_than_crypto_but_thats_n0t_a_CATegory}
quit
[*] end interactive mode
[*] connection closed

楽しい問題でした(*´ω`*)

FLAG:flag{more_MATH_than_crypto_but_thats_n0t_a_CATegory}