cookies.txt      .scr

ただのテキストファイルのようだ

Harekaze mini CTF 2020 WASM BF writeup

これはTSG Advent Calendar 8日目の記事ということにします。
adventar.org

とりあえず11月中にAdvent Calendarへ登録をするだけして、11月12月に大量に開催されるCTFで何らかの非自明な問題でも解いたらwriteupを書いて埋めるかーと思っていたのですが、それほど非自明な問題は解けないわAdvent Calendarを書く気が出ないわでこのまま踏み倒そうかと思っていたところ、ちょうど手頃に解説しやすく、解説しがいがあり、いい感じにインスタ映えのしそうな問題があったものですから、もう年始に向けてカウントダウンを始めても差し支えなさそうな12月29日に投稿しています。


12/26-27にHarekaze mini CTF 2020が開催されました。
github.com

mini CTFという名前にふさわしく、特別長時間悩みこむ問題という感じではなかったですが、しっかり面白い問題が揃っていて、面白かったです(面白い問題なので)*1
その中でWebジャンルのWASM BFという問題を解いたので、それのwriteupをしていこうと思います。方法の説明というよりは、問題を解くときの試行過程をそのままメモしています。

screenshot
WASM BF screenshot

*1:まあ、そこまで全体感想を言えるほど全問題を見たわけでもないんですが。

続きを読む

CTFZone 2019 Quals writeup - M394Dr1V3 cr4cKM3

TSGアドベントカレンダー 2019 3日目です。
adventar.org

こないだ11/30 18:00 JST - 12/2 06:00 JST、TSGでCTFZone 2019 Qualsに参加しました。
わりとみんなでまじめに参加して、結果はなんとか10位となりました。
アドベントカレンダー登録時の予定では、Web問あたりがいくつか解けて、ここでwriteupを書くはずだったんですが、かなりエスパー要素があるわ1問あたりの段階数がおおいやらで、全体的にいいところまでは進めても解ききれませんでした。悲しいね。全体的にこれ〇〇〇CONか?

初心に戻って唯一解けたRevering: M394Dr1V3 cr4cKM3のwriteupを書きます。

続きを読む

高速整数乗算アルゴリズムSchönhage Strassen Algorithmを雑に実装した話

そういえばIS Advent Calendarに投稿しようと思ってずっと放置していたのがあったのに、登録するのを忘れていたことを思い出したので、雑に供養します。


だいぶ昔の話なんですが、大学の演習IIIとかいう授業で、なんかSchönhage Strassen Algorithmというのを実装したくなったので実装させてもらいました。

当時のスライドから面白くないものを削除したスライドです。それなりにイメージは伝わると思っています。

www.slideshare.net

実装は公開しています。見るに堪えないかもわかりませんが。
github.com


Schönhage Strassen Algorithmは、整数乗算アルゴリズムで、まあもちろん速いわけなんですが、速いと言っても定数倍がかなり重くて日常的な乗算にはむしろ不利なやつです。
日本語WikipediaにはGMPでは「10進法で33 000 - 150 000桁の大きさ」でSSAを初めて用いるようになるとあります。
ソースに当たると、MUL_FFT_THRESHOLDというのが関係してくるらしくって、その値はx86_64で11520らしいんですが、limbってなんだかわからないしこれがなんなのかはわかりません。


実装するときは、スライドにもありますが、「Multiplying large numbers and the Schönhage-Strassen Algorithm - Theo Kortekaas」とか参考にするといいです。オンラインで見つかるPDFです。
今終わってみるとGMP manualとかも参考になったのかもしれないと思いますが、当時は見つけられなかったのでしかたない。


今回の実装では、スライドのpage 22を見ると、10^6 bit同士の乗算あたりからKaratsuba法を上回ったようです。
まあ圧倒的にGMPには劣るわけですが(スライドpage 23)。


そんなちゃんと実装したわけじゃないので、同じbit数同士の乗算しかできなかったり(当然0埋めすれば違ってもできるが、計算量的に劣る)、詳しくは書きませんが計算途中に特別な条件を満たすと続行不可能になってエラー返したりします*1

以上、供養でした。

*1:参考PDFでも触れられているのと、「続行不可能」でスライド検索すればなんとなく分かります。

min-caml compiler pwn (ISer advent calendar 12/2出題)writeup

この記事はISer Advent Calendar 2018 16日目の記事です。
adventar.org

昨日はMisterプロによる「簡潔ビットベクトル(完備辞書)」でした。
misteer.hatenablog.com

17erのこおしいずです。CPU実験は1年前です。
アドベントカレンダー2日目の記事に、moratoriumプロによる「min-camlのプログラムからシェルが取れるか?」というのがあって、そこでpwn問題が出されていました。
もう2週間経ちますので、writeupをやっていこうと思います。
とはいえ、出題者からはもっと良質な想定解が提示される予定なので、12/23のアドベントカレンダー記事も読みましょう。
moraprogramming.hateblo.jp

問題概要

ISのCPU実験でのコンパイラ開発のベースとして使われる、min-camlというOCaml subsetコンパイラがあるのですが、この問題では、min-camlソースコードを与えると、そのコンパイラ(に制限を加えたもの)でコンパイルした結果を実行してくれるので、シェルをとれという問題です。
CTFでコンパイラへの入力を与えるタイプはあんまり見ない気がしますが、OCamlはめっちゃ型つける系だし、今回glibcも外されて*1、自明ではない、ということです。

コンパイラはなぜかArrayのPUT構文を潰されています。ふむ。

*1:ゆーてこれヒントかもしれない、外す理由あんまりなくないですか?

続きを読む

hxpctf2018 writeup blind

なかなか好きな問題でした。

問題

#!/usr/bin/env python3
import os, random
from Crypto.Cipher import AES

aes = AES.new(os.urandom(16), AES.MODE_ECB)
enc = lambda x: aes.encrypt(x.to_bytes(16, 'big')).hex()
dec = lambda y: int.from_bytes(aes.decrypt(bytes.fromhex(y)), 'big')

p = 0xfffffed83c17          # |G| = p
mul = lambda x, y: (x+y)%p  # g^x * g^y = g^(x+y)
inv = lambda x: (-x)%p      # (g^x)^-1  = g^(-x)
dhp = lambda x, y: x*y%p    # enjoy your oracle!

g = 1
y = random.randrange(p)
print(y, file=__import__('sys').stderr)

print(enc(g), enc(y))

for _ in range(0x400):
    try:
        q = input().strip().split()
    except EOFError: break
    if q[0] == 'mul':
        print(enc(mul(*map(dec, q[1:]))))
    if q[0] == 'inv':
        print(enc(inv(dec(q[1]))))
    if q[0] == 'dhp':
        print(enc(dhp(*map(dec, q[1:]))))
    if q[0] == 'sol':
        if int(q[1]) % p == y:
            print(open('flag.txt').read().strip())
        break

固定値pをmodとした世界で、コネクションごとに乱数yが生成されます。
g=1と乱数yを暗号化した結果を接続時に与えられます。
暗号化は、AESで毎回keyはrandomにgenerateされますが、ECBです。
oracleとして、暗号化された数値を送ると、mul: x + y, inv: -x, dhp: x * yの暗号文を得ることができます。
0x400 == 1024クエリ以内に、yがいくらであったのかをexactに求めてください。

考察

今回の回答は、1/18未満の確率でうまくいくものです。(クエリ回数超過の可能性と、最後の解答が17/18で間違う可能性)

まず、今回のAES暗号化は、ECBなので(じゃなくてもか?)同じメッセージに対する暗号文は不変です。
ですから、xに対していろいろと操作をして、またxにもどったかどうかを判定することができます。

mul: x+yと、inv: -xは正直ほとんど役に立てられません。pは素数なので、足し算や反数をとってもだいたい対称な操作で、求めることにあまり意味を感じられません。
せいぜいyにひたすらg=1を足していって、g=1と等しくなったかで判明するくらいでしょうか。
dhpを繰り返し行うことで、x^nを求めることができます。nはこちらで自由に設定できる数字です。バイナリ法により、2 \lg nの回数程度で求めることができます。

|Z_p^*| = p-1 = 2 \cdot 3^2 \cdot 7 \cdot 13^4 \cdot 47 \cdot 103 \cdot 107 \cdot 151であり、こちらの世界では値ごとに特徴が十分見いだせます。
まず、Z_p^*の生成元を g=5(いままでg=1として使っていましたが、以降ではg=5として使います。生成元にg以外を使うのは考えられません。)として、各数値の指数(i.e.  i = \log_g x)を考えます。
yの(gでの)指数をiとしたとき、i(p-1) \mod (p-1) = 0は当然なのですが、i \frac {p-1} 2 \mod (p-1)が0か否かによって、iの偶数性が分かります。
これらは、それぞれ、y^{p-1} = 1 \mod pが常に成立することと、y^{\frac {p-1} 2} \mod pが1かどうか確かめることに相当します。
これでは0か否か、しか求められないので、modをちゃんと求めるには、指数をdecrementして0かどうか確かめる...ということを繰り返す必要があります。
つまり、i \mod 151を求めるには、g^{i \frac {p-1} {151}} = g^{(151k+n) \frac {p-1} {151}} = y^{\frac {p-1} {151}} \mod pを確認し、1でなければg^{(151k+n-1) \frac {p-1} {151}} = y^{\frac {p-1} {151}} {(g^{-1})}^{\frac {p-1} {151}} \mod pを確認し...とつづけることになります。

m = 151, 107, 103, 47, 7それぞれについて、指数のmodを確認するために、{(g^{-1})}^{\frac {p-1} m}と、y^{\frac {p-1} m}を計算する必要があり、あわせて2 * 2lg((p-1)/m) < 2*2 lg p < 184回クエリ、それから、mod pが1でない間、掛け算を繰り返す必要があり、最大でm回のクエリが必要となります。
m = 13, 13^2, 13^3, 13^4については、m=13^4に対して {(g^{-1})}^{\frac {p-1} m}y^{\frac {p-1} m}を計算したら、それを13乗してm=13^3のもの、また13乗してm=13^2、次にm=13のものを得ることができます。
そしてi \mod 13を計算できたら、i \mod 13^2は13通り、それもわかったらi \mod 13^3も13通りなので、4 \cdot 13程度のクエリでがんばれます。


とまあこの雑なクエリ回数見積もりを合計すると、1500を超えるんですが、まあ大きめに見積もったからね、しょうがないね。(ほんまか)
一応姑息な感じに多少のクエリ回数ゴルフをして、あとは運任せです。

ここまででyの指数iについて i \mod (7 \cdot 13^4 \cdot 47 \cdot 103 \cdot 107 \cdot 151)が判明した(∵中国人剰余定理)ので、確率は \frac 1 {2 \cdot 3^2} = \frac 1 {18}というわけです。
最後にg ^ iを雑に投げます。当たると嬉しいです。

回答

攻撃コードです。もうちょっときれいにならなかったのか。中国人剰余定理のためにgpを呼び出しています。

require 'socket'

def pow(x, y, m)
  r = 1
  while y > 0
    r *= x if y.odd?
    x *= x
    y >>= 1
    r %= m
    x %= m
  end
  r
end

class S < TCPSocket
  attr_reader :g, :y, :ctr

  def initialize
    #super '78.46.149.10', 13373
    super 'localhost', 4567
    @ctr = 0
    @g, @y = gets.split
  end

  def add x, y
    @ctr += 1
    puts 'mul %s %s' % [x, y]
    gets.chomp
  end
  def inv x
    @ctr += 1
    puts 'inv %s' % x
    gets.chomp
  end
  def mul x, y
    @ctr += 1
    puts 'dhp %s %s' % [x, y]
    gets.chomp
  end
  def sol x
    @ctr += 1
    puts 'sol %d' % x
  end
  def pow x, y
    res = @g
    loop do
      res = mul(res, x) if y.odd?
      y >>= 1
      break if y == 0
      x = mul(x, x)
    end
    res
  end
end

s = S.new

P = 0xfffffed83c17
PHI = P-1
# 2,3,3,7,13,13,13,13,47,103,107,151

G, Y = s.g, s.y
ONE = G
TWO = s.add(ONE, ONE)
FOUR= s.add(TWO, TWO)
FIVE= s.add(FOUR, ONE)
GEN = FIVE # 5
IGEN= s.pow(GEN, PHI-1)

puts 'p: %d' % P
puts 'one: %s' % G
puts 'y: %s' % Y

gpq = ['a = Mod(0, 1)']
factors = [7, 47, 103, 107, 151]
memo = s.pow(IGEN, 2*3*3)
memoy= s.pow(Y, 2*3*3)
factors.each do |f|
  seed = s.pow(memo, PHI/(2*3*3*f))
  now = s.pow(memoy, PHI/(2*3*3*f))
  idx = f.times.find do |t|
    next true if now == ONE
    now = s.mul(now, seed)
    false
  end
  mod = idx
  puts 'idx mod %d == %d' % [f, mod]
  gpq << 'a = chinese(a, Mod(%d, %d))' % [mod, f]
  puts 'ctr: %d' % s.ctr
end

begin
  f = 13
  ig4= s.pow(memo, PHI/(2*3*3*f**4))
  ig3= s.pow(ig4, f)
  ig2= s.pow(ig3, f)
  ig1= s.pow(ig2, f)

  n4 = s.pow(memoy, PHI/(2*3*3*f**4))
  n3 = s.pow(n4, f)
  n2 = s.pow(n3, f)
  n1 = s.pow(n2, f)

  idx = f.times.find do |t|
    next true if n1 == ONE
    n1 = s.mul(n1, ig1)
    false
  end
  m1 = idx
  puts 'm1: %d' % m1

  n2 = s.mul(n2, s.pow(ig2, m1))
  idx = f.times.find do |t|
    next true if n2 == ONE
    n2 = s.mul(n2, ig1)
    false
  end
  m2 = idx
  puts 'm2: %d' % m2

  n3 = s.mul(n3, s.pow(ig3, m1))
  n3 = s.mul(n3, s.pow(ig2, m2))
  idx = f.times.find do |t|
    next true if n3 == ONE
    n3 = s.mul(n3, ig1)
    false
  end
  m3 = idx
  puts 'm3: %d' % m3

  n4 = s.mul(n4, s.pow(ig4, m1))
  n4 = s.mul(n4, s.pow(ig3, m2))
  n4 = s.mul(n4, s.pow(ig2, m3))
  idx = f.times.find do |t|
    next true if n4 == ONE
    n4 = s.mul(n4, ig1)
    false
  end
  m4 = idx
  puts 'm4: %d' % m4
  gpq << 'a = chinese(a, Mod(%d, %d))' % [[m4,m3,m2,m1].inject(0){|s,x|s*13+x}, f**4]

  puts 'ctr: %d' % s.ctr
end

gpq << 'print(a)'
mod = nil
IO.popen("gp -q", "r+") do |gpio|
  gpio.puts gpq.join("\n")
  gpio.close_write
  mod = gpio.read.lines[-1]
end
a, b = mod.scan(/Mod\((\d+), (\d+)\)/)[0].map(&:to_i)
puts 'Mod(%d, %d)' % [a, b]

s.sol pow(5, a, P)

puts s.read