10月19日19:00 -- 20日19:00(JST) に開催された, hack.lu CTF 2016にm1z0r3として参加していました.

結果は62位. 獲得素点は750点で, ボーナスポイントが-156点の計594点となっています. ボーナスポイントについてはややこしいので, 以降の得点表記はすべて素点となります.

個人的にはcryptoの200点問題を2つ解き, もう1つの200点問題の方針だけ考えて実装はチームメイトに投げました.

以下writeupです.


cornelius1 (crypto:200pt)

構成としてはシンプルで, userとして渡した値とflagをjsonとして圧縮・暗号化し, base64エンコードを施したものがcookieに入る. 簡単に書くと以下の感じ.

 auth = Base64(encrypt(deflate([input_value,flag:flag_value])))

暗号化処理は, rubyのデフォルト機能で実装していることや, 乱数をkeyやivに使っていることからも安全そう. というわけで平文の生成方法に注目する.

ここでは, 入力値とflagをjsonとした後, deflate圧縮により圧縮を施している. これを見ると明らかにCRIME攻撃ができることがわかる. ここでCRIMEの詳細な説明は省くが, 要約するとこんな感じ.

  • AESのCTRモードにおいて, 平文と暗号文の長さは変わらない
  • deflate圧縮は, 繰り返し出現する文字列があると圧縮をする
  • この特徴を利用し, 総当たりで同じ文字列を複数回送ったとき, 一番短い暗号文が返ってくるものが正解となる.
  • 本番ではCRIMEをするところまで考え実装はチームメイトに投げたものの, その後書いたsolverがこちら. (終了条件を書いていないのでちょうどいいところで手動ストップ)

    #!/usr/bin/python
    # -*- coding: utf-8 -*-
    import socket
    import struct
    import binascii
    import sys
    import requests
    import base64
    import string
    
    # settings
    url = "https://cthulhu.fluxfingers.net:1505/?user="
    
    def brute(key):
      tmplen = 0
      for c in string.printable:
          u = url + (key+c)*10
          r = requests.get(u).cookies['auth'].decode('base64')
          l = len(r)
          print "[+] senddata = " + u
          print "[+] len  = " + str(l)
          if tmplen>l:
            return key+c
          tmplen = l
      return 0
    
    nowans = 'flag:'
    while nowans!= 0:
      nowans = brute(nowans)
      print nowans

    katagaitai勉強会のおかげで解けました(圧倒的感謝)

    flag:Mu7aichede


    redacted (crypto:200pt)

    一部が壊れたPEM形式のRSA秘密鍵が渡され, それを修復してssh接続をする問題.

    base64形式では読めないのでデコードした上で16進ダンプした上で残っている値を取り出していく.

    $ xxd <(cat redacted_6175ab865421ca2c83b7c77d7ee521f3 | awk /^[^-]/{print} | base64 -D)
    0000000: c71c 71c7 1c71 c71c 71c7 1c71 c71c 71c7  ..q..q..q..q..q.
    0000010: 1c71 c71c 71c7 1c71 c71c 71ff 4a9c d78e  .q..q..q..q.J...
    0000020: 945d 76f1 c71c 71c7 1c71 c71c 71c5 67bd  .]v...q..q..q.g.
    0000030: 011d 643b 3c71 c71c 71c7 1c71 c71c 71c7  ..d;<q..q..q..q.
    0000040: 1c71 c71c 71c4 c492 0b1c 71c7 1c71 c71c  .q..q.....q..q..
    0000050: 71c7 1c71 c7c7 02a2 f21c 00e6 7114 4685  q..q........q.F.
    0000060: 7236 b5c3 1106 e4c1 d3ee 5bd7 c785 342a  r6........[...4*
    0000070: adb6 a7d1 76df 7edc b7ce 1d78 dfe9 9285  ....v.~....x....
    0000080: 7e1a 3473 0756 186c a4c2 00de c2a9 7f33  ~.4s.V.l.......3
    0000090: b36c 789f d7bb 5866 fbd6 8e83 d823 eae6  .lx...Xf.....#..
    00000a0: 4c9e 2d74 0f2f 09d0 383b 39d5 1aae b190  L.-t./..8;9.....
    00000b0: 858e 8a3b 6ad9 cbab 8d93 5aa1 bd01 d1cb  ...;j.....Z.....
    00000c0: ba23 8af4 df84 55d7 d789 c71e e609 1f71  .#....U........q
    00000d0: 1e76 6f63 3a04 20f5 30ad b704 9506 6070  .voc:. .0.....`p
    00000e0: a070 73fc b01d 21cc 2fd5 648d 9f54 75d7  .ps...!./.d..Tu.
    00000f0: 6969 7d3e 3258 6831 5ab8 e50e 7350 0f4c  ii}>2Xh1Z...sP.L
    0000100: 2d0b 8548 ce38 e013 3829 4e81 0203 0100  -..H.8..8)N.....
    0000110: 0102 8201 0030 5b82 3a4e 4f4d edfd cd3b  .....0[.:NOM...;
    0000120: 0055 d9ff 9494 66bb 68be 5870 1a78 1f91  .U....f.h.Xp.x..
    0000130: d7b2 9046 e947 b2de 99df 4b62 a77d 9605  ...F.G....Kb.}..
    0000140: 8f81 1a8f 3731 476a 1f35 4852 8039 38d5  ....71Gj.5HR.98.
    0000150: 7b1b 7592 9b15 56d2 c5eb 0de6 326e a93c  {.u...V.....2n.<
    0000160: da8e 267d 916e 9f9c fd85 5a01 81f4 ffd7  ..&}.n....Z.....
    0000170: 43b2 4a85 bf37 8bfb bcdf ab13 cea1 2a5b  C.J..7........*[
    0000180: 7ef4 9bf0 4b05 0b89 a31b 9700 6369 c45a  ~...K.......ci.Z
    0000190: e902 9291 e30f 789b 3fd3 dab4 cd3b 3b88  ......x.?....;;.
    00001a0: b748 90b3 57ee c0f0 0753 5b25 58c5 7604  .H..W....S[%X.v.
    00001b0: ade3 6522 c39c fe22 baba 4394 0747 8059  ..e"..."..C..G.Y
    00001c0: d630 747d 752d f521 f88f 44a0 fed2 88d9  .0t}u-.!..D.....
    00001d0: 8e25 4840 a259 b46d 451b b8e1 60f2 5946  .%H@.Y.mE...`.YF
    00001e0: 85ec 68ff 6cef 2dbb 5631 34f4 4deb 0e6d  ..h.l.-.V14.M..m
    00001f0: 467e 8ebf 9551 6d51 efa7 b10b bb0f 20a4  F~...QmQ...... .
    0000200: a6cd 9c52 599d 6706 3dc8 c07a 0a48 589c  ...RY.g.=..z.HX.
    0000210: f5ec 5a32 8102 8181 00e4 ddba 96c1 cbc4  ..Z2............
    0000220: f412 04ee 6fc1 6e14 8304 38ae ee4b bd21  ....o.n...8..K.!
    0000230: af5c e88d fd25 a12f 2a9a 2699 4eef a0e6  .\...%./*.&.N...
    0000240: bed0 4ac2 e29b f639 b4c8 f975 ad88 6f31  ..J....9...u..o1
    0000250: 15ec 5e38 4cc6 8c1f d7d7 db63 cc63 f634  ..^8L......c.c.4
    0000260: 6152 809c 71d2 2622 3d7d 6990 cae6 4dfc  aR..q.&"=}i...M.
    0000270: 16f1 74fa 1a6e e46b 25af affc f393 6a61  ..t..n.k%.....ja
    0000280: d3f2 c69d 6cee 994f eff8 f2f0 a706 3842  ....l..O......8B
    0000290: 0110 d303 d075 ab16 d302 8181 00de e559  .....u.........Y
    00002a0: 9894 7bfd b75c 7e34 9bc7 6a16 73a8 c41b  ..{..\~4..j.s...
    00002b0: 6292 9c24 2c0e 3d0c 8087 3897 2518 f863  b..$,.=...8.%..c
    00002c0: 9304 b334 0d6a 8851 0cc5 24e3 7963 a42d  ...4.j.Q..$.yc.-
    00002d0: 0638 f605 572a a7b9 3eda 07dc 2945 7118  .8..W*..>...)Eq.
    00002e0: fa9a 9900 62f0 5d00 25d5 467d 3edf 8db4  ....b.].%.F}>...
    00002f0: 48cf 12ed 4ab6 7967 be70 c2a5 617b 3085  H...J.yg.p..a{0.
    0000300: d0e1 5135 7d63 b1ec a4b5 3746 fcbe 586c  ..Q5}c....7F..Xl
    0000310: dc8a 4405 cfaf 719f 3f01 1318 db02 8180  ..D...q.?.......
    0000320: 061a b3e3 597f e9dc e8ae 20fd f216 d18d  ....Y..... .....
    0000330: 3d0b 95fe dd1e 4a4b b71a acce d7b6 18df  =.....JK........
    0000340: f604 998a 3572 0135 8db0 b0ca 0286 eabb  ....5r.5........
    0000350: 1bb1 2ba6 5941 3df9 ebb8 07a0 649b 502e  ..+.YA=.....d.P.
    0000360: 1d9f c865 a734 e5e8 c29e 938d a5a1 46c0  ...e.4........F.
    0000370: 851b cfb4 d9b7 b2c5 99e3 18d8 a3a4 8c07  ................
    0000380: 114c 8c5e a2cb ef98 0b9d a88d 433f eb95  .L.^........C?..
    0000390: e6f9 f3d9 409d 3785 77c1 6914 a24e d1e9  ....@.7.w.i..N..
    00003a0: 0281 807c 71c7 1c71 c71c 71c7 1c71 c71c  ...|q..q..q..q..
    00003b0: 71c7 1c71 c71c 71c7 1c71 c71c 53e8 2ecf  q..q..q..q..S...
    00003c0: 9659 a276 fe5e db49 4353 fd4a edcf 16d8  .Y.v.^.ICS.J....
    00003d0: 0c1c 2ffc 71c7 1c71 c71c 71c7 1c71 c71c  ../.q..q..q..q..
    00003e0: 71c7 1c71 c71c 71c7 1c71 c71c 7154 eabf  q..q..q..q..qT..
    00003f0: a80a 11b7 1c71 c71c 71c7 1c71 c71c 71c7  .....q..q..q..q.
    0000400: 1c71 c71c 71c7 1c4e 0a6c 3981 108e 695d  .q..q..N.l9...i]
    0000410: 4559 880b ff22 c86b 1a6f 7b2b c342 a24e  EY...".k.o{+.B.N
    0000420: 0fb4 f1c7 1c71 c71c 71c7 1c71 c71c 71c7  .....q..q..q..q.
    0000430: 1c71 c71c 71c7 1c71 c71c 71c7 1c71 c71c  .q..q..q..q..q..
    0000440: 71c7 1c71 c71c 71c7 1c78 8544 52a2 7d35  q..q..q..x.DR.}5
    0000450: 8a79 163d 47ae c71c 71c7 1c71 c71c 71c7  .y.=G...q..q..q.
    0000460: 1c71 c71c 71c7 1c71 c71c 71c7 1c71 c71c  .q..q..q..q..q..
    0000470: 71c7 1c71 c71c 71c7 1c71 c77b e212 bf27  q..q..q..q.{...'
    0000480: e83f c219 3dba 0d56 4d87 4637 fa89 7520  .?..=..VM.F7..u
    0000490: a6a9 df3e 843f ab3c 0512 5610 2723 ef1d  ...>.?.<..V.'#..
    00004a0: fed1 7983 ad0d                           ..y...

    基本的にRSA秘密鍵に入っているパラメータは以下の通りである.

    RSAPrivateKey ::= SEQUENCE {
        version           Version,
        modulus           INTEGER, -- n
        publicExponent    INTEGER, -- e
        privateExponent   INTEGER, -- d
        prime1            INTEGER, -- p
        prime2            INTEGER, -- q
        exponent1         INTEGER, -- d mod (p-1)
        exponent2         INTEGER, -- d mod (q-1)
        coefficient       INTEGER, -- (inverse of q) mod p
        otherPrimeInfos   OtherPrimeInfos OPTIONAL
    }

    DERフォーマットの基本的な構成は以下のようになる.

  • ID (1byte. INTEGER型は0x02)
  • length
    • IDに続く1byteの最上位bitが立っていないときはその1byteが長さを表す.
    • 最上位bitが立っているときは, 残りの7bitが表す数値byte分の続きが長さを表す.
  • data
  • 例としてRSA暗号においてよく使われるe = 0x10001の場合を考えてみる.

  • ID = INTEGER型なので 0x02
  • length = 0x010001 より, 3byteであるから, 0x03
  • data = 0x010001
  • 以上より, 0x0203010001 となる.

    先ほどのダンプ結果からこれを探すと, 0x0000100の行の最後あたりに同じものが見つかるので, ここを基準に読み進めていく.

    eの直後に0x02がきていることから, dの値があることがわかる.

    eと同様に読むと, lengthが0x82であり最上位bitがたっていることから, 続く2byteが長さを表している. length=0x0100分読み進めた値がdとなる.

    この様にして読んでいくと, 素数p qの値が残っていることがわかる. したがって,得られたp qからrsatoolを使い秘密鍵を新たに作成し指定されたサーバへssh接続したところflagが降ってきた.

    今にして思えば, 素数を使わなくてもdの値で秘密鍵を作れた.

    flag{thought_ssh_privkeys_are_secure?}

    参考
    RSA 秘密鍵/公開鍵ファイルのフォーマット

    cryptolocker (crypto:200pt)

    AESCipher.py, cryptolock.py, flag,encrypted という3つのファイルが渡される.それぞれの概要は以下の通り.

  • AESCipher.py
    • AESの処理が書かれたもの. 外部ソースそのまま. 16byteのivをランダムに作成し, 平文を32byteの倍数長にパディングし暗号化.暗号文の先頭にivをくっつけreturn.
  • cryptolock.py:AESCipher.pyを用いてオレオレ暗号を実装したもの.
    • 8文字のinputをとり,2文字ずつsha256をとったものをkeyとして4回繰り返し暗号化.
  • flag.encrypted:暗号 = encrypt(encrypt(encrypt(encrypt(plain))))
  • inputの8文字をすべて総当たりで当てようとすると100**8となってしまい不可能である. しかし, 1回の暗号化に用いられるのは2文字のため100**2通り程度であり総当たり可能である. したがって, どうにかして1回ごとにkeyを特定していくことを考える.

    4回目の暗号化結果 = enc(3回目の暗号化結果+padding) であるが, 3回目の暗号化結果がわからないため総当たりしていった結果が当たっているのかの判定をすることができない. そこで注目するのがパディングである.

    padding = chr(padding_size) * padding_size
    # padding_size = 1 ~ 32

    であることから, 復号結果の最後の方が正しいパディング形式になっているかを確かめてやればよい.

    さらに, 暗号化結果 = iv + AESCipher であり, この長さは32byteの倍数長+16byteである. つまりパディングサイズは必ず16となっている.

    以上より, 2文字のinputを総当たりしつつ, 後ろ16文字がchr(16)となっているものを正解としていけば平文を1回暗号化したものまで求めることができる.

    また最後については, 問題文より平文がodtであることがわかるので, 復号結果にzip特有の文字列(PK など)が見られた場合を正解とした.

    # -*- coding: utf-8 -*-
    #!/usr/bin/env python3
    import sys
    import itertools
    import hashlib
    from AESCipher import *
    from Crypto import Random
    import string
    
    class SecureEncryption(object):
        def __init__(self, keys):
            # assert len(keys) == 4
            self.keys = keys
            self.ciphers = []
            for i in range(len(keys)):
              self.ciphers.append(AESCipher(keys[i]))
    
        def dec_first(self, ciphertext):
            plaintext  = self.ciphers[0].decrypt(ciphertext)
            return plaintext
    
        def dec_second(self, ciphertext):
            one        = AESCipher._unpad(self.ciphers[1].decrypt(ciphertext))
            plaintext  = self.ciphers[0].decrypt(one)
            return plaintext
    
        def dec_third(self, ciphertext):
            two        = AESCipher._unpad(self.ciphers[2].decrypt(ciphertext))
            one        = AESCipher._unpad(self.ciphers[1].decrypt(two))
            plaintext  = self.ciphers[0].decrypt(one)
            return plaintext
    
        def dec_last(self, ciphertext):
            three      = AESCipher._unpad(self.ciphers[3].decrypt(ciphertext))
            two        = AESCipher._unpad(self.ciphers[2].decrypt(three))
            one        = AESCipher._unpad(self.ciphers[1].decrypt(two))
            plaintext  = self.ciphers[0].decrypt(one)
            return plaintext
    
    if __name__ == "__main__":
      # Read encrypted file
      ciphertext = open("flag.encrypted", "rb").read()
    
      passwd = []
      password = ""
    
      for i in itertools.product(string.printable,repeat=2):
        user_input = ''.join(i)
        keys = [hashlib.sha256(user_input).digest()]
        s = SecureEncryption(keys)
        plaintext = s.dec_first(ciphertext)
        pad = plaintext[-1]
        if ord(pad) != 16:
          continue
        c = True
        for x in plaintext[-ord(pad):]:
          if ord(x) != ord(pad):
            c = False
        if c == False:
          continue
        passwd.append(user_input)
      print "[+] first stage"
      print passwd
      print
    
      password = passwd[len(passwd)-1]
      print "[+] now password:",password
      
      for i in itertools.product(string.printable,repeat=2):
        user_input = ''.join(i)+password
        keys = [
            hashlib.sha256(user_input[0:2]).digest(),
            hashlib.sha256(user_input[2:4]).digest()
        ]
        s = SecureEncryption(keys)
        plaintext = s.dec_second(ciphertext)
        pad = plaintext[-1]
        if ord(pad) != 16:
          continue
        c = True
        for x in plaintext[-ord(pad):]:
          if ord(x) != ord(pad):
            c = False
        if c == False:
          continue
        passwd.append(user_input)
      print "[+] second stage"
      print passwd
      print
      
      password = passwd[len(passwd)-1]
      print "[+] now password:",password
      
      for i in itertools.product(string.printable,repeat=2):
        user_input = ''.join(i)+password
        keys = [
            hashlib.sha256(user_input[0:2]).digest(),
            hashlib.sha256(user_input[2:4]).digest(),
            hashlib.sha256(user_input[4:6]).digest()
        ]
        s = SecureEncryption(keys)
        plaintext = s.dec_third(ciphertext)
        pad = plaintext[-1]
        if ord(pad) != 16:
          continue
        c = True
        for x in plaintext[-ord(pad):]:
          if ord(x) != ord(pad):
            c = False
        if c == False:
          continue
        passwd.append(user_input)
      print "[+] third stage"
      print passwd
      print 
    
      password = passwd[len(passwd)-1]
      print "[+] now password:",password
    
      for i in itertools.product(string.printable,repeat=2):
        user_input = ''.join(i)+password
        keys = [
            hashlib.sha256(user_input[0:2]).digest(),
            hashlib.sha256(user_input[2:4]).digest(),
            hashlib.sha256(user_input[4:6]).digest(),
            hashlib.sha256(user_input[6:8]).digest()
        ]
        s = SecureEncryption(keys)
        plaintext = s.dec_last(ciphertext)
        pad = plaintext[-1]
        if ord(pad) > 32 or ord(pad) == 1:
          continue
        c = True
        for x in plaintext[-ord(pad):]:
          if ord(x) != ord(pad):
            c = False
        if c == False:
          continue
        flag = AESCipher._unpad(plaintext)
        if "PK" in flag or "PNG" in flag or "IHDR" in flag:
          print user_input

    解いたときは一度に全部やらずに2文字ずつ特定してたので, 全部まとめるとものすごい読みにくくなってるけどそれはそう. 最後のodtファイルもprintしてるだけでファイル出力とかはしてないです.

    flag{v3ry_b4d_crypt0_l0ck3r}


    まとめ

    それなりに時間がとれた & cryptoが多かったこともあって久しぶりに通してずっと解いてた. CthCoinはずっとECDSAの問題だと思って格闘してたけど結局解けなかった. writeupを見てもなんだかなぁという感じ. あとやっぱり世界共通言語としてアセンブリを読めないと人権が無さそうなのでRevCryptoも解けるようになりたいですね...