TJ CTF 2024
Lightweight Crypto Guard System [220 pts]
They said OTPs were too simple.
Before you begin reading this writeup, I highly, highly recommend you read this post to better understand LCG cracking, it’s a very informative post.
Anyways, here’s the out.txt and the source code for this challenge:
123855601
1877660078
2332452388
2265666365
2173629406
2460275121
n = 987
1206854768 2992162445 3135492212 887994692 534230744 1943570677 4075068186 2588097251 1919066614 3141628272 2820004859 3943659937 507477506 3325988700 1973806154 3297149759 3342769118 2237197104 214875713 1971810277 308098372 1329057967 4001561791 4071836506 2137131459 3511584640 3870166967 1871343251 65352411 1357942164 3460110072 2827539493 1519378450 1997667329 943836747 3140107620 4187030116 1999810548 3507465171 2498552067 1656529038 1144473747 2107635247 462808704 2817568665 2609416923 1861071513 2149240870 4031669371 341119412 3822349094 4128738655 1784294991 670824691 3015500585 3834352161 1327326305 1158101900 3617921101 2867451082 1339948485 3745091722 2632776423 4156371585 1333152448 2503110679 3891380014 3384289405 2442119134 980158389 696237731 2049377746 1229491184 1669461342 1296836903 3412495574 939394151 1937096740 3861124598 2766018653 2917429608 649064533 926827932 3870228763 777013275 3932568858 428472071 389190794 3125535656 4047810152 4122034269 4225394560 3300846052 2020417643 3681379766 955145273 1033071663 4070943374 725489858 2001566661 787585949 2730053969 3107670800 383735110 604763880 1712661692 2855824824 1157583316 2357301460 1600155792 2452875946 2784397385 4161763206 2691752766 1190706431 947568400 1815062243 811913616 483330983 1419779375 812916680 3577543624 1799687575 521111208 1633702612 2436067413 1377696153 288048399 1531149718 3498214442 2572585561 464222958 1060533594 4061534051 515038774 866953577 435965399 1961350 3911429171 824066962 2928252188 2942822710 3643092546 4013506041 2829361953 2868020557 1135042534 138384457 56255147 3542673334 2067426705 2427475497 1570622368 2287003201 1280280405 90880459 2769189058 1611159458 2905940692 611985708 2115801377 4269407573 524359605 3464881874 60458966 2802015237 201280209 3168269375 3414490619 740237968 131905878 142984738 80226227 3682480712 2825213868 2661796218 3854495440 3587600740 3564880604 2303161177 1216960595 1351616451 2253047403 1510185890 2746788835 1635520599 3882647944 3855503274 4076942487 2347589606 3277914966 2694389396 1427825891 1805598172 648961706 447334511 4040118070 2253845050 1974619538 1112067129 700651884 2343331489 406281601 1502222687 1244888582 1236247187 3857149455 3667021946 570480595 2901172206 2889447597 381484664 3532152292 3895143189 1519810824 1412862858 3328608041 145690491 1148264912 3359575847 3346469556 1926666828 1118983375 4194567615 369314703 84344309 2611086251 1689492167 964339284 1504335868 2700554813 635274834 36143442 592775951 3130244551 2283522884 630870234 33047478 3558317765 690579270 1163837241 1358788745 2770905350 3855778228 3818048456 253448982 2393084830 1899122952 1141035301 1771381366 1684995798 3965871136 3076376621 56778883 2680564527 2059836209 1372833858 620819944 4218008777 2186309229 3052649657 2364127948 1415476904 3312329754 2850755499 2302113487 22735352 3611394103 3170611825 927607441 1940365361 2205843362 2513740411 3407322203 683838309 1737474539 1142368874 1854858867 2409280008 725521114 576899863 2230210465 3236971865 3592105094 3412161456 3318158915 1131913590 2054125253 1601661815 1477336963 165370762 2367124720 698761982 3326457157 1542376443 3514733674 116026773 950103422 1442568566 2628155113 2916420438 2563013321 4176707190 1789973210 3060866592 426992729 2942571130 2204114159 591703364 3089201803 2079887398 773202857 1594224113 2253083530 93400828 318518719 1089285192 2666263389 1022292040 1959452804 3945323873 2330000636 1887003857 2353870750 1266850147 9897949 3259536466 3079650476 3433812957 2931132492 2548990947 2617476325 446678387 2668073104 1495534718 3362709114 2964487356 153081052 1578973485 3223803701 1315336534 2388952771 601583867 1688606067 799640042 106761166 1654891822 720686154 2536616647 1203502079 2362007208 2578184895 2756768110 73869295 3524414326 369646680 2128274052 4215090008 3571888749 4207401791 2043044856 33931465 1709658027 2026551704 1663833215 560036349 4152363056 4092462798 3726411125 3583748543 148450488 2406844104 551363976 3817412412 1460410027 1526854403 3982982647 851880073 2125732055 2209319597 3016140804 9417605 1541846475 154627250 392190208 2633096549 2811218199 860365804 672357262 674825005 2114729849 3970573195 4154761243 3309073018 141320864 2231676566 647853021 2023163800 1416538745 834858730 3001219627 495632546 2387798079 560830113 1701930668 2903198396 3850041740 2578518128 3619707754 348588616 3045962853 670902144 3759673327 1585249615 2315906484 4225900190 1298052772 2765819136 4153494011 762952302 4264530540 4247299082 3530470660 3297463211 3893758805 2070808879 742770830 122719496 161362782 270134154 1850361202 2650314190 689199410 3962030476 515378348 2111693246 541242012 2416580590 3907232782 1314378938 3120346798 382998025 2026262686 638146766 2955405248 1657103434 952120788 1961582015 2121260142 975792828 3746692866 4088415380 2030854952 1901822201 1260294343 57445446 2187915893 2090792552 1328413894 732501507 3435831801 2554758554 1616733300 1031946679 2730109316 1325042612 315666628 3304267688 3975562773 743660191 1385888427 106499189 367681157 1081031135 2942911342 2308032058 3962558505 2055026112 1181296861 2615488861 1970136582 3252716821 176589894 2671649906 1713320736 388342305 1991680063 206590977 3247224207 2460605403 221831261 3486179057 3126257669 2268306866 3368349677 817578838 1840351834 2628856010 3702164161 220111670 1429794258 651591723 2780348614 3288461626 1807342088 747276403 2651229209 646560089 1054900830 1187970860 3920239091 674006403 3609889089 819827407 1908006902 601071029 2341864889 3385150935 3981338037 2623852859 3873393331 1193579864 407675281 331459699 1029705123 1417574303 4003923709 1646594228 2709207007 1874714092 579516848 1687534129 3779383523 1382404787 2894511173 3311341887 3522861840 1957606935 1338693480 1552929150 1072085095 1223066639 4130301832 233298632 2753036032 2467423284 1201662523 3363139050 291997781 3510414043 335040191 3977224935 518500026 1184956656 339997938 1047045299 4138077069 1407278295 1400746455 3923785634 4068068876 2710353937 2412644583 1579659461 3566156931 2170948283 3531989436 3632367078 3357817878 2678094228 1161577400 3773273574 4169912546 1810823659 3651086911 2658218045 1518914671 171582199 3826092583 2117537084 3003089037 3944674868 286436215 328572397 128074409 4056792834 814159637 3407916272 632721698 3001340411 2213754276 920374882 2750248333 485219143 2817345168 2216155891 1161609536 2949171533 2609313292 4096381413 201373085 3750892204 1411461241 3248106952 2154562468 1903624992 2829884530 1178821031 2078960433 3973253710 3483836815 45731347 2756986768 2372174858 2088373193 2923589247 3935527827 999300813 2597736569 1579411494 2328456248 2699496808 1949043287 414740969 3731131259 71316277 3859841902 2755965078 2097069843 4208970656 3226762988 616684700 1805597411 2099193957 1316130119 455120562 2341859645 3195700671 2834829365 101841062 3709056795 2292093735 3847170828 3557788340 234513576 1932539699 2576934124 854820799 3327022158 2644798880 179449306 2860085076 3272608711 3212018300 551362386 1948750578 875109035 372352553 19323968 1783192086 2189881165 3074610544 1934315671 4255287854 1471470781 2296190851 1987469089 3430289283 1277328926 3457696008 1585704443 1943463401 1167206249 3996323441 2646399071 2696106538 338946568 3245897694 4214350374 519129723 1361630564 278822118 565080912 593813151 3143149002 706159445 2987133597 3610024303 2343641608 4116932120 3492148555 2468865091 3572072557 1970360355 3976198715 349204322 515416796 54113183 1760788010 2821501073 2434521416 1360539602 3236961172 1956757164 2305482806 2953306996 2883563547 3340299505
#!/usr/local/bin/python3.10 -u
from Crypto.Util.number import *
import random
a = getRandomNBitInteger(30)
c = getRandomNBitInteger(15)
m = getPrime(32)
x0 = getRandomNBitInteger(30)
n = random.randint(2**8, 2**10)
flag = open("flag.txt").read().strip()
class Random():
global m, a, c
def __init__(self, x0):
self.x0 = x0
def random(self):
self.x0 = (a*self.x0+c) % m
return self.x0
encryptor = Random(x0)
assert m < 2**32
assert isPrime(m)
x = [ord(i) for i in flag]
with open("out.txt", "w") as wfile:
for ind in range(len(x)):
next = encryptor.random()
if ind < 6:
print(str(next))
wfile.write(str(next) + "\n")
for __ in range(n-1):
x[ind] ^= encryptor.random()
print(f"n = {n}")
print(" ".join([str(i) for i in x]))
wfile.write("n = " + str(n) + "\n")
wfile.write(" ".join([str(i) for i in x]) + "\n")
So, the Random function is pretty much just your standard LCG. There are a few key things to note:
-
The initial state (x0), multiplier (a), increment (c), and modulus (m) are all unknown.
-
The encryption for loop calls encryptor.random() 186 times between the 6 provided states at the top of out.txt, i.e. the second output is the 187th .random() call after the first output, and so on.
-
The challenge at hand requires us to figure out a, c, and m, because we need to know all the numbers generated by the LCG and used to XOR with our flag bytes. Notably, we don’t need to know the intial state because we are provided the first state after the initial state (the very first provided state at the top of out.txt), which is enough to figure out everything after that state once we have a, c, and m.
modulus
The first step (as outlined in the previously linked site) of breaking this LCG is to find the modulus m. How can we do that?
Well, we can actually follow very similar steps in breaking standard LCGs (where we are provided 6 consecutive states) to get m. Time for some math!
Let us define s0, s1, etc. to be the provided states of the LCG. Then, we can write:
Note that these derivations come from going through the math for the first few states of the LCG.
From these initial equations, we can derive the following:
\[t0 = s1 - s0\] \[t1 = s2 - s1 = (a^n)(s1 - s0) \;(mod \;m)\] \[t2 = s3 - s2 = (a^n)(s2 - s1) \;(mod \;m)\] \[t2 \cdot t0 - t1 \cdot t1 = (a^n)(s2 - s1)(s1 - s0) - (a^{2n})(s1 - s0)(s1 - s0) \;(mod \;m)\] \[t2 \cdot t0 - t1 \cdot t1 = (a^n)(a^n)(s1 - s0)(s1 - s0) - (a^{2n})(s1 - s0)(s1 - s0) = 0 \;(mod \;m) = k*m\]where k is some integer.
We can extend this to any expression \(t_{r+2} \cdot t_{r} - t_{r + 1} \cdot t_{r + 1}\)
where r is some integer >= 0
Because we know that expression will be equal to a multiple of m.
Through this, by taking the GCD of this expression for a few different values of r, we can get the modulus! Also, it turns out this site’s function for doing so does the exact thing we want it too!
multiplier
Now let’s find the multiplier. Take a look at this equation:
\[t1 = s2 - s1 = (a^n)(s1 - s0) \;(mod \;m)\]Well, we can pretty easily solve for a^n:
\[a^n = \frac{s2 - s1}{s1 - s0} \;(mod \;m)\]Now that we have the modulus, we can simply calculate the inverse for the modulus of \(s1 - s0\)
\[a^n = (s2 - s1) \cdot inverse(s1 - s0) \;(mod \;m)\]Perfect! So now we have a^n. Now… how do we calculate a?
I’m sure there’s a smart solution to this, but uh… a is only 30 bits.
…
Yeah I just brute-forced it: (only took like 10 minutes)
for a in trange(1<<30):
if pow(a, n, m) == a_power_n:
print(a)
Sweet, now we have the multiplier!
increment
Do you enjoy using your brain to solve crypto challenges? Not me!
for c in trange(1<<15):
lcg = Random(states[0])
for _ in range(n-1):
lcg.random()
res = lcg.random()
if res == states[1]:
print(c)
break
Only 15 bits for the increment, and only 187 calls to lcg.random(), so easy brute-force!
WIN
Now that we have the modulus, multiplier, and increment, we can just iterate forward from the very first state we were provided, do the same encryption process on the ciphertext (since XOR encryption == decryption) and get the flag!
Here’s my full implementation:
from functools import reduce
from Crypto.Util.number import *
from tqdm import trange
states = [123855601,1877660078,2332452388,2265666365, 2173629406,2460275121]
n = 987
class Random():
global m, a, c
def __init__(self, x0):
self.x0 = x0
def random(self):
self.x0 = (a*self.x0+c) % m
return self.x0
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(GCD, zeroes))
return modulus
def crack_unknown_multiplier(states, modulus):
multiplier = (states[2] - states[1]) * inverse(states[1] - states[0], modulus) % modulus
return multiplier
m = crack_unknown_modulus(states)
a_power_n = crack_unknown_multiplier(states, m)
# NOTE: find a
# for a in trange(1<<30):
# if pow(a, n, m) == a_power_n:
# print(a)
a = 779849675
# NOTE: find c
# for c in trange(1<<15):
# lcg = Random(states[0])
# for _ in range(n-1):
# lcg.random()
# res = lcg.random()
# if res == states[1]:
# print(c)
# break
c = 23327
out = # ommitted because very long
lcg = Random(states[0])
for i in range(len(out)):
if i != 0:
lcg.random()
for _ in range(n - 1):
out[i] ^= lcg.random()
print(''.join(map(chr, out)))
tjctf{1t_15_a_p3r1od_of_c1v1l_war5_1n_th3_galaxy._a_brav3_all1anc3_of_und3rground_fr33dom_f1ght3r5_ha5_chall3ng3d_th3_tyranny_and_oppr3551on_of_th3_aw35om3_galact1c_3mp1r3._5tr1k1ng_from_a_fortr355_h1dd3n_among_th3_b1ll1on_5tar5_of_th3_galaxy,_r3b3l_5pac35h1p5_hav3_won_th31r_f1r5t_v1ctory_1n_a_battl3_w1th_th3_pow3rful_1mp3r1al_5tarfl33t._th3_3mp1r3_f3ar5_that_anoth3r_d3f3at_could_br1ng_a_thou5and_mor3_5olar_5y5t3m5_1nto_th3_r3b3ll1on,_and_1mp3r1al_control_ov3r_th3_galaxy_would_b3_lo5t_for3v3r._to_cru5h_th3_r3b3ll1on_onc3_and_for_all,_th3_3mp1r3_15_con5truct1ng_a_51n15t3r_n3w_battl3_5tat1on._pow3rful_3nough_to_d35troy_an_3nt1r3_plan3t,_1t5_compl3t1on_5p3ll5_c3rta1n_doom_for_th3_champ1on5_of_fr33dom.}