Zenn
💡

ångstromCTF 2023 Writeup

2023/04/30に公開
Security
CTF
tech

ångstromCTF 2023に0nePaddingのメンバーとして参加したので解けた問題のwriteupを残します。主にcryptoを担当しました。もっと難しいcryptoも解けるようになりたいです。

https://2023.angstromctf.com/

Impossible

コードが与えられているのを知らず適当に数字を打ち込んだら解けてしまった問題。

pythonコード

#!/usr/local/bin/python  
  
def fake_psi(a, b):  
    return [i for i in a if i in b]  
  
def zero_encoding(x, n):  
    ret = []  
  
    for i in range(n):  
        if (x & 1) == 0:  
            ret.append(x | 1)  
  
        x >>= 1  
  
    return ret  
  
def one_encoding(x, n):  
    ret = []  
  
    for i in range(n):  
        if x & 1:  
            ret.append(x)  
  
        x >>= 1  
  
    return ret  
  
print("Supply positive x and y such that x < y and x > y.")  
x = int(input("x: "))  
y = int(input("y: "))  
  
if len(fake_psi(one_encoding(x, 64), zero_encoding(y, 64))) == 0 and x > y and x > 0 and y > 0:  
    print(open("flag.txt").read())

フラッグ箇所

if len(fake_psi(one_encoding(x, 64), zero_encoding(y, 64))) == 0 and x > y and x > 0 and y > 0:  
    print(open("flag.txt").read())

上記のif文が通ればフラッグが出てきます。fake_psiのリストの長さがゼロになっていることが鍵みたいですね。

Encoding Functions

def fake_psi(a, b):  
    return [i for i in a if i in b]  
  
def zero_encoding(x, n):  
    ret = []  
  
    for i in range(n):  
        if (x & 1) == 0:  
            ret.append(x | 1)  
  
        x >>= 1  
  
    return ret  
  
def one_encoding(x, n):  
    ret = []  
  
    for i in range(n):  
        if x & 1:  
            ret.append(x)  
  
        x >>= 1  
  
    return ret

フラグを取得するために上のコードが何をしているのかを理解する必要があります。xはone_encodingを、yはzero_encodingを通し、それぞれで作られたリストをfake_psiで比べます。
fake_psiはリストの被っているアイテムをリストとして返します。これの中身が空であるとフラグが取れます。

one_encoding

xが奇数である場合、その値をリストに追加してbitシフトを行います。n回繰り返します。

zero_encoding

yの値と1でbit andの操作を行い、それがゼロであればリストにyと1でbit orの結果をリストに入れます。その後、bitシフトを行い、n回繰り返します。

試してみる

小さな値

Supply positive x and y such that x < y and x > y.
x: 100
y: 10
one_encoding:[25, 3, 1]
zero_encoding:[11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
fake_psi: [3, 1]

リストに共通の値があるのでlistに値が追加されています。

大きな値

Supply positive x and y such that x < y and x > y.
x: 111111111111111111111111111111111111111
y: 111
one_encoding: [111111111111111111111111111111111111111, 55555555555555555555555555555555555555, 27777777777777777777777777777777777777, 1736111111111111111111111111111111111, 868055555555555555555555555555555555, 434027777777777777777777777777777777, 27126736111111111111111111111111111, 13563368055555555555555555555555555, 6781684027777777777777777777777777, 423855251736111111111111111111111, 211927625868055555555555555555555, 105963812934027777777777777777777, 6622738308376736111111111111111, 3311369154188368055555555555555, 1655684577094184027777777777777, 103480286068386501736111111111, 51740143034193250868055555555, 25870071517096625434027777777, 1616879469818539089626736111, 808439734909269544813368055, 404219867454634772406684027, 202109933727317386203342013, 50527483431829346550835503, 25263741715914673275417751, 12631870857957336637708875, 6315935428978668318854437, 1578983857244667079713609, 197372982155583384964201, 24671622769447923120525, 6167905692361980780131, 3083952846180990390065, 192747052886311899379, 96373526443155949689, 12046690805394493711]
zero_encoding: [7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
fake_psi: []

リストに共通の値がないので、empty listが返ってきます。

Result

xが64回シフトを行っても1にならないくらい大きな値と小さなyの値を使うとif文の条件を満たすのでフラッグが出てきます。

nc challs.actf.co 32200
Supply positive x and y such that x < y and x > y.
x: 1111111111111111111111111111
y: 11
actf{se3ms_pretty_p0ssible_t0_m3_7623fb7e33577b8a}

Royal Society of Arts

Python code

from Crypto.Util.number import getStrongPrime, bytes_to_long  
f = open("flag.txt").read()  
m = bytes_to_long(f.encode())  
p = getStrongPrime(512)  
q = getStrongPrime(512)  
n = p*q  
e = 65537  
c = pow(m,e,n)  
print("n =",n)  
print("e =",e)  
print("c =",c)  
print("(p-2)*(q-1) =", (p-2)*(q-1))  
print("(p-1)*(q-2) =", (p-1)*(q-2))

Solution

n,e,c,(p-2)*(q-1),(p-1)*(q-2)の値が与えられていて、\phiの値を求めることが出来ればdの値を求めることができるのでmの値も求めることができます。

以下のような数式を準備して解きました。

\phi = (p-1)(q-1)= pq-(p+q)+1
A =(p-2)(q-1) = pq-(p+q)+1-q+1= \phi -q + 1
B =(p-1)(q-2) = pq-(p+q)-p+1 = \phi -p + 1
A+B = 2\phi -(p+q)+2 = 2\phi - (pq-\phi+1)+2=3\phi-n+1
\phi = \frac{1}{3}(A+B+n-1)

solve.py

from Crypto.Util.number import long_to_bytes  
  
A = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230125943565148141498300205893475242956903188936949934637477735897301870046234768439825644866543391610507164360506843171701976641285249754264159339017466738250  
B = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230123577760657520479879758538312798938234126141096433998438004751495264208294710150161381066757910797946636886901614307738041629014360829994204066455759806614  
n = 125152237161980107859596658891851084232065907177682165993300073587653109353529564397637482758441209445085460664497151026134819384539887509146955251284230158509195522123739130077725744091649212709410268449632822394998403777113982287135909401792915941770405800840172214125677106752311001755849804716850482011237  
c = 40544832072726879770661606103417010618988078158535064967318135325645800905492733782556836821807067038917156891878646364780739241157067824416245546374568847937204678288252116089080688173934638564031950544806463980467254757125934359394683198190255474629179266277601987023393543376811412693043039558487983367289  
e = 65537  
  
phi = (A+B+n-1)//3  
print(phi)  
  
d = pow(e,-1,phi)  
print("d:",d)  
  
m = pow(c,d,n)  
print(m)  
  
flag = long_to_bytes(m)  
print(flag)

Flag

b'actf{tw0_equ4ti0ns_in_tw0_unkn0wns_d62507431b7e7087}'

Royal Society of Arts 2

この問題は結構悩んでしまったので、チームメイトと一緒に解きました。
離散対数問題かと思いましたが値の大きさ的に無理そうだったのでそこでしばらく詰まっていました。選択暗号文攻撃であることに気が付いてからはすぐに解くことができました。

Python Code

from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes  
f = open("flag.txt").read()  
m = bytes_to_long(f.encode())  
p = getStrongPrime(512)  
q = getStrongPrime(512)  
n = p*q  
e = 65537  
c = pow(m,e,n)  
print("n =",n)  
print("e =",e)  
print("c =",c)  
  
d = pow(e, -1, (p-1)*(q-1))  
  
c = int(input("Text to decrypt: "))  
  
if c == m or b"actf{" in long_to_bytes(pow(c, d, n)):  
    print("No flag for you!")  
    exit(1)  
  
print("m =", pow(c, d, n))

解答

平文をm,暗号文をc,公開鍵をe,二つの素数p,qからなるn=pqを定義。

c = m^e \quad mod \quad n

与えられたプログラムを使い、任意の暗号文c_2からm_2を求める。

m_2 = c_2^d \quad mod \quad n

c_2 = r^e c　を定義。rは正の整数。RSAは準同型なので以下が成り立つ。

m_2 = (r^e c)^d \quad mod \quad n = r^{ed}c^d \quad mod \quad n = rc^d \quad mod \quad n

上記より、

m = c^d \quad mod \quad n
m_2 = rm \quad mod \quad n
m = r^{-1}m_2 \quad mod \quad n

平文mが出ます。

solve.py

rの値は何でもいいのでr=2を選択します。

from pwn import *  
from Crypto.Util.number import long_to_bytes  
  
def get_data():  
    data = io.recvline()  
    split_data = data.decode('utf-8').strip().split()  
    val = int(split_data[2])  
    return val  
  
# establish connection to the server  
r = 2  
io = remote('challs.actf.co', 32400)  
  
# get data from server  
n = get_data()  
e = get_data()  
c = get_data()  
  
print("n:", n)  
print("e:", e)  
print("c:",c)  
  
# prepare sending value  
rx = pow(r,e,n) % n  
val = (rx*c) % n  
  
# send  
io.sendlineafter(':',str(val))  
  
# receive value  
m = get_data()  
  
# retrieve m value  
ans = m//r%n  
print("m:",m)  
print('ans:',ans)  
  
# show flag  
flag = long_to_bytes(ans)  
print(flag)

Flag

n: 135291038888793674081776961279399742623134478354181013976448948265418016652135941189276147606048697271313468517528811904236384239492279398916189360035446858218141353462425760944118912376275367774389274337603996681341082545591060957057219070134564284492106422433938814045514928728137313579647203953029927420583
e: 65537
c: 126667612092204060247464488567551771489573639427193618423757112096280333360128328709020942725048878179237903750845855266997208305430596204551603510922586052197228450969135170895059992705914688376208590598442171599456876631724192606207907005155997857084544429941088380377551997735541715744959498911112204116412
m: 117105165974072590517019806408040611880451156921473596166283382655895433672616710548173931231725049171307435181306
ans: 58552582987036295258509903204020305940225578460736798083141691327947716836308355274086965615862524585653717590653
b'actf{rs4_is_sorta_homom0rphic_50c8d344df58322b}'

Discussion