ASIS CTF Finals 2021 Writeup - よっちんのブログ

この大会は2021/12/25 0:00(JST)～2021/12/26 0:00(JST)に開催されました。
今回もチームで参戦。結果は939点で198チーム中32位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome! (Warm-up)

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

ASIS{ASIS_is_the_last_real_CTF_of_2021!}

mDLP (Crypto)

Q = A ** d
C = A ** r
D = Q ** r
E = D * M = Q ** r * M
※d, rは不明
※Mが平文
※C, Eが暗号

行列を使ったElGamal暗号。A = P * J * inverse(P)となるJ(=ジョルダン標準形), Pを求める。

Q = A ** d = P * J**d * inverse(P)
　　　↓
J**d = inverse(P) * Q * P

以上で整数のDLPになるので、この問題を解き、dを求める。dがわかれば、ElGamal暗号の復号方法を応用して復号する。

M = inverse(Q ** r) * E
  = inverse((A ** d) ** r) * E
  = inverse((A ** r) ** d) * E
  = inverse(C ** d) * E

#!/usr/bin/env sage
from Crypto.Util.number import *

p = 94413310751917369305079812653655619566021075449954923397392050181976939189891
A = matrix(Zmod(p),
    [[38199337272663519912859864066101528484023656231849338967558894235177040565160,
    39708167173513090810083500967474691943646789486489990958101592717502452906918],
    [8216211510625558273096642057121313417997488994504871245106775381995665925783,
    56213973479253849392219948587554091081997419218105584429833155946799898624740]])
Q = matrix(Zmod(p),
    [[61709241598677561125021718690991651934557899286972116933820920757636771220273,
    1945367449329759288724720626216309893787847192907494307536759223359193510642],
    [37495232301500074672571996664644922614693962264764098174213150757616575323566,
    7348269231944161963123250652171976847627786311806728904368575861561449853500]])
C = matrix(Zmod(p),
    [[47566868540912475779105819546118874217903268597017385039977593878486632022506,
    86073162301954995219912739344010659248720823814557810528618517154406350653517],
    [23443866424088482893369441934221448179896589659663581973508963775891809430857,
    74567333640177484678138574534395714128854315440076840728428649074147859070975]])
E = matrix(Zmod(p),
    [[56937964695156855099385034285428853461603799261684034842341841781057485084327,
    82459328835322885824854425864023809222717401981993182346342472865578156162544],
    [85092677346274708324092648597361729755305119435989183201786866456596369562681,
    22228861714953585357281182780002271505668586948202416054453861940155538803489]])

J, P = A.jordan_form(transformation=True)
pub_J = ~P * Q * P
R = IntegerModRing(p)
d = discrete_log(R(pub_J[1][1]), R(J[1][1]))
assert A ** d == Q

M = ~(C ** d) * E

flag = ''
for i in range(2):
    for j in range(2):
        flag += long_to_bytes(int(M[i][j])).decode()
print(flag)

ASIS{PuBl1c-K3y_CRyp70sy5tEm_B4S3d_On_Tw0D!m3nSiOn_DLP!}

nDLP (Crypto)

g = 685780528648223163108441
n = 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
y = pow(g, x, n)
y = 9136134187598897896238293762558529068838567704462064643828064439262538588237880419716728404254970025

このパラメータのDLP問題。nを素因数分解する。

$ python -m primefac 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189: 795045813258486756062581 196506778231841265839577533 685825230919805430353639 117487902085160690512598387

それぞれの素数でDLP問題を解き、CRTでxを求める。

#!/usr/bin/env sage
from Crypto.Util.number import *

g = 685780528648223163108441
n = 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
ps = [795045813258486756062581, 196506778231841265839577533,
    685825230919805430353639, 117487902085160690512598387]
y = 9136134187598897896238293762558529068838567704462064643828064439262538588237880419716728404254970025

xs = []
for i in range(4):
    p = ps[i]
    yp = y % p

    R = IntegerModRing(p)
    x = discrete_log(R(yp), R(g))
    xs.append(x)

phis = [p -1 for p in ps]

x = crt(xs, phis)
flag = long_to_bytes(x).decode()
print(flag)

ASIS{D!5Cre73_L09_iN_Zn_I5_3aSy?!}

RAS (Crypto)

RSA暗号だが、キーの生成方法に特徴がある。p, qは以下のように生成される。

・a: 2以上nbit未満
・b: 32以上nbit未満
・a**bをベースとしてpは31ビット素数、qは37ビット素数をプラスした素数

まずは総当たりでa**bの積がnの上位ビットに合うものを探す。1組しかないので、それを元にCoppersmithの定理を使って、pを求める。あとはqもわかるので、そのまま復号する。

#!/usr/bin/env sage
from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    pubkey = int(f.readline().rstrip().split(' ')[-1])
    enc = int(f.readline().rstrip().split(' ')[-1])

e = 0x10001
nbit = 512

params = []
for a in range(2, nbit):
    for b in range(32, nbit):
        if (a ** b).bit_length() == nbit:
            params.append(a ** b)

bits = nbit - 68
ps = []
for p_base in params:
    for q_base in params:
        n_base = p_base * q_base
        high_n = bin(n_base)[2:2+bits]
        if high_n == bin(pubkey)[2:2+bits]:
            ps.append(p_base)

pbar = ps[0]
kbits = 31

PR.<x> = PolynomialRing(Zmod(pubkey))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]
p = int(x0 + pbar)
assert pubkey % p == 0

q = pubkey // p
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = int(pow(enc, d, pubkey))
flag = long_to_bytes(m).decode()
print(flag)

ASIS{RAS_iZ_51mpl!FI3D_RSA_sY573M!}

Stairs (Crypto)

$ nc 95.217.210.96 11010
------------------------------------------------------------------------
|          ..:: Try to going down the stairs carefully ::..            |
|           Try to break this cryptosystem and find the flag!          |
------------------------------------------------------------------------
| Options:                                                             |
|	[E]ncryption function                                          |
|	[T]ry encryption!                                              |
|	[P]ublic key                                                   |
|	[Q]uit                                                         |
|----------------------------------------------------------------------|
E
def encrypt(m, pubkey):
	e, n = 5, pubkey
	M = bytes_to_long(flag)
	m += M
	c = (pow(m, e, n) + m) % n 
	return c

P
pubkey = 15060802253368783203672548391896406306029436929856566108211916459409792485326483349854098210603317087853426828546799430827915392008092992017065843498028611098413414785163827185628682946947055542589227339278245590924021491841430777648771688443092326521946668363720819122599386340380935602204069804397635565260718714893714701326812248697554813631054146038513391555568643441157216775404231187675356172223145591685443357656186455694687658112632978686212712150319446402150547928713883150461878758916314008918325136319043472502668277283157993750823577682647174133496505293974724526382965408292344593806168177959971555981261
T
| send your message as integer to encrypt: 
0
| the encrypted message is: 14438441481384215336070064515366556832658896022392060016367979867263945263759011612374309755113968390989244127524435444212713909276521005399831164087064467142488347400943896111932592376674307002424140295588955477337071921519566795253271343975810556249775485454841541954133105104208633193492354729975950889850639458494889601023126863703687753556727851276669070809236320615985578687297367682360853575399526166224302939077494156280541322009075616974516937572203504357870059229041200144293476918627661621223240591102791790823339549720724568567083903182107083041509117937159739327348652800137033175409627744625073517485334
T
| send your message as integer to encrypt: 
1
| the encrypted message is: 15059722439631001176733498206244491685167254847041003197176272812427379980303452200162657484262554801668051554531107304578228437403686532372919655283309614655972498315991675730779778183966356620068650597719906674821968503938519261320657726617212189063110555225286212881602499399557757577559296083712544814928767465932232219115379643790630690864915164100266002922172314630327636767013039246169493779122458005784028041421978794505194457734916212519534755070216646967580504379001817299577276053435342545206908185096062080241587755167104376706934300629703682656094260951600872735807751248436879434180727214993586989789110

暗号部分はこうなっている。

c = (pow(m + M, e, n) + m + M) % n

m = 0の場合
c0 = (pow(M, e, n) + M) % n

m = 1の場合
c1 = (pow(M + 1, e, n) + M + 1) % n

平文の差は1で、Franklin-Reiter Related Message Attackをカスタマイズして復号する。

#!/usr/bin/env sage
import socket
from Crypto.Util.number import *

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

def custom_related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e + x - c1
    g2 = (x+diff)^e + x - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return int(-gcd(g1, g2)[0])

e = 5

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('95.217.210.96', 11010))

for _ in range(10):
    data = recvuntil(s, b'\n').rstrip()
    print(data)

print('E')
s.sendall(b'E\n')
for _ in range(7):
    data = recvuntil(s, b'\n').rstrip()
    print(data)

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

print('T')
s.sendall(b'T\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
print('0')
s.sendall(b'0\n')
data = recvuntil(s, b'\n').rstrip()
print(data)
c0 = int(data.split(' ')[-1])

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

M = custom_related_message_attack(c0, c1 - 1, 1, e, n)
flag = long_to_bytes(M).decode()
print()
print(flag)

実行結果は以下の通り。

------------------------------------------------------------------------
|          ..:: Try to going down the stairs carefully ::..            |
|           Try to break this cryptosystem and find the flag!          |
------------------------------------------------------------------------
| Options:                                                             |
|	[E]ncryption function                                          |
|	[T]ry encryption!                                              |
|	[P]ublic key                                                   |
|	[Q]uit                                                         |
|----------------------------------------------------------------------|
E
def encrypt(m, pubkey):
	e, n = 5, pubkey
	M = bytes_to_long(flag)
	m += M
	c = (pow(m, e, n) + m) % n
	return c

P
pubkey = 19587328428746756706779160889219187895184005583219108559561246514116121562327955692664330926417393884946057140261879120881461257903277582988716850871485609906983476936276321858531992279018601806301980002554298923321556875980970886653403444503848822725669561506312519984989206229517003468156629695004060676060243242827106497894501889046908655585506087589947689560820383600383066107382746694916659834361927883505820386382444268806756617665905365824529275604125334164763335392991283279251945320738642725936560565848618698292156330834497300129199445187221152291508791470607656934670276122122943170919674090848649795494983
T
| send your message as integer to encrypt:
0
| the encrypted message is: 18430823245361022406509393577098533960124710070535508069188661824724559030001033606137513505265473683671741006908270622178679602180317754997393282543058171741616406215511118133036359111100049508510109927461201875039648340037977969013404572743709795542217362509254012885686358973557023020547196007376017695785934908677349072535436581091850107681552433319354444398509019893111823048802559769626481614810966153498970788513365451486845843243007214030655442857314617565175410969204375954268249940520156779782527316452713050529234993632433946089297062744618272253527549504472825864590287392196623383709848315806845074823498
T
| send your message as integer to encrypt:
1
| the encrypted message is: 6858486508085154465066478995298682424653619658697625617508538701290351244284200255195067569699472047229236766199112430492136842407327186687194556505810051920898419379100595759306254415753889479590661034801766510949045176336785558912197070257535396146998790074377336473482904203188104319357248213483598792757815499419983309825693180864930981335345320527852691637037454702246252807813699495389539717853099061235209990097095803057612025690358122407386222488340964640949933858395963089399131291983175973194659590397282841919694764390766616641079257315968565416222269089704904811564390928727147720295323735690143627401905

:::. The flag is: ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?} .:::

ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?}