Skip to content

Latest commit

 

History

History
94 lines (71 loc) · 2.83 KB

WRITEUP.md

File metadata and controls

94 lines (71 loc) · 2.83 KB

Challenge name: I'm so Random

Description:

Aplet's quirky and unique so he made my own PRNG! It's not like the other PRNGs, its absolutely unbreakable!

nc crypto.2021.chall.actf.co 21600

P.S: given files: chall.py

Solution:

According to code, we can ask the server to give us random number up to 3 times. How server generates random number? Simple, just generates 2 random number with Generator and multiples them.

class Generator():
    DIGITS = 8
    def __init__(self, seed):
        self.seed = seed
        assert(len(str(self.seed)) == self.DIGITS)

    def getNum(self):
        self.seed = int(str(self.seed**2).rjust(self.DIGITS*2, "0")[self.DIGITS//2:self.DIGITS + self.DIGITS//2])
        return self.seed


r1 = Generator(random.randint(10000000, 99999999))
r2 = Generator(random.randint(10000000, 99999999))

...

        if query.lower() == "r" and query_counter < 3:
            print(r1.getNum() * r2.getNum())

First, I was trying to break generator some how, then I relized there is no need to break generator. All we need to do is get a random number from server, try to divide it to r1 and r2 and create next numbers. To verfy that, we get another random number from server and compare our results to them.

def find_r(x, y):
    d = divisors(x)
    print ('\t|Divisors:\n{0}\n'.format(d))
    
    for r1 in d:
        if (valid(r1) == False):
            continue
        r2 = x // r1
        if (valid(r2) == False):
            continue
        
        print ('\t|p1: {0}\n\t|p2: {1}\n'.format(r1, r2))
            
        g1 = Generator(r1)
        g2 = Generator(r2)
        
        o = g1.getNum() * g2.getNum()
        if (o == y):
            return (r1, r2)
        
    raise Exception('divisors not found')

Note: For finding divisors, I used sagemath library.

final exploit.py

Output

[+] Opening connection to crypto.2021.chall.actf.co on port 21600: Done
[*] Randoms recovery phase
[*] Checking divisors:
    |p1: 15525328
    |p2: 96681138
[*] Checking divisors:
    |p1: 15628704
    |p2: 96041641
[*] Checking divisors:
    |p1: 16113523
    |p2: 93151968
[*] Checking divisors:
    |p1: 19076107
    |p2: 78685152
[*] Checking divisors:
    |p1: 19671288
    |p2: 76304428
[*] Checking divisors:
    |p1: 23287992
    |p2: 64454092
[*] Checking divisors:
    |p1: 26228384
    |p2: 57228321
[*] Guessing phase
[+] Next random: 331960767242752
[+] Next random: 1995896433251328
b"Congrats! Here's your flag: \nactf{middle_square_method_more_like_middle_fail_method}\n"

The Flag

actf{middle_square_method_more_like_middle_fail_method}