SUSCTF 2022
| Challenge Name | Tags |
|---|---|
| large case | rsa |
| ez pager typer | lfsr |
large case
from Crypto.Util.number import *
from secret import e,message
def pad(s):
if len(s)<3*L:
s+=bytes(3*L-len(s))
return s
L=128
p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n=p*q*r
assert isPrime(GCD(e,p-1)) and isPrime(GCD(e,q-1)) and isPrime(GCD(e,r-1)) and e==GCD(e,p-1)*GCD(e,q-1)*GCD(e,r-1)
assert len(message)>L and len(message)<2*L
assert b'SUSCTF' in message
m=bytes_to_long(pad(message))
c=pow(m,e,n)
print(c)
'''
2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
'''
The flag is padded with trailing null bytes and encrypted with RSA using three primes. $e$ is however unknown.
solution
We are given that for each of the primes $p, q, r$, $gcd(e, prime - 1)$ is a prime number, meaning it cannot be 1. We are also told that the product of these gcd’s for each prime is $e$ itself, meaning that $e$ is comprised of a prime factor from each of $p-1, q-1, r-1$.
To figure out what prime factor this is, recall Fermat’s Little Theorem, which states that:
\[a^{p-1} \equiv 1 \mod p\]Let the prime factor of $p-1$ that makes up the exponent be $e_p$. We are given $c^{e_p}$ for some unknown $c$. If we raise this to a power $x$ such that $e_p * x = p - 1$, then the result should be 1. Since $e_p$ is a factor of $p-1$, we can enumerate all factors of $p-1$ and then raise $c^{e_p}$ to the power of $\frac{p-1}{e_p}$, and see if the result is equal to 1. If so, we know that our guess for $e_p$ is correct.
p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
c=2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
pfac = [7, 757, 1709, 85015583, 339028665499, 149105250954771885483776047, 1642463892686572578602085475101104723805585678675707586553009837707279291648160744722745420570786735582631019452016654157586623543454908938807521637550223579103317696104438456966780396624343550451096013730928292041667133825444056448136643704677066463120079]
qfac = [3, 66553, 84405986771, 38037107558208320033, 16137718604846030589135490851713, 14369576056311038198362075935199486201201115381094289671031774994452214307042971166730146897009438957078052300683916910041250723573953110349566216311685009675744215421971185909678546052934704709232060199286321405045769976194110037]
rfac = [5156273, 10012111, 11607389, 68872137169799749, 9691125310820433463, 12030248809636768339, 31518759824860728158228953, 36076471911113920369056477734714059]
pr = {p: pfac, q: qfac, r: rfac}
e = 1
for prime, facs in pr.items():
print(prime)
for fac in facs:
if pow(c, (prime-1)//fac, prime) == 1:
print("found factor:", fac)
e *= fac
print("e:", e)
127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
found factor: 757
145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
found factor: 66553
165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
found factor: 5156273
So, now we have the value of $e$, how do we get the flag?
We’ll need to take the e’th root mod each of these primes, and then combine them with CRT to get possible values for the flag, which we can then check for SUSCTF to get the right one. The issue here is that there will exist $e$ possible roots after combining with CRT, which will be far too many to search through, given that $e$ is around 48 bits long.
We can use a bit more information in the code to help us out though. We are given that: assert len(message)>L and len(message)<2*L
This means that, because of the pad function, the padded message will end in 128 null bytes, which gives us 1024 bits of information and therefore only requires us to find 2048 more bits. We can get these bits by only taking roots mod $p$ and $q$, which there will be $757 * 66553 = 50380621$ possible roots of, and then combining all the information we have with CRT, we should be able to get a bunch of possible flags.
The code for the n’th root algorithm was taken from here. Solve script runs in about 30 minutes.
import random
def AMM(o, r, q):
start = time.time()
print('\n----------------------------------------------------------------------------------')
print('Start to run Adleman-Manders-Miller Root Extraction Method')
print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
g = GF(q)
o = g(o)
p = g(random.randint(1, q))
while p ^ ((q-1) // r) == 1:
p = g(random.randint(1, q))
print('[+] Find p:{}'.format(p))
t = 0
s = q - 1
while s % r == 0:
t += 1
s = s // r
print('[+] Find s:{}, t:{}'.format(s, t))
k = 1
while (k * s + 1) % r != 0:
k += 1
alp = (k * s + 1) // r
print('[+] Find alp:{}'.format(alp))
a = p ^ (r**(t-1) * s)
b = o ^ (r*alp - 1)
c = p ^ s
h = 1
for i in range(1, t):
d = b ^ (r^(t-1-i))
if d == 1:
j = 0
else:
print('[+] Calculating DLP...')
j = - discrete_log(d, a)
print('[+] Finish DLP...')
b = b * (c^r)^j
h = h * c^j
c = c^r
result = o^alp * h
end = time.time()
print("Finished in {} seconds.".format(end - start))
print('Find one solution: {}'.format(result))
return result
def findAllPRoot(p, e):
print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
start = time.time()
proot = set()
c = 0
while len(proot) < e:
c += 1
if c % 5000 == 0: # just to keep track of how many roots left
print(len(proot))
proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
end = time.time()
print("Finished in {} seconds.".format(end - start))
return proot
def findAllSolutions(mp, proot, cp, p, e):
print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
start = time.time()
all_mp = set()
for root in proot:
mp2 = mp * root % p
if (pow(mp2, e, p) == cp):
all_mp.add(mp2)
end = time.time()
print("Finished in {} seconds.".format(end - start))
return all_mp
def find_roots(_c, _e, _p):
mp = AMM(_c, _e, _p)
p_proot = findAllPRoot(_p, _e)
mps = findAllSolutions(mp, p_proot, _c, _p, _e)
return mps
p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
e = 259776235785533
c = 2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
import time
import random
from math import gcd
from tqdm import tqdm
from Crypto.Util.number import long_to_bytes
ep = gcd(e, p-1)
eq = gcd(e, q-1)
dp = pow(e//ep, -1, p-1)
dq = pow(e//eq, -1, q-1)
cp = pow(c, dp, p)
cq = pow(c, dq, q)
proots = list(find_roots(cp, ep, p))
print(len(proots))
qroots = list(find_roots(cq, eq, q)) # takes about 10 minutes
print(len(qroots))
qrootadd = [CRT([0, int(root)], [1<<1024, q]) for root in qroots] # precompute these
n1 = p
n2 = q*(1<<1024)
k1 = int(pow(n1, -1, n2))
k2 = int(pow(n2, -1, n1))
n3 = n1 * n2
def crt(a, b, n1, n2): # optimization since the moduli remain the same
return (a*k2*n2 + b*k1*n1) % n3
for proot in tqdm(proots):
for qroot in qrootadd:
m = crt(int(proot), int(qroot), p, q*<<1024)
if b'SUSCTF'.hex() in hex(m):
print(long_to_bytes(m))
For RSA, the wrong key generation method can also reveal information. You recover my secret message, and here is the flag:SUSCTF{N0n_c0prime_RSA_c1pher_cAn_a1s0_recover_me33age!!!}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
Flag: SUSCTF{N0n_c0prime_RSA_c1pher_cAn_a1s0_recover_me33age!!!}
ez pager typer
class lfsr():
def __init__(self, seed, mask, length):
self.length_mask = 2 ** length - 1
self.mask = mask & self.length_mask
self.state = seed & self.length_mask
def next(self):
next_state = (self.state << 1) & self.length_mask
i = self.state & self.mask & self.length_mask
output = 0
while i != 0:
output ^= (i & 1)
i = i >> 1
next_state ^= output
self.state = next_state
return output
def getrandbit(self, nbit):
output = 0
for _ in range(nbit):
output = (output << 1) ^ self.next()
return output
class generator():
def __init__(self, lfsr1, lfsr2, magic):
self.lfsr1 = lfsr1
self.lfsr2 = lfsr2
self.magic = magic
def infinit_power(self, magic):
return int(magic)
def malicious_magic(self, magic):
now = (-magic & magic)
magic ^= now
return int(now), int(magic)
def confusion(self, c1, c2):
magic = self.magic
output, cnt = magic, 0
output ^= c1 ^ c2
while magic:
now, magic = self.malicious_magic(magic)
cnt ^= now >> (now.bit_length() - 1)
output ^= now
output ^= cnt * c1
return int(output)
def getrandbit(self, nbit):
output1 = self.lfsr1.getrandbit(nbit)
output2 = self.lfsr2.getrandbit(nbit)
return self.confusion(output1, output2)
from Crypto.Util.number import *
from secret import mask1, mask2, seed1, seed2, seed3
n1, n2 = 64, 12
flag = 'SUSCTF{***}'
def encrypt(cipher, ipath, opath):
ifile=open(ipath,'rb')
ofile=open(opath,'wb')
plaintext=ifile.read()
for ch in plaintext:
c=ch^cipher.getrandbit(8)
ofile.write(long_to_bytes(c))
ifile.close()
ofile.close()
def problem1():
r = getRandomInteger(6)
magic = 1<<r
lfsr1 = lfsr(seed1, mask1, n1)
lfsr2 = lfsr(seed2, mask2, n2)
cipher = generator(lfsr1, lfsr2, magic)
encrypt(cipher, "MTk4NC0wNC0wMQ==_6d30.txt", "MTk4NC0wNC0wMQ==_6d30.enc")
def problem2():
magic = getPrime(64)
lfsr1=lfsr(seed1, mask1, n1)
lfsr2=lfsr(seed3, mask2, n2)
cipher = generator(lfsr1, lfsr2, magic)
encrypt(cipher, "MTk4NC0xMi0yNQ==_76ff.txt", "MTk4NC0xMi0yNQ==_76ff.enc")
# flag in it?
print(f'hint={magic}')
# hint = 15193544052573546419
problem1()
problem2()
We are given two encrypted files encrypted with some sort of LFSR stream cipher. We are able to get 128 known bits of each of the generator outputs (via the date header).
solution
Since we are given almost no information about the LFSRs apart from the length, we’ll need to figure out the masks and eventually therefore the seeds. We’ll focus on problem1 first.
problem1
After playing around a bit with the confusion function in the generator, we can notice two things.
First, notice that the cnt variable only depends on the number of bits set in the magic variable. In the case of problem1, we definitely know how many 1 bits are set, it is only 1. This means that the end result of cnt will be 1, and so the output at the end will be xored with c1.
Secondly, notice that in the malicious_magic function, the sum of the now variables is equal to magic, therefore the final output will eventually be xored with magic.
Combining both of these together, we can see that the eventual output of confusion(c1, c2) will equal:output = magic ^ c1 ^ c2 ^ c1 ^ magic = c2, so we are directly getting output of the 2nd generator! Notably, this generator is incredibly short, with a length of 12. Given 128 bits, we can use the Berklamp-Massey algorithm to recover the mask/feedback polynomial, and then invert the LFSR to get the seed. (Alternatively, you could probably just bruteforce both the mask and seed simultaneously since combined they are only 24 bits, but I chose not to do this.)
from Crypto.Util.number import *
class lfsr():
def __init__(self, seed, mask, length):
self.length_mask = 2 ** length - 1
self.mask = mask & self.length_mask
self.state = seed & self.length_mask
def next(self):
next_state = (self.state << 1) & self.length_mask
i = self.state & self.mask & self.length_mask
output = 0
while i != 0:
output ^^= (i & 1)
i = i >> 1
next_state ^^= output
self.state = next_state
return output
def getrandbit(self, nbit):
output = 0
for _ in range(nbit):
output = (output << 1) ^^ self.next()
return output
ct = bytes_to_long(open("MTk4NC0wNC0wMQ==_6d30.enc", "rb").read()[:16])
pt = bytes_to_long(b"Date: 1984-04-01")
out = pt ^^ ct
lfsr2out = [GF(2)(int(x)) for x in "{:0128b}".format(out)]
g = sage.matrix.berlekamp_massey.berlekamp_massey(lfsr2out)
M = companion_matrix(g, 'bottom')
v0 = vector(lfsr2out[:12])
seed2 = M^-12 * v0
seed2 = ZZ(list(seed2[::-1]), base=2)
print(seed2)
for _mask2 in range(2^12):
l = lfsr(seed2, _mask2, 12)
if l.getrandbit(128) == out:
mask2 = _mask2
print(mask2)
2989 - seed2
2053 - mask2
(Sidenote: I wasn’t really sure how the mask corresponded to the feedback polynomial I was getting in Sage, so I ended up just bruteforcing the mask with the correct seed until the same output was given. I believe it was something to do with the +1 term in the polynomial, although I’m not sure)
problem2
Now that we have the value for seed2, we can go look at problem2. This time, the hint has an even number of 1 bit set, so the resulting cnt will be 0, and then our output will be:output = magic ^ c1 ^ c2 ^ magic = c1 ^ c2.
We’ll ideally want to recover the feedback polynomial for the first LFSR, and we can attempt to do this by bruteforcing the seed for the second LFSR, which is only a 12 bit bruteforce. For each seed, we’ll calculate the output stream of the 1st generator, and then apply the Berklamp-Massey algorithm again to recover a possible feedback polynomial. Then, using this feedback polynomial, we can advance the keystream and decrypt the full file, and check if it contains the flag.
from tqdm import tqdm
ct = bytes_to_long(open("MTk4NC0xMi0yNQ==_76ff.enc", "rb").read()[:16])
pt = bytes_to_long(b"Date: 1984-12-25")
out = pt ^^ ct
fullct = open("MTk4NC0xMi0yNQ==_76ff.enc", "rb").read()
ctlen = len(fullct)
F = GF(2)
def xor(a, b):
return bytes([_a ^^ _b for _a, _b in zip(a,b)])
for seed3 in tqdm(range(2^12)):
l = lfsr(seed3, mask2, 12)
l2out = l.getrandbit(128)
l1out = l2out ^^ out
lfsr1out = [F(int(x)) for x in "{:0128b}".format(l1out)]
g = sage.matrix.berlekamp_massey.berlekamp_massey(lfsr1out)
M = companion_matrix(g, 'bottom')
if len(list(M)) != 64:
continue
else:
v = []
v0 = vector(lfsr1out[:64])
for x in range(0, len(fullct) * 8, 64):
v += ((M^x) * v0)
v = v[:len(fullct) * 8]
keystream1 = ZZ(list(v[::-1]), base=2)
l = lfsr(seed3, mask2, 12)
keystream2 = l.getrandbit(ctlen * 8)
k1 = long_to_bytes(keystream1, ctlen)
k2 = long_to_bytes(keystream2, ctlen)
plaintext = (xor(xor(k1, k2), fullct))
if b"SUSCTF" in plaintext:
print(plaintext.decode())
break
Date: 1984-12-25
Though the hunger pangs were no longer so exquisite, he realized that he was weak. He was compelled to pause for frequent rests, when he attacked the muskeg berries and rush-grass patches. His tongue felt dry and large, as though covered with a fine hairy growth, and it tasted bitter in his mouth. His heart gave him a great deal of trouble. When he had travelled a few minutes it would begin a remorseless thump, thump, thump, and then leap up and away in a painful flutter of beats that choked him and made him go faint and dizzy.
In the middle of the day he found two minnows in a large pool. It was impossible to bale it, but he was calmer now and managed to catch them in his tin bucket. They were no longer than his little finger, but he was not particularly hungry. The dull ache in his stomach had been growing duller and fainter. It seemed almost that his stomach was dozing. He ate the fish raw, masticating with painstaking care, for the eating was an act of pure reason. While he had no desire to eat, he knew that he must eat to live.
In the evening he caught three more minnows, eating two and saving the third for breakfast. The sun had dried stray shreds of moss, and he was able to warm himself with hot water. He had not covered more than ten miles that day; and the next day, travelling whenever his heart permitted him, he covered no more than five miles. But his stomach did not give him the slightest uneasiness. It had gone to sleep. He was in a strange country, too, and the caribou were growing more plentiful, also the wolves. Often their yelps drifted across the desolation, and once he saw three of them slinking away before his path.
The content is an excerpt from Love of Life, by Jack London. The problem is mainly about LFSR and I've tried not to make it hard (with the cost of some running time, actually). Your flag is SUSCTF{Thx_f0r_y0uR_P4ti3nce_:)_GoodLuck!_1bc9b80142c24fef610b8d770b500009} and I hope you will enjoy our game. You'll find this problem so ez while solving other problems, which is created by --.