ログイン
編集不可のページディスカッション情報添付ファイル

2014-12-07 18:58:50時点のリビジョン2

メッセージを消す
CTF/Writeup/SECCON 2014 Quals Online Winter

MMA

Writeups for tkbctf4

SECCON 2014 Quals Online WinterにチームMMAとして参加した。最終順位は11位であった。

Easy Cipher (Crypto 100pts)

2進数、8進数、10進数、16進数で記述された数字の列が渡される。判定は次のようにした。

  • 0から始まる文字列なら8進数
  • [01]のみを含み5文字以上なら2進数
  • [0-9]のみを含むなら10進数
  • それ以外なら16進数

後は出来た数値の列を文字として表示すれば解が得られる。

irb> a =  %W(87 101 108 1100011 0157 6d 0145 040 116 0157 100000 0164 104 1100101 32 0123 69 67 0103 1001111 1001110 040 062 060 49 064 100000 0157 110 6c 0151 1101110 101 040 0103 1010100 70 101110 0124 1101000 101 100000 1010011 1000101 67 0103 4f 4e 100000 105 1110011 040 116 1101000 0145 040 1100010 0151 103 103 0145 1110011 0164 100000 1101000 0141 99 6b 1100101 0162 32 0143 111 1101110 1110100 101 0163 0164 040 0151 0156 040 74 0141 1110000 1100001 0156 056 4f 0157 0160 115 44 040 0171 1101111 117 100000 1110111 0141 0156 1110100 32 0164 6f 32 6b 1101110 1101111 1110111 100000 0164 1101000 0145 040 0146 6c 97 1100111 2c 100000 0144 111 110 100111 116 100000 1111001 6f 117 63 0110 1100101 0162 0145 100000 1111001 111 117 100000 97 114 0145 46 1010011 0105 0103 67 79 1001110 123 87 110011 110001 67 110000 1001101 32 55 060 100000 110111 0110 110011 32 53 51 0103 0103 060 0116 040 5a 0117 73 0101 7d 1001000 0141 1110110 1100101 100000 102 0165 0156 33 )
irb> a.map{|a|a.start_with?('0') ? a.to_i(8) : (/^[0-1]+$/ =~ a && a.size >= 5? a.to_i(2) : (/^\d+$/=~a ? a.to_i(10) : a.to_i(16)))}.map(&:chr).join
=> "Welcome to the SECCON 2014 online CTF.The SECCON is the biggest hacker contest in Japan.Oops, you want to know the flag, don't you?Here you are.SECCON{W31C0M 70 7H3 53CC0N ZOIA}Have fun!"

Ms.Fortune? Misfortune. : 4096-bit RSA (Crypto 400pts)

与えられたファイルを展開してみて中身を調べてみた。

  • key.pub.gpg

    • GPGでのRSA暗号化に用いる公開鍵
  • encrypted.gpg

    • GPGによってRSAで暗号化されたデータ
  • key.gpg.masked

    • GPGのRSAの秘密鍵のテンプレート
  • recover.py

    • p, qを入力するとRSA秘密鍵を生成するプログラム

pgpdumpをインストールし、gpgの公開鍵の内容を見てみた。

$ pgpdump key.pup.gpg
Old: Secret Key Packet(tag 5)(1816 bytes)
(中略)
Old: User ID Packet(tag 13)(31 bytes)
        User ID - SECCON ____Key <____key@seccon>
Old: Signature Packet(tag 2)(555 bytes)
        Ver 4 - new
        Sig type - Positive certification of a User ID and Public Key packet(0x13).
        Pub alg - RSA Encrypt or Sign(pub 1)
        Hash alg - SHA1(hash 2)
        Hashed Sub: signature creation time(sub 2)(4 bytes)
                Time - Fri Jan  2 09:00:00 JST 1970
        Hashed Sub: key flags(sub 27)(1 bytes)
                Flag - This key may be used to certify other keys
                Flag - This key may be used to sign data
(中略)
Old: Secret Subkey Packet(tag 7)(1816 bytes)
(中略)
Old: Signature Packet(tag 2)(543 bytes)
        Ver 4 - new
        Sig type - Subkey Binding Signature(0x18).
        Pub alg - RSA Encrypt or Sign(pub 1)
        Hash alg - SHA1(hash 2)
        Hashed Sub: signature creation time(sub 2)(4 bytes)
                Time - Fri Jan  2 09:00:00 JST 1970
        Hashed Sub: key flags(sub 27)(1 bytes)
                Flag - This key may be used to encrypt communications
                Flag - This key may be used to encrypt storage
(省略)

Flagの内容からSecret Subkey Packetが暗号化に用いる鍵だと分かるらしい。(ytokuさんに教えてもらった)

pgpdumpの引数として-iを渡すとnの具体的な値が取れる。 このnについて、各種素因数分解アルゴリズムを適用した所、Fermat法によって素因数分解に成功した。

   1 require 'gmp'
   2 n = GMP::Z(ARGV[0].to_i)
   3 x = n.sqrt + 1
   4 y = (x * x - n).sqrt
   5 while true
   6   w = x * x - n - y * y
   7   break if w == 0
   8   if w > 0
   9     y += 1
  10   else
  11     x += 1
  12   end
  13 end
  14 p [x+y,x-y,n]

$ ruby fermat.rb (cat n)
32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261446073, 32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261414507, 1034186074668005446865661651578208369514158803552244005581133348807218259696136975186768057532805396894757503164834709575083359161158060701923008831149233177215596305395749862300700772298386522636562203611668211601359078939366452933448401372783149865070405032946502692195960337152490393257718681775969357953766124434670452760182942622011519373645653657784274264774773270847089540432369489508909290697992927057404389218509541644042197448296417276686963995927414541514778710278820030649227976349765070908207584414253880096569270321293357683127769728901749940165024782079154839570419235490028108256539125090626571373643257455521820767805808214404175900736109428513289545954241551995058498737472560704736894014465695117165251699935296644992760434412206519036326801985540077086806228464411438175416317958133959586691011057808141234300883692932436022122663781160823472736298914304029803683697389880156222528045623045436226522780569221934366978973936408257173404970887883159180079205465195884955186605310665826226975454171035075016280417683011623124380312403051425940705920625660567584606796218038626946234225864706878239646554381165540673005572649955471689205027195933802181344480474070023069194083134722979170599617466579222550596280381011]

recover.pyに引数として素因数分解の結果を渡して、秘密鍵key.gpgを作成し、encrypt.gpgを解読した。

$ python recover.py 32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261414507 32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261446073

$ gpg --import key.gpg

$ gpg --decrypt encrypted.gpg 
gpg: 4096-ビットRSA鍵, ID 7DAD8D6C, 日付1970-01-02に暗号化されました
      “SECCON ____Key <____key@seccon>”
SECCON{g^2-f^2=(g+f)(g-f)~is~still~important~to~factor~BIG~numbers,.025f0ddfdc463a24bf0350c15b175eee}

Shuffle (Binary 100pts)

逆アセンブルを眺みてみると、0x0804854bから0x080486afにかけて文字列を生成しているのに気づいた。 gdbを用いて表示してみた。

$ gdb ./shuffle
(略)
(gdb) b *0x80486af
Breakpoint 1 at 0x80486af
(gdb) r
Starting program: ...

Breakpoint 1, 0x080486af in main ()
(gdb) x/s $esp + 0x24
0xffffd0e4:     "SECCON{Welcome to the SECCON 2014 CTF!}\b"
(gdb)