🔐

SECCON beginners 2021 write up

2021/05/26に公開

SECCONに出た

前々から出てみたかったCTFの大会に初めて出ました．丁度CTFつよつよの友人が居たのでチームunnamersの仲間に入れてもらって参加しました！
問題はどれも難しくて友達にほぼ解いてもらった形でしたが，2問だけ自力で解けた問題があるのでその解説を書きます💪

問題解説

simple_RSA

ダウンロードできるデータの中のoutput.txtを見ると

n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613

となっています．　RSA暗号の公開鍵である素数の積 $n$ と任意の正数 $e$ ，そして暗号文 $c$ が与えられていますが，ここで注目するべきはeです．通常のRSA暗号ではデフォルトで $65535$ 程度の大きな整数を利用するそうですが，ここでは $3$ と小さな値を取っています．
私はセキュリティ知識が皆無なのでここからはGoogle先生の力をフル活用します．RSA関係の脆弱性を頑張って探します．するとLow Public-Exponent Attackという攻撃を見つけました．

Low Public-Exponent Attack
$e$ が小さく，平文 $m$ が $\sqrt[e]{n}$ 以下の時， $m = \sqrt[e]{c}$ となる

なのでこの攻撃の方法を素直に実装します．akashisnさんとももいろテクノロジーさんの記事を参考にしました．ありがとうございます．

LPEA.py

import gmpy2
import binascii

n = int(input())
e = int(input())
c = int(input())

m, result = gmpy2.iroot(c, e)
flag = binascii.unhexlify(format(m, 'x')).decode()
print(flag)

Mail_Address_Validator

この問題は友人と協力して解きました！
正規表現の問題です．問題となっているRubyのコードを読むと

main.rb(抜粋)

pattern = /\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z/i

begin
  Timeout.timeout(60) {
    Process.wait Process.fork {
      puts "I check your mail address."
      puts "please puts your mail address."
      input = gets.chomp
      begin
        Timeout.timeout(5) {
          if input =~ pattern
            puts "Valid mail address!"
          else
            puts "Invalid mail address!"
          end
        }
      rescue Timeout::Error
        exit(status=14)　# ここに来るとflagが取れる
      end
    }

与えられたデータが正しいメールアドレスかどうかを正規表現で確認しているようです．このpatternで解析するのに時間のかかりそうなデータを投げる事によってTimeoutを狙います．
patternを眺めると怪しげな部分が見つかります．

patternの抜粋

(\.[a-z]+)*

ここの判定ですが，ピリオドの後に[a-z]が1文字以上存在する事が0回以上繰り返されているか？という判定になっていて二重ループになっています．つまり，計算量が $O(N^2)$ となっています．
つまり，ここの部分の判定の回数を増やす事でDOS攻撃を行う事ができます．より具体的には，この正規表現の部分はメールアドレスの@とトップレベルドメインの間の部分なので

aaa@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.com

という文字列を送ることで処理をタイムアウトさせる事ができます．これをサーバに送って無事flagをゲットです！

$ nc mail-address-validator.quals.beginners.seccon.jp 5100
I check your mail address.
please puts your mail address.
aaa@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.com
ctf4b{...}

終わりに

以上が私の解いた問題です！人生初のCTFだったのでAtCoderなどの別の競プロとはまた違った楽しさがあって新鮮な気持ちで参加できました！他のCTFにも出てみたいと思っているのでまたどこかでお会いしましたらよろしくお願いします〜！

SECCONに出た

問題解説

simple_RSA

Mail_Address_Validator

終わりに

Discussion