about 9 years ago

Olympic CTF 2014 Figure Crypting 300 GuessGame Writeup

亂試了一陣，觀察並猜測的結論如下

  1. 第一次 mix 的兩個數字，第一個當 1，第二個當 g (base)
  2. mix 是模某個質數 P 下的乘法
  3. 題目問 how much A in B，意思是求出 x 使 A^x = B
  4. inv x = x^(-1)

所以這是一個離散對數問題，題目的數字範圍卡得很緊 (它其實會故意生成最差的情況)，所以要小心處理。
限制 mix + guess 總共 251 次，inv 不計次數，我們可以用 Pollard's rho algorithm，最差情況下花 O(sqrt(P)) 步解出。

sha1prefix.cpp 
#include <bits/stdc++.h>
#include <openssl/sha.h> // man 3 sha1

// g++ sha1prefix.cpp -o sha1prefix -Ofast -lcrypto
// ./sha1prefix bedca4b89c129c89

int main(int argc, char *argv[]) {
    int n = strlen(argv[1]) / 2, x;
    unsigned char s[64] = {}, h[64];
    for (int i = 0; i < n; i++) {
        sscanf(argv[1] + 2*i, "%2x", &x);
        s[i] = x;
    }
    while (true) {
        for (int i = n; ++s[i] == 0; i++);
        SHA1(s, n + 4, h);
        if (!h[0] && !h[1] && !h[2]) break;
    }
    for (int i = 0; i < n + 4; i++) printf("%02x", s[i]);
    puts("");
}
guess.rb 
#!/usr/bin/env ruby


require 'socket'

$sock = TCPSocket.new('109.233.61.11', 3126)

def send(s)
  puts s
  $sock.puts s
  res = $sock.gets
  puts res
  res.split.first
end

def mix(x, y)
  send "mix #{x} #{y}"
end

def inv(x)
  send "inv #{x}"
end

def guess(x)
  send "guess #{x}"
end

lines = 4.times.map { $sock.gets }
puts lines

prefix = lines[1].split.last
s = `./sha1prefix #{prefix}`
puts s
$sock.puts s

lines = 5.times.map { $sock.gets }
puts lines
a, b = lines[1].scan(/'(.*?)'/).flatten

inv('one')

Q = 120 # Q + P / (2Q) <= 251

pow_of_a = {
  0 => 'one',
  +1 => a,
  -1 => inv(a)
}

(2..Q).each do |i|
  pow_of_a[+i] = mix(a, pow_of_a[i-1])
  pow_of_a[-i] = inv(pow_of_a[i])
end

step = mix(pow_of_a[-Q], pow_of_a[-Q]) # a ^ (-2Q)

k = 0
now = b
until pow_of_a.has_value?(now) do
  now = mix(now, step)
  k += 1
end

t = pow_of_a.rassoc(now).first
guess(t + k * 2 * Q) # b * a^(k * -2Q) = a^t
← Olympic CTF 2014 Figure Crypting 200 mic Writeup Olympic CTF 2014 Nopsleigh 300 Echof Writeup →