👋

RICERCA CTF 2023 に参加しました

2023/04/28に公開

CTF

idea

結果

チーム参加。47位/187チーム

解けた問題

crypto

Revolving Letters (119 solves)
Rotated Secret Analysis (34 solves)

reversing

crackme (134 solved)

Revolving Letters (119 solves)

Who keeps spinning letters around?

chall.py

LOWER_ALPHABET = "abcdefghijklmnopqrstuvwxyz"

def encrypt(secret, key):
  assert len(secret) <= len(key)
  
  result = ""
  for i in range(len(secret)):
    if secret[i] not in LOWER_ALPHABET: # Don't encode symbols and capital letters (e.g. "A", " ", "_", "!", "{", "}")
      result += secret[i]
    else:
      result += LOWER_ALPHABET[(LOWER_ALPHABET.index(secret[i]) + LOWER_ALPHABET.index(key[i])) % 26]

  return result

flag    = input()
key     = "thequickbrownfoxjumpsoverthelazydog"
example = "lorem ipsum dolor sit amet"
example_encrypted = encrypt(example, key)
flag_encrypted = encrypt(flag, key)

print(f"{key=}")
print(f"{example=}")
print(f"encrypt(example, key): {example_encrypted}")
print(f"encrypt(flag, key): {flag_encrypted}")

output.txt

key='thequickbrownfoxjumpsoverthelazydog'
example='lorem ipsum dolor sit amet'
encrypt(example, key): evvug kztla qtzla exl vqvm
encrypt(flag, key): RpgSyk{qsvop_dcr_wmc_rj_rgfxsime!}

keyが与えられているうえ、単純にそのアルファベットの分だけシフトしているだけなので、逆順の操作をするdecrypt関数を作成すればよい。

solve.py

LOWER_ALPHABET = "abcdefghijklmnopqrstuvwxyz"

key='thequickbrownfoxjumpsoverthelazydog'

enc = "RpgSyk{qsvop_dcr_wmc_rj_rgfxsime!}"

def decrypt(ct, key):
    result = ""
    for i, c in enumerate(ct):
        if c not in LOWER_ALPHABET:
            result += c
        else:
            result += LOWER_ALPHABET[((LOWER_ALPHABET.index(c)) - LOWER_ALPHABET.index(key[i]) + 26) % 26]
    return result
    
print(decrypt(enc, key))

RicSec{great_you_can_do_anything!}

Rotated Secret Analysis (34 solves)

$P$ の上位 $512 bit$ の値を $a$ , 下位 $512 bit$ の値を $b$ とする。

\begin{align} p = a \times 2^{512} + b \\ q = b \times 2^{512} + a \end{align}

と表せる。これを用いて、与えられている $N$ は

\begin{align} N &= pq \\ &= (a \times 2^{512} + b)(b \times 2^{512} + a) \\ &= ab \times 2^{1024} + (a^2 + b^2) \times 2^{512} + ab \end{align}

と表せる。ここで、

$ab \times 2^{1024}$ の下位 $1024bit$ は $0$
$(a^2 + b^2) \times 2^{512}$ の下位 $512bit$ は $0$
$(a^2 + b^2) < 2 \times 2^{512}$

であることを利用すると、

「 $N$ の上位 $256bit$ 、あるいはそれから $1$ を引いたもの」は $ab$ の上位 $512bit$
$N$ の下位 $512bit$ は $ab$ の下位 $512bit$

なのがわかり、 $ab$ は $2$ 通りに絞られる（詳細は画像参照）

ちょっとした図

いま、 $ab$ がわかったので、 $a, b$ に関する方程式を $2$ つ立てることができた。

あとは z3 に任せて、 $a, b$ の値を得た。

そこから先は基本的なRSA暗号の復号を行えば平文を求めることができる。

solve.py

from Crypto.Util.number import *
import math
import sys
import z3

N=24456513668907101359271796518022987404822072050667823923658615869713366383971188719969649435049035576669472727127263581903194099017975695864947929128367925596885753443249213201464273639499012909424736149608651744371555837721791748016889531637876303898022555235081004895411069645304985372521003721010862125442095042882100526577024974456438653686633405126923109918116756381929718438800103893677616376097141956262119327549521930637736951686117614349172207432863248304206515910202829219635801301165048124304406561437145821967710958494879876995451567574220240353599402105475654480414974342875582148522218019743166820077511
e=65537
c=18597341961729093099197297749831937867867316311655201999082918827905805371478429928112783157010654738161403312986940377995349388331953112844242407426040120302839420903486499187443737383169223520050969011318937950864196985991944523897440559547618789750180738003138383081085865616976666352985134179471231798760776607911573149993314296253654585181164097972479570867395976653829684069633563438561147707530130563531572708010593487686521808574459865586551335422619675302973576174518308347087901889923892503468385483111040271271572302540992212613766789315482719811321158322571666641755809592299352653626100918299699982602448

for up in range(2):

    ab_1 = ((N >> 1536) - up) * (2 ** 512)
    ab_2 = N & (2 ** 512 - 1)

    ab = ab_1 + ab_2

    num = N - ab * (2 ** 1024) - ab

    if num % (2 ** 512) != 0:
        continue

    num //= (2 ** 512)

    a, b = z3.Ints('a b')

    s = z3.Solver()

    s.add(num == a * a + b * b, ab == a * b, a > 0, b > 0)

    while s.check() == z3.sat:

        a = s.model()[a].as_long()
        b = s.model()[b].as_long()

        p = (2 ** 512) * a + b
        q = (2 ** 512) * b + a

        phi = (p - 1) * (q - 1)

        d = pow(e, -1, phi)

        m = pow(c, d, N)

        m = long_to_bytes(m)

        if m.startswith(b'RicSec{'):
            print(m)
            sys.exit()

RicSec{d0nt_kn0w_th3_5ecr3t_w1th0ut_r0t4t1n9!}

crackme

Can you crack the password?

strings で得た情報を覗いていたらflagらしき値が見えたので、それを打ってflagを得た。

> ./crackme
Password: N1pp0n-Ich!_s3cuR3_p45$w0rD
[+] Authenticated
The flag is "RicSec{U_R_h1y0k0_cr4ck3r!}"

RicSec{U_R_h1y0k0_cr4ck3r!}

upsolve した問題

[misc]gatekeeper (21 solved)

[misc]gatekeeper (21 solved)

> nc gatekeeper.2023.ricercactf.com 10005
password: b3Blbg==IA==c2VzYW1lIQ==
RicSec{b4s364_c4n_c0nt41n_p4ddin6}

RicSec{b4s364_c4n_c0nt41n_p4ddin6}

base64のパディングって途中に挟んでもいいみたい。初耳。

upsolve したい問題

[crypto]RSALCG (20 solved)
- 問題文すら見てないので、時間をとって解きたいね。
[reversing]ignition (6 solved)
- 最近revを頑張っているので、答えを見ながらでも頑張ってみたい。

感想

解いたり開いたりした問題はどれもシンプルで、考えたり実験したりするパートにたくさん時間を費やせたのが非常に楽しかった。同時開催中の他のCTFに時間を割いていたからあまり参加できなかったけど、非warmup問（運営視点）を解けたのですごく満足。

結果