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!
Opening the challenge display the following website:
Entering a username gives us an access token for the “Quotes API”:
Let’s try it:
$ curl "http://ctf.one:36089/quote.php?token=1952540257"
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.
quotes.php endpoint doesn’t look interesting from here, it returns a random quote if the token is valid but nothing else interesting.
So far here are the informations we can gather to progress:
- app is running PHP
- token is always 10 chars long
- length of the
usernamedoesn’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
Generate a random integer
If we follow the documentation this would mean the quote API is using the following code to generate a 10 long integer token:
php > echo rand(1000000000, 9999999999);
Doesn’t seems like a logical nor practical way to me. Let’s see if other functions exist.
[rand()](https://www.php.net/manual/en/function.rand.php) php documentation also link to the
Generate a random value via the Mersenne Twister Random Number Generator
Again, let’s give it a try:
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.
While checking the PHP documentation of
mt_rand() we stumble across this warning:
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.
If you are unfamiliar with PRNG here are the key points you have to remember:
All PRNG algorithms take an input called seed as starting point. This seed is the base number on which an algorithmic formula is applied.
Then the formula is applied on this initial seed and the result generated is a random-looking number.
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:
static unsigned long int next = 1;
With all this knowledge we can start to see where the issue is and how we could potentially exploit it right ?
Let’s try to imagine how the token generation code in this
Quote API works. Here is one theory:
- The php
mt_rand()function gets initialized with an hard-coded seed using
- Tokens get generated with
mt_rand()and saved to a database.
- Admin generate the first token for himself and get stored in the database.
- 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
Running the script will output the following list of tokens:
Let’s now feed this list of tokens to a PRNG seed recovering tool like
$ ./untwister -i quotes-tokens.txt -r php-mt_rand -S 1000000
Alright! Sound good, we now have the initial seed:
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:
$ php56 -a
We have a first token, let’s try to use it to see if the API return a different output:
$ curl "ctf.one:36089/quote.php?token=531921107"
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
- CheatSheets: Secure Random Number Generation | OWASP
- Not So Random Exploiting Unsafe Random Number Generator Use
- Authentication Bypass by abusing Insecure crypto tokens - HackerOne
- Predictability of password reset tokens | Black Hat
That’s it folks! As always do not hesitate to contact me for any questions or feedbacks!
See you next time ;)