ACSC 2023
Writeup for the challenges I solved in ACSC. I mainly focused on Crypto challenges.
Reverse
Serverless
I made a serverless encryption service. It is so serverless that you should host it yourself. I encrypted the flag with “acscpass” as the password, but have not finished implementing the decryption feature. Help me decrypt the flag!
Observation
We are given an encrypted text with the password, and the js file used to perform the encryption.
The objective of the challenge is to find out what was the encryption and try to decrypt it.
Solution
Looking at how function b is called, we can deduce that b is the encryption function and the two parameters are message and password.
Let’s do some rename and combine the constants.
For the specific functions that I not sure what it is doing, I just throw it into ChatGPT
Great! Now this seems more readable than the first version. Since there are some modulo exponential involved, I suspected that it is doing some RSA encryption.
Checking all the constants in array g and h, I found that all of them are primes. So it indeed is an RSA encryption with primes known.
I then coded a simple decryption function in python to find the flag.
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
s = [117,96,98,107,7,43,220,233,126,131,201,15,244,105,252,125,10,166,219,230,250,82,211,101,195,39,240,158,174,59,103,153,122,36,67,179,224,108,9,88,191,91,14,224,193,52,183,215,11,26,30,183,133,161,169,91,48,229,99,199,165,100,218,0,165,41,55,118,227,236,80,116,120,125,10,123,125,131,106,128,154,133,55,5,63,236,69,27,201,118,180,74,213,131,47,200,116,52,49,120,86,124,178,92,246,119,98,95,86,104,64,30,54,20,109,133,155,122,11,87,16,223,162,160,215,209,136,249,221,136,232]
s = s[::-1]
g = [0x9940435684b6dcfe5beebb6e03dc894e26d6ff83faa9ef1600f60a0a403880ee166f738dd52e3073d9091ddabeaaff27c899a5398f63c39858b57e734c4768b7, 0xbd0d6bef9b5642416ffa04e642a73add5a9744388c5fbb8645233b916f7f7b89ecc92953c62bada039af19caf20ecfded79f62d99d86183f00765161fcd71577, 0xa9fe0fe0b400cd8b58161efeeff5c93d8342f9844c8d53507c9f89533a4b95ae5f587d79085057224ca7863ea8e509e2628e0b56d75622e6eace59d3572305b9, 0x8b7f4e4d82b59122c8b511e0113ce2103b5d40c549213e1ec2edba3984f4ece0346ab1f3f3c0b25d02c1b21d06e590f0186635263407e0b2fa16c0d0234e35a3, 0xf840f1ee2734110a23e9f9e1a05b78eb711c2d782768cef68e729295587c4aa4af6060285d0a2c1c824d2c901e5e8a1b1123927fb537f61290580632ffea0fbb, 0xdd068fd4984969a322c1c8adb4c8cc580adf6f5b180b2aaa6ec8e853a6428a219d7bffec3c3ec18c8444e869aa17ea9e65ed29e51ace4002cdba343367bf16fd, 0x96e2cefe4c1441bec265963da4d10ceb46b7d814d5bc15cc44f17886a09390999b8635c8ffc7a943865ac67f9043f21ca8d5e4b4362c34e150a40af49b8a1699, 0x81834f81b3b32860a6e7e741116a9c446ebe4ba9ba882029b7922754406b8a9e3425cad64bda48ae352cdc71a7d9b4b432f96f51a87305aebdf667bc8988d229, 0xd8200af7c41ff37238f210dc8e3463bc7bcfb774be93c4cff0e127040f63a1bce5375de96b379c752106d3f67ec8dceca3ed7b69239cf7589db9220344718d5f, 0xb704667b9d1212ae77d2eb8e3bd3d5a4cd19aa36fc39768be4fe0656c78444970f5fc14dc39a543d79dfe9063b30275033fc738116e213d4b6737707bb2fd287]
h = [0xd4aa1036d7d302d487e969c95d411142d8c6702e0c4b05e2fbbe274471bf02f8f375069d5d65ab9813f5208d9d7c11c11d55b19da1132c93eaaaba9ed7b3f9b1, 0xc9e55bae9f5f48006c6c01b5963199899e1cdf364759d9ca5124f940437df36e8492b3c98c680b18cac2a847eddcb137699ffd12a2323c9bc74db2c720259a35, 0xcbcdd32652a36142a02051c73c6d64661fbdf4cbae97c77a9ce1a41f74b45271d3200678756e134fe46532f978b8b1d53d104860b3e81bdcb175721ab222c611, 0xf79dd7feae09ae73f55ea8aa40c49a7bc022c754db41f56466698881f265507144089af47d02665d31bba99b89e2f70dbafeba5e42bdac6ef7c2f22efa680a67, 0xab50277036175bdd4e2c7e3b7091f482a0cce703dbffb215ae91c41742db6ed0d87fd706b622f138741c8b56be2e8bccf32b7989ca1383b3d838a49e1c28a087, 0xb5e8c7706f6910dc4b588f8e3f3323503902c1344839f8fcc8d81bfa8e05fec2289af82d1dd19afe8c30e74837ad58658016190e070b845de4449ffb9a48b1a7, 0xc351c7115ceffe554c456dcc9156bc74698c6e05d77051a6f2f04ebc5e54e4641fe949ea7ae5d5d437323b6a4be7d9832a94ad747e48ee1ebac9a70fe7cfec95, 0x815f17d7cddb7618368d1e1cd999a6cb925c635771218d2a93a87a690a56f4e7b82324cac7651d3fbbf35746a1c787fa28ee8aa9f04b0ec326c1530e6dfe7569, 0xe226576ef6e582e46969e29b5d9a9d11434c4fcfeccd181e7c5c1fd2dd9f3ff19641b9c5654c0f2d944a53d3dcfef032230c4adb788b8188314bf2ccf5126f49, 0x84819ec46812a347894ff6ade71ae351e92e0bd0edfe1c87bda39e7d3f13fe54c51f94d0928a01335dd5b8689cb52b638f55ced38693f0964e78b212178ab397]
password = b'acscpass'
for i in range(len(s)):
s[i] = s[i] ^ password[i % len(password)]
print(s)
x = bytes_to_long(bytes(s[:-3])[::-1])
p = g[s[-1]]
q = h[s[-2]]
n = p * q
e = 2**(2**s[-3]) + 1
d = inverse(e, (p - 1) * (q - 1))
m = pow(x, d, n)
print(long_to_bytes(m))
ans = []
while m > 0:
ans.append(m & 0xff)
m = m // 256
print(bytes(ans[::-1]))
flag : ACSC{warmup_challenge_so_easy}
Crypto
Merkle Hellman
We tired of RSA, try a new cryptosystem by merkle and hellman but we don’t know how to decrypt the ciphertext. We need your help for decrypt the ciphertext to get back my flag.txt!
Oberservation
We are given everything, public key, private key and ciphertext. This should be an easy solve once we can figure out what the encryption is doing
Solution
Let’s focus on the encryption part
c = []
for f in flag:
s = 0
for i in range(7):
if f & (64>>i):
s += b[i]
c.append(s)
Every integer in c is encryption of a single character in flag.
The encryption is done by summing up a subset of the integers in b based on the character value (convert to 8 bits)
So I constructed a reverse decryption map by encrypting all possible characters
\[D: \mathbb{Z} \to char\]Then just use the decryption map to find out the flag
p = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
q = 20910
c = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]
dic = {}
for i in range(2**7):
s = 0
for j in range(7):
if (i & (1 << j)):
s += p[6 - j]
dic[s] = i
for i in c:
print(chr(dic[i]), end='')
flag : ACSC{E4zY_P3@zy}
Check Number 63
I know the “common modulus attack” on RSA. But as far as I know, the attacker can NOT factor n, right? I generated 63 keys with different public exponents. I also generated the check numbers to confirm the keys were valid. Sadly, public exponents and check numbers were leaked. Am I still safe?
Observation
To get the flag, we must recover p and q
The only hint we have is pairs of \((e_i,k_i)\) that satisfies
\[e_id_i - 1 = k_i(phi)\]Solution
First let’s see what we can do with the hints.
\[\begin{aligned} e_id_i - 1 &= k_i(phi)\\ e_id_i - k_i(phi) &= 1\\ \end{aligned}\]Notice that this equation is the linear diophantine equation.
Since \(e_i\) is prime, and \(k_i\) very likely to coprime with \(e_i\), so suppose we have found a solution \((x,y)\) with extended euclidean algorithm such that
\[e_i \cdot x - k_i \cdot y = 1\]Since \((d_i, phi)\) is also one of the solution for the equation, by the properties of linear diophantine equation,
For some \(c \in \mathbb{Z}\)
\[\begin{aligned} d_i &= y + c \cdot k_i\\ phi &= x + c \cdot e_i\\ \end{aligned}\]The first equation is not so useful for us. For the second one, we can transform it into
\[phi \equiv x \text{ mod } e_i\]Since we have 63 pairs of \((e_i, k_i)\), so
\[\begin{cases} phi \equiv x \text{ mod } e_1\\ phi \equiv x \text{ mod } e_2\\ \dots\\ phi \equiv x \text{ mod } e_{63}\\ \end{cases}\]Now perform CRT to get
\[phi \text{ mod } (e_1 \cdot e_2 \cdot \dots \cdot e_{63})\]After this step, I notice that the \(E = e_1 \cdot e_2 \cdot \dots \cdot e_{63}\) is only 1006 bits. This is not sufficient for us to recover \(phi\) as \(phi\) is 2048 bits.
Also, we do not have any information on the lower bits or upper bits of phi because \(E\) is not divisible by power of 2.
To move on, let’s convert the equation to something useful but with smaller bits.
\[\begin{aligned} c &\equiv phi \text{ mod } E\\ c &\equiv (N - p - q + 1) \text{ mod } E\\ p + q &\equiv N - c + 1 \text{ mod } E \end{aligned}\]Since \(N\) and \(c\) are both known, we can get approximation of \(p+q \text{ mod } E\).
This is useful because \(p+q\) is at most 1025 bits, way lesser than \(phi\). And knowing it means that we can factorise \(N\) .
Final transformation,
\[\begin{aligned} p + q &\equiv x \text{ mod } E \\ p + q &= x + E \cdot k \end{aligned}\]Note that \(k\) must be less than \(1025 - 1006 = 19\) bits
So to find the actual value of \(p + q\) we just have to brute force \(k\).
Once \(p + q\) is found, factorising \(N\) is trivial
Sage script to find p,q
n = 24575303335152579483219397187273958691356380033536698304119157688003502052393867359624475789987237581184979869428436419625817866822376950791646781307952833871208386360334267547053595730896752931770589720203939060500637555186552912818531990295111060561661560818752278790449531513480358200255943011170338510477311001482737373145408969276262009856332084706260368649633253942184185551079729283490321670915209284267457445004967752486031694845276754057130676437920418693027165980362069983978396995830448343187134852971000315053125678630516116662920249232640518175555970306086459229479906220214332209106520050557209988693711
arr = [(65537,36212),(65539,5418),(65543,27200),(65551,37275),(65557,19020),(65563,18986),(65579,30121),(65581,55506),(65587,34241),(65599,35120),(65609,49479),(65617,38310),(65629,65504),(65633,15629),(65647,27879),(65651,6535),(65657,24690),(65677,57656),(65687,58616),(65699,19857),(65701,9326),(65707,8739),(65713,60630),(65717,35109),(65719,47240),(65729,12246),(65731,35776),(65761,23462),(65777,48929),(65789,13100),(65809,10941),(65827,55227),(65831,21264),(65837,36029),(65839,1057),(65843,11772),(65851,30488),(65867,45637),(65881,40155),(65899,42192),(65921,64114),(65927,8091),(65929,5184),(65951,8153),(65957,33274),(65963,17143),(65981,7585),(65983,62304),(65993,58644),(66029,15067),(66037,47377),(66041,35110),(66047,30712),(66067,4519),(66071,53528),(66083,1925),(66089,29064),(66103,32308),(66107,52310),(66109,13040),(66137,27981),(66161,36954),(66169,9902)]
mods = []
vals = []
roots = []
def mult(arr):
res = 1
for i in arr:
res *= i
return res
for i in arr:
mods.append(i[0])
t = xgcd(i[0], -i[1])
vals.append(t[2])
phi = crt(vals, mods)
N = mult(mods)
x = (n - phi + 1) % N
count = 0
while True:
p_plus_q = int(x) + N * count
F.<p> = ZZ[]
f = (p_plus_q - p) * p - n
if (len(f.roots()) != 0):
print(f.roots())
break
count += 1
Script to find flag after knowing p and q
from hashlib import sha512
p = 171823887776209292519493321228755219023175009255195110622647307497341870443014434666845601427385499203400333540040725767709419551347691446599690252231568600428766452893220619476321379858695057145670890344898096557861212360950270158676107428897032154828961726031035925801766641485210298624626739013655188317629
q = 143026116177515987828041940647526671395967499944486647122671304348705870893095386822209597313090170117018866207825081216305902261238513999958328503013758234695405284984667174362118290023851621106497360421553676680838786617409394739766549865486382387391080554313144716298920178020814779020633607861091589038459
if p > q:p,q = q,p
flag = "ACSC{" + sha512( f"{p}{q}".encode() ).hexdigest() + "}"
print(flag)
DSA
It must be twice as powerful as the ordinal one.
Observation
The objective of this challenge is to find the private exponent used for signing.
We are given digital signature of the same message using the same \(k\) (very sus) but different modulus
Solution
Once a value is being taken as a exponent of some \(g\), it is very hard to get back the original exponent (DLP with strong prime).
So we can just ignored all the values that has been raised by power \(g\) (y1 and y2)
We have these 2 equations
\[\begin{aligned} k^{-1}(z + r_1 \cdot x) &\equiv s_1 \text{ mod } p_1\\ k^{-1}(z + r_2 \cdot x) &\equiv s_2 \text{ mod } p_2 \end{aligned}\]where the only unknowns are \(k\) and \(x\)
So we use the trick to solve simultaneous modulo equation.
Rewrite the equations
\[\begin{aligned} k &\equiv (z + r_1 \cdot x)/s_1 \text{ mod } p_1\\ k &\equiv (z + r_2 \cdot x)/s_2 \text{ mod } p_2 \end{aligned}\]Then perform CRT to get
\[k \equiv f(x) \text { mod } (p_1 \cdot p_2)\]\(f(x)\) is thankfully a nice linear function
Since \(p_1 \cdot p_2\) is 1024 bits, \(k, x\) are both 512 bits, we can find bivarate small roots for the equation.
I used defund’s coppersmith script for this last part.
Script to find the combined equations with CRT
g = 4
p1, p2 = 6276170351477662358610296265757659534898563584329624403861678676207084984210281982964595245398676819568696602458985212398017251665201155991266054305219383699, 6592790035600261324619481304533463005761130886111654202136347967085156073379713687101783875841638513262245459729322943177912713281466956529743757383039213839
y1, y2 = 4402230695629594751098609664164747722309480897222957264699530671849221909102875035849237359507796750078710393158944361439911537205013148370997499859214033074, 1681962252704346790535503180583651281903938541944441796556533586799974913619493902209110690623728835694029912753819263510084101226503501626563053650880055759
m = b'omochi mochimochi mochimochi omochi'
r1, s1 = (2059408995750136677433298244389263055046695445249968690077607175900623237060138734944126780231327500254319039236115174790677322287273023749694890125234033630, 705204023016308665771881112578269844527040578525414513229064579516151996129198705744493237004425745778721444958494868745594673773644781132717640592278534802)
r2, s2 = (3246603518972133458487019157522113455602145970917894172952170087044203882577925192461339870709563972992589487629762432781841010769867505736764230484818447604, 2142497127325776381345617721109438439759390966544000203818908086062572965004742554536684765731611856029799528558073686810627789363181741779462572364133421373)
def h(m: bytes) -> int:
return int(sha256(m).hexdigest(), 16)
def crt(vals, mods):
N = 1
res = 0
for i in mods:
N *= i
for i in range(len(mods)):
res += ((N // mods[i]) * inverse(N // mods[i], mods[i]) * vals[i])
return res
q1 = (p1 - 1)//2
q2 = (p2 - 1)//2
F.<k,x> = ZZ[]
eq = [(h(m) + x * r1)/s1, (h(m) + x * r2)/s2]
g = k - crt(eq, [q1, q2])
print(g)
Script to find \((k,x)\) with defund’s script
N = q1 * q2
G = Zmod(N)
F.<k,x> = Zmod(N)[]
f = k - G(531694614462395965093271397376200180548318673453002006041785926852304763015686027564344853695056469964101783067804008628190148659186135013048502680310000634123295901580576509636455194391078031671758562527912670388086404351854774673728765104465456618607588897084427601987941841987078859449738735256204047740558996449799601732032672101414425242681661740568534385206264895712523054280407123398554886981408219087933538698398043769303914081993700953835174993624580697206638028383072998266647427511589787246036927023470199769687194517173908014454494015179194159296060601899321849553145433707463252860438277495029588487477724907945)/24369316024048742020807794670172794836056486372260256257122664723648207275525578061223052729535793577680707442634922008708862786915336316379707528285705443748713589372343051313078888009005999077691949876857223511798101755944700764538406257861663356607304098985858378955230341758625812430858348015479794188889083*x - G(7615220845290791214365189062511551572612753079400380498844052198091117849900996116616977334580544911770575851147960371775159709438022397610539622297850005097789803814299921205576892521474481449222560481434208583288508677442216924474767389658506987303010423563613094006177354660276298691926417744761799250783308745738533528920045454512278723219625477253689796612150482275973928208378929844626436615942319657324887787778659933347142735765477667836813435775460463816349126339888685250977451888470363616839186908338123858013239774260853884642409598)/24369316024048742020807794670172794836056486372260256257122664723648207275525578061223052729535793577680707442634922008708862786915336316379707528285705443748713589372343051313078888009005999077691949876857223511798101755944700764538406257861663356607304098985858378955230341758625812430858348015479794188889083
load("coppersmith.sage")
print(small_roots(f, (2^512, 2^512), m = 5, d = 5))
flag: ACSC{okay_you_must_be_over_twice_as_powerful_as_the_DSA}
Corrupted
My private key was corrupted, luckily I managed to recover some parts. Can you help me to recover the whole private key? I got an important file on my server
Observation
We are given a corrupted pem private RSA key. Some parts of the key are changed to ?. We need to recover the original key
Solution
For information on how to read ASN.1, you can refer to my previous writeup on a similar challenge
First notice that some lines are longer than usual. I didn’t suspect anything at first but I had issues finding the correct offset.
Then only I realise that newline are also converted to ? (This part took me 2 hours)
Convert some of the ? back to new line so that the length are the same.
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnP
NixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD
1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVB
BseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8X
xpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+Rn
JLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQA?AoI?????8S??Om/???xN
3c??0?/G?OO?aQWQB??ECCi??KD?w??2mFc??pTM?r?rX??X+XFW??Rtw?o?d???
ZQ?yp?mczG?q2?0O???1o3?Jt?8?+00s?SY+??MG??7d??7k??o?????ci?K????
?wK??Y??gqV????9????YA?Hh5T????ICP+?3HTU?l???m0y?6??2???b2x?????
?+7??T????????n?7????b?P??iL?/???tq???5jLuy??lX?d?ZEO?7???ld???g
?r?rK??IYA???0???zYCIZt2S???cP??W????f???l5?3c+??UkJr4E?QH??PiiD
WLB???f5A?G?A???????????u???3?K???????I???S?????????J?p?3?N?W???
????r???????8???o???m?????8?s???1?4?l?T?3?j?y?6?F?c?g?3?A?8?S?1?
X?o?D?C?+?7?F?V?U?1?f?K?a?F?7?S?b?V?/?v?5?1?V?A?5?G?y?X?AoGB?L?i
?2?C?t?W?s?Z?h?L?t?3?r?d?M?s?U?E?L?P?n?2?U?G?M?g?D?u?E?s?a?h?K?m
?9?/?n?o?J?8?e?9?9?k?N?2?l?T?8?k?b?e?j?n?Q?u?z?z?e?A?S?6?0?w?5?0
?B?V?i?s?R?W?6?Y?6?u?l?s?G?c?Q?2?Q?w?U?l??GA??V?f???kVYfl???WyY?
3J?2fF?h/???UqfpeO???o?k?9kF??a8L?V?w??????J??9?iP????D???JSx??g
?IUC0??t7???I??c??????eh/No?????y8???0?E+??1?JC?Oj??HFy??2T?1nV?
HH?+???+??s?L?o??K?zc?????BhB2A?????E??b???e?f??KruaZ??u?tp?Tq?c
t?????iQ1qS??h??m?S?/????FDu3i?p???S??Q?o??0s?e0?n?Hv??C?CnM?/Dw
m9?????uC?Ktm????D?e????h7?A??V??O??5/XsY??Y?A???????q?y?gk?Pbq?
????MQK?gQ??SQ?????ERjLp?N??A??P?So?TPE??WWG???lK?Q????o?aztnUT?
eKe4+h0?VkuB?b?v?7ge?nK1??Jy7?y??9??????BP??gG?kKK?y?Z???yES4i??
?Uhc?p????c4ln?m?r???P??C?8?X?d??TP??k??B?dwjN7??ui?K????????-?N? ?S? ?RI?A?? KE?-???-
By manually work out the offset, we can get full N and partial d,p,q,p_d,q_d. I generated multiple 2048 bits RSA as reference to make sure I get it right.
Next I use the branch and prune attack to recover p and q. I just used the solve script from jvdsn/crypto-attacks
Once p and q are found, generated a RSA private key from them and login to the server to get flag
Script to examine the offset and get the partial d,p,q,p_d,q_d
base64_chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
s = "A?AoI?????8S??Om/???xN3c??0?/G?OO?aQWQB??ECCi??KD?w??2mFc??pTM?r?rX??X+XFW??Rtw?o?d???ZQ?yp?mczG?q2?0O???1o3?Jt?8?+00s?SY+??MG??7d??7k??o?????ci?K?????wK??Y??gqV????9????YA?Hh5T????ICP+?3HTU?l???m0y?6??2???b2x??????+7??T????????n?7????b?P??iL?/???tq???5jLuy??lX?d?ZEO?7???ld???g?r?rK??IYA???0???zYCIZt2S???cP??W????f???l5?3c+??UkJr4E?QH??PiiDWLB???f5A?G?A???????????u???3?K???????I???S?????????J?p?3?N?W???????r???????8???o???m?????8?s???1?4?l?T?3?j?y?6?F?c?g?3?A?8?S?1?X?o?D?C?+?7?F?V?U?1?f?K?a?F?7?S?b?V?/?v?5?1?V?A?5?G?y?X?AoGB?L?i?2?C?t?W?s?Z?h?L?t?3?r?d?M?s?U?E?L?P?n?2?U?G?M?g?D?u?E?s?a?h?K?m?9?/?n?o?J?8?e?9?9?k?N?2?l?T?8?k?b?e?j?n?Q?u?z?z?e?A?S?6?0?w?5?0?B?V?i?s?R?W?6?Y?6?u?l?s?G?c?Q?2?Q?w?U?l??GA??V?f???kVYfl???WyY?3J?2fF?h/???UqfpeO???o?k?9kF??a8L?V?w??????J??9?iP????D???JSx??g?IUC0??t7???I??c??????eh/No?????y8???0?E+??1?JC?Oj??HFy??2T?1nV?HH?+???+??s?L?o??K?zc?????BhB2A?????E??b???e?f??KruaZ??u?tp?Tq?ct?????iQ1qS??h??m?S?/????FDu3i?p???S??Q?o??0s?e0?n?Hv??C?CnM?/Dwm9?????uC?Ktm????D?e????h7?A??V??O??5/XsY??Y?A???????q?y?gk?Pbq?????MQK?gQ??SQ?????ERjLp?N??A??P?So?TPE??WWG???lK?Q????o?aztnUT?eKe4+h0?VkuB?b?v?7ge?nK1??Jy7?y??9??????BP??gG?kKK?y?Z???yES4i???Uhc?p????c4ln?m?r???P??C?8?X?d??TP??k??B?dwjN7??ui?K????????"
front = "MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnPNixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVBBseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8XxpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+RnJLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQ"
frontExpanded = ""
for i in front:
frontExpanded += bin(base64_chars.find(i))[2:].zfill(6)
for i in range(len(frontExpanded)//4):
print(hex(int(frontExpanded[i * 4 : (i + 1) * 4], 2))[2:], end='')
print()
expanded = ""
for i in s:
if (i == "?"):
expanded += "?" * 6
else:
expanded += bin(base64_chars.find(i))[2:].zfill(6)
start = 11 * 4
print(expanded[: start])
end = start + (257) * 8
d = expanded[start : end]
start = end + 3 * 8
print(expanded[end: start])
end = start + 129 * 8
p = expanded[start : end]
start = end + 3 * 8
print(expanded[end: start])
end = start + 129 * 8
q = expanded[start : end]
print(expanded[end: end + 3 * 8])
start = end + 3 * 8
end = start + 128 * 8
dp = expanded[start : end]
print(expanded[end: end + 3 * 8])
start = end + 3 * 8
end = start + 128 * 8
dq = expanded[start : end]
n = 0x009fef118f5d5cd893a0c9feacd478a2c2de79de1c3dfa819c775106a3c1f9b493848949cf362c5a20630ad4eec253bf8811ee373c97063cf902b62da4cf9a805c0c975c1300947178eaca6641a405a5545154c643d7222787441712380104564a687dd52e1f45a42298a5faa28fe3a5a61a121e57dcee5d967dcb78d130c5835dd676954106c782126698fdbfa4c7075f55eec3cedf247760123ee35b3aa2afbfc8a34e08aaa6c5f9ba29e3bebff7fecac8366f17c6900da8efde4973fc90ee1a6ce26dc9f8366d6bcef50bd045a5088e7622a009328aa72db5bcc621e9027e4b6503e46724b2f5f6d106e3786e6ce640c2a183c6f5df2842b1f44d98c780daff
print(p)
print(q)
print(d)
print(dp)
print(dq)
Script to find p and q, using the function from branch_and_prune.py
N = 0x009fef118f5d5cd893a0c9feacd478a2c2de79de1c3dfa819c775106a3c1f9b493848949cf362c5a20630ad4eec253bf8811ee373c97063cf902b62da4cf9a805c0c975c1300947178eaca6641a405a5545154c643d7222787441712380104564a687dd52e1f45a42298a5faa28fe3a5a61a121e57dcee5d967dcb78d130c5835dd676954106c782126698fdbfa4c7075f55eec3cedf247760123ee35b3aa2afbfc8a34e08aaa6c5f9ba29e3bebff7fecac8366f17c6900da8efde4973fc90ee1a6ce26dc9f8366d6bcef50bd045a5088e7622a009328aa72db5bcc621e9027e4b6503e46724b2f5f6d106e3786e6ce640c2a183c6f5df2842b1f44d98c780daff
e = 0x10001
p_bits = "????????????????????????????????????????????????????????????????101110??????????????????110111??????001010??????????????????????????????????????????001000??????????????????010010??????????????????????????????????????????????????????001001??????101001??????110111??????001101??????010110??????????????????????????????????????????101011??????????????????????????????????????????111100??????????????????101000??????????????????100110??????????????????????????????111100??????101100??????????????????110101??????111000??????100101??????010011??????110111??????100011??????110010??????111010??????000101??????011100??????100000??????110111??????000000??????111100??????010010??????110101??????010111??????101000??????000011??????000010??????111110??????111011??????000101??????010101??????010100??????110101??????011111??????001010??????011010??????000101??????111011??????010010??????011011??????010101??????111111??????101111??????111001??????110101??????010101??????000000??????111001??????000110??????110010??????010111??????"
q_bits = "1011??????100010??????110110??????000010??????101101??????010110??????101100??????011001??????100001??????001011??????101101??????110111??????101011??????011101??????001100??????101100??????010100??????000100??????001011??????001111??????100111??????110110??????010100??????000110??????001100??????100000??????000011??????101110??????000100??????101100??????011010??????100001??????001010??????100110??????111101??????111111??????100111??????101000??????001001??????111100??????011110??????111101??????111101??????100100??????001101??????110110??????100101??????010011??????111100??????100100??????011011??????011110??????100011??????100111??????010000??????101110??????110011??????110011??????011110??????000000??????010010??????111010??????110100??????110000??????111001??????110100??????000001??????010101??????100010??????101100??????010001??????010110??????111010??????011000??????111010??????101110??????100101??????101100??????000110??????011100??????010000??????110110??????010000??????110000??????010100??????100101"
d_bits = "????????????????111100010010????????????001110100110111111??????????????????110001001101110111011100????????????110100??????111111000110??????001110001110??????011010010000010110010000000001????????????000100000010000010100010????????????001010000011??????110000????????????110110100110000101011100????????????101001010011001100??????101011??????101011010111????????????010111111110010111000101010110????????????010001101101110000??????101000??????011101??????????????????011001010000??????110010101001??????100110011100110011000110??????101010110110??????110100001110??????????????????110101101000110111??????001001101101??????111100??????111110110100110100101100??????010010011000111110????????????001100000110????????????111011011101????????????111011100100????????????101000??????????????????????????????011100100010??????001010??????????????????????????????110000001010????????????011000????????????100000101010010101????????????????????????111101????????????????????????011000000000??????000111100001111001010011????????????????????????001000000010001111111110??????110111000111010011010100??????100101??????????????????100110110100110010??????111010????????????110110??????????????????011011110110110001????????????????????????????????????111110111011????????????010011????????????????????????????????????????????????100111??????111011????????????????????????011011??????001111????????????100010001011??????111111??????????????????101101101010??????????????????111001100011001011101110110010????????????100101010111??????011101??????011001000100001110??????111011??????????????????100101011101??????????????????100000??????101011??????101011001010????????????001000011000000000??????????????????110100??????????????????110011011000000010001000011001101101110110010010??????????????????011100001111????????????010110????????????????????????011111??????????????????100101111001??????110111011100111110????????????010100100100001001101011111000000100??????010000000111????????????001111100010100010000011010110001011000001??????????????????011111111001"
dp_bits = "????????????010101??????011111??????????????????100100010101011000011111100101??????????????????010110110010011000??????110111001001??????110110011111000101??????100001111111??????????????????010100101010011111101001011110001110??????????????????101000??????100100??????111101100100000101????????????011010111100001011??????010101??????110000????????????????????????????????????001001????????????111101??????100010001111????????????????????????000011??????????????????001001010010110001????????????100000??????001000010100000010110100????????????101101111011??????????????????001000????????????011100????????????????????????????????????011110100001111111001101101000??????????????????????????????110010111100??????????????????110100??????000100111110????????????110101??????001001000010??????001110100011????????????000111000101110010????????????110110010011??????110101100111010101??????000111000111??????111110??????????????????111110????????????101100??????001011??????101000????????????001010??????110011011100??????????"
dq_bits = "01100001000001110110000000??????????????????????????????000100????????????011011??????????????????011110??????011111????????????001010101011101110011010011001????????????101110??????101101101001??????010011101010??????011100101101??????????????????????????????100010010000110101101010010010????????????100001????????????100110??????010010??????111111????????????????????????000101000011101110110111100010??????101001??????????????????010010????????????010000??????101000????????????110100101100??????011110110100??????100111??????000111101111????????????000010??????000010100111001100??????111111000011110000100110111101??????????????????????????????101110000010??????001010101101100110????????????????????????000011??????011110????????????????????????100001111011??????000000????????????010101????????????001110????????????111001111111010111101100011000????????????011000??????000000??????????????????????????????????????????101010??????110010??????100000100100??????001111011011101010??????????????????????????????00110001"
print(factorize_pqddpdq(N, e, PartialInteger.from_bits_be(p_bits), PartialInteger.from_bits_be(q_bits), PartialInteger.from_bits_be(d_bits), PartialInteger.from_bits_be(dp_bits), PartialInteger.from_bits_be(dq_bits)))
flag: ACSC{R3c0vEr_F4ctOr5_fROm_Kn0wn_b17$s!}
SusCipher
I made SusCipher, which is a vulnerable block cipher so everyone can break it! Please, try it and find a key. Hint: Differential cryptanalysis is useful.
Observation
The server is running a 3 round Substitution-Permutation Network cipher. We need to find the key and send it to the server to get the help.
Also the author hinted to use differential cryptanalysis, so I just use that in the end.
Solution
I mostly just followed this paper to implement the attack.
I think the paper explains the concept of differential cryptanalysis better than I do so I will just skip the explaination.
What’s different from this cipher and the standard Substitution-Permutation Network cipher is that the last round is permuted before xor with the key again. That increases the number of dirty SBox in the last round.
The gist of how I solved it is I try different delta and filter out the possible keys until I get a unique key for each round.
I also had issues with timeout and did some weird optimisation to speed up the code lol.
In the end I used pypy3 and it takes around 4 minutes to get the flag 😅. Also it fails half of the time.
Abit clutch but yeah, I am happy that I solved the challenge in time.
6 hours spend on implementation, 2 hours spend on optimisation.
Solve script
import random
from pwn import *
def blockToInt(block: list[int]) -> int:
res = 0
for v in block:
res <<= 6
res |= v
return res
def intToBlock(v: int) -> list[int]:
l: list[int] = []
for _ in range(8):
l.append(v & 0b111111)
v >>= 6
return l[::-1]
def isEqual(a, b):
equal = len(a) == len(b)
for i in range(len(a)):
equal &= a[i] == b[i]
return equal
class SusCipher:
S = [
43, 8, 57, 53, 48, 39, 15, 61,
7, 44, 33, 9, 19, 41, 3, 14,
42, 51, 6, 2, 49, 28, 55, 31,
0, 4, 30, 1, 59, 50, 35, 47,
25, 16, 37, 27, 10, 54, 26, 58,
62, 13, 18, 22, 21, 24, 12, 20,
29, 38, 23, 32, 60, 34, 5, 11,
45, 63, 40, 46, 52, 36, 17, 56
]
US = [24, 27, 19, 14, 25, 54, 18, 8,
1, 11, 36, 55, 46, 41, 15, 6, 33,
62, 42, 12, 47, 44, 43, 50, 45,
32, 38, 35, 21, 48, 26, 23, 51,
10, 53, 30, 61, 34, 49, 5, 58,
13, 16, 0, 9, 56, 59, 31, 4,
20, 29, 17, 60, 3, 37, 22,
63, 2, 39, 28, 52, 7, 40, 57]
P = [
21, 8, 23, 6, 7, 15,
22, 13, 19, 16, 25, 28,
31, 32, 34, 36, 3, 39,
29, 26, 24, 1, 43, 35,
45, 12, 47, 17, 14, 11,
27, 37, 41, 38, 40, 20,
2, 0, 5, 4, 42, 18,
44, 30, 46, 33, 9, 10
]
ROUND = 3
BLOCK_NUM = 8
MASK = (1 << (6 * BLOCK_NUM)) - 1
@classmethod
def _divide(cls, v: int) -> list[int]:
l: list[int] = []
for _ in range(cls.BLOCK_NUM):
l.append(v & 0b111111)
v >>= 6
return l[::-1]
@classmethod
def _sub(cls, block: list[int]) -> list[int]:
return [cls.S[v] for v in block]
@classmethod
def _unsub(cls, block: list[int]) -> list[int]:
return [cls.US[v] for v in block]
@classmethod
def _perm(cls, block: list[int]) -> list[int]:
bits = ""
for b in block:
bits += f"{b:06b}"
buf = ["_" for _ in range(6 * cls.BLOCK_NUM)]
for i in range(6 * cls.BLOCK_NUM):
buf[cls.P[i]] = bits[i]
permd = "".join(buf)
return [int(permd[i : i + 6], 2) for i in range(0, 6 * cls.BLOCK_NUM, 6)]
@classmethod
def _unperm(cls, block: list[int]) -> list[int]:
bits = ""
for b in block:
bits += f"{b:06b}"
buf = ["_" for _ in range(6 * cls.BLOCK_NUM)]
for i in range(6 * cls.BLOCK_NUM):
buf[i] = bits[cls.P[i]]
permd = "".join(buf)
return [int(permd[i : i + 6], 2) for i in range(0, 6 * cls.BLOCK_NUM, 6)]
@staticmethod
def _xor(a: list[int], b: list[int]) -> list[int]:
return [x ^ y for x, y in zip(a, b)]
def best(self, v):
total = 0
maxi = 0
maxiIndex = 0
for i in range(len(self.diffTable[v])):
total += self.diffTable[v][i]
if (self.diffTable[v][i] > maxi):
maxi = self.diffTable[v][i]
maxiIndex = i
return maxiIndex, maxi/total
def simulate(self, block, round) -> int:
prob = 1
for r in range(round - 1):
for i in range(8):
block[i], p = self.best(block[i])
prob *= p
block = self._perm(block)
dirty = [0b111111 if i != 0 else 0 for i in block]
dirty = self._perm(dirty)
return block, prob, dirty
def decOne(self, block, k):
block = self._xor(block, k)
block = self._unperm(block)
block = self._unsub(block)
return block
def __init__(self, diffTable):
self.diffTable = diffTable
S = [
43, 8, 57, 53, 48, 39, 15, 61,
7, 44, 33, 9, 19, 41, 3, 14,
42, 51, 6, 2, 49, 28, 55, 31,
0, 4, 30, 1, 59, 50, 35, 47,
25, 16, 37, 27, 10, 54, 26, 58,
62, 13, 18, 22, 21, 24, 12, 20,
29, 38, 23, 32, 60, 34, 5, 11,
45, 63, 40, 46, 52, 36, 17, 56
]
diffTable = [[0 for _ in range(2**6)] for _ in range(2**6)]
for i in range(2**6):
for j in range(2**6):
diffTable[i ^ j][S[i] ^ S[j]] += 1
useful = []
for i in range(2**6):
for j in range(2**6):
if (diffTable[i][j] == 8):
useful.append((i, j))
cipher = SusCipher(diffTable)
r = remote("suscipher-2.chal.ctf.acsc.asia", 13579)
realKeys = []
for round in range(3, 0, -1):
print(realKeys)
keys = [0 for _ in range(8)]
arr = []
for i in range(len(useful)):
for j in range(8):
block = [0 for _ in range(8)]
block[j] = useful[i][0]
block, p, dirty = cipher.simulate(block, round)
arr.append((i, j, block, p, dirty))
arr.sort(key=lambda x:-x[3])
while True:
checkKey = True
for i in range(8):
if not (isinstance(keys[i], set) and len(keys[i]) == 1):
checkKey = False
break
if (checkKey):
break
maxi = 0
mini = 100000000000000000
index = 0
for j in range(len(arr)):
elem = arr[j]
if (elem[3] < 0.01):
continue
iterations = 1
for i in range(8):
if (elem[4][i] != 0):
if (keys[i] == 0):
iterations *= 2**6
else:
iterations *= len(keys[i])
if (iterations == 1): continue
if (iterations < 2**17):
index = j
maxi = 2**19
break
maxi = max(maxi, iterations)
if (iterations < mini):
index = j
mini = iterations
if (maxi <= 2**18):
index = 0
elem = arr[index]
del arr[index]
print(elem)
keysCandidate = {}
minCount = 1000000000000
minmm = 1000
while True:
r.recvuntil("> ")
p1 = [random.getrandbits(6) for _ in range(8)]
p2 = p1.copy(); p2[elem[1]] ^= useful[elem[0]][0]
r.sendline(str(blockToInt(p1)).encode() + b"," + str(blockToInt(p2)).encode())
c1, c2 = map(intToBlock, map(int, r.recvline().split(b',')))
for i in range(3 - round):
c1 = cipher.decOne(c1, realKeys[i])
c2 = cipher.decOne(c2, realKeys[i])
candidate = True
for i in range(8):
if (elem[4][i] == 0 and c1[i] != c2[i]):
candidate = False
test = cipher._xor(c1, c2)
test = cipher._unperm(test)
for i in range(8):
if (diffTable[elem[2][i]][test[i]] == 0):
candidate = False
if (not candidate):
continue
def func(index, subkeys):
if (index == 8):
cc1 = c1.copy()
cc2 = c2.copy()
cc1 = cipher.decOne(cc1, subkeys)
cc2 = cipher.decOne(cc2, subkeys)
check = cipher._xor(cc1, cc2)
if (isEqual(check, elem[2])):
t = blockToInt(subkeys)
if t not in keysCandidate:
keysCandidate[t] = 0
keysCandidate[t] += 1
return
if (elem[4][index] == 0):
func(index + 1, subkeys)
elif (keys[index] == 0):
for i in range(2**6):
subkeys[index] = i
func(index + 1, subkeys)
else:
for i in keys[index]:
subkeys[index] = i
func(index + 1, subkeys)
func(0, [0 for _ in range(8)])
mm = 0
for i in keysCandidate:
mm = max(mm, keysCandidate[i])
print("maximum", mm)
count = 0 if mm != 0 else 10000000
for i in keysCandidate:
if (keysCandidate[i] == mm):
count += 1
print("count", count)
if (count < minCount):
minmm = mm
minCount = count
dic = {}
if (mm >= 4):
for i in keysCandidate:
if (keysCandidate[i] == mm):
t = intToBlock(i)
for j in range(8):
if (elem[4][j] != 0):
if (j not in dic):
dic[j] = set()
dic[j].add(t[j])
for i in dic:
if (keys[i] == 0):
keys[i] = dic[i]
else:
keys[i] = keys[i].intersection(dic[i])
print(keys)
break
oneRealKey = []
for i in range(8):
oneRealKey.append(list(keys[i])[0])
realKeys.append(oneRealKey)
r.recvuntil("> ")
p1 = [0 for _ in range(8)]
r.sendline(str(blockToInt(p1)).encode())
c = intToBlock(int(r.recvline()))
for i in range(3):
c = cipher.decOne(c, realKeys[i])
r.sendline(str(blockToInt(cipher._xor(c, p1))))
r.interactive()
flag: ACSC{There_may_be_a_better_solution_to_solve_this_but_I_used_diff_analysis_:(}