ångstrom CTF 2021 - I'm so random [crypto]

• Competition: ångstrom CTF 2021
• Challenge Name: I’m so random
• Type: Crypto
• Points: 100 pts
• Description:

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

This challenge involves a very broken PRNG.

PRNG source code

import time
import random
import os

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))

query_counter = 0
while True:
    query = input("Would you like to get a random output [r], or guess the next random number [g]? ")
    if query.lower() not in ["r", "g"]:
        print("Invalid input.")
        break
    else:
        if query.lower() == "r" and query_counter < 3:
            print(r1.getNum() * r2.getNum())
            query_counter += 1;
        elif query_counter >= 3 and query.lower() == "r":
            print("You don't get more random numbers!")
        else:
            for i in range(2):
                guess = int(input("What is your guess to the next value generated? "))
                if guess != r1.getNum() * r2.getNum():
                    print("Incorrect!")
                    exit()
            with open("flag", "r") as f:
                fleg = f.read()
            print("Congrats! Here's your flag: ")
            print(fleg)
            exit()

PRNG analysis

1. The class Generator is the PRNG. It starts with a seed of 8 digits.
2. getNum changes the “seed” according to a deterministic algorithm and returns it.
3. Obviously we can bruteforce 8 digits worth of randomness.

Interaction anslysis

1. We generate two PRNGs instances.
2. You have 3 queries to get the next random output, but it’d be the multipication of both PRNGs “next” numbers.
3. You get one guess of the next multipication.

Solution

The first idea was to build a table and answer accordinly. It looks like the table would be pretty big, so I decided to just think about factorization. Since they give us the multipication of the PRNG values, we could make educated guesses.

I ended up factoring the number and hope I have very little factors. On my 3rd attempt I got the number 4391105936381657 from the server. Here is the factorization:

4391105936381657 = 17*83*684637*4545551

So there are only 4 factors! The second number that I got was 216227383182400, and experimenting with these I concluded two seed values: 77274367 and 56824871 (just by bruteforcing all possibilities). From there getting the following numbers was just running their code. The flag I got: actf{middle_square_method_more_like_middle_fail_method}.