Skip to content

Latest commit

 

History

History
161 lines (152 loc) · 10.9 KB

write-up-fcsc2021.md

File metadata and controls

161 lines (152 loc) · 10.9 KB

Write Up of FCSC 2021

Challenges :

  1. RSA Destroyer (Crytpo)
  2. Malware 1/3 (Forensics)

RSA Destroyer

Challenge description :

This destroyes the RSA cryptosystem.

Resolution :

So, we have two files which are :

  1. output.txt
e = 65538
n = 444874973852804286630293120525019547982392964519934608680681255396764239795499482860997657663742247333836933457910503642061679607999128792657151145831533603267962151902191791568052924623477918783346790554917615006885807262798511378178431356140169891510484103567017335784087168191133679976921108092647227149255338118895695993606854195408940572577899625236666854544581041490770396755583819878794842828965377818593455075306655077757834318066860484956428681524881285058664687568640627516452658874124048546780999256640377399347893644988620246748059490751348919880389771785423781356133657866769589669296191804649195706447605778549172906037483
c = 95237912740655706597869523108017194269174342313145809624317482236690453533195825723998662803480781411928531102859302761153780930600026069381338457909962825300269319811329312349030179047249481841770850760719178786027583177746485281874469568361239865139247368477628439074063199551773499058148848583822114902905937101832069433266700866684389484684637264625534353716652481372979896491011990121581654120224008271898183948045975282945190669287662303053695007661315593832681112603350797162485915921143973984584370685793424167878687293688079969123983391456553965822470300435648090790538426859154898556069348437896975230111242040448169800372469
  1. rsa_destroyer.py
from Crypto.Util.number import isPrime, bytes_to_long
from Crypto.Random.random import getrandbits

def fastPrime(bits, eps = 32):
	while True:
		a, e, u = getrandbits(eps), getrandbits(eps), getrandbits(4 * eps)
		p = a * (2 ** bits - e) + u
		if isPrime(p):
			return p

def generate(bits = 2048):
	p = fastPrime(bits // 2)
	q = fastPrime(bits // 2)
	return p * q, 2 ** 16 + 1

n, e = generate()

p = bytes_to_long(open("flag.txt", "rb").read())
c = pow(p, e, n)

print(f"e = {e}")
print(f"n = {n}")
print(f"c = {c}")

So basically we have two files, the first one contain n and e wich are a RSA public key and the python3 script wich create this ouput. We have also c which is the ciphertext of the flag. The most interesting part of this script is this liness :

def fastPrime(bits, eps = 32):
	while True:
		a, e, u = getrandbits(eps), getrandbits(eps), getrandbits(4 * eps)
		p = a * (2 ** bits - e) + u
		if isPrime(p):
			return p

It creates a prime number of 1024 bits which is of the form a * (2^1024 -e) + u.

def generate(bits = 2048):
	p = fastPrime(bits // 2)
	q = fastPrime(bits // 2)
	return p * q, 2 ** 16 + 1

So we know that it generates 2 primes numbers of 1024 bits and return n = pq and e = 2^16 + 1 = 65537 However this is not secure because of the structure of p and q. Explanation : We have p = a * (2^1024 -e) + u and q = a' * (2^1024 -e') + u' so n = pq = (a * (2^1024 -e) + u)(a' * (2^1024 -e') + u') = aa'*2^2048 + 2^1024*(a'u +au' -aa'e -aa'e') + aa'ee'-aeu'-a'e'u + uu' When we look at n given in the file output.txt in hex value we have : n = bf0a8dd7d8f16cad00[some zeros] 001002c0b6fc6c3c2949b0a1e097f3c51eff2e8919800[some zeros] 00526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f110eb When we look at the form of n given just before, we see that aa' = bf0a8dd7d8f16cad = 13765971169208528045, a'u +au' -aa'e -aa'e' = 1002c0b6fc6c3c2949b0a1e097f3c51eff2e89198 = 1462483866390329830822836164002145062407975244184 and aa'ee'-aeu'-a'e'u + uu' = 526e422445cbd24c429d60a4a3d75cfd20d09708a2945d9ad2d3b65a55f110eb = 37284463254120829734596659590852831388840149328402126048476097877596519338219 So we can deduce a system :

aa' = 13765971169208528045
a'u +au' -aa'e -aa'e' = 1462483866390329830822836164002145062407975244184
aa'ee'-aeu'-a'e'u + uu' = 37284463254120829734596659590852831388840149328402126048476097877596519338219

Now it's time to us our best friend : sagemath

var('a a2 u u2 e e2') # note that ' is remplaced by 2 (a' = a2)
assume(a, 'integer')
assume(a2, 'integer')
assume(e, 'integer')
assume(e2, 'integer')
assume(u, 'integer')
assume(u2, 'integer')
[solve([13765971169208528045*e*e2-a*e*u2-a2*e2*u+u*u2==37284463254120829734596659590852831388840149328402126048476097877596519338219, a==sol[0], a2==sol[1], a2*u+a*u2-13765971169208528045*e-13765971169208528045*e2==1462483866390329830822836164002145062407975244184], a,a2,e,e2,u,u2) for sol in solve([a*a2==13765971169208528045], a,a2) if sol[0]>0]
# in the last line, we solve a*a2==13765971169208528045 and use all positives solutions to try to solve 13765971169208528045*e*e2-a*e*u2-a2*e2*u+u*u2==37284463254120829734596659590852831388840149328402126048476097877596519338219 and a2*u+a*u2-13765971169208528045*e-13765971169208528045*e2==1462483866390329830822836164002145062407975244184

output of script :

[some solutions]
 [[a == 3751916785, a2 == 3669050237, e == r199, e2 == r200, u == 3751916785*r199 + 584756716714593367476088089245695598060995702445/3669050237, u2 == 3669050237*r200 + 877727149675736463346748074756449464346979541739/3751916785], [a == 3751916785, a2 == 3669050237, e == r201, e2 == r202, u == 3751916785*r201 + 239224620263965184662787181879747443847, u2 == 3669050237*r202 + 155855460081744155068217508253103646077]],
 [[a == 750383357, a2 == 18345251185, e == r203, e2 == r204, u == 750383357*r203 + 116951343342918673495217617849139119612199140489/3669050237, u2 == 18345251185*r204 + 877727149675736463346748074756449464346979541739/750383357], [a == 750383357, a2 == 18345251185, e == r205, e2 == r206, u == 750383357*r205 + 239224620263965184662787181879747443847/5, u2 == 18345251185*r206 + 779277300408720775341087541265518230385]]]

And here we have our solution ! [a == 3751916785, a2 == 3669050237, e == r201, e2 == r202, u == 3751916785*r201 + 239224620263965184662787181879747443847, u2 == 3669050237*r202 + 155855460081744155068217508253103646077] It's the good solution because all other solutions contain non integer values like u == 750383357*r205 + 239224620263965184662787181879747443847/5. Now we know that a = 3751916785 and a' = 3669050237. An other thing that the solution tells us is that e and e' can be random values if we calculate u and u' by the way that he provided to us. I chose e=1 and e2=1. I solve this same equation but now I have a, a', e and e' with sage:

solve([a == 3751916785, a2 == 3669050237, u == 3751916785*e + 239224620263965184662787181879747443847, u2 == 3669050237*e2 + 155855460081744155068217508253103646077, a2*u+a*u2-13765971169208528045*e-13765971169208528045*e2==1462483866390329830822836164002145062407975244184, e==1,e2==1], a,a2,e,e2,u,u2)

output :[[a == 3751916785, a2 == 3669050237, e == 1, e2 == 1, u == 239224620263965184662787181883499360632, u2 == 155855460081744155068217508256772696314]] I calculate

p = a * (2^1024 -e) + u = 3751916785*(2**1024 - 1) + 239224620263965184662787181883499360632 = 674479504696919171818209138170896929184144160503723157685764656019609458897622458911275118577732691008132669767000954379937521636401079275913922817460366250826125040174843950575328660454671227442465816947925083890925687493439889603241440139069690138898350567875821173147474029551344349606413915259235906464902601014407

A little verification with sage and we obtain:

n%674479504696919171818209138170896929184144160503723157685764656019609458897622458911275118577732691008132669767000954379937521636401079275913922817460366250826125040174843950575328660454671227442465816947925083890925687493439889603241440139069690138898350567875821173147474029551344349606413915259235906464902601014407=0

which mean that n can be divided by our value so our value is a factor of n. We compute

q = 659582642251985314362307734210980141587990030204881394001744413074708308546817474685792301171688495448876790836409125328438208366401710517774121396192603597603616766901493450446136669311578027124303640315728150060301983975690325150435563807547229372690246398941352389804231125578232145988030672542255427199846588966269

Now that we have p and q we can compute d with python3:

q = 659582642251985314362307734210980141587990030204881394001744413074708308546817474685792301171688495448876790836409125328438208366401710517774121396192603597603616766901493450446136669311578027124303640315728150060301983975690325150435563807547229372690246398941352389804231125578232145988030672542255427199846588966269
p = 674479504696919171818209138170896929184144160503723157685764656019609458897622458911275118577732691008132669767000954379937521636401079275913922817460366250826125040174843950575328660454671227442465816947925083890925687493439889603241440139069690138898350567875821173147474029551344349606413915259235906464902601014407
n = p*q
e = 2**16+1
phi_n = (p-1) * (q-1)
d = pow(e,-1,phi_n) # d = e^-1 mod phi_n
c = 95237912740655706597869523108017194269174342313145809624317482236690453533195825723998662803480781411928531102859302761153780930600026069381338457909962825300269319811329312349030179047249481841770850760719178786027583177746485281874469568361239865139247368477628439074063199551773499058148848583822114902905937101832069433266700866684389484684637264625534353716652481372979896491011990121581654120224008271898183948045975282945190669287662303053695007661315593832681112603350797162485915921143973984584370685793424167878687293688079969123983391456553965822470300435648090790538426859154898556069348437896975230111242040448169800372469
from Crypto.Util.number import long_to_bytes
decrypted = pow(c,d,n)
flag = long_to_bytes(decrypted)
print(flag) #FCSC{...}

Malware

Resolution :

First of all, we have a file ”snapshot.sav” wich is a memory dump. We know that this file contains a program which can encrypt ”/home/%USER%/Desktop/flag.txt". That means it’s a linux memory dump. We need to find the username, the hostname and the command line which encrypts the flag. Let’s try to find command line with strings and key words using grep like malware,admin,fcsc and with fcsc we have an interesting output :

strings snapshot . sav | grep ”fcsc”
output :
    [ some strings ]
    forensics@fcsc2021: ~/Bureau
    [ some strings ]

This output looks like a shell command prompt so let’s try with forensics@fcsc2021: :

strings snapshot.sav | grep "forensics@fcsc2021:"
output :
    [ some lines ]
    forensics@fcsc2021:~/Bureau$  /bin/1 --client -i 192.168.56.103
    [ some lines ]

All lines look normal except this line : ”forensics@fcsc2021: /Bureau$ /bin/1 –client -i 192.168.56.103”. Moreover /bin/1 isn’t a current command... So we have our hostname : fcsc2021, our username : forensics and our command line : /bin/1 –client -i 192.168.56.103

python3 -c "import hashlib;print('FCSC{'+hashlib.sha256(b'forensics:fcsc2021:/bin/1 --client -i 192.168.56.103').hexdigest()+'}')"

output :
 FCSC{...}

We have our flag and it works !