ふるつき

v(*'='*)v かに

Ricerca CTF 2023 writeup / upsolve

CTF日本最強企業であるところのリチェルカセキュリティが開催していたCTF、Ricerca CTF 2023にzer0ptsとして参加していました。私はCryptoのRevolving Letters, Rotated Secreat Analysis, RSALCGを解いたあとはひたすらdice-vs-kymnに負けていました。その間にチームメイトのst98さんが色々通してくれたのでチームとしては6位。ありがとうございます。順位がいいとモチベがあがります

st98さんのwriteupはこちら

nanimokangaeteinai.hateblo.jp

以下は解いたCryptoのwriteupと、解けなかったdice-vs-kymnのupsolveです

Revolving Letters

次のような問題でした。驚くほど簡単でしたが、他のカテゴリのwarmup問題も似たような難易度だったので、CTF自体のコンセプトとして門戸を広く構えているんだろうなと思っています。

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}")

encrypt の中身になんとなく見覚えがあって、ROT13みたいな感じですね。ただ、ずらす量がkeyによって決められていて、文字ごとに変わっているところが異なります。ご丁寧にもkeyは渡されているのでずらす量を逆にしたdecrypt関数を書くだけで解けますが、さらに念には念をということでexampleを暗号化したものも渡されているので自分で書いたdecrypt関数の処理があっているかを確かめることもできます。そこそこCTFに慣れている人なら、自分で適当な文字列を暗号化して確かめられますが、そういう仕草になれていない人向けということだと思っています。優しさを感じる。

というわけでsolution scriptはこう。かかった時間は2分くらいでした

LOWER_ALPHABET = "abcdefghijklmnopqrstuvwxyz"

def decrypt(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

key     = "thequickbrownfoxjumpsoverthelazydog"
example = "evvug kztla qtzla exl vqvm"
flag = "RpgSyk{qsvop_dcr_wmc_rj_rgfxsime!}"

print(decrypt(example, key))
print(decrypt(flag, key))

Rotated Secret Analysis

問題はこう。

import os
from Crypto.Util.number import bytes_to_long, getPrime, isPrime

flag = os.environ.get("FLAG", "fakeflag").encode()

while True:
  p = getPrime(1024)
  q = (p << 512 | p >> 512) & (2**1024 - 1) # bitwise rotation (cf. https://en.wikipedia.org/wiki/Bitwise_operation#Rotate)
  if isPrime(q): break

n = p * q
e = 0x10001
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'{n=}')
print(f'{e=}')
print(f'{c=}')

どこかで見たことがありそうというか、これ既出じゃないんだという感じのいかにもな問題です。つまり、RSAで、素数の生成方法が独特で、pとqに共通する部分があるので素因数分解しましょうという問題です。

落ち着いて整理すると、A, Bを512bitの整数として p = A*2^{512} + Bで q = B*2^{512} + Aです。したがって n = pq = AB*2^{1024} + (A^2 + B^2)*2^{512} + ABと表せます。解いている途中の私は次のような図を書いて整理していました。

              | A* B         |
       | B**2 + A**2  |
 |   A * B    |

図を見るとわかるように、 nの上位256bitは ABの上位256bitに、下位256bitは ABの下位256bitにおよそ一致します。したがって、 nの上位bitと下位bitを切り貼りすると ABが求められます。

ABがわかれば、 nから A^2 + B^2の値を求めることができ、 AB = ...の式と A^2 + B^2 = ...の式がたつので連立方程式を解いて A, Bをそれぞれ求めれば、 p, qの値がわかるので、RSA暗号を解いてフラグが手に入ります。

solution scriptはこちら。 nから切り貼りした ABの一部分は A^2 + B^2と被っているbitで影響を受けるので多少探索を入れていますが、LSBは上位bitに影響を受けるはずなので yの足し方はまちがっていますね。

from sympy.solvers import solve
from sympy import symbols
from timeout_decorator import timeout


n = ...
e = ...
c = ...


@timeout(0.5, timeout_exception=StopIteration, use_signals=False)
def find(AB, A2B2):
    a, b = symbols("a, b", integer=True)
    solutions = solve([a*b - AB, (a**2 + b**2)*2**512 - A2B2])
    for s in solutions:
        return (s[a], s[b])


AB_LSB = n & (2**512 - 1)  # lower 512bits of A*B 
AB_MSB = n >> (2048 - 512)  # higher 512bits of A*B



for x in range(-3, 3):
    for y in range(-3, 3):
        AB = (AB_MSB + x) * (2**512) + (AB_LSB + y)
        A2B2 = n - (AB*2**1024 + AB)  # A**2 + B**2

        try:
            solutions = find(AB, A2B2)
            if solutions is not None:
                a, b = int(abs(solutions[0])), int(abs(solutions[1]))
                p =  a * 2**512 + b
                q =  b * 2**512 + a

                d = pow(e, -1, (p-1)*(q-1))
                m = pow(c, d, n)

                print(bytes.fromhex(hex(m)[2:]))
        except StopIteration:
            pass

nから ABを取り出す部分の整理に時間がかかって（というか整理をちゃんとやらなかったせいで錯覚があって）30分くらいかかっています。

RSALCG

from Crypto.Util.number import getPrime, getRandomNBitInteger
import os

FLAG = os.getenv("FLAG", "RicSec{*** REDACTED ***}").encode()

def RSALCG(a, b, n):
    e = 65537
    s = getRandomNBitInteger(1024) % n
    while True:
        s = (a * s + b) % n
        yield pow(s, e, n)

def encrypt(rand, msg):
    assert len(msg) < 128
    m = int.from_bytes(msg, 'big')
    return int.to_bytes(m ^ next(rand), 128, 'big')

if __name__ == '__main__':
    n = getPrime(512) * getPrime(512)
    a = getRandomNBitInteger(1024)
    b = getRandomNBitInteger(1024)
    rand = RSALCG(a, b, n)
    print(f"{a = }")
    print(f"{b = }")
    print(f"{n = }")
    print(encrypt(rand, b"The quick brown fox jumps over the lazy dog").hex())
    print(encrypt(rand, FLAG).hex())
    print(encrypt(rand, b"https://translate.google.com/?sl=it&tl=en&text=ricerca").hex())

encryptは単純なXORによる暗号化で、その鍵を生成するのがRSALCGですね。線形合同法によって生成した乱数 sを更にRSAで暗号化した値がXORの鍵になっています。

3回の暗号化で使われる鍵を k_1, k_2, k_3とすると、その値はそれぞれ k_1 = (as + b)^e \pmod n, k_2 = ((as + b)*a + b)^e \pmod n, k_3 = (((as + b)*a + b)*a + b)^e \pmod nとなります。さらに、 s' = as + bと置きなおすと k_1 = s'^e \pmod n, k_2 = (as' + b)^e \pmod n, k_3 = (as' + b)*a + b)^e \pmod nです。

RSAによって暗号化されている複数の平文の間に線形な関係性があるので、鍵が2つ手に入ればFranklin-Reiter's Related Message Attackで sの値を求められます。与えられている暗号文は平文が既知のものが2つあるのでこの値をつかって k_1, k_3を得たあと、Franklin-Reiter's Related Message Attackで sを求め、 k_2を計算すればフラグが手に入りそうです。

Franklin-Reiter's Related Message Attackでは多項式のGCDを計算しますが、今回は e = 65537とそこそこ eが大きかったので、Half-GCDを使いました。solution scriptでは省略しているので、この部分は half-GCD - crypto-writeup-publicを参照してください。

a = ...
b = ...
n = ...

X = int("...", 16)
Y = int("...", 16)
Z = int("...", 16)

x = int.from_bytes(b"The quick brown fox jumps over the lazy dog", "big")
z = int.from_bytes(b"https://translate.google.com/?sl=it&tl=en&text=ricerca", "big")

PR.<s> = PolynomialRing(Zmod(n))
e = 65537

t1 = cputime()
f1 = s**e - (x ^^ X)
f2 = ((s*a + b)*a + b)**e - (z ^^ Z)
t2 = cputime()
print(t2 - t1)

t1 = cputime()
r = pgcd(f1, f2)
t2 = cputime()

print(t2 - t1)
print(r)

s = int(-r.monic().constant_coefficient())
m = (pow(int((s*a + b) % n), e, n) ^^ Y)
print(bytes.fromhex(hex(m)[2:]))

この問題は13分でした。Half-GCDの計算は2分くらいだった。流石に典型という感じがするのでもっと早く解きたいですね。しかし意外と（私が解いた中では）まったく同じコンセプトという問題は見つかりませんでした。

dice-vs-kymn

この問題は競技時間中に解けなかったのでupsolveです。

janken-vs-yoshiking, janken-vs-kurenaifに続くvsシリーズです。問題はこう

import os
import signal

signal.alarm(1000)

for _ in range(77):
    x = randrange(1, 1 << 64)
    print("x:", x)
    a, b = int(input('a: ')), int(input('b: '))
    assert a != 0 and b != 0, "[kymn] Sorry for you!"

    for _ in range(10):
        p = random_prime(1 << 256)
        if legendre_symbol(x^3 + a*x + b, p) == 1:
            break
    else:
        print("[kymn] (^o^)m9 Bad luck!")
        exit()

    F = GF(p)
    E = EllipticCurve(F, [F(a), F(b)])
    G = E.lift_x(F(x))

    k = randrange(1, p)
    Q = k * G
    kymn_dice = (k % 6) + 1
    print("commitment:", (G[1], Q[1]))

    player_dice = int(input("Your dice: "))
    assert 1 <= player_dice <= 6, "Wrong input"

    if kymn_dice + player_dice == 7:
        print("[kymn] o(.o.)o You lucky bastard!")

    else:
        print("[kymn] (^o^)m9 Bad luck!")
        print("proof:", (p, k))
        exit()

else: # 77 wins!
    print("[kymn] I got totally destroyed! Hats off to you...")
    print("FLAG:", os.getenv("FLAG", "RicSec{*** REDACTED ***}"))

楕円曲線の問題で、 Gと Q = kGが与えられるので、 k \mod 6を77回連続で当てる必要があります。楕円曲線のパラメータは毎回異なっていて、 GのX座標 xが与えられるのでこちらで楕円曲線のパラメータ a, bを指定すると y^2 \equiv x^3 + ax + b \mod pを満たす yが存在するような pがランダムに選ばれます。

パラメータがランダムで、特に pを知らないという制約が厳しく、 a, bを工夫してECDLPを簡単に解くというのは難しそうです。となると生成される点の側をなんとかして k \mod 6を当てやすくしたいですが、 k自体を求めたいのではなく k \mod 6を求めたいという点に着目すると、 Gの位数を調整して6になるようにできれば簡単に解けそうです。

私はここで \mathcal{O}なので 5G = -Gとなるから…と頑張って立式していたのですが、チームメイトのmitsuくんが「それ等分多項式（division polynomial）って概念ですよ」と教えてくれてそうじゃんになりました。等分多項式を使うと楕円曲線のパラメータ a, bに対して、 6G = \mathcal{O}を満たす G = (x, y)の xが満たすべき式 f_6(a, b, x)が得られます。今回は xは決まっていて a, bを求めたいので g(a, b) = (x \mapsto f_6(a, b, x))として、 g(a, b) = 0を満たすような a, bが得られれば、 Gが 6G = \mathcal{O}となります。

ただし、当然 g(a, b)は2変数の多項式なので、単純には a, bは求まりません。これもmitsuくんが g(a, b)の判別式 d(b)を使って制約を増やすことで g(a, b) = 0を満たす a, bを探すアルゴリズムを考案してくれました。これで a, b, xが f_6(a, b, x) = 0を満たすようできるので、 Gの位数が6になって勝ち……と思ったのですが、まだ落とし穴がありました。

f_6(a, b, x) = 0を満たす a, b, xによる点 Gは 6G = \mathcal{O}を満たすだけで位数6とは言っておらず、見つかったパラメータで生成された Gは位数3になってしまっていて、 k \mod 3はわかっても k \mod 6はわかりませんでした。 k \mod 3はわかるので k \mod 6も2分の1の確率では求められますが、77回連続で当てるのは到底不可能です。

式自体はあっていそうなのでなんとか位数6の点が求まるにできないかと思いましたが、見つかる解は全部位数が3の点を生成してしまい、これがどうにもできずタイムアップとなりました*1。無念です。よって、ここから先はあとから教えてもらった方針によるupsolveです。

等分多項式を使うところまでの方針はよかったのですが、位数6の点が生成されるようなパラメータを見つけられない、というのが問題でした。これを解決する方法は……気合の探索です。

ax, bが x^3と同じくらいの大きさになるように、 a = a'x^2, b = b'x^3として係数 a', b'を適当に探索すると g(a, b) = 0を満たす a, bを見つけられるどころか、 xも変数とおいて xがいかなる値のときでも f_6(a, b, x) = 0を満たすようなパラメータ a, bを見つけられます。

当然ここで求めたパラメータ a, bも位数3の点を生成することはありますが、解はいくつも見つかるので、位数6の点を生成するケースを探せば良いです*2。

これでようやく Gの位数を6にできました。あとは pがわからない状態で Q = kGを解くだけで、これは剰余を取らない状態で G, 2G, \dots, 6Gを計算して Qと一緒にGCDをとったりしたらだいたい求まります。

solution scriptは以下

gist.github.com

完敗ですが、おもしろかったです。division polynomialは前回のyoshicampで教えてもらった概念で、それをちゃんと問題に落とし込んでくるptr-yudaiが偉かったと思います。気合の探索を担当したというkeymoonもえらい。私も解ききって偉くなりたかった。精進します

*1:これがjankenなら位数3で良かったのに……

*2:理由はわかっていませんが、生成される点の位数はxによらずa, bのみで決まりそうでした