LoTuX CTF WriteUp-Crypto

, , , , , , , , , , ,

Before all

After I written the web writeups for it, it’s time to have some cryptography~
LoTuXCTF.com

Write Up

Story Teller

It’s a system which you have to netcat to the machine and receive some strings of the story, a tricky point, the option 2 to show the entire story aren’t availible, which took me some time to get the part containing the flag XD.
After receiving some strings, I guessed that was subtituition cipher, and I threw it into online solver :)
Solver link
Payload: 

1
2
Iol sgfu qfr qkrxgxl jxtlz iqr egdt zg qf tfr,Iol itqkz kqetr ql it kxlitr ygkvqkr,Vig iqr q rtth yqleofqzogf vozi ysqul.Qekgll cqlz dgxfzqofl qfr zktqeitkgxl koctkl,Dgfzil zxkftr ofzg ntqkl, qfr lzoss, it htklolztr,
Qfr zitkt oz vql, ysxzztkofu of zit vofr, zit Ugsrtf Ysqu.Wn zit vqn, zit Ugsrtf ysqu ol SgZxB{Ek4eA_ZkqFlhGl1zogf_e1hi3k}

Plaintext(?) 

1
2
His long and arduous quest had come to an end,His heart raced as he rushed forward,Who had a deep fascination with flags.Across vast mountains and treacherous rivers,Months turned into years, and still, he persisted,
And there it was, fluttering in the wind, the Golden Flag.By the way, the Golden flag is LoTuZ{Cr4cK_TraNspOs1tion_c1ph3r}

Ah… A little bit spelling mistake but I could fix that!
Flag:LoTuX{Cr4cK_TraNspOs1tion_c1ph3r}

Ultra Easy RSA

This is the RSA source code of it: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import getPrime, bytes_to_long, isPrime

flag = bytes_to_long(open('flag', 'rb').read())

base = getPrime(1024) + 1
p = base + getPrime(32)
while not isPrime(p):
    p = base + getPrime(32)
q = base + getPrime(32)
while not isPrime(q):
    q = base + getPrime(32)

assert isPrime(p) and isPrime(q)

n = p * q
e = 65537

print(f'n : {n}')
print(f'e : {e}')
print(f'c : {pow(flag, e, n)}')

and this is the cipher text and public keys: 

1
2
3
n : 18237670125629885217430444493412839683095316338154144657680055976957974511816887698014416778742458617727487825434215559521989763244658964742225298092775063375018442448500053641936340518366158207747898446464520032586461919330382037485266254993555571157687695056078760857442635607952038570214754973168928089799842679683858910621891986110243891564040587804656833234367273023439077360826316365299615019347351708635126105543987138042781032074548061385679276733178303852236701205308618104580479348575448991707466053009501662110431355315670739380731676506390117135831446230889312521145538861000127173891904075977932619433701
e : 65537
c : 2794914051908911497221655143209424203922373183519333986384370150540081118988520470638422240640871503705252562916755361442937060309400197458850988987533804149120361867582722612196413981932620461095660678707865772870903786875488203232110180545108071103351865212866486810405978838144245014127614439626237547452221513936043858002978206734391643932326225256517137555670052456674982930815715697146571529593744303003652598514891831529852333422746758214908655326413375875929526048928440304071556256481865754300879231890488410605859312056395813613983737119590091264580408250111053950716284781610855403529161875851373036573381

We can observe that the difference between p and q is low, so it’s a good way to enumeration through the difference. 

1
2
3
let p=a+b
    q=a-b
    n=a^2-b^2, while b is small, we can make a estimation that a is almost equal to n.

This was my solve script: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
from gmpy2 import *
n=18237670125629885217430444493412839683095316338154144657680055976957974511816887698014416778742458617727487825434215559521989763244658964742225298092775063375018442448500053641936340518366158207747898446464520032586461919330382037485266254993555571157687695056078760857442635607952038570214754973168928089799842679683858910621891986110243891564040587804656833234367273023439077360826316365299615019347351708635126105543987138042781032074548061385679276733178303852236701205308618104580479348575448991707466053009501662110431355315670739380731676506390117135831446230889312521145538861000127173891904075977932619433701
e=65537
c=2794914051908911497221655143209424203922373183519333986384370150540081118988520470638422240640871503705252562916755361442937060309400197458850988987533804149120361867582722612196413981932620461095660678707865772870903786875488203232110180545108071103351865212866486810405978838144245014127614439626237547452221513936043858002978206734391643932326225256517137555670052456674982930815715697146571529593744303003652598514891831529852333422746758214908655326413375875929526048928440304071556256481865754300879231890488410605859312056395813613983737119590091264580408250111053950716284781610855403529161875851373036573381
'''
# brute forcing the base
base=int(iroot(n, 2)[0])
i=0
while True:
    i=i+1
    if iroot((base+i)**2-n, 1)[1]==True:
        print(base+i)
        break
'''
base=135046918238180782328924971921958639261591204333628236588208930075562324277197936991698876778956199104793720358740299658687466966551023519180829878597741679344340717369554900909298947887554903073150791778577280508711415653004575837190385463599852964397715671365204087723325984507408797902938259367674214992035
pad=int(iroot(base**2-n, 2)[0])
p=base+pad
q=base-pad
d=inverse(e, (p-1)*(q-1))
flag=long_to_bytes(pow(c, d, n))
print(flag)

and finally, I got the flag:LoTuX{4sYmm3tR1c}

Bad Privacy

The source: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import getPrime, bytes_to_long
from flag import flag
import os

p, q = getPrime(1024), getPrime(1024)
n = p * q
d = getPrime(500)
e = pow(d, -1, (p - 1) * (q - 1))

flag += b'\x00' + os.urandom(n.bit_length() // 8 - len(flag) - 1)
c = pow(bytes_to_long(flag), e, n)

print(f'{n, e = }')
print(f'{c = }')

ciphertext: 

1
2
3
n, e = (17931953129698545860672038166028641954211279868347010542121381522667183633654326153957901012736767926583895074075364454732415371988672711250552233364148619238124205992079987287032753603740879208227974019911770407580002458086483457941143722287017418948106156662337731905493480955268532227886732623142880169309291516456509754017328833523667904784256091479734388109422882591425800752647369349484968205543256347464275671725136701166089617502616428600867096627161749301161622412955242636638883206530169334556183645604728422783310878651509098626849351203005652884326862518439282339266587358921695257337994346530294379799713, 6429612413476205915435062664586221987266728476324429759478636846601841457248411300522968107483913162956560510606687683087570538068744774753786338439784578451887065650935242982338955084352549776989544241687047148672460229410005415566973404149241388633539038484420213725248760668987344228735725963502285593544916442673326026828057883738757861159402439164322495097760924015952567105010877972853876504056471966751308006181695402303033833156301078335468253261591674289896625773475364950380799836993215091688800787918071824307845038843678471739904411406065925753148271164925604607165382477612342803025945280286782801081709)
c = 5808824944844149727771265099593085156170782038346130466697544160912957964694001898321313061748692927503448308895020346102848151119516478731215714116386757105053889318916251229295825483854561411436075680376250409732167265792475265936667433509075434517970352484245084493797741546494778583083258894741352496183649534791939546039484141394521931063022600705304609657072860338412264090017971488965745739106188918871960930640977339294906315812462625918308606782358708347513890899250818772613434856885849072024549071522932681241209502561201893189085521782173799276971060267532081898267672091645231297285377428516846987643669

Since the d is too small, the Wiener’s Attack would work!(Maybe there would be a post in future talking about Wiener’s Attack)
Wiener’s Attack on Python
Online Solver
and the CRYING FLAG:
LoTuX{Oh_n0!_W1en3r_4t7@ck_M3!}
LMAO

Johnny

First of all, the shadow file in Linux will store all the passwords’ hash+salt and passwd file would record users and its home file location
In this challenge, I already got the passwd file + shadow file, so it’s time to unshadow it: 

1
unshadow passwd shadow > john

after this step, I would like to use john + rockyou.txt to bruteforce the hash: 

1
john --format=crypt  john --wordlist=~/rockyou.txt

and the password revealed: 

1
passw0rd

nc to the server and got the flag: 

1
LoTuX{RRRRRRR_start_a_livestream}

How is your math

I was saccrafied because I didn’t know AES well at that time, but after a brain storming, I realized that its just a simple XOR XD
After connected to the server, some data would be retrieved 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
##################################################################
#                     AES CBC Mode (Decrypt)                     #
##################################################################
#                                                                #
#          -----------         -----------         -----------   #
#         |  cipher1  |---*   |  cipher2  |---*   |  cipher3  |  #
#          -----------    |    -----------    |    -----------   #
#               |         |         |         |         |        #
#          -----------    |    -----------    |    -----------   #
#         |           |   |   |           |   |   |           |  #
#         |  Decrypt  |   |   |  Decrypt  |   |   |  Decrypt  |  #
#         |           |   |   |           |   |   |           |  #
#          -----------    |    -----------    |    -----------   #
#   ------      |         |         |         |         |        #
#  |  IV  | --> ⊕         *-------> ⊕         *-------> ⊕        #
#   ------      |                   |                   |        #
#          -----------         -----------         -----------   #
#         |  plain1   |       |  plain2   |       |  plain3   |  #
#          -----------         -----------         -----------   #
#                                                                #
##################################################################

cipher : 0d6beaad8daba34786cf9ba261eab7c3129a455629eae4111cc66957e27198d219c549c854df275c5f889df6e97d44ae
last block of plain : c588b65dba94c71918dfaa27b4990e80
let the last block of plain change to :  488fc668a2664a640a2e012f45cdc851

Since we can use XOR to cauculate new cipher text, is easy to write a solve script down below 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from pwn import *

r = remote('lotuxctf.com', 30000)

r.recvlines(22)

cipher = bytes.fromhex(r.recvline().strip().split(b': ')[1].decode())
ori_plain_block = bytes.fromhex(r.recvline().strip().split(b': ')[1].decode())
new_plain_block = bytes.fromhex(r.recvline().strip().split(b': ')[1].decode())

cipher = cipher[:16] + xor(cipher[16: 32], ori_plain_block, new_plain_block) + cipher[32:]
r.sendlineafter(b'> ', cipher.hex().encode())

r.interactive()

FLAG: LoTuX{Bit_Flipping_is_a_usefull_skill!}
thx to the flag, I learned that the name of this skill is Bit Flipping

NPC

An LLL(Known High Bits Of p one)
link
gen.py: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)

if p < q:
    p, q = q, p

n = p * q
m = bytes_to_long(open('flag.txt', 'rb').read())
e = 65537
c = pow(m, e, n)

p ^= getRandomNBitInteger(128)

print(f'{n = }')
print(f'{p = }')
print(f'{c = }')

which gave me the most parts of p, it allows an LLL attack…
text: 

1
2
3
n = 49317379804500209796069154838279294954734740260396969034362244628150502249525013341446737093977379039171277765668408135551429857961821092446119100418821374122189863172040513586589131824390453447510139315735819628529302309979625386802390332631395130113472540866945551795771627526235891533041190420454741961703
p = 7146471852062807277569830669618365331180167544805326080561292157538715086180460637539592780330363947718000143009999132925845868128087197314427832652781728
c = 34947545889759223661585220387725459637867459013983415649668150556071818987266451435085470915014102268810099737752533693324005084812311826831142921631853103134471247181887924060648234847407394744849343861064479563108491457911737123039686631953466948411009164374963649430994606479666126787716286750789879631629

solve script with sage math: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def known_high_bits_of_p(n: int, p0: int, epsilon=None):
    """
    - input : `n (int)`, `p0 (int)`, `epsilon (default=None)` , `0 < epsilon <= 0.5/7`
    - output : `(p, q) (int, int)`
    """
    P = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
    x = P._first_ngens(1)[0]
    
    f = p0 + x
    small_roots = f.small_roots(beta=0.5, epsilon=epsilon)
    if len(small_roots) > 0:
        p = p0 + int(small_roots[0])
        q = n // p
        assert p * q == n
        return p, q
    else:
        return -1
known_high_bits_of_p(49317379804500209796069154838279294954734740260396969034362244628150502249525013341446737093977379039171277765668408135551429857961821092446119100418821374122189863172040513586589131824390453447510139315735819628529302309979625386802390332631395130113472540866945551795771627526235891533041190420454741961703, 7146471852062807277569830669618365331180167544805326080561292157538715086180460637539592780330363947718000143009900000000000000000000000000000000000000000, 0.5/7)

result: 

1
2
(7146471852062807277569830669618365331180167544805326080561292157538715086180460637539592780330363947718000143009998945637393289245323312523102267744789853,
 6900940887392552831713258834784967859343838581927688776237960830841652678336056473627273516987132914717019357115938384799740731873908854572472606894546451)