m0leCon CTF 2022 Teaser Writeup

この大会は2022/5/14 2:00(JST)~2022/5/15 2:00(JST)に開催されました。
今回もチームで参戦。結果は176点で577チーム中70位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity Check (misc, warmup)

問題にフラグが書いてあった。

ptm{pl3453_54v3_4_7r33_d0n7_pr1n7_7h15_fl46}

Fancy Notes (web, crypto, warmup)

cookieに以下のbase64文字列が設定される。

username=[username],locale=en|[sha256(SECRET_KEY + [username],locale=en)]

Hash Length Extension Attackで攻撃する。
まずusername=noraでログインすると、クッキーのuserに以下が設定されている。

dXNlcm5hbWU9bm9yYSxsb2NhbGU9ZW58YzBmYmU3MzA2YjMwMjIxYzMzZDAzNDFlZjEzZjVlMjBkNmYxODM1NzYwODkzMTZlZDFmM2Y0ODM0MGU4ZTg1Zg==

base64デコードする。

$ echo dXNlcm5hbWU9bm9yYSxsb2NhbGU9ZW58YzBmYmU3MzA2YjMwMjIxYzMzZDAzNDFlZjEzZjVlMjBkNmYxODM1NzYwODkzMTZlZDFmM2Y0ODM0MGU4ZTg1Zg== | base64 -d
username=nora,locale=en|c0fbe7306b30221c33d0341ef13f5e20d6f183576089316ed1f3f48340e8e85f

",username=admin"を追加して、そのハッシュを求め、定型データにした後、base64エンコードし、クッキーに設定し、リクエストする。これをSECRET_KEYのサイズのブルートフォースでフラグが表示されるものを探す。

#!/usr/bin/env python3
import requests
import hashpumpy
import base64
import re
import warnings

warnings.simplefilter('ignore')

url = 'https://fancynotes.m0lecon.fans/notes'

known_hash = 'c0fbe7306b30221c33d0341ef13f5e20d6f183576089316ed1f3f48340e8e85f'
known_str = 'username=nora,locale=en'
add_data = ',username=admin'

for key_size in range(1, 50):
    h, d = hashpumpy.hashpump(known_hash, known_str, add_data, key_size)
    cookie_user = base64.b64encode(d + b'|' + h.encode()).decode()
    cookie = {'user': cookie_user}
    r = requests.get(url, cookies=cookie)
    if 'ptm{' in r.text:
        print('[+] SECRET_KEY size:', key_size)
        print('[+] Cookie: user =', cookie_user)
        pattern = '(ptm\{.+\})'
        m = re.search(pattern, r.text)
        flag = m.group(1)
        print('[*] flag:', flag)
        break

実行結果は以下の通り。

[+] SECRET_KEY size: 19
[+] Cookie: user = dXNlcm5hbWU9bm9yYSxsb2NhbGU9ZW6AAAAAAAAAAAAAAAAAAAAAAAAAAAFQLHVzZXJuYW1lPWFkbWlufGExMDcxZWM4NTM4ODBjNDVkMWY3ZjM4NjYzNWViOGU1MjFhYzNlMDk5MjYyMWVlNWUyZjVhOTE2N2FmMTljNzA=
[*] flag: ptm{pleaseD0NOTUseCr3am1nCarbon4r4!}
ptm{pleaseD0NOTUseCr3am1nCarbon4r4!}

MOO (crypto, warmup)

サーバの処理概要は以下の通り。

・p, pfs = gen_prime()
 ・以下繰り返し
  ・cnt = 0
  ・p = 1
  ・fs = []
  ・cntが4未満の間繰り返し
   ・e: 1~3のランダム値
   ・x: 1~2**128のランダム値の次の素数
   ・p *= x**e
   ・cnt += e
   ・fsに(x, e)を追加
   ・2 * p + 1が素数の場合
    ・fsに(2, 1)を追加
    ・2 * p + 1, fsを返却
・q, qfs = gen_prime()
・n = p * q
・e = 65537
・c = pow(flag, e, n)
・n, c, eを表示
・10回以下繰り返し
 ・g: 数値入力(g % n > 0)
 ・M = int(f2(g, (p, q), (pfs, qfs)))
  ・mofs = (f1(g, p, pfs), f1(g, q, qfs))
  ・lcm(mofs[0], mofs[1])を返却
 ・Mを表示

いろいろ試してみた結果、10回のMのLCMをMとすると、以下のようになる。

M * 2 == (p - 1) * (q - 1)

これはphiの値と同じ。あとは通常通りRSA暗号の復号方法で復号する。

#!/usr/bin/env python3
import socket
from functools import reduce
from gmpy2 import lcm
from Crypto.Util.number import *

def recvuntil(s, tail):
    data = b''
    while True:
        if tail in data:
            return data.decode()
        data += s.recv(1)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('challs.m0lecon.it', 1753))

data = recvuntil(s, b'\n').rstrip()
print(data)
data = recvuntil(s, b'\n').rstrip()
print(data)
n = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
c = int(data.split(' ')[-1])
data = recvuntil(s, b'\n').rstrip()
print(data)
e = int(data.split(' ')[-1])

MS = []
for g in [2, 3, 5, 7, 11, 13, 17, 19, 23, 27]:
    data = recvuntil(s, b': ')
    print(data + str(g))
    s.sendall(str(g).encode() + b'\n')
    data = recvuntil(s, b'\n').rstrip()
    print(data)
    M = int(data.split(' ')[-1])
    MS.append(M)

M = reduce(lcm, MS)
phi = M * 2
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print(flag)

実行結果は以下の通り。

Generating data...
n = 80924461791103577815850837875689177067665660234445708567868383751818584680054212313448507244659384038344296284890326734437750370989793572004432057543584093509122904180873669729045717066000876815786773368721692867813728603696567519284588068661539554205344620595619616197032933279794714455517366126694456718371958485054786951039462446603035275625576016214168193861388025096261118256254847981918655730252681107799019957520565656769423615296272038483342199962277
c = 34678191167506589626473690826771207402512855207909013228665864018996039251258639747055677874717524199976497403718168616081427221073854389668864212952920274252275639592937453805238201563942728842002703847403245420942852906355189826830449376572164310919971611166703159996155980459714493754291592255753617940295635967125247300508189411576356861614569600197002478111615705983219332020380884388259523695371993728777571638161513806749997177326679452387510245066452
e = 65537
Choose a value: 2
M = 40462230895551788907925418937844588533832830117222854283934191875909292340027106156724253622329692019172148142445163367218875185494896786002216028771792046754561452090436834864522858533000438407893386684360846433906864301848283750568281115476752022006327775818235970852463054567632754882562762652567053568179886431880992248559145873484988235549033924726342262095528474171847733648132700161835891101957238621876330616277742644684424666414473086012696739321398
Choose a value: 3
M = 20231115447775894453962709468922294266916415058611427141967095937954646170013553078362126811164846009586074071222581683609437592747448393001108014385896023377280726045218417432261429266500219203946693342180423216953432150924141875284140557738376011003163887909117985426231527283816377441281381326283526784089943215940496124279572936742494117774516962363171131047764237085923866824066350080917945550978619310938165308138871322342212333207236543006348369660699
Choose a value: 5
M = 40462230895551788907925418937844588533832830117222854283934191875909292340027106156724253622329692019172148142445163367218875185494896786002216028771792046754561452090436834864522858533000438407893386684360846433906864301848283750568281115476752022006327775818235970852463054567632754882562762652567053568179886431880992248559145873484988235549033924726342262095528474171847733648132700161835891101957238621876330616277742644684424666414473086012696739321398
Choose a value: 7
M = 20231115447775894453962709468922294266916415058611427141967095937954646170013553078362126811164846009586074071222581683609437592747448393001108014385896023377280726045218417432261429266500219203946693342180423216953432150924141875284140557738376011003163887909117985426231527283816377441281381326283526784089943215940496124279572936742494117774516962363171131047764237085923866824066350080917945550978619310938165308138871322342212333207236543006348369660699
Choose a value: 11
M = 40462230895551788907925418937844588533832830117222854283934191875909292340027106156724253622329692019172148142445163367218875185494896786002216028771792046754561452090436834864522858533000438407893386684360846433906864301848283750568281115476752022006327775818235970852463054567632754882562762652567053568179886431880992248559145873484988235549033924726342262095528474171847733648132700161835891101957238621876330616277742644684424666414473086012696739321398
Choose a value: 13
M = 20231115447775894453962709468922294266916415058611427141967095937954646170013553078362126811164846009586074071222581683609437592747448393001108014385896023377280726045218417432261429266500219203946693342180423216953432150924141875284140557738376011003163887909117985426231527283816377441281381326283526784089943215940496124279572936742494117774516962363171131047764237085923866824066350080917945550978619310938165308138871322342212333207236543006348369660699
Choose a value: 17
M = 40462230895551788907925418937844588533832830117222854283934191875909292340027106156724253622329692019172148142445163367218875185494896786002216028771792046754561452090436834864522858533000438407893386684360846433906864301848283750568281115476752022006327775818235970852463054567632754882562762652567053568179886431880992248559145873484988235549033924726342262095528474171847733648132700161835891101957238621876330616277742644684424666414473086012696739321398
Choose a value: 19
M = 40462230895551788907925418937844588533832830117222854283934191875909292340027106156724253622329692019172148142445163367218875185494896786002216028771792046754561452090436834864522858533000438407893386684360846433906864301848283750568281115476752022006327775818235970852463054567632754882562762652567053568179886431880992248559145873484988235549033924726342262095528474171847733648132700161835891101957238621876330616277742644684424666414473086012696739321398
Choose a value: 23
M = 40462230895551788907925418937844588533832830117222854283934191875909292340027106156724253622329692019172148142445163367218875185494896786002216028771792046754561452090436834864522858533000438407893386684360846433906864301848283750568281115476752022006327775818235970852463054567632754882562762652567053568179886431880992248559145873484988235549033924726342262095528474171847733648132700161835891101957238621876330616277742644684424666414473086012696739321398
Choose a value: 27
M = 20231115447775894453962709468922294266916415058611427141967095937954646170013553078362126811164846009586074071222581683609437592747448393001108014385896023377280726045218417432261429266500219203946693342180423216953432150924141875284140557738376011003163887909117985426231527283816377441281381326283526784089943215940496124279572936742494117774516962363171131047764237085923866824066350080917945550978619310938165308138871322342212333207236543006348369660699
ptm{y0u_found_another_w4y_t0_factorize}
ptm{y0u_found_another_w4y_t0_factorize}