[Pwnable.kr] Why random number aren’t really random

We’ve made it so far to the “random” challenge. Granted, the challenges don’t need that much explaining as they are somewhat easy, but I try to dive into some of the details, because I believe, that if you master the little details, and know how things work, and develop a structured method to tackle problems, this will become like a second nature. To be honest, I’m not doing this to only help people solve the challenges and gain a bit of modest knowledge, but this is helping me too; writing these blog posts pushes me to go the extra mile, and truly think of a structured way to explain stuff, research stuff I’m not sure about, and really think into the depth of things, to present an as logical solution as possible, a logical solution that would be easily replicated into other similar but different problems.

Enough chit-chat, let’s dive into the small piece of code presented by the challenge :

The code is straight forward; it initializes a variable with a random value, takes the user input, XORes it with the random value. The program will read the flag to us if the XOR result equals to 0xdeadbeef .

Before I get into how funnily this challenge easy is, I’d like to talk a bit about random numbers. Now what is random anyway ? How do we define random ? Well, the first thing that pops up to my mind is, any series of events, things, numbers or information, where we can’t find a pattern that defines the relationships between those events or numbers; they are independent events. In fact, in mathematics, especially in probability and statistics, we define a random or aleatory variable as a variable who can take a number of possible values which are subject to variations because of chance. These possible values constitute a set of numbers or events that are associated with a probability.

For example, if we toss a fair coin, we can get either heads, or tails, there’s no way we can predict for certain the event that’ll happen, i.e. the value we’ll get, so we have a chance of fifty-fifty for each value.

Same thing for a dice, we have a chance or probability of 1/6 that we’ll get either value. There’s no way we can define a pattern to predict what number we’ll get from a fair dice. The outcome is totally… random !

Humans find it easy to shout out random numbers, but even for humans, sometimes I suspect that we can truly say random stuff easily. If I ask you right now to say a random number between 1 and 10, may be you’ll say 7 because last time you checked the clock it was 8:37; or may be you’ll say 3 because there’s a drawing of tree in front of you. Even you, need a seed to generate a random number. Remember this example.

But again, I remember only humans can come up with the most weird random stuff to do…

Now, computers are deterministic, and leave nothing to chance. In fact we spent so much time on making them as predictable and deterministic as possible, trying to wipe out illegal instructions from processors, refining those compilers, redesigning programming languages, just so we can know for sure that, every time we lunch that piece of code, we’d expect the same result every time, in every situation, at any time, in any platform. It’s computers’ job to be deterministic. They just follow any set of instructions we program into them, which makes it really hard for a deeply deterministic machine to produce random number or events.

But we really need random numbers day to day computing… From chance games, poker games, to large prime random numbers or random keys generation that are used in cryptography, that’s why mathematicians and computer scientists tried to come up with algorithms that can generate for us pseudorandom numbers. There are a numerous methods with mathematical proof, that try to give us the most realistic random numbers generators, but they always stay kind of, predictable.

In fact, when Apple introduced the iPod shuffle, people complained that the shuffle functionality wasn’t really random, as they felt the device always played related songs, people kept finding the pattern in the random playlist generation, which is not weird given what we can expect from a deterministic system. So Apple had to play with the algorithm to remember the songs that were played and try to avoid them, as they said : “We’re making it less random to make it feel more random.”

John von Neumann once joked that “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”

There’s another trick that is used in the implementation of random generators, is that, the function usually needs a seed, to help them generate a more random number. The seed can be the current time of the system, the current position or movement of the cursor of the mouse or any activity that would be considered as an unpredictable random event happening in the system.

I think I’ve talked enough about random numbers, now let’s see where that leaves us with our challenge.

Let’s create a simple program to test what we said :

Let’s compile, and execute it many times :

Huh ! See ? it’s supposed to be random, but it always gives the same value  0x6b8b4567 .

Now why is that ? Because this particular function rand() , requires to be fed by a seed first, so it can truly generate random numbers. This seed is usually the current system time. To fix the program, we should add this line  srand(time(NULL)); as shown in this code :

Let’s see now if that’s fixed :

That did it !

Let’s go back to the challenge. We’ve seen that the program always generates the value 0x6b8b4567 .

To unlock the challenge, we need to XOR the value 0x6b8b4567  to the value 0xdeadbeef :

0x6b8b4567 ^ 0xdeadbeef = 3039230856

I’ve explained in a previous article how to get the expected key value from a XOR operation that satisfies the equation key ^ 0x6b8b4567 = 0xdeadbeef

Let’s feed the value 3039230856 to the program input and see if we got it right :

Tada ! We got it right ! You thought wrong little toddle, libc random is not as unpredictable as you’d think :/

If you noticed any inaccuracies, or have any questions, criticisms, remarks, corrections or observations I’ll be happy to hear from you !

Take care ! See ya 😀

One thought on “[Pwnable.kr] Why random number aren’t really random

Leave a Reply

Your email address will not be published. Required fields are marked *