Dr. J’s Group Test Randomizer #1

---

PART 1 : CHALLENGE DESCRIPTION

Dr. J is back with another group test, and he patched his prng so we 
can't predict the next number based on the previous one! Can still 
you help Leaf predict the next output of the prng?

nc shell.2019.nactf.com 31258

---

PART 2 : GIVEN FILES

[>] class-randomizer-1.c

---

PART 3 : PROGRAM FLOW

1. A seed is initialized:

   uint64_t seed = 0;
   
   void init_seed() {
     uint64_t r1 = (uint64_t) randombytes_random();
     uint64_t r2 = (uint64_t) randombytes_random();
     seed = (r1 << 32) + r2;
   }
   

   NOTE(S):

   1. The generated seed has a maximum value of 0xffffffff.
2. An actions menu is presented to the user:

   printf("\nWelcome to Dr. J's Random Number Generator v2! A vulnerability involving "
   "predictability of outputs has been patched. \n"
   "[r] Print a new random number \n"
   "[g] Guess the next four random numbers and receive the flag! \n"
   "[q] Quit \n\n");
   

   1. [r] generates a new random number:

      uint64_t nextRand() {
        // Keep the 8 middle digits from 5 to 12 (inclusive) and square.
        seed = getDigits(seed, 5, 12);
        seed *= seed;
        return getDigits(seed, 13, 16);
      }
      

      NOTE(S):

      1. The 5th to the 8th digits from the right of the seed is squared.
      2. The squared number is now the new seed.
      3. This time, the “random” number generated is no longer the new seed.
         • It is now The 13th to the 16th digits (from the right) or the leading digits of the new seed.

   2. [g] lets the user guess the next four “random” numbers to get the flag.

   3. [q] lets the user exit the program.

---

PART 4 : GETTING THE FLAG

1. Write a script that approximates the initial middle value used to generate the first number:

   from math import sqrt
   from sys import argv
      
   def approximateMiddleValue(num):                  # In order to generate the next "random" numbers, the seed
       curr = int(num)                               # used to generate the first number should be known.
       root = int(sqrt(curr)*100)                    #
                                                     # The first number generated is the 13th-16th digits (from 
       return root*(10**4), (root+100)*(10**4)       # the right) or basically the leading digits of the middle
                                                     # square value of the initial or current seed.
   def getNextRand(seed):                            #
       mid = str(seed)[-12:-4]                       # The initial or seed's middle value used to generate the
       m_s = int(mid)**2                             # first number could be approximated by taking the square
                                                     # root of the first number multiplied by a hundred to 
       return m_s, str(m_s)[:-12]                    # increase its precision then rounding it down. All this
                                                     # times 10^4 should be quite near the initial seed value.          
   min_val,max_val = approximateMiddleValue(argv[1]) #
                                                     # With the limited number of middle values to work with,
   for i in range(min_val, max_val):                 # bruteforcing the initial seed and generating new numbers
       seed = i**2                                   # should no longer be a problem.  
       if str(seed)[:-12] == argv[1]:                #
           seed,num = getNextRand(seed)              # This code requires three succeeding numbers generated to       
           if num == argv[2]:                        # make sure that the program returns accurate results.       
               for x in range(5):                     
                   seed,num = getNextRand(seed)               
                   if x==0 and num!=argv[3]: break   
                   elif x!=0: print(num)
               if x==5: break   
   

2. Run the PRNG and generate three (3) “random” numbers:

   $ nc shell.2019.nactf.com 31258
   
     Welcome to Dr. J's Random Number Generator v2! A vulnerability involving predictability of outputs has been patched. 
     [r] Print a new random number 
     [g] Guess the next four random numbers and receive the flag! 
     [q] Quit
   
   $ > r
     95
   $ > r
     5453
   $ > r
     2112
   $ >
   

3. Run the python script above to generate the next four numbers:

   $ python3 class-randomizer-1.py 95 5453 2112
     1498
     5923
     50
     123
   

4. Go back to the running PRNG and submit the next four numbers generated by te script:

   $ > g
        
     Guess the next four random numbers for a flag! Dr. Strange sees fourteen million six hundred and five possibilies... and you only guess correctly in one. Good luck!
     Enter your first guess:
   $ > 1498
   
     Yeah, yeah, one correct guess is easy.
     Enter your second guess:
   $ > 5923
   
     Okay, you're lucky... You won't be able to guess right a third time.
     Enter your third guess:
   $ > 50
   
     Wow. I'll admit I'm impressed. This is the final test. 
     Enter your fourth guess:
   $ > 123
    
     Oh no... we're in the endgame now... Here's your flag:
     nactf{th3_b35t_pr3d1ct0r_0f_fu7ur3_b3h4v10r_15_p4st_b3h4v10r}
   
   

---

FLAG : nactf{th3_b35t_pr3d1ct0r_0f_fu7ur3_b3h4v10r_15_p4st_b3h4v10r}