fr33f0r4ll

自分用雑記

Hackconに参加した

ctf

HackCon writeup

72位、一人じゃキツイなぁ。 Web問全然分からなかった。

rev

Key-gen1

match_meという実行ファイルが渡されるので、リバーシング。 見てみると最後の方にstrncmpしてるところがあるので、gdbで実行しつつ入力によって引数がどのように変化するか観察した。 しばらくやってると、2文字の入力が1文字にマッピングされているようであると分かった。 その上、位置に関係なく同じ2文字は同じ1文字に変換されるようなので、必要な文字に変換される組合せを見つければいい。 しかも、f以上の文字は使えないことが分かった(実際は16進数として解釈されているらしいことに後で気付いた)。 対応する文字に変換される組合せを探して、サーバに入力するとフラグが返された。

Key-gen2

match_meに受理される10個のキーを探す問題。 16進数に解釈されることに気付いたので、6組の異なる変換テーブルを作り、適当に組合せた。 これで通った。

crypto

RSA-2

今度はn, e, cだけが渡される。 eの値が異常に大きく、wiener-attackが出来そう。 求めたdで正常に復号化できた。

(ql:quickload :hackrsa)
;; hackrsa is in my tool set, https://github.com/4hiziri/tktools

(setf d (hackrsa:wiener-attack n e))
(setf m (mod-expt c d n))
(hackrsa:decode m)

Bacche

Rotate it

crypto
“q4ex{ju0_tvir$_pn3fne_va_PGS???}p0qr"が渡されるので、ぱっと見でrot13だと分かる。 flag形式が"d4rk{xxx}c0de"なので、鍵は13で良さそう。 単純にnkfでrot13してフラグゲット。

# echo "q4ex{ju0_tvir$_pn3fne_va_PGS???}p0qr" | nkf -r

ALL CAPS

crypto

“OF EKBHMGUKZHJB, Z LWALMOMWMOGF EOHJTK OL Z DTMJGX GY TFEGXOFU AB NJOEJ WFOML GY HSZOFMTVM ZKT KTHSZETX NOMJ EOHJTKMTVM, ZEEGKXOFU MG Z YOVTX LBLMTD; MJT "WFOML” DZB AT LOFUST STMMTKL (MJT DGLM EGDDGF), HZOKL GY STMMTKL, MKOHSTML GY STMMTKL, DOVMWKTL GY MJT ZAGRT, ZFX LG YGKMJ. MJT KTETORTK XTEOHJTKL MJT MTVM AB HTKYGKDOFU MJT OFRTKLT LWALMOMWMOGF. MJZFQL YGK KTZXOFU MJZM, JTKT'L BGWK YSZU: X4KQ{MKB_YZEEJ3_OYMJOL_MGG_LODHTS}E0XT"

渡された文章、フラグ形式っぽいものもあり、一文字だけのZが複数回出てたり、記号はそのままだったりすることから単一換字式暗号かと思った。 とりあえず、フラグ形式のところは確定できるので確定させる。

“OF crBHMGUrZHJB, Z LWALMOMWMOGF cOHJer OL Z DeMJGd GY eFcGdOFU AB NJOcJ WFOML GY HSZOFMeVM Zre reHSZced NOMJ cOHJerMeVM, ZccGrdOFU MG Z YOVed LBLMeD; MJe "WFOML” DZB Ae LOFUSe SeMMerL (MJe DGLM cGDDGF), HZOrL GY SeMMerL, MrOHSeML GY SeMMerL, DOVMWreL GY MJe ZAGRe, ZFd LG YGrMJ. MJe receORer decOHJerL MJe MeVM AB HerYGrDOFU MJe OFRerLe LWALMOMWMOGF. MJZFkL YGr reZdOFU MJZM, Jere\‘L BGWr YSZU: d4rk{MrB_YZccJ3_OYMJOL_MGG_LODHeS}c0de"

そうするとZreだったりJereだったり英単語が類推できる箇所だったりが出てくるので、それを埋めていく作業を繰り返す。 文字の出現頻度でやってもいいが、あまり参考にならなかった。 pythonでdict使って変換テーブルを作って、逐一復号しながら解いた。 復号すると、暗号学における単一換字式暗号の説明みたいな文章とフラグがでてくる。

high bass

crypto

“VGhpcyB3YXMgaW4gYmFzZS02NDogZDRya3t0aGF0XyRpbXBsXzNuMHVnaDRfVX1jMGRl"が渡される。 よく分からなかったのでBase64したら解けた。 印字可能で空白がないなら取り敢えず試す。

flag.txt

web

URLが渡されるので行ってみると、リンクが一つだけあった。 踏んでみるとロボットが人間をどうたらみたいな外部のサイトに飛ばされた。 外部サイトにフラグはもちろん無いので戻る。 リンク先にロボットの話題が出てたので、robots.txtを開いてみる。 ハッシュ値みたいな名前のディレクトリがDisallowになっていた。 問題のタイトルがflag.txtだったので、そのディレクトリ直下のflag.txtにアクセスしたらflagがでてきた。

one

なんだろう、rev?

バイナリファイルを渡されたのでfileで形式を調査する。 elf形式の実行ファイルなので、とりあえず実行する(アブナイ)。 フラグが出力された。

cave

crypto

象形文字みたいなものの画像が渡される。 名前が思い出せなかったが、これはヒエログリフである。 ヒエログリフタイピング的なサイトが見つかり、おそらくそのサイトで生成したであろう問題であることが分かった。 とりあえず復号するとflag_isなんたらかんたらみたいになるので、flag_isのあとをフラグの形式にして提出すると通った。

needle

foren

zip形式のファイルを渡され、解凍するとクソ長いテキストファイルが出てくる。 フラグ形式でgrepしたら該当する部分があったので、提出して終了。

RAS-1

crypto
RSAに関する暗号問題。 p, q, c, eが渡されるので、普通に復号するだけでいい。 ed = 1 mod (p - 1)(q - 1)となるdを求めて、cd mod pqを計算すると平文mが得られる。 ed = 1 mod (p - 1)(q - 1)は拡張ユークリッドの互除法で求められる。 ed + k(p-1)(q-1) = 1となるk, dを求めればいい。この式のmodを取れば元の式になることが分かる。

(setf p 152571978722786084351886931023496370376798999987339944199021200531651275691099103449347349897964635706112525455731825020638894818859922778593149300143162720366876072994268633705232631614015865065113917174134807989294330527442191261958994565247945255072784239755770729665527959042883079517088277506164871850439)

(setf  q 147521976719041268733467288485176351894757998182920217874425681969830447338980333917821370916051260709883910633752027981630326988193070984505456700948150616796672915601007075205372397177359025857236701866904448906965019938049507857761886750656621746762474747080300831166523844026738913325930146507823506104359)

(setf c 8511718779884002348933302329129034304748857434273552143349006561412761982574325566387289878631104742338583716487885551483795770878333568637517519439482152832740954108568568151340772337201643636336669393323584931481091714361927928549187423697803637825181374486997812604036706926194198296656150267412049091252088273904913718189248082391969963422192111264078757219427099935562601838047817410081362261577538573299114227343694888309834727224639741066786960337752762092049561527128427933146887521537659100047835461395832978920369260824158334744269055059394177455075510916989043073375102773439498560915413630238758363023648)

(setf  e 65537)

(defun extend-gcd (a b)
  "return (x . y) | ax + by = 1"
  (flet ((next-val (x1 x2 q)
       (- x1 (* x2 q))))
    (loop for q = (/ (- a (mod a b)) b) then (/ (- z1 (mod z1 z2)) z2)
      for ztmp = (next-val a b q) then (next-val z1 z2 q)
      for z1 = a then z2
      for z2 = b then ztmp
      for xtmp = (next-val 1 0 q) then (next-val x1 x2 q)
      for x1 = 1 then x2
      for x2 = 0 then xtmp
      for ytmp = (next-val 0 1 q) then (next-val y1 y2 q)
      for y1 = 0 then y2
      for y2 = 1 then ytmp
      when (= z2 1)
        do (if (< x2 0)
           (return (cons (+ x2 b) (- y2 a)))
           (return (cons x2 y2))))))

(defun mod-expt (base exp modulus)
  "more effective expotential and modulus.
calculate mod at every step of exp."
  (if (< exp 0) ;; if exp < 0, cannot calc mod so simply return base^exp
      (expt base exp)
      (loop for acc = 1 then (if (evenp e) acc (mod (* acc b) modulus))
        for b = (mod base modulus) then (if (evenp e) (mod (expt b 2) modulus) b)
        for e = exp then (if (evenp e) (/ e 2) (1- e))
        when (= e 0)
          do (return acc))))

(defun decode (encoded-num)
  (labels ((inner-loop (num acc)
         (if (> num 0)
         (inner-loop (truncate num (expt 2 8)) (cons (mod num (expt 2 8)) acc))
         acc)))
    (inner-loop encoded-num nil)))

stego

standard stego

画像にデータを隠すpythonプログラムと画像ファイルが落ちてくるので、逆算する。 どうやら文字列をバイナリ表現に変換して、画像ファイルの先頭からRGBのいずれかの末尾に1bitずつセットしているようである。 なので、画像の先頭から対応するRGBの値の末尾のbitを取り出すプログラムを書いて、マーカービット列の間を取り出した。 あとは1byte単位で取り出して文字に戻すだけである。

from PIL import Image


def getLSB(target):
    binary = str(bin(target))
    return binary[-1]


def binToAscii(bin):
    ret = ''
    length = len(bin) // 8
    for i in range(length):
        binary = bin[i*8:i*8 + 8]
        ret += chr(int(binary, 2))

img = Image.open('Secret.png')
pixels = list(img.getdata())
mode = img.mode
ret = []
for i in range(10000):
    newPixel = list(pixels[i])
    ret.append(getLSB(newPixel[i % len(mode)]))
    
header, trailer = 2 * "11001100", 2 * "0101010100000000"
bin_str = ""
for b in ret:
    bin_str += b

tmp = bin_str[:bin_str.find(trailer)]
tmp = tmp.replace(header, '')

まとめ

全然分からんかった。